Ghép đôi tối đa trong đồ thị hai phần (Maximum Bipartite Matching)

Ghép đôi hai phần (bipartite matching) là một tập hợp các cạnh trong đồ thị được chọn sao cho không có hai cạnh nào trong tập hợp đó chia sẻ cùng một đỉnh. Ghép đôi tối đa là ghép đôi với số lượng cạnh lớn nhất.

Khi tìm thấy ghép đôi tối đa, ta không thể thêm cạnh nào nữa. Nếu thêm một cạnh vào đồ thị đã ghép đôi tối đa, nó sẽ không còn là một ghép đôi. Với đồ thị hai phần, có thể tồn tại nhiều hơn một ghép đôi tối đa.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề.
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
Đầu ra: Số lượng ứng viên khớp tối đa cho công việc: 5

Thuật toán

bipartiteMatch(u, visited, assign)

Đầu vào: Đỉnh bắt đầu, danh sách đã thăm để theo dõi, danh sách gán để gán đỉnh này với đỉnh khác.

Đầu ra: Trả về true khi ghép đôi cho đỉnh u là có thể.

Bắt đầu
  với mọi đỉnh v kề với u, thực hiện
    nếu v chưa được thăm thì
      đánh dấu v đã thăm
      nếu v chưa được gán, hoặc bipartiteMatch(assign[v], visited, assign) là true thì
        assign[v] := u
        trả về true
  kết thúc
  trả về false
Kết thúc

maxMatch(graph)

Đầu vào: Đồ thị cho trước.

Đầu ra: Số lượng ghép đôi tối đa.

Bắt đầu
  ban đầu không đỉnh nào được gán
  count := 0
  với mọi ứng viên u trong M, thực hiện
    đánh dấu tất cả nút là chưa thăm
    nếu bipartiteMatch(u, visited, assign) thì
      tăng count lên 1
  kết thúc
Kết thúc

Ví dụ (C++)

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

bool bipartiteGraph[M][N] = {
  // Đồ thị với M ứng viên và N công việc
  {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++) {
    // cho tất cả công việc từ 0 đến N-1
    if (bipartiteGraph[u][v] && !visited[v]) {
      // khi công việc v chưa thăm và u quan tâm
      visited[v] = true; // đánh dấu công việc v đã thăm
      // khi v chưa được gán hoặc đã gán trước đó
      if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) {
        assign[v] = u; // gán công việc v cho ứng viên u
        return true;
      }
    }
  }
  return false;
}

int maxMatch() {
  int assign[N]; // mảng theo dõi công việc nào được gán cho ứng viên nào
  for(int i = 0; i < N; i++)
    assign[i] = -1; // ban đầu tất cả công việc đều khả dụng
  
  int jobCount = 0;
  for (int u = 0; u < M; u++) {
    // cho tất cả ứng viên
    bool visited[N];
    for(int i = 0; i < N; i++)
      visited[i] = false; // ban đầu không công việc nào được thăm
    if (bipartiteMatch(u, visited, assign)) // khi u nhận được công việc
      jobCount++;
  }
  return jobCount;
}

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

Đầu ra

Maximum number of applicants matching for job: 5