이분법 일치는 그래프의 모서리 세트가 끝점을 공유하지 않는 방식으로 그래프의 모서리 세트를 선택하는 것입니다. 최대 일치는 최대 가장자리 수와 일치합니다.
최대 일치 항목이 발견되면 다른 가장자리를 추가할 수 없습니다. 최대 일치 그래프에 하나의 간선이 추가되면 더 이상 일치하지 않습니다. 이분 그래프의 경우 최대 일치가 두 개 이상 있을 수 있습니다.
입력 및 출력
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
알고리즘
bipartiteMatch(u, 방문, 할당)
입력: 시작 노드, 추적을 위해 방문한 목록, 다른 노드에 노드를 할당하려면 목록을 할당합니다.
출력 - 꼭짓점 u에 대한 일치가 가능한 경우 true를 반환합니다.
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(그래프)
입력 - 주어진 그래프.
출력 - 최대 일치 수입니다.
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
예시
#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();
} 출력
Maximum number of applicants matching for job: 5