กราฟสองส่วน

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

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

(marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง (perfect matchings)

นิยาม

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

ตัวอย่าง

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

คุณสมบัติ

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

ดูเพิ่ม

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