Đối sánh lưỡng cực tối đa

So khớp lưỡng phân là tập hợp các cạnh trong đồ thị được chọn theo cách sao cho không có hai cạnh nào trong tập hợp đó sẽ chia sẻ một điểm cuối. Đối sánh tối đa là khớp với số cạnh tối đa.

Khi tìm thấy kết quả phù hợp tối đa, chúng ta không thể thêm cạnh khác. Nếu một cạnh được thêm vào đồ thị được so khớp tối đa, thì nó không còn là một đối sánh nữa. Đối với biểu đồ hai bên, có thể có nhiều hơn một đối sánh tối đa.

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

Input:
The adjacency matrix.
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

Thuật toán

bipartiteMatch (u, đã truy cập, chỉ định)

Đầu vào: Nút bắt đầu, danh sách đã truy cập để theo dõi, gán danh sách để gán nút với một nút khác.

Đầu ra - Trả về true khi có thể so khớp với đỉnh u.

Begin
   for all vertex v, which are adjacent with u, do
      if v is not visited, then
         mark v as visited
         if v is not assigned, or bipartiteMatch(assign[v], visited, assign) is true, then
            assign[v] := u
            return true
   done
   return false
End

maxMatch (biểu đồ)

Đầu vào - Biểu đồ đã cho.

Đầu ra - Số trận đấu tối đa.

Begin
   initially no vertex is assigned
   count := 0
   for all applicant u in M, do
      make all node as unvisited
      if bipartiteMatch(u, visited, assign), then
         increase count by 1
   done
End

Ví dụ

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

bool bipartiteGraph[M][N] = {    //A graph with M applicant and N jobs
   {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++) {    //for all jobs 0 to N-1
      if (bipartiteGraph[u][v] && !visited[v]) {    //when job v is not visited and u is interested
         visited[v] = true;    //mark as job v is visited
         //when v is not assigned or previously assigned
         if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) {
            assign[v] = u;    //assign job v to applicant u
            return true;
         }
      }
   }
   return false;
}

int maxMatch() {
   int assign[N];    //an array to track which job is assigned to which applicant
   for(int i = 0; i<N; i++)
      assign[i] = -1;    //initially set all jobs are available
   int jobCount = 0;

   for (int u = 0; u < M; u++) {    //for all applicants
      bool visited[N];
      for(int i = 0; i<N; i++)
         visited[i] = false;    //initially no jobs are visited
      if (bipartiteMatch(u, visited, assign))    //when u get a job
         jobCount++;
   }
   return jobCount;
}

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

Đầu ra

Maximum number of applicants matching for job: 5