Introduction to Graph Theory part 7 : Matching

• Part 1
• Part 2
• Part 3
• Part 4
• Part 5
• Part 6
• Part 8

เริ่มต้นด้วยการพิจาณาเหตุการณ์สมมุติเหตุการณ์หนึ่ง มีหญิงสาวโสดจำนวน 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}$