ps:이분_매칭
목차
이분 매칭 (Bipartite Matching)
- 이분 그래프에서 최대 매칭을 찾는 문제를 이분 매칭이라고 부른다.
이분매칭을 푸는 알고리즘
- 이분 매칭은 최대 유량 문제로 쉽게 변환해서 풀 수 있다.
- 그래프를 유량 그래프롤 변형해서 최대 유량 알고리즘을 적용해도 되지만, 이게 더 단순한 문제이다보니 (유량이 모두 1인 그래프) 최대 유량 알고리즘을 이분 그래프에 맞게 단순화시켜서 적용하는 것이 더 간단하고 효율적이다.
- 최대 유량 문제와 비슷하게, worst case를 가지고 입력 제한을 주지 않는 경우가 많다. 알고리즘의 시간복잡도에, 노드와 엣지의 갯수를 대입해서 계산한 worst case로는 시간 내에 안돌아갈것 같지만, 그냥 돌리면 풀리는 문제들이 많다. 이 사실을 염두에 두고 아래를 보자.
- 좀더 이론적인 설명을 찾은 것은, 위키피디아의 Hopcroft Karp 알고리즘 문서 에서인데, 평균적으로 스파스한 그래프는 높은 확률로 로그길이의 증가경로를 갖고, 그래서 이런 그래프에서는 Hopcroft Karp 알고리즘도 O(E*sqrt(V))가 아니라 O(ElogV)으로 돌아간다고 한다.
포드-풀커슨 알고리즘
- 최대 유량 알고리즘 중, 임의의 증가경로를 한개 찾아서 업데이트하는것을 반복하는 포드풀커슨 알고리즘을 사용하면 O(fE)가 걸리는데, 이분매칭의 경우에는 f⇐V 이므로 O(VE)가 걸린다.
- 일반적인 최대유량 문제에서는 augment path를 BFS로 찾는 에드먼드-카프 알고리즘을 사용하면 O(VE^2)의 더 효율적인 시간복잡도가 나오지만, 이분매칭에서는 똑같이 O(VE)이다. 그래서 굳이 BFS를 쓰는 것보다 그냥 DFS로 짜는 것이 실질적으로 더 빠르게 동작한다.
- 이렇게 DFS로 짜는 방식을 CP-algorithm에서는 Kuhn's algorithm이라고도 부르고 있는데.. 국내 자료에서는 이렇게 부르는 것을 못본거 같다. 위키피디아에서도 그냥 포드-풀커슨 알고리즘을 이분 그래프에 적용한거 라고만 부른다.
호프크로프트-카프 알고리즘
- 최대 유량 알고리즘 중에서 일반적으로 가장 빠른것은 Dinic 알고리즘으로 일반적인 그래프에서의 시간복잡도는 O(V^2E)이다. 이것은 BFS로 레벨그래프를 찾고 블로킹 플로우를 찾는 작업에 O(VE)가 걸리고, 이것을 최대 O(V)번 반복해야 하기 때문이다.
- 그러나 모든 엣지의 캐퍼시티가 일정한 그래프에서는 블로킹 플로우를 O(E)에 찾을수 있고, 반복횟수는 최대 min(V^(2/3), E^(1/2))이 된다. 그래서 총 시간 복잡도는 O(E * min(V^(2/3), E^(1/2)))로 줄어든다
- 그리고 이 Dinic 알고리즘을 이분매칭에 적용한 것이 호프크로프트-카프 알고리즘이다. 레벨그래프를 만들고 블로킹 플로우를 찾는 것이, BFS로 가장 짧은 증가경로의 길이를 찾고, 그 길이만큼의 모든 증가경로를 DFS로 찾아서 업데이트하는 방식으로 O(E)에 구현된다. 그리고, 이분그래프에서는 반복 횟수가 최대 O(V^(1/2))가 된다. 그래서 전체 시간복잡도가 O(sqrt(V)*E)가 된다.
- 그냥 대강의 증명을 위해서 필요한 lemma들은,
- 1)길이가 가장 짧은 증가경로를 찾아서 업데이트하는 것을 반복할때, 찾아지는 증가경로의 길이는 감소하지 않는다. 2) i번째 증가경로와 i+1번째 증가경로의 길이가 같다면, 두 증가경로는 노드를 공유하지 않는다. ⇒ 이것들로부터 길이가 x인 증가경로들을 한번 이터레이션에서 모두 업데이트해주는 것으로 처리해도 알고리즘이 제대로 돌아간다는 것을 알수 있다.
- 3) 증가경로들의 길이의 갯수는 최대 2*sqrt(V)이다. ⇒ 알고리즘의 이터레이션의 횟수가 O(sqrt(V))임을 보일수 있다.
기타 알고리즘
- PS에서 쓸일은 없어보이지만..위키에 따르면,
- |V|대신에 매칭의 크기에 바운드되게 하는 살짝 더 빠른 알고리즘도 있다.
- 스파스한 그래프에서는 O(E^(10/7))에 풀수 있다.
- 플래너 그래프에서는 최대 유량 문제로 바꿔서 O(Vlog^3V)에 풀수있다
- 레귤러 이분 그래프는 항상 퍼펙트 매칭을 가지므로 따라서 매칭의 크기는 그냥 항상 노드의 갯수와 같다. 매칭을 구하는 것은 O(nlogn)에 할수 있다는 것 같다.
실제 실행 속도
- 3736은 V가 최대 20000, E는 문제 조건상으로는 최대 1억까지도 가능한 문제로 (실제 테스트 데이터에 저렇게 E가 큰 경우는 없는듯 하다), 그냥 DFS로는 안풀리고 호프크로프트-카프 알고리즘으로 풀어야 풀리는 문제이다.
- 그러나, 더 크기가 큰 문제에서는 호프크로프트-카프 알고리즘으로도 풀리지 않았다. https://judge.yosupo.jp/problem/bipartitematching 에서는 V와 E가 모두 20만개인 이분 그래프를 제공하는데, 호프크로프트-카프 알고리즘으로는 이것을 통과하는 것에 실패했다. 파이썬으로 이 문제를 푼 코드들은https://snuke.hatenablog.com/entry/2019/05/07/013609 에서 설명한 방법을 사용하고 있다.
- 이 방식도 한번의 BFS/DFS에서 여러개의 증가경로들을 찾아서 업데이트 해준다는 것은 호프크로프트-카프와 비슷하다. 그러나, 동작 방식이 다른 것이, 가장 작은 증가경로부터 업데이트 해주는 것을 보장하지 않는다. 그래서 O(sqrt(V)*E)의 시간복잡도가 되지는 않을것 같고 (적어도 위 방식 처럼은 증명이 안될듯.. 다른 방법으로 증명가능할지는 모르겠다) 그냥 O(VE)일것 같아 보이는데.. 실질적인 실행 속도는 더 빨랐다.
- 최종적으로 teflib에 구현하는 것은 이 방법으로 했다. 출처 블로그에 있던 구현에 추가로, 단순한 휴리스틱으로 초기 매칭을 찾는 과정을 추가했다.
- 속도를 좀더 비교해보면
| 문제 | 크기 | DFS | 호프크로프트-카프 | teflib |
|---|---|---|---|---|
| 2188 | V≤200, E≤200 | ? | 84ms | 192ms |
| 11365 | V≤1000, E≤1000 | ? | 484ms | 408ms |
| 11014 | V≤6400, E≤20000 | ? | ? | 292ms |
| 3736 | V≤20000, E≤??? | X | 120ms | 216ms |
| yusupo | V≤200000, E≤200000 | X | X | 650ms |
- 이렇게 보면 teflib에 구현한 방법이 가장 빠른게 맞다는 확신은 없지만.. 적어도 TLE가 나는 경우는 없었으니 이렇게 가도록 하자.
관련된 문제와 정리들
- 이분그래프에서 최소 버텍스 커버 (minimum vertex cover)와 최대 독립집합(Maximum independent set을 이분 매칭으로 구할수 있다.
- DAG에서의 최소 경로 커버와 최대 반사슬도 이분 매칭으로 구할수 있다.
- 이런 문제들은 사실상 추가 지식이 필요하지만, 태그에는 이분매칭만 달려 있기 때문에 고생할수 있다..
최소 버텍스 커버 / 최대 독립집합
- 쾨닉의 정리 (Kőnig's theorem (graph theory) - 이분 그래프에서는 최소 버텍스 커버의 크기와 최대 매칭의 크기가 동일하다.
- 따라서 최소 버텍스 커버의 크기도 이분 매칭을 통해서 쉽게 구할수 있다.
- 일반 그래프에서는 성립하지 않는다 → 일반 그래프에서 최소 버텍스 커버를 구하는 것은 NP-complete이다.
- 쾨닉의 정리의 증명에는 구성적인 방법과 LP dual을 이용한 방법이 있다
- 구성적인 방법은 kks 블로그의 이 포스트를
- LP dual을 이용한 증명은 kks 블로그의 이 포스트와 관련된 이전 포스트들을 쭉 따라가면 된다.
- 최대 독립집합의 크기를 구하는 것은, 최대 독립집합이 최소 버텍스 커버의 여집합이기 때문에 가능하다.
- 정리하면
- |최소 버텍스 커버| = |최대 매칭|
- |최대 독립집합| = |V| - |최소 버텍스 커버| = |V| - |최대 매칭|
- 관련 문제 - 최소 버텍스커버나 최대 독립집합을 구해야 하는 문제이지만 결국 모두 이분매칭 알고리즘을 돌려서 푼다.
최소 버텍스 커버 구하기
- 최소 버텍스 커버의 크기만 필요한 것이 아니라, 최소 버텍스 커버의 원소들을 모두 찾아야 할때에는 다음과 같은 방법을 사용한다.
- 1) 최대 매칭 M*를 구한다.
- 2) 정점 집합 X를 구한다: L의 매칭되지 않은 정점들과, 그 정점으로부터 alternating path를 통해 도달할 수 있는 L, R의 모든 정점
- 3) 최소 버텍스 커버 C* = (L - X) U (R ∩ X)
- 즉, L의 정점들 중에서는 X에 미포함인 것들, R의 정점들 중에서는 X에 포함인 것들을 묶어 최소 버텍스 커버 C*를 구할 수 있다.
- 코드는 tgraph.bipartite_matching() 에서 얻은 매칭 결과를 이용해서 이런식으로 구현할 수 있다.
from teflib import tgraph def minimum_vertex_cover(bigraph): def dfs_rec(u, is_mvc): is_mvc[u] = False for v in bigraph[u]: if not is_mvc[v]: is_mvc[v] = True if (next_u := matched_node[v]) is not None and is_mvc[next_u]: dfs_rec(next_u, is_mvc) matching = tgraph.bipartite_matching(bigraph) matched_node = [None] * len(bigraph) for u, v in matching.items(): matched_node[v] = u is_mvc = [bool(edges) for edges in bigraph] for u, edges in enumerate(bigraph): if edges and u not in matching: dfs_rec(u, is_mvc) return [u for u, u_is_mvc in enumerate(is_mvc) if u_is_mvc]- tgraph.bipartite_matching을 활용해서 구현하다보니, 이분매칭 과정에서 이미 구했던 matched_node 리스트를 minimum vertext cover를 구하기 위해서 다시 만들어야 하는 등, 다소 비효율적인 부분은 있다.
- 관련 문제: 최소 버텍스 커버
최소 경로 커버 / 최대 반사슬
- DAG에서 최소 경로 커버 (Minumum Path Cover)은 DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제이다.
- 이 문제를 이분 매칭으로 변환하는 방법은 다음과 같다.
- 원래 DAG의 노드 갯수 * 2 개의 노드로 이루어진 이분 그래프를 만든다
- 원래 DAG에 v_1~v_n 까지의 노드가 존재했다면 l_1 ~ l_n, r_1 ~ r_n 의 노드를 갖도록 한다.
- DAG에 존재하는 엣지 v_i ⇒ v_j 에 대해서 l_i 와 r_j 를 연결하는 엣지를 만든다.
- 이분 그래프에서 매칭된 엣지들은 DAG에서 패스를 구성하는 엣지들이 된다.
- 패스의 갯수는 n - {이분매칭의 크기} 가 된다.
- 각 패스의 시작점에 해당하는 노드들은, l_1 ~ l_n 중에서 매치되지 않는 노드들이다.
- 각 패스의 끝점에 해당되는 노드들은, r_1 ~ r_n 중에서 매치되지 않는 노드들이다.
- 부분 순서 집합에서의 최대 반사슬(Maximum Anti Chain)은 위상관계가 없는 정점들로 이루어진 최대 크기의 집합을 구하는 문제이다.
- 딜워스의 정리(Dilworth's theorem)는 부분순서집합(POSET; Partially Ordered Set)에서 최대 반사슬의 크기가 최소 경로 커버의 크기와 같다는 정리이다.
- 따라서 최대 반사슬의 크기도 이분 매칭을 이용해서 구할 수 있다.
- POSET으로 문제가 주어진 경우에는, transivity를 적용해서 DAG를 만든 다음에, 최소 경로 커버에서 설명했던것처럼 다시 이분그래프를 만들어서 이분 매칭을 돌리면 된다.
- 최대 반사슬의 크기 역시 n - {이분매칭의 크기} 가 된다.
- 최대 반사슬 집합을 찾을 때에는, 최소 버텍스 커버의 여집합을 구해주면 된다.
- l_i와 r_i가 모두 최소 버텍스 커버에 포함되지 않는 v_i들의 집합을 구하면 된다.
- 좀더 자세한 설명과 증명: https://tamref.com/145
- 관련 문제
- 13503 : 최소 경로 커버
- 3295 : 최소 경로 커버
- 13411 : 최대 반사슬의 크기
- 스포츠 전문 채널 GSK : 최대 반사슬 집합 구하기
홀의 결혼 정리
- [작성중]
문제풀이 테크닉
한 노드에서 여러개의 노드로 연결이 가능할 때
- 매칭의 정의상, 한 노드에 연결된 엣지는 한개만 존재해야 한다.
- 따라서 그래프를 그대로 둔 상태에서는 한 노드를 최대 k개의 노드와 연결시키는 문제는 매칭으로 풀수가 없다.
- 이분 매칭을 플로우 문제로 변형하는 기본 방식을 적용하면, 시작 노드에서 왼쪽 그룹의 노드들까지의 유량을 k로 설정함으로써 이 문제를 최대유량 문제로 만들수 있고, 최대유량 알고리즘으로 풀수 있다.
- 하지만 k가 작을경우 (2~3정도)에는 그냥 동일한 노드들을 k개씩 만들어서 그래프를 만든 뒤, 그냥 이분매칭으로 푸는 방법이 가능하고, 더 빠르다.
- 관련 문제:
그리드를 이분그래프로 모델링
- 몇가지 유형이 있다.
각 셀을 노드로 모델링
- 제일 직관적이다
- 문제에서 인접한 셀 또는 특정 위치 관계에 있는 셀들 간에 제약 조건이 들어가게 되면, 이 위치 관계에 있는 셀들 사이에 엣지를 추가해서 그래프를 만들면 된다.
- 위치 관계에 따라서 이분 그래프가 만들어지는 경우에는 이분 매칭을 사용할수 있게 된다.
- 관련 문제
- 11014: 이렇게 만들어진 이분그래프에서 최대 독립집합을 찾는 문제
각 셀을 엣지로 모델링
인접한 셀 사이의 테두리를 노드로 모델링
- 그리드를 특정 타일들로 채우는 문제들의 경우, 각 테두리가 타일 내부에 있게 될지 타일의 테두리에 있게 될지를 결정하는 문제로 바꿀수 있다.
- 테두리들을 노드로 만들고, 타일의 형태에 따라서 엣지들을 만들었을때 이분 그래프가 된다면, 타일링 문제를 이분 매칭으로 바꿔서 풀수 있는 경우가 있다
- 관련 문제
에지에 가중치가 있고, 매칭에서 최대 가중치를 최소화 시키는 문제
- 보통은 가중치가 x이하인 엣지들만으로 그래프를 구성할때 퍼펙트 매칭을 만들수 있는 x의 최소값을 찾는 문제가 된다.
- 이분 탐색으로 x의 값을 찾을 수 있다.
- 관련 문제
ps/이분_매칭.txt · 마지막으로 수정됨: 2022/04/22 14:16 저자 teferi
토론