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