กราฟสองส่วน - วิกิพีเดีย

# กราฟสองส่วน

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

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

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

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

## [แก้] นิยาม

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

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

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

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

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

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

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

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%81/%E0%B8%A3/%E0%B8%B2/%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F%E0%B8%AA%E0%B8%AD%E0%B8%87%E0%B8%AA%E0%B9%88%E0%B8%A7%E0%B8%99.html".

หมวดหมู่: กราฟ

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Česky
- Deutsch
- English
- Español
- עברית
- Italiano
- Polski
- Tiếng Việt
- 中文