티스토리 뷰
이분 매칭(Bipartite Matching)문제는 이분 그래프에서 최대 매칭을 구하는 문제입니다.
이 때 이분 그래프(Bipartite Graph)란 정점을 두 그룹으로 나눠서 모든 간선이 서로 다른 그룹의 정점들을 연결 할 수 있도록
할 수 있는 그래프로 이 그래프에서 끝 점이 공유하지 않는 간선의 집합을 구하는 문제로도 설명할 수 있습니다.
이러한 문제를 네트워크 유량 문제로 접근한다면 소스와 한 그룹의 모든 정점을 잇고 다른 그룹의 모든 정점과 싱크를 이은 뒤
서로 다른 그룹을 연결하는 간선을 포함해서 모든 간선을 비용이 1인 간선으로 만들어주고 최대 유량을 구하게 된다면
최대 매칭을 알아낼 수 있습니다.
이 때 네트워크 유량의 포드-풀커슨 알고리즘을 그대로 사용하여 문제를 풀지 않고 이분 그래프의 특성을 이용하여
약간의 변형을 거친 이분 매칭만을 위한 간결한 코드를 사용합니다.
(추후 더 빠른 호프크로프트 카프 알고리즘에 관하여 설명합니다.)
시간복잡도는 포드-풀커슨 알고리즘의 시간 복잡도를 따라 정점 개수가 V, 간선 개수가 E일 때 O(VE)입니다.
이 값을 이용하여 최대 독립 집합, 최소 버텍스 커버를 쉽게 구할 수 있습니다.
먼저 최대 독립 집합(Maximum Independent Set)이란 정점들을 가능한 한 많이 선택하되 선택된 정점끼리는
서로 인접하지 않게 되는 집합을 말합니다. 이 문제는 NP로 알려져 있지만 이분 그래프에서는 다항시간만에 구할 수 있으며
최대 독립 집합의 크기 = 전체 정점의 수 - 최대 매칭의 크기
라는 식을 통하여 이분 매칭을 이용해 값을 구합니다.
또한 모든 정점을 하나씩 지워본 뒤 최대 독립 집합의 크기가 이전에 비해 줄어들었다면
최대 독립 집합에 꼭 필요한 정점인 것을 알 수 있으므로 실제 최대 독립 집합 또한 찾아낼 수 있습니다.
최소 버텍스 커버(Minimum Vertex Cover)는 정점들을 최소한으로 선택하여 버텍스 커버에 포함된 정점들과
그 정점에 연결된 간선들을 제거하였을 때 간선이 하나도 남지 않게 되는 집합으로
이 문제 또한 이분 그래프에서는 다항시간만에 구할 수 있으며
최소 버텍스 커버의 크기 = 최대 매칭
라는 식을 통하여 이분 매칭을 이용해 값을 구합니다.
최대 독립 집합의 여집합이 최소 버텍스 커버가 되며 위와 같은 방법으로 실제 최소 버텍스 커버 또한 찾아낼 수 있습니다.
이외에도 격자 그래프에서의 이분 매칭등 여러 응용이 되는 문제이니 다양한 유형을 풀어보시는 것이 좋습니다.
기본 문제
