이분 매칭 (Bipartite Matching)

좀더 이론적인 설명을 찾은 것은, 위키피디아의 Hopcroft Karp 알고리즘 문서 에서인데, 평균적으로 스파스한 그래프는 높은 확률로 로그길이의 증가경로를 갖고, 그래서 이런 그래프에서는 Hopcroft Karp 알고리즘도 O(E*sqrt(V))가 아니라 O(ElogV)으로 돌아간다고 한다.

일반적인 최대유량 문제에서는 augment path를 BFS로 찾는 에드먼드-카프 알고리즘을 사용하면 O(VE^2)의 더 효율적인 시간복잡도가 나오지만, 이분매칭에서는 똑같이 O(VE)이다. 그래서 굳이 BFS를 쓰는 것보다 그냥 DFS로 짜는 것이 실질적으로 더 빠르게 동작한다.

|V|대신에 매칭의 크기에 바운드되게 하는 살짝 더 빠른 알고리즘도 있다.

스파스한 그래프에서는 O(E^(10/7))에 풀수 있다.

플래너 그래프에서는 최대 유량 문제로 바꿔서 O(Vlog^3V)에 풀수있다

이 방식도 한번의 BFS/DFS에서 여러개의 증가경로들을 찾아서 업데이트 해준다는 것은 호프크로프트-카프와 비슷하다. 그러나, 동작 방식이 다른 것이, 가장 작은 증가경로부터 업데이트 해주는 것을 보장하지 않는다. 그래서 O(sqrt(V)*E)의 시간복잡도가 되지는 않을것 같고 (적어도 위 방식 처럼은 증명이 안될듯.. 다른 방법으로 증명가능할지는 모르겠다) 그냥 O(VE)일것 같아 보이는데.. 실질적인 실행 속도는 더 빨랐다.

최종적으로 teflib에 구현하는 것은 이 방법으로 했다. 출처 블로그에 있던 구현에 추가로, 단순한 휴리스틱으로 초기 매칭을 찾는 과정을 추가했다.

따라서 최소 버텍스 커버의 크기도 이분 매칭을 통해서 쉽게 구할수 있다.

일반 그래프에서는 성립하지 않는다 → 일반 그래프에서 최소 버텍스 커버를 구하는 것은 NP-complete이다.

|최소 버텍스 커버| = |최대 매칭|

|최대 독립집합| = |V| - |최소 버텍스 커버| = |V| - |최대 매칭|

1867 : 최소 버텍스 커버

2414 : 최소 버텍스 커버

복수전공 : 최대 독립집합

11014 : 최대 독립집합

kks 블로그

1) 최대 매칭 M*를 구한다.

2) 정점 집합 X를 구한다: L의 매칭되지 않은 정점들과, 그 정점으로부터 alternating path를 통해 도달할 수 있는 L, R의 모든 정점

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를 구하기 위해서 다시 만들어야 하는 등, 다소 비효율적인 부분은 있다.

참고 : https://blog.naver.com/jqkt15/222058427237 https://gazelle-and-cs.tistory.com/52

참고 : https://blog.naver.com/jqkt15/222062117806

딜워스의 정리(Dilworth's theorem)는 부분순서집합(POSET; Partially Ordered Set)에서 최대 반사슬의 크기가 최소 경로 커버의 크기와 같다는 정리이다.

13503 : 최소 경로 커버

3295 : 최소 경로 커버

13411 : 최대 반사슬의 크기

스포츠 전문 채널 GSK : 최대 반사슬 집합 구하기

11376

1671

11014: 이렇게 만들어진 이분그래프에서 최대 독립집합을 찾는 문제

1574: 최대한 많은 셀을 고르는 문제이므로, 최대한 많은 엣지를 찾는 이분 매칭 문제가 된다

2414: 최대한 적은 행 또는 열을 골라서 모든 셀을 커버하는 문제다. 이 모델링에 의하면 모든 엣지를 커버하는 최소한의 노드를 찾는 문제이므로 최소 버텍스 커버 문제가 된다.

1799: 행과 열이 아니라, 대각선들을 노드로 만들게 되지만 기본 원리는 동일하다.

14930

1348