กราฟประกอบด้วยจุดยอดและขอบ จุดยอดเชื่อมต่อกันด้วยขอบตามคุณสมบัติบางอย่าง - ความสัมพันธ์ของอุบัติการณ์ซึ่งกำหนดชุดของขอบ ในกรณีนี้สามารถเกิดลูปและจุดยอดที่แยกได้
คำแนะนำ
ขั้นตอนที่ 1
ให้ชุดของขอบของกราฟและให้ความสัมพันธ์ซึ่งเป็นไปได้ที่จะวาดขอบจากจุดยอดหนึ่งไปยังอีกจุดหนึ่ง ตัวอย่างเช่น ชุดของจุดยอด {1, 2, 3, 4, 5, 6, 7, 8} จุดยอดสองจุด x และ y อยู่ในอัตราส่วน x + y <8
ขั้นตอนที่ 2
สร้างเมทริกซ์ที่อยู่ติดกันจุดยอด เมื่อต้องการทำสิ่งนี้ ให้สร้างตารางสี่เหลี่ยม จำนวนแถวและคอลัมน์ในตารางตรงกับจำนวนจุดยอด จากนั้นใส่ 1 ที่จุดตัดของแถวที่ i และคอลัมน์ที่ j หากจุดยอด i และ j เป็นไปตามอัตราส่วนที่กำหนด ใส่ 0 ที่จุดตัดของแถวที่ i และคอลัมน์ที่ j หากไม่เป็นไปตามอัตราส่วนขององค์ประกอบที่เกี่ยวข้อง
ในตัวอย่างของเรา บรรทัดแรกจะกรอกดังนี้:
1 + 1 <8 ดังนั้นจึงมี 1 ที่จุดตัดของแถวที่ 1 และคอลัมน์ที่ 1
1 + 2 <8 อีกครั้ง 1
1 + 3 <8 อีกครั้ง 1
1 + 7 <8 ความไม่เท่าเทียมกันไม่ถูกต้อง ดังนั้นองค์ประกอบนี้ของตารางจะเป็น 0
1 + 8 <8 อีกครั้ง 0
ขั้นตอนที่ 3
หากต้องการทราบจำนวนขอบ ให้นับจำนวนขอบในเมทริกซ์ที่อยู่ติดกันโดยไม่ทำให้ขอบซ้ำกัน
ในตัวอย่าง ได้รับเมทริกซ์สมมาตร ดังนั้นเราจึงนับจำนวนที่อยู่เหนือเส้นทแยงมุมหลักของเมทริกซ์ (ทำเครื่องหมายด้วยสีน้ำเงิน) ก่อน จากนั้นจึงนับจำนวนบนเส้นทแยงมุมหลัก (ทำเครื่องหมายด้วยสีแดง) จำนวนซี่โครงทั้งหมด 12 ซี่
ขั้นตอนที่ 4
สร้างเมทริกซ์ของเหตุการณ์ (ขอบ) เมื่อต้องการทำสิ่งนี้ ให้วาดตาราง จำนวนแถวในนั้นเท่ากับจำนวนจุดยอดในกราฟ และจำนวนคอลัมน์เท่ากับจำนวนขอบ วางหน่วยบนเส้นที่จะเชื่อมต่อด้วยขอบ ขอบที่นำจากจุดยอดไปยังจุดนั้นเรียกว่าลูปและถูกเพิ่มที่ส่วนท้ายของเมทริกซ์ ในคอลัมน์ที่สอดคล้องกับลูป มีเพียงหน่วยเดียว ตรงกันข้ามกับส่วนที่เหลือของขอบ
ขั้นตอนที่ 5
ตอนนี้วาดกราฟ วางจุดยอดบนกระดาษในลักษณะใดๆ และเชื่อมต่อกับขอบโดยใช้ตารางที่สร้างขึ้น จุดยอดที่ไม่ได้เชื่อมต่อด้วยขอบเรียกว่าโดดเดี่ยว