이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.
2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem)
무언가를 최적화시키는 문제를 보면 생각보다 많은 경우 다른 최적화 문제와 크게 관련이 있는 것을 볼 수 있습니다. 대표적인 예시가 바로 최대유량 최소컷 정리(maximum flow minimum cut theorem)입니다. 이 정리에 따르면, 어떤 flow network에서 유량(flow)을 최대화하는 문제는 곧 그 network의 최소 컷(cut)을 찾는 문제와 동일하다는 사실을 알 수 있습니다..
이번에 함께 살펴 볼 문제들도 이와 비슷한 관계가 있습니다. 바로 matching과 vertex cover입니다. 각각이 익숙한 분들도 있으시리라 생각합니다. 저 또한 그랬으니까요. 그런데, 둘이 매우 밀접하게 연관되어있다는 사실은 최근에서야 알게 되었습니다. 이를 한 번 공유하고자 합니다.
먼저 matching과 vertex cover가 무엇인지 확실하게 하고 가시죠. 사실, 이전 포스팅에 matching이 많이 (아마 모두죠?) 등장했는데 반해서, matching의 정의를 제대로 짚고 넘어가지는 않았습니다. 이번에는 겸사겸사 정의를 하고 넘어가도록 하겠습니다.
Matching
임의의 그래프 \(G = (V, E) \)에 대해서, 부분집합 \(M \subseteq E\)의 모든 간선이 정점을 공유하지 않을 때, \(M\)을 matching이라고 부른다.
이전 포스팅에서는 bipartite graph에서만 다루었지만, 사실 matching은 일반적인 그래프에서도 정의가 됩니다. 다음 그림에서 빨간색 실선이 matching에 해당하게 되지요.
자, 다음 선수는 vertex cover입니다. 지금까지는 간선의 부분집합을 다루었는데 이번에는 정점의 부분집합을 다루게 됩니다.
Vertex cover
어떤 그래프 \(G = (V, E)\)가 주어졌을 때, 부분집합 \(U \subseteq V\)에 대해서, 모든 간선의 한 끝점이 \(U\)에 속하면 \(U\)를 vertex cover라고 부른다.
즉, 부분집합 \(U\)와 그와 붙어있는 간선들을 함께 제거했을 때, 그래프에 간선이 하나도 남아있지 않으면, 우리는 \(U\)를 vertex cover라고 부릅니다. 그림 1과 동일한 그래프에 대해서 다음 그림의 빨간색 점은 vertex cover를 이룹니다.
컴퓨터과학 전공자는 익숙할 것인데, 이 분야는 항상 무언가를 최적화시키려고 합니다. 무언가를 적게 뽑아야 하면, 어떻게 하면 가장 적게 뽑을 수 있을까를 고민하고, 반대로 무언가를 많이 뽑아야 한다면, 어떻게 해야 가장 많이 뽑을 수 있을까를 정말 주구장창 고민합니다.
당연히 matching과 vertex cover도 똑같겠죠? 어떤 그래프에서 matching을 적게 만드는 것은 쉽습니다. 그냥 간선 하나 고르면 끝이잖아요? 그러니 matching의 크기는 어떻게든 늘리려고 할 겁니다. 그러니 다음과 같은 문제를 정의하기에 이르죠.
Maximum matching problem
어떤 그래프가 주어졌을 때, 크기가 가장 큰 matching을 찾으시오.
반대로 vertex cover는 적게 뽑을 수록 어렵습니다. 그래프에 있는 모든 정점을 고르면 그 자체로 vertex cover니까요. 그러니 비슷하게 다음 문제를 정의합니다.
Minimum vertex cover problem
어떤 그래프가 주어졌을 때, 크기가 가장 작은 vertex cover를 찾으시오.
각각을 찾아보기 전에, 한 가지 질문을 드려보도록 하겠습니다. 과연 동일한 그래프에서 matching의 크기보다 작은 vertex cover를 찾을 수 있을까요? 잘 생각해 보면, matching에 속한 간선들의 끝점(endpoint)은 서로 다릅니다. 즉, vertex cover의 정점 하나가 처리할 수 있는 matching의 간선은 최대 하나입니다.
자, 이제 vertex cover의 크기가 matching보다 작다고 가정해보죠. 위에서 알게 된 사실을 토대로, vertex cover의 정점 하나씩을 빼서 matching 간선을 처리하다보면 분명 vertex cover의 정점으로 처리가 되지 않는 matching의 간선이 있을 것입니다. 이는 vertex cover의 정의에 어긋나게 되니 모순이 발생하게 되죠. 따라서 우리는 다음과 같은 사실을 도출할 수 있습니다.
정리 1. Matching과 Vertex cover의 관계
어떤 그래프 \(G\)가 주어졌을 때, \(M\)을 \(G\)의 어떤 matching, \(U\)를 \(G\)의 어떤 vertex cover라고 하면 \( |M| \leq |U| \)가 성립한다.
위의 예시에서 maximum matching과 minimum vertex cover는 각각 무엇일까요? 일단, 그림 1과 그림 2는 해당하지 않습니다. 잘 찾아보면 다음과 같습니다.
저는 무슨 근거로, 어떤 확신을 가지고, 여러분에게 그림 3과 그림 4가 각각 maximum matching과 minimum vertex cover라고 당차게 말씀드리는 것일까요? 네, 바로 정리 1 때문입니다. 어떤 그래프를 가지고 와도, matching의 크기는 vertex cover의 크기를 넘을 수 없으며, 반대로 vertex cover의 크기는 matching의 크기보다 작아질 수 없습니다. 그런데, 우리는 지금 서로 크기가 같은 matching과 vertex cover를 가지고 왔으니, 각각이 자신이 할 수 있는 최선이라는 것을 알 수 있습니다.
정리 2. Maximum matching과 Minimum vertex cover의 관계
어떤 그래프 \(G\)에서 크기가 서로 같은 matching \(M^*\)와 vertex cover \(U^*\)가 존재하면, \(M^*\)는 \(G\)의 maximum matching이며 \(U^*\)는 \(G\)의 minimum vertex cover이다.
따라서, 서로 크기가 같은 matching과 vertex cover를 찾기만 한다면 우리는 위의 두 문제를 동시에 풀어 제낄 수 있습니다. 말 그대로, 님도 보고 뽕도 따는 그런 멋진 상황인 것이죠. 과연, 그런 matching과 vertex cover가 존재할까요? 일단 최소한 bipartite graph에 대해서는 존재한다는 것이 알려져 있습니다. 바로, 그리고 드디어, 오늘의 주제인 쾨니그의 정리(Kőnig's theorem)입니다. (사실, 발음 어떻게 하는지 모릅니다. 그냥 위키피디아에서 그렇게 나와 있길래 저도 따라 적었습니다.)
쾨니그의 정리 (Kőnig's theorem)
모든 bipartite graph에서 maximum matching의 크기와 minimum vertex cover의 크기는 동일하다.
이 정리를 증명하는 방법도 매우 다양하게 있습니다만, 제가 이번에 하려고 하는 증명은 지난 홀의 정리의 증명과 매우 유사합니다. 똑같이 최대유량 최소컷 정리(max-flow min-cut theorem)를 사용합니다. 우리는 어떤 bipartite graph의 maximum matching problem을 풀 때, 이를 flow network로 구성하여 maximum flow problem으로 바꾸어 해결할 수 있습니다. 이 때, maximum matching의 크기나, maximum flow의 값이나 minimum cut의 크기 모두 같다는 것도 해당 정리를 통하여 알 수 있습니다. 그리고, 어떤 flow network든지 minimum cut은 다음 그림과 같이 이루어질 것입니다.
우리가 무엇을 할지를 상기시켜 드리죠. 우리가 원하는 것은 어떤 matching과 크기가 같은 vertex cover를 찾는 것입니다. 그러면 정리 2를 통해서 자연스럽게 쾨니그의 정리가 증명이 되겠죠. 그런데, minimum cut의 크기가 maximum matching과 크기가 동일하다는 것을 아니까, 만약 우리가 minimum cut과 크기가 같은 vertex cover를 찾는다면, 동일한 결과를 얻을 수 있습니다.
자, 여기서 지난 시간 우리가 홀의 정리를 증명하면서 배운 내용을 써먹어 볼까 합니다. 바로 \(L_1\)과 인접한 정점은 모두 \(R_1\)에 속한다는 사실입니다. 도식화하면 다음과 같았죠.
여기서 끝나지 않습니다. 곰곰이 따져보면, \(R_2\)에 대해서도 비슷하게 써먹어 볼 수 있을 것입니다. 즉, \(L_1\)과 \(R_2\) 사이에는 간선이 존재하지 않으므로, \(R_2\)에 인접한 정점들(\(N(R_2)\)라고 표현하죠.)은 모두 \(L_2\)에 속할 것입니다.
그렇다면 우리가 \(L_2 \cup R_1\)을 뽑으면 어떻게 될까요? 이는 바로 vertex cover가 됩니다.
좀 더 자세히 설명드리겠습니다. 먼저, \(L_1\)과 \(R_1\)을 잇는 간선은 \(R_1\)에 의해서 모두 처리가 됩니다 (빨간색 파선). 또, \(L_2\)와 \(R_2\)를 잇는 간선은 \(L_2\)에 의해서 커버가 되지요 (파란색 쇄선). 마지막으로 \(L_2\)와 \(R_1\)을 잇는 간선들의 경우에는 어차피 양 끝 점이 모두 뽑혔습니다 (검정색 실선). 나머지 \(L_1\)과 \(R_2\)를 잇는 간선은 없다는 것도 알고 있으니, \(L_2 \cup R_1\)은 진짜로 vertex cover입니다.
이것만으로는 부족하죠? 네, 우리는 그 크기가 minimum cut과 동일한지를 따져봐야 합니다. 그런데 사실, 따질 것도 없죠? 바로 \( |L_2| + |R_1| \)이 minimum cut의 크기였으니까요. 드디어 이것으로 모든 증명이 끝나게 됩니다.
지금까지 우리는 모든 bipartite graph에서 maximum matching과 minimum vertex cover의 크기가 같다는 쾨니그의 정리를 알아보았습니다. 사실, 위의 증명을 그대로 따라하기만 하면 다항 시간에 풀 수 있으므로, bipartite graph에서는 각각을 구하는 것도 어렵지 않습니다. 그렇다면 일반 그래프에서는 어떻게 될까요? 불행하게도, 크기가 서로 같아지지 않는 경우가 존재합니다. 매우 간단한 예시가 있습니다.
정말, '헐!' 입니다. 각각이 maximum matching이고 minimum vertex cover라는 사실은 굳이 보이지 않겠습니다. 경우의 수도 얼마 없으니까 그냥 다 해보시면 알 수 있습니다.
여기서 매우 재밌는(?) 상황이 발생합니다. 알고리즘 수업을 들으신 분이라면 아시겠지만, minimum vertex cover problem은 유명한 NP-hard 문제 중 하나입니다.[1] 즉, 일반적인 그래프에서 minimum vertex cover를 찾는 것은 아무래도 어렵다는 뜻이죠. 그런데 일반적인 그래프에서 maximum matching을 다항 시간에 구하는 알고리즘은 알려져 있습니다. 바로 blossom algorithm인데요. 아직 저도 잘 몰라서, 이번에 한 번 공부해 보고자 합니다.
매우 깊은 관계가 있는 두 문제 중에 하나는 쉽게 풀리고, 반면 다른 하나는 아직 푸는 방법을 모르는, 아마도 쉽게 못 풀 것 같은, 그런 상황, 신기하지 않으신가요? 과연 둘은 어떠한 연관성을 더 가지고 있을까요? 최근에 너무 재밌게 고민해 봐서 이렇게 정리해 봅니다.
궁금하신 점이나 잘못된 점이 있으면 댓글을 남겨주세요. 여기까지 긴 글을 읽어주셔서 대단히 고맙습니다.
각주
[1] 어떤 그래프에 크기가 \(k\)보다 작은 vertex cover가 존재하는지를 판단하는 문제가 NP-complete입니다. 만약 minimum vertex cover를 구하는 알고리즘을 알고있다면, 이 알고리즘을 이용해서 \(k\)보다 작은 vertex cover가 있는지 없는지를 판단할 수 있습니다.
'조합론적 최적화 > Matching' 카테고리의 다른 글
| 텃의 정리 (Tutte's Theorem) (0) | 2020.10.10 |
|---|---|
| 헝가리안 알고리즘 시간 복잡도 분석 (7) | 2020.03.18 |
| 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm) (9) | 2020.02.22 |
| 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) (30) | 2019.08.07 |
| 홀의 정리 (Hall's Theorem) (8) | 2019.01.28 |
