여러분이 어떤 단체의 인사 담당자라고 하죠. 총 다섯 명의 직원이 새로이 자리를 배치 받아야 하는 상황입니다. 고맙게도 충원되어야 하는 자리도 총 다섯 개입니다. 자애로운 여러분은 모든 직원들이 만족하도록 자리를 배치하고 싶어서 직원들에게 자신이 배치 받아도 좋은 자리가 어딘지를 먼저 물어 보았습니다. 직원은 알파벳(A-E)으로, 자리는 숫자(1-5)로 표현했을 때, 여러분은 직원들이 원하는 자리를 다음과 같이 표현하였습니다.
이제 여러분은 직원들에게 자리를 배치해야 합니다. 아마도 여러분은 다음 그림과 같이 손쉽게 네 명은 배치할 수 있을 것입니다. 실제로 배치된 것을 빨간 실선으로 표현하였습니다.
하지만 직원 E를 배치하지 못한 상황입니다. 과연 여러분은 모든 직원에게 서로 다른 자리를 하나씩 배치할 수 있을까요? 가능하다면, 어떻게 배치하면 될까요? 불가능하다면, 어째서 그것이 불가능하다는 것을 확신할 수 있을까요? 정답을 말씀드리자면, 아쉽게도 여러분은 다른 직원들도 각자 자리를 하나씩 가지면서 직원 E를 배치할 수는 없습니다. 어떻게든 직원 E를 배치하려고할 때면 다른 직원 한 명이 자리를 잃게될 것입니다.
만일 여러분이 컴퓨터과학 전공에다 알고리즘 수업을 들으셨다면 이 문제가 어떤 bipartite graph에서 모든 정점이 참여하는 matching(즉, perfect matching)을 찾는 것이라는 점을 알 수 있으실 터입니다. 이 정의가 익숙하지 않다면, 먼저 이를 숙지하고 오시는 것을 추천드립니다. 그렇게 어려운 내용은 아닙니다. 간단히 설명을 드리자면, bipartite graph는 정점을 정확히 두 개의 partition으로 쪼개며, 모든 간선이 두 partition에 걸쳐있는 그래프를 의미합니다. 주어진 그래프에서 정점들의 짝을 짓는 것을 matching이라고 합니다.
본론으로 돌아와서, 그럼 어째서 모든 직원을 배치할 수 없는 것일까요? 알고리즘을 들으신 분들이라면 이렇게 대답하실 수도 있을 것 같습니다.
어떤 bipartite graph에서 maximum matching을 다항 시간에 해결하는 알고리즘이 존재하기 때문에 이를 활용하여 maximum matching을 구한 후 정점이 모두 참여하는지를 따지면 되지 않을까요?
물론 맞는 말씀입니다만, 제가 여러분에게 질문을 드리고자 하는 내용은 좀 더 원론적입니다. 도대체 저 그래프에 어떤 성질이 있어서 모든 직원을 배치하는 방법이 존재하지 않는 것일까요? 이 질문에 대한 대답을 1935년 Philip Hall이 해주었습니다.
Hall's theorem
어떤 bipartite graph \(G = (L \cup R, E) \)가 주어졌다고 하자. 어떤 부분집합 \(S \subseteq L\)에 대해서, \(S\)에 인접한 정점들의 집합을 \(N(S) \subseteq R\)라고 할 때, \(L\)의 모든 정점이 참여하는 matching이 존재하는 필요충분조건은 모든 \(L\)의 부분집합 \(S\)가 \(|S| \leq |N(S)|\)를 만족하는 것이다.
홀의 정리가 강력한 이유는 바로 필요충분조건이기 때문입니다. 위 그래프에서 직원(A-E)을 \(L\), 자리(1-5)를 \(R\)이라고 했을 때, \(|S| > |N(S)|\)가 되는 \(L\)의 부분집합 \(S\)를 찾는다면, 이 그래프는 모든 직원이 참여하는 matching이 존재하지 않게 됩니다. 그런 부분집합을 찾으셨나요?
바로 직원 B, C, E로 이루어지는 부분집합입니다. 이 직원들이 희망하는 자리는 2와 3 밖에 없습니다. 그림 3을 보면 홀의 정리가 내포하는 의미를 직관적으로 이해할 수 있으리라고 봅니다. 만약 \(L\)이 모두 참여하는 matching이 존재하려면, 분명히 어떤 부분집합 \(S \subseteq L\)에 대해서 최소한 \(|S|\)개의 정점이 \(R\)에 있어야 합니다. 그래야 서로 다른 정점에 짝을 지어줄 수 있겠죠. 반대로, 그림 3의 경우와 같이, \(N(S))\)가 \(|N(S)| < |S|\)라면, \(S\)의 모든 정점을 서로 다른 이웃 정점에게 짝지어줄 수 없으니 분명 어느 정점이 비게 됩니다.
직관적으로 이해를 하였으니, 이제 증명을 해보도록 하겠습니다. 홀의 정리는 주어진 조건이 필요충분조건이기 때문에 양방향을 모두 보여야합니다. 즉, \(L\)이 모두 참여하는 matching이 존재할 때, 모든 부분집합 \(S \subseteq L\)에 대해서 \(|S| \leq |N(S)|\)라는 점과, 반대로 모든 부분집합 \(S \subseteq L\)이 \(|S| \leq |N(S)|\)를 만족할 때, \(L\)이 모두 참여하는 matching이 존재한다는 점입니다.
전자의 증명은 간단합니다. \(L\)이 모두 참여하는 matching이 존재한다고 하니, 그 matching을 그대로 갖다 사용하면 됩니다. 만약 다음 그림과 같이 왼쪽 정점이 모두 참여하는 matching을 갖고 왔다고 가정해 봅시다.
이 때, 어떤 부분집합 \(S \subseteq L\)에 대해서, 그것이 matching에서 대응되는 정점들을 \(M(S) \subseteq R\)이라고 합시다. 우리는 쉽게 다음과 같은 사실을 알 수 있습니다.
$$ |S| = |M(S)| $$
다음 그림을 보시면 더욱 명확하게 확인할 수 있습니다.
그런데, matching에서 짝을 지어주는 간선들 역시 원래 그래프의 간선이므로
$$ M(S) \subseteq N(S) $$
라는 사실을 얻을 수 있고, 이를 조합해 보면
$$ |S| = |M(S)| \leq |N(S)| $$
라는 우리가 원하는 식을 얻을 수 있습니다.
이제, 반대 방향을 증명해 보도록 하겠습니다. 이 방향의 증명이 위의 것보다 훨씬 까다로우며, 매우 다양한 증명 방법이 알려져 있습니다. 이번에 제가 보여드릴 방법은 제가 대학원 알고리즘 수업 시간에 들은 내용인데 제 생각에는 가장 간단한 방법입니다. 바로 최대유량 최소컷 정리(max-flow min-cut theorem)을 활용한 방법입니다.
Max-flow min-cut theorem
어떤 flow network에서 최대 유량의 값은 최소 컷의 크기와 동일하다.
이 정리는 너무도 유명하기 때문에 이번 포스팅에서는 따로 다루지는 않겠습니다. 나중에 기회가 되면 학부생들을 위해서 따로 다뤄보도록 하죠. 이것 하나만 짚고 넘어가겠습니다. 최소 컷에는 나가는 간선의 용량(capacity)만 더해줍니다. (학부생 때는 이게 그렇게 와닿지가 않더라고요. 허허.)
아무튼 이 정리를 사용한다는 것은 지금 이 문제를 maximum flow problem으로 바꾸어서 풀겠다는 의미입니다. 간단하게 어떤 bipartite graph를 flow network로 바꾸는 방법에 대해서 알아보겠습니다. 다음과 같이 bipartite graph \(G = (L \cup R, E)\)가 주어졌습니다.
이 bipartite graph를 다음과 같은 flow network로 만들어 줍니다. 새로운 정점 \(s\)와 \(t\)를 넣고 \(s\)에서 \(L\)로 가는 용량 1짜리 간선, \(R\)에서 \(t\)로 가는 용량 1짜리 간선을 넣습니다. 기존에 있는 \(E\)는 방향을 \(L\)에서 \(R\)로 향하게 하고 용량을 \(\infty\)로 줍니다.
이 flow network를 풀었을 때, 모든 간선의 유량의 값이 정수인 최대 유량(integral maximum flow)을 얻을 수 있고, 그 유량의 값은 maximum matching의 크기와 동일하게 됩니다. 또한 최대유량 최소컷 정리에 의해서 그 값이 최소 컷의 크기와 동일하다는 것도 알 수 있습니다. (앞에서와 마찬가지로, 증명은 생략하겠습니다. 나중에 기회가 되면 다루도록 할게요.)
여기서 제가 집중하고자 하는 부분은 바로 최소 컷입니다. 앞에서 최소 컷에는 나가는 간선의 용량만 고려한다고 말씀드렸습니다. 이 때, \(L\)에서 \(R\)로 가는 간선의 용량이 무지막지하게 크기 때문에, 우리는 이 flow network에서 최소 컷이 다음과 같이 형성된다는 것을 알 수 있습니다.
설명을 드리자면, \(L\)과 \(R\)이 각각 \(L_1, L_2\)와 \(R_1, R_2\)로 분할되며 \(L_1\)에서 \(R_2\)로 가는 간선은 존재하지 않는 상태입니다. 그 사이에 간선이 존재하면 컷의 용량이 \(\infty\)가 되기 때문입니다. 참고로 \(L_1\)이나 \(R_2\)가 공집합일 수 있습니다. 이 경우에는 각각 \(L\)이 모두 참여하는 matching과 \(R\)이 모두 참여하는 matching이 존재하는 상태를 나타냅니다. (잘 생각해 보세요!)
그림 8에서 최소 컷의 크기는 다음과 같습니다.
$$ |L_2| + |R_1| $$
그런데, \(L_1\)에서 \(R_2\)를 잇는 간선은 존재하지 않으므로 다음과 같은 사실을 알 수 있습니다.
$$ N(L_1) \subseteq R_1 $$
이를 그림으로 표현하면 다음과 같습니다.
그런데 우리는 조건에서 임의의 모든 부분집합 \(S \subseteq L\)에 대해서
$$ |S| \leq |N(S)| $$
라는 사실을 알고 있기 때문에, 이를 통해 우리가 알게된 사실을 모두 종합해 보면 최소 컷의 크기가
$$ |L_2| + |R_1| \geq |L_2| + |N(L_1)| \geq |L_2| + |L_1| = |L| $$
즉, \(|L|\) 보다 크거나 같다는 것을 알 수 있습니다. 이는 자연스럽게 크기가 \(|L|\)인 matching이 존재한다는 사실을 알려주며, 이로써 증명이 모두 끝이 납니다.
증명까지 모두 따라오시느라 고생이 많으셨습니다. 지금 보니까 그림 9에서 \(N(L_1)\)의 크기가 \(L_1\)의 크기보다 작군요. 그럼에도 여러분은 모두 이해하셨으리라 믿습니다.
사실 처음에 홀의 정리를 포스팅할 생각은 없었습니다. 그런데 최근에 bipartite graph에서 matching과 vertex cover가 매우 재미있는 관계에 있다는 사실을 알게 되었습니다. 바로 쾨니그의 정리(Kőnig's theorem)입니다. 이 정리가 홀의 정리와 매우 밀접하다는 것도 알게 되어서, 그거 포스팅할 겸해서 함께 홀의 정리도 주절주절 적어봤습니다. 쓰다 보니 영어와 우리말을 마구잡이로 사용한 것 같아서 죄송합니다. 사실 영어로만 쓰는게 편한데 (심지어 이제는 문장도 영어로 쓰는게 편합니다. 허허허.) 우리말로 옮겨 적겠다는 의지가 있어서 꽤 힘드네요. 계속 운영하면서 적응해야겠습니다. 당연히 다음 포스팅 주제는 쾨니그의 정리입니다.
혹시 궁금하신 점이나 잘못된 부분이 있으면 댓글 남겨주시기 바랍니다. 감사합니다.
'조합론적 최적화 > 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 |
| 쾨니그의 정리 (Kőnig's Theorem) (10) | 2019.01.28 |
