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

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

ตัวอย่าง

K_3,1

K_3,2

K_3,3

คุณสมบัติ

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

ดูเพิ่ม

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