การจับคู่แบ่งสองส่วนสูงสุด (Maximum Bipartite Matching)

การจับคู่แบ่งสองส่วน (Bipartite Matching) คือการเลือกชุดของเส้นเชื่อม (Edges) ในกราฟ โดยที่ไม่มีเส้นเชื่อมสองเส้นใดๆ ที่แบ่งปันจุดปลาย (Endpoint) ร่วมกัน การจับคู่สูงสุด (Maximum Matching) คือการจับคู่ที่มีจำนวนเส้นเชื่อมมากที่สุด

เมื่อพบการจับคู่สูงสุดแล้ว จะไม่สามารถเพิ่มเส้นเชื่อมได้อีก หากเพิ่มเส้นเชื่อมเข้าไป จะไม่เป็นการจับคู่ที่ถูกต้องอีกต่อไป สำหรับกราฟแบ่งสองส่วน อาจมีการจับคู่สูงสุดมากกว่าหนึ่งแบบ

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
0 1 1 0 0 0
1 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1

Output: Maximum number of applicants matching for job: 5

อัลกอริทึม

bipartiteMatch(u, visited, assign)

Input: โหนดเริ่มต้น รายการที่เยี่ยมชมแล้ว รายการการจับคู่

Output: True ถ้าสามารถจับคู่โหนด u ได้

Begin
  for ทุกโหนด v ที่ติดกับ u do
    if v ยังไม่ถูกเยี่ยมชม then
      ทำเครื่องหมาย v ว่าเยี่ยมชมแล้ว
      if v ยังไม่ถูกจับคู่ หรือ bipartiteMatch(assign[v], visited, assign) เป็น true then
        assign[v] := u
        return true
      end if
    end if
  done
  return false
End

maxMatch(graph)

Input: กราฟที่กำหนด

Output: จำนวนการจับคู่สูงสุด

Begin
  เริ่มต้นไม่มีโหนดใดถูกจับคู่
  count := 0
  for ทุกผู้สมัคร u ใน M do
    ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชม
    if bipartiteMatch(u, visited, assign) then
      เพิ่ม count ขึ้น 1
    end if
  done
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#define M 6
#define N 6
using namespace std;

bool bipartiteGraph[M][N] = {
  {0, 1, 1, 0, 0, 0},
  {1, 0, 0, 1, 0, 0},
  {0, 0, 1, 0, 0, 0},
  {0, 0, 1, 1, 0, 0},
  {0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 1}
};

bool bipartiteMatch(int u, bool visited[], int assign[]) {
  for (int v = 0; v < N; v++) {
    if (bipartiteGraph[u][v] && !visited[v]) {
      visited[v] = true;
      if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) {
        assign[v] = u;
        return true;
      }
    }
  }
  return false;
}

int maxMatch() {
  int assign[N];
  for(int i = 0; i < N; i++) assign[i] = -1;
  
  int jobCount = 0;
  for (int u = 0; u < M; u++) {
    bool visited[N];
    for(int i = 0; i < N; i++) visited[i] = false;
    
    if (bipartiteMatch(u, visited, assign))
      jobCount++;
  }
  return jobCount;
}

int main() {
  cout << "Maximum number of applicants matching for job: " << maxMatch();
}

ผลลัพธ์

Maximum number of applicants matching for job: 5