กราฟสองส่วนบริบูรณ์
หน้าตา
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ (อังกฤษ: complete bipartite graph) คือ กราฟสองส่วนที่จุดยอดทุกจุดในเซตแรก เชื่อมโยงกับจุดยอดทุกจุดในเซตที่สอง
นิยาม[แก้]
กราฟสองส่วนบริบูรณ์ คือ กราฟสองส่วนที่ สำหรับจุดยอด และ จุดยอด จะมีเส้นเชื่อมเชื่อมระหว่าง กับ กราฟสองส่วนบริบูรณ์ที่มีขนาด และ จะเขียนแทนด้วย
ตัวอย่าง[แก้]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Complete_bipartite_graph_K3%2C1.svg/200px-Complete_bipartite_graph_K3%2C1.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Complete_bipartite_graph_K3%2C2.svg/200px-Complete_bipartite_graph_K3%2C2.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Complete_bipartite_graph_K3%2C3.svg/200px-Complete_bipartite_graph_K3%2C3.svg.png)
คุณสมบัติ[แก้]
- กราฟเชิงระนาบ จะไม่มี เป็นไมเนอร์
- กราฟสองส่วนบริบูรณ์ จะมีขนาดของการจับคู่สมบูรณ์เท่ากับ