เริ่มต้นด้วยการพิจาณาเหตุการณ์สมมุติเหตุการณ์หนึ่ง มีหญิงสาวโสดจำนวน 4 คน คือ \(F_1,F_2,F_3,F_4 \) และชายหนุ่มโสด 5 คน คือ \(M_1,M_2,M_3,M_4,M_5 \) โดยฝ่ายหญิงรู้จักกับฝ่ายชายดังแสดงในตารางที่ 1 คำถามที่ต้องการหาคำตอบคือ มีทางเป็นไปได้หรือไม่ที่ฝ่ายหญิงทุกคนจะจับคู่แต่งงานกับฝายชาย( 1:1 ) โดยที่ต้องเป็นชายที่ตัวเองรู้จักเท่านั้น คำถามนี้ถูกเรียกว่า "Marriage Problem" ถูกตั้งโดยนักคณิตศาสตร์ชื่อ Philip Hall ในปี 1935
 |
| ตารางที่ 1 |
ในการตอบคำถามนี้ เริ่มต้นด้วยการสร้าง bipartite graph (อ่าน Introduction to Graph Theory part 1 ) โดยให้ edges แทนการรู้จักกันของทั้งสองฝ่าย ดังรูปที่ 1
 |
| รูปที่ 1 |
เริ่มต้นการหาคำตอบโดยการมองหา edge ที่ไม่มี vertex ร่วมกัน แล้วนำมาสร้างเป็นเซต ดังแสดงในรูปที่ 2 โดย edges ที่ไม่มี vertex ร่วมกัน ถูกแทนที่ด้วยเส้นประ
 |
| รูปที่ 2 |
ผลที่ได้มีหลายเซต เช่น
• \(\{ (F_1,M_1),(F_2,M_2),(F_4,M_4)\}\) รูปที่ 2 (a)
• \(\{ (F_1,M_5),(F_2,M_1),(F_3,M_2),(F_4,M_4)\}\) รูปที่ 2 (b)
• \(\{ (F_1,M_5),(F_2,M_1),(F_3,M_3),(F_4,M_2)\}\) รูปที่ 2 (c)
• \(\{ (F_1,M_4),(F_2,M_1),(F_3,M_3),(F_4,M_2)\}\) รูปที่ 2 (d)
แต่ละเซตก็คือรูปแบบการจับคู่แต่งงานของคนกลุ่มนี้ที่เป็นได้ ถ้าเลือกมา 1 เซต (สมมุติว่าเลือก 2(d)) แล้วนำมาสร้าง graph ใหม่จะได้ดังรูปที่ 3
 |
| รูปที่ 3 |
Graph ในรูปที่ 3 คือ subgraph ของ graph ในรูปที่ 1 เรียกว่า Matching มีข้อสังเกตุคือ degree (จำนวน edges ที่ต่อกับ vertex) ของทุก vertex มีค่าเป็น 0 หรือ 1
ถ้ามี graph G = (V,E) แล้ว Matching คือ subgraph ของ G ที่ทุก vertex มี degree ไม่เกิน 1
ตัวอย่างปัญหานี้ เราทราบว่าการแต่งงานจะเกิดขึ้นได้มากที่สุดคือ 4 ครั้ง ดังนั้น matching ที่ได้จะต้องมี edges มากที่สุดเป็น 4 ด้วยเช่นกัน matching ที่มีจำนวน edges มากที่สุดเท่าที่เป็นไปได้เรียกว่า Maximum matching
Maximum matching คือ matching ที่มีจำนวน edges มากที่สุดเท่าที่เป็นไปได้
กลับไปพิจารณา subgraph ในรูปที่ 3 อีกครั้ง ถ้าทำการตัดเอา \( M_5 \) ออกไป จะได้ matching ตามรูปที่ 4 ซึ่งจะเห็นว่าทุก vertex จะมี edge เชื่อมต่อ 1 edge เท่านั้น เรียก matching ลักษณะนี้ว่า Perfect matching
 |
| รูปที่ 4 |
1. Perfect matching คือ matching ที่ทุก vertex มี edge เชื่อมเพียง 1 เดียว (degree = 1)
2. สำหรับ perfect matching ใดๆ, จำนวน edges = \(\frac{\text{จำนวน vertices}}{2} \)
ความคิดเห็น
แสดงความคิดเห็น