กราฟสองส่วน

แม่แบบ:ต้องการอ้างอิง ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วน (bipartite graph) คือ กราฟที่เซตจุดยอดสามารถแบ่งได้เป็น 2 เซตที่ไม่มีส่วนร่วมกัน และจุดยอด 2 จุดใด ๆ ในเซตเดียวกัน จะไม่มีเส้นเชื่อมเชื่อมระหว่างกัน

กราฟสองส่วนมีประโยชน์ในการแก้ปัญหาการจับคู่ (matching problems) เช่น ปัญหาการจัดงาน สมมติว่ามีคนอยู่ P คน และมีงานอยู่ J งาน ซึ่งแต่ละคนจะทำงานได้บางงานเท่านั้น เราจะแทนปัญหานี้ด้วยกราฟที่มีจุดยอด P + J จุด ถ้า $p_i$ สามารถทำงาน $j_i$ ได้ เราจะแทนด้วยเส้นเชื่อมเชื่อมระหว่าง $p_i$ กับ $j_i$

ทฤษฎีบทการสมรส (marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง การจับคู่สมบูรณ์ (perfect matchings)

นิยาม

กราฟไม่ระบุทิศทางเชิงเดียว (simple undirected graph) $G:=(V,E)$ จะเป็นกราฟสองส่วน ถ้ามีการแบ่งกั้นที่แบ่งเซตจุดยอด $V=V_1\cup V_2$ ซึ่ง $V_1$ และ $V_2$ เป็นเซตอิสระ เราเขียน $G:=(V_1+V_2,E)$ แทนกราฟสองส่วนที่มีผลแบ่งกั้นระหว่าง $V_1$ กับ $V_2$

ตัวอย่าง

• ต้นไม้ทุกต้น เป็นกราฟสองส่วน
• กราฟวัฏจักรที่มีจุดยอดเป็นจำนวนคู่ เป็นกราฟสองส่วน

คุณสมบัติ

• กราฟเป็นกราฟสองส่วน ก็ต่อเมื่อ มันไม่มีวัฏจักรที่มีจุดยอดเป็นจำนวนคี่
• กราฟเป็นกราฟสองส่วน ก็ต่อเมื่อ มันเป็นกราฟสองสี

ดูเพิ่ม

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