이분매칭 알고리즘 (feat. Minimum Vertex Cover) (추후 보완 예정)

이분매칭 (Bipartite Matching)

• Maximum Flow를 구하는 방법에는 Dinic Algorithm이 존재한다.
• 그런데, 모든 간선의 flow가 1이고, 이분 그래프 형태로만 존재한다면 bipartite Matching을 시도할 수 있다. (예를 들어 남녀가 미팅을 하며 각자가 원하는 짝을 1명씩 선택할 때, 최대 수로 성사시킬 수 있는 경우의 수는 이분 매칭으로 구할 수 있다.)
• 참고로 먼 옛적에는 Blossom Algorithm (1961)으로 최대 이분매칭 수를 O(EV^2)에 구했었다. 최악의 경우 O(V^4)까지 나올 수 있었던 셈. 원리가 궁금하다면 소멤 글을 참고해보자. https://www.secmem.org/blog/2020/04/18/Blossom/
• 이분매칭의 시간복잡도는 O(EV)
• 다만, Dinic Algorithm + bipartite matching => Hocropt-Karp Algorithm 을 사용하면 O(E(V^1/2))만에 이분매칭을 돌릴 수 있다.
• 만약 E = V^2 / 2일 경우 단순 이분매칭은 O(V^3)인데, 호프크로프트 카프 알고리즘을 이용하면 O(V^2)에 처리할 수 있는 것!

출처:

https://koosaga.com/18

https://m.blog.naver.com/kks227/220816033373

https://koosaga.com/133

---

최소 버텍스 커버 (Minimum Vertex Cover)

• 이분 매칭하면 빠질 수 없는 개념인 최소 버텍스 커버 (Minimum Vertex Cover)이다. 
• 그래프 간선의 양 끝점 중 하나 이상이 Vertex Cover에 들어가있어야 하며, 최소 노드의 수로 버텍스 커버를 이루는 경우를 최소 버텍스 커버라고 한다. 아래 그림의 경우, 두 개의 노드로 버텍스 커버를 만들 수 있다.

출처: 위키백과(영문)

In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard.
- 출처: https://en.wikipedia.org/wiki/Vertex_cover

 

다만, 이분그래프인 경우는?  Maximum Bipartite Matching = Minimum Vertex Cover

(feat. Konig's Theory)

proof)

1. 귀류법으로 Maximum Bipartite Matching보다 적은 경우로 버텍스 커버를 이룰 수 있다고 해보자.
2. 이 경우 Maximum Bipartite Matching을 이루며, 버텍스 커버에는 포함되지 않는 간선이 존재할 것이다.
3. 이러한 경우 그 간선은 버텍스 커버에 포함되지 않으므로 버텍스 커버의 정의에 위반된다.
4. 따라서 Maximum Bipartite Matching <= Vertex Cover 이다. (그려봐야 이해가 쉬울 것이다...ㅎㅇㅌ)

다만, 이분 그래프일 때만 통한다는 점에 주의하자.

 

 

추천 문제)

https://kth990303.tistory.com/185

이분 그래프로 모델링이 가능하므로 Konig's Theory를 이용하여 해결하자.

[BOJ] 백준 1867. 돌멩이 제거 (Platinum III)

https://kth990303.tistory.com/186

Maximum Independent Set은 Minimum vertex Cover의 여집합이며,

이분 그래프로 모델링이 가능한 문제이므로 이분 매칭으로 접근이 가능하다.

[BOJ] 백준 11014, 1014. 컨닝 2 (Platinum II)

 

 

출처:

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jqkt15&logNo=222053051039 

http://www.secmem.org/blog/2019/12/15/theorem-about-bipartite-matching/

https://koosaga.com/133