สารานุกรมออนไลน์ | Siam Wiki
ไม่เจอคำค้นที่ต้องการ
หน้าแรก
กราฟสองส่วน
หน้าแรก
กราฟสองส่วน
ใน
คณิตศาสตร์
สาขา
ทฤษฎีกราฟ
กราฟสองส่วน
(bipartite graph) คือ
กราฟ
ที่เซต
จุดยอด
สามารถแบ่งได้เป็น 2 เซตที่ไม่มีส่วนร่วมกัน และจุดยอด 2 จุดใด ๆ ในเซตเดียวกัน จะไม่มีเส้นเชื่อมเชื่อมระหว่างกันกราฟสองส่วนมีประโยชน์ในการแก้
ปัญหาการจับคู่
(matching problems) เช่น ปัญหาการจัดงาน สมมติว่ามีคนอยู่ P คน และมีงานอยู่ J งาน ซึ่งแต่ละคนจะทำงานได้บางงานเท่านั้น เราจะแทนปัญหานี้ด้วยกราฟที่มีจุดยอด P + J จุด ถ้า p i {\displaystyle p_{i}} สามารถทำงาน j i {\displaystyle j_{i}} ได้ เราจะแทนด้วยเส้นเชื่อมเชื่อมระหว่าง p i {\displaystyle p_{i}} กับ j i {\displaystyle j_{i}}
ทฤษฎีบทการสมรส
(marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง
การจับคู่สมบูรณ์
(perfect matchings)
เมนูนำทาง
กราฟสองส่วน
นิยาม
ตัวอย่าง
ดูเพิ่ม
คุณสมบัติ
ใกล้เคียง
แหล่งที่มา
WikiPedia: กราฟสองส่วน
×