이분 매칭 (Bipartite Matching)

이분 매칭 (Bipartite Matching)

이분 그래프(Bipartite Graph)에서 두 정점 집합 간의 최대 매칭(Maximum Matching)을 찾는 문제로, 중복 없이 최대한 많은 간선을 선택하여 일대일 대응을 만드는 알고리즘

목적: 최대 매칭, 자원 할당, 작업 배정, 최적 매칭 문제 해결

특징: 이분 그래프 전용, 증가 경로(Augmenting Path) 활용, 홀의 정리(Hall's Theorem) 기반

이분 그래프: 정점 집합을 두 개로 분할, 같은 집합 내 간선 없음, 예: 학생-과목, 작업자-작업

증가 경로(Augmenting Path) 알고리즘: DFS/BFS 기반으로 증가 경로를 반복 탐색하여 매칭 증가

증가 경로: 매칭되지 않은 정점에서 시작하여 매칭-비매칭-매칭... 교대로 매칭되지 않은 정점으로 끝나는 경로

동작: ① 빈 매칭으로 시작 → ② DFS/BFS로 증가 경로 탐색 → ③ 경로 발견 시 매칭 업데이트 → ④ 경로 없을 때까지 반복

시간 복잡도: O(VE), V = 정점 수, E = 간선 수, 헝가리안 O(V³)

공간 복잡도: O(V + E)

최대 매칭 크기: 홀의 정리(Hall's Theorem), 최소 정점 커버 = 최대 매칭(König's Theorem)

장점: 최대 매칭 보장, 다양한 응용, 효율적 알고리즘

단점: 이분 그래프만 적용, 가중치 고려 어려움(헝가리안으로 해결)

적용사례: 작업 배정, 학생-과목 매칭, 결혼 문제, 자원 할당, 네트워크 플로우

비교: 이분 매칭(이분그래프/최대매칭) vs 일반 매칭(일반그래프/Blossom)

연관: 이분 그래프, 헝가리안, 홀의 정리(Hall's Theorem), 최대 유량, 네트워크 플로우