매칭을 찾는 알고리즘 자체는 문제를 그 알고리즘으로 환원하는 것만큼 어렵지 않습니다.
간단한 예제부터 시작합시다.
#주사위
주사위 $n$개가 주어지며, 각 주사위에는 면이 6개 있고 각 면에는 어떤 글자가 하나씩 적혀 있습니다. 단어 $s$가 주어지며, 단어 $s$의 각 글자에 서로 다른 주사위를 하나씩 대응시켜, 그 주사위를 돌려서 필요한 글자를 얻을 수 있도록 해야 합니다.
예를 들어, 각 면에 글자가 적힌 주사위 세 개가 주어졌다고 합시다:
- (a, a, a, a, a, a)
- (a, a, a, a, a, b)
- (а, а, а, б, б, с)
단어 «acb»가 주어지면 답은 정확히 하나, 132뿐입니다.
풀이. 이분 그래프를 만듭시다. 한쪽 부분에는 주사위 번호를, 다른 쪽 부분에는 단어 $s$의 글자 번호를 둡니다. 주사위를 문자열의 해당 위치에 놓을 수 있을 때, 즉 그 주사위에 해당 글자가 적힌 면이 있을 때에만 주사위 번호에서 글자 번호로 간선을 긋습니다. 이제 답은 이 그래프의 최대 매칭입니다.
매칭의 정의에 의해 어떤 주사위도 여러 글자에 대응시키지 않으며, 우리의 매칭은 최대 매칭이므로 가능한 한 가장 많은 글자를 덮게 됩니다.
#도미노
일부 칸이 뚫려 있는 $n \times m$ 크기의 직사각형 판이 있습니다. 이 판 위에 도미노 조각($1 \times 2$ 크기의 직사각형)을 가능한 한 많이 놓아야 하는데, 뚫린 칸 위에는 아무것도 놓여서는 안 된다는 조건이 있습니다.
칸을 정점으로 하고, 인접한 두 빈 칸에 도미노를 놓을 수 있는 경우를 간선으로 하는 그래프를 만듭시다. 이러한 그래프는 이분 그래프임에 주목하십시오. 체스판처럼 칠할 수 있으며, 그러면 검은 칸은 첫 번째 쪽의 정점이 되고 흰 칸은 두 번째 쪽의 정점이 됩니다.
답은 이러한 그래프에서의 최대 매칭입니다. 정점과 간선이 $O(nm)$개이므로, 쿤 알고리즘을 사용하면 시간 복잡도는 $O(n^2 m^2)$입니다.
#DAG의 경로 덮개
스스로 해법을 떠올리기 어려운, 더 복잡한 문제를 살펴봅시다.
방향 비순환 그래프 $G$(영어: directed acyclic graph, DAG)가 주어집니다. 이 그래프를 가장 적은 수의 경로로 덮어야 합니다. 즉, 각 정점이 정확히 하나의 경로에 속하도록 하는 단순 경로의 최소 집합을 찾아야 합니다.
원래 그래프 $G$에 대응하는 두 이분 그래프 $H$와 $\overline{H}$를 다음과 같이 구성합시다.
- 그래프 $H$의 각 부분에는 $n$개의 정점이 있습니다. 이를 각각 $a_i$와 $b_i$로 표기하겠습니다.
- 원래 그래프 $G$의 각 간선 $(i, j)$에 대해, 그래프 $H$에 대응하는 간선 $(a_i, b_j)$를 긋습니다.
- 이제 각 $i$에 대해 역방향 간선 $(b_i, a_i)$를 추가하여 그래프 $H$로부터 그래프 $\overline{H}$를 만듭시다.
원래 그래프 $G$에서 임의의 경로 $v_1, v_2, \ldots, v_k$를 생각하면, 그래프 $\overline{H}$에서는 이에 대응하는 경로 $a_{v_1}, b_{v_2}, a_{v_2}, b_{v_3}, \ldots, a_{v_{k-1}}, b_{v_k}$가 존재합니다. 그 역도 성립합니다. $\overline{H}$의 왼쪽 파트에서 시작하여 오른쪽 파트에서 끝나는 임의의 경로는 $G$의 어떤 경로에 대응합니다.
따라서 $G$의 경로와 $\overline{H}$에서 왼쪽 부분에서 오른쪽 부분으로 가는 경로 사이에는 일대일 대응이 존재합니다. 이러한 $\overline{H}$의 경로는 모두 $H$에서의 매칭이라는 점에 주목하십시오(다시 말하지만, $H$는 $\overline{H}$에서 역방향 간선을 제외한 그래프입니다). 결국 $G$의 모든 경로에 $H$의 매칭을 대응시킬 수 있으며, 그 역도 성립합니다. 더 나아가, $G$에서 서로 겹치지 않는 경로들에는 $H$에서 서로 겹치지 않는 매칭들이 대응됩니다.
그래프의 모든 정점 $n$개를 덮는 서로 겹치지 않는 경로가 $p$개 있다면, 이 경로들은 모두 합쳐 $r = n - p$개의 간선을 포함한다는 점에 주목합시다. 따라서 경로의 개수 $p$를 최소화하려면 경로에 포함된 간선의 개수 $r$를 최대화해야 합니다.
이제 우리는 문제를 이분 그래프 $H$에서 최대 매칭을 찾는 문제로 환원할 수 있습니다. 이 매칭을 찾은 후에는 이를 $G$의 경로 집합으로 변환해야 합니다. 이는 간단한 알고리즘으로 수행됩니다. $a_1$을 잡고, 그것이 어떤 $b_k$와 연결되어 있는지 살펴본 다음, $a_k$를 살펴보는 식으로 계속합니다. 일부 정점은 포화되지 않은 채로 남을 수 있습니다. 이 경우 답에 이러한 정점 각각에서 시작하는 길이 0인 경로를 추가해야 합니다.
#최소 정점 덮개
문제. 그래프의 모든 간선이 집합에 속한 정점 중 적어도 하나에 인접하도록 하는 정점들의 집합을 그래프의 정점 덮개라고 합시다. 크기가 가장 작은 정점 덮개를 찾아야 합니다.
일반적인 경우 이는 NP-완전 문제이지만, 이분 그래프에서는 꽤 간단한 해법이 있습니다.
$V_{min}$을 최소 정점 덮개, $M$을 그래프의 최대 매칭이라고 합시다. 그러면 $M$은 서로 독립인 간선들의 집합이므로 $|V_{min}| \ge |M|$임을 바로 알 수 있습니다. 이제 크기가 정확히 $|M|$인 정점 덮개를 구성하는 알고리즘을 제시하겠습니다. 이 덮개가 최소임은 자명합니다.
알고리즘. 그래프의 간선에 머릿속으로 방향을 부여합시다. $M$에 속한 간선은 오른쪽 부분에서 왼쪽 부분으로, 나머지 간선은 왼쪽 부분에서 오른쪽 부분으로 향하게 한 뒤, $M$에 포함되지 않은 왼쪽 부분의 모든 정점에서 깊이 우선 탐색을 실행합니다.
그래프가 여러 집합 $L^+, L^-, R^+, R^-$로 나뉘었다는 점에 주목하십시오. 여기서 «플러스» 집합은 탐색 과정에서 방문한 정점들의 집합입니다. 이러한 형태의 그래프에는 자명한 이유로 $L^+ \rightarrow R^-$ 간선과 $L^- \leftarrow R^+$ 간선이 존재하지 않습니다. $L^+ \leftarrow R^-$ 간선은 존재하지 않습니다. 만약 존재한다면 매칭 $M$은 최대가 아니게 되기 때문입니다. 이러한 유형의 간선으로 매칭을 확장할 수 있기 때문입니다.
$$ L^- \cup R^+ = V_{min} $$이 집합이 모든 간선을 덮는다는 것은 분명합니다. 이제 $L^- \cup R^+$인 이유를 밝히는 일이 남았습니다. 이것이 성립하는 이유는 $L^- \cup R^+$가 $M$의 모든 간선을 정확히 한 번씩 덮기 때문이며(실제로 $L^- \rightarrow R^+$ 간선은 $M$에 속하지 않습니다), 또한 이 집합에 $M$에 속하지 않는 정점이 없기 때문입니다($L^-$에 대해서는 정의에 의해 성립하고, $R^+$에 대해서는 교대 경로를 이용한 귀류법으로 증명할 수 있습니다).
연습 문제. 이것을 최대 독립 집합을 구하는 문제를 해결하는 데 어떻게 적용할 수 있을지 생각해 보십시오.
#최소 가중치 매칭
왼쪽 부분의 정점들에 어떤 가중치가 있고, 최소 가중치의 최대 매칭을 구해야 한다고 합시다.
왼쪽 부분의 정점들을 가중치 기준으로 정렬한 뒤, 그 순서대로 표준 쿤 알고리즘을 사용하여 매칭에 추가해 보면 된다는 것이 밝혀집니다. 이 사실의 증명은 라도-에드먼즈 탐욕 알고리즘에 관한 글을 참고하십시오. 이러한 쿤 알고리즘의 변형은 라도-에드먼즈 알고리즘의 특수한 경우입니다.
비슷한 문제이지만 간선에 가중치가 있는 경우에는 최소 비용 흐름을 찾는 문제로 환원하여 푸는 것이 가장 간단합니다.