กราฟสองส่วน

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

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

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

นิยาม 

กราฟไม่ระบุทิศทางเชิงเดียว (simple undirected graph)  จะเป็นกราฟสองส่วน ถ้ามีการแบ่งกั้นที่แบ่งเซตจุดยอด  ซึ่ง  และ  เป็นเซตอิสระ เราเขียน  แทนกราฟสองส่วนที่มีผลแบ่งกั้นระหว่าง  กับ

ตัวอย่าง 

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

คุณสมบัติ 

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

ดูเพิ่ม 

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

กราฟ
ตระกูลกราฟ
กราฟสมบูรณ์
ภาวะคู่หรือคี่