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

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

นิยาม

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

ตัวอย่าง

K_3,1

K_3,2

K_3,3

คุณสมบัติ

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

ดูเพิ่ม

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