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

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

นิยาม

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

ตัวอย่าง

คุณสมบัติ

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

ดูเพิ่ม

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