กราฟบริบูรณ์

จากวิกิพีเดีย สารานุกรมเสรี

กราฟบริบูรณ์ (complete graph) เป็น กราฟ ที่ทุกคู่ของ จุดยอด ถูกเชื่อมต่อด้วย เส้นเชื่อม เป็น กราฟสม่ำเสมอ ที่มีระดับขั้น n-1 กราฟบริบูรณ์บนจุดยอด n จุด ใช้สัญลักษณ์ K_n, มี n จุดยอด, และ \frac{n \left ( n-1 \right) }{2} เส้นเชื่อม

ไดกราฟบริบูรณ์ (complete digraph) ก็เป็นลักษณะเดียวกับกราฟ ต่างกันที่เส้นเชื่อมแต่ละเส้น จะถูกแทนด้วยเป็นเส้นเชื่อมระบุทิศทาง 2 เส้น ในทิศทางตรงข้ามกัน

K_1: 0 K_2: 1 K_3: 3 K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg

อ้างอิง[แก้]