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

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

นิยาม

กราฟสองส่วนบริบูรณ์ $G:=(V_{1}+V_{2},E)$ คือ กราฟสองส่วนที่ สำหรับจุดยอด $v_{1}\in V_{1}$ และ จุดยอด $v_{2}\in V_{2}$ จะมีเส้นเชื่อมเชื่อมระหว่าง $v_{1}$ กับ $v_{2}$ กราฟสองส่วนบริบูรณ์ที่มีขนาด $\|V_{1}\|=m$ และ $\|V_{2}\|=n$ จะเขียนแทนด้วย $K_{m,n}$

ตัวอย่าง

K_3,1

K_3,2

K_3,3

คุณสมบัติ

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

ดูเพิ่ม

• กราฟสองส่วน