ดูต้นฉบับสำหรับ กราฟสองส่วน

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

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

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

== นิยาม ==

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

== ตัวอย่าง ==

* [[ต้นไม้ (ทฤษฎีกราฟ)|ต้นไม้]]ทุกต้น เป็นกราฟสองส่วน
* [[กราฟวัฏจักร]]ที่มีจุดยอดเป็นจำนวนคู่ เป็นกราฟสองส่วน

== คุณสมบัติ ==

* กราฟเป็นกราฟสองส่วน [[ก็ต่อเมื่อ]] มันไม่มี[[วัฏจักร (ทฤษฎีกราฟ)|วัฏจักร]]ที่มีจุดยอดเป็นจำนวนคี่
* กราฟเป็นกราฟสองส่วน ก็ต่อเมื่อ มันเป็นกราฟสองสี

== ดูเพิ่ม ==

* [[กราฟสองส่วนบริบูรณ์]]
{{โครงคณิตศาสตร์}}

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