กราฟสองส่วน

จากวิกิพีเดีย สารานุกรมเสรี

ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วน (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

ตัวอย่าง[แก้]

คุณสมบัติ[แก้]

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

ดูเพิ่ม[แก้]