กราฟสองส่วนบริบูรณ์

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

ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ (complete bipartite graph) คือ กราฟสองส่วนที่จุดยอดทุกจุดในเซตแรก เชื่อมโยงกับจุดยอดทุกจุดในเซตที่สอง

สารบัญ

[แก้] นิยาม

กราฟสองส่วนบริบูรณ์ G: = (V1 + V2,E) คือ กราฟสองส่วนที่ สำหรับจุดยอด v_1 \in V_1 และ จุดยอด v_2 \in V_2 จะมีเส้นเชื่อมเชื่อมระหว่าง v1 กับ v2 กราฟสองส่วนบริบูรณ์ที่มีขนาด \|V_1\|=m และ \|V_2\|=n จะเขียนแทนด้วย Km,n

[แก้] ตัวอย่าง

K3,1
ขยาย
K3,1
K3,2
ขยาย
K3,2
K3,3
ขยาย
K3,3


[แก้] คุณสมบัติ

  • กราฟเชิงระนาบ จะไม่มี K3,3 เป็นไมเนอร์
  • กราฟสองส่วนบริบูรณ์ Km,n จะมีขนาดของการจับคู่สมบูรณ์เท่ากับ min{m,n}

[แก้] ดูเพิ่ม

ภาษาอื่น