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

ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ (อังกฤษ: 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$

ดูเพิ่ม

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