텃의 정리 (Tutte's Theorem)

Photo by Dylan Gillis on Unsplash

드넓은 황야에 위치한 초원 대학교의 컴퓨터과학과 소속 폰가젤 교수는 2인 조별 과제를 내는 것을 좋아합니다. 혼자서 해결하기에는 벅찬 문제를 두 명이서 협력하여 해결한다면 학생들에게 협동심은 물론 위기에 굴복하지 않는 능력을 기를 수 있다고 굳게 믿기 때문이죠. 물론 '조별과제 잔혹사'라는 말을 언젠간 들어 봤을 정도로 학생들의 원성이 자자하다는 사실도 잘 알고 있습니다. 그가 개설했던 알고리즘 수업의 강의 평가를 보면 쉽게 유추할 수 있었죠. 그동안은 학생들이 자율적으로 조를 편성하도록 놔두었는데, 이러니 어떤 학생들은 전혀 마음이 맞지 않는 사람과 조를 이루어야 하는 불상사가 발생했었죠. 이 부분이 바로 학생들이 가장 불편을 느낀 부분이었습니다.

 

이번 학기에 가젤 교수는 이러한 학생들의 원성을 잠재우고자 한 가지 묘수를 냈습니다. 학기 초에 모든 학생들에게 함께 조를 이루어도 괜찮은 사람의 명단을 제출하라고 하는 것이죠. 그러고는 서로가 서로를 괜찮다고 하는 경우에 한해 조를 지어주는 것입니다. 과연 가젤 교수는 모든 학생들을 본인이 원하는 학생과 조를 맺어줄 수 있을까요? 이를 알 수 있다면 가젤 교수에게는 명분이 생길 겁니다. 만일 모든 학생들이 각자 원하는 사람과 조를 이룬다면 원만하게 한 학기를 보낼 수 있을 것이고, 반대로 불가능하다면 학생들에게 "저는 최대한 노력하였지만, '이론적으로' 불가능합니다, 학생 여러분."이라며 나름의 변명을 할 수는 있겠죠.(물론, 그냥 조별 과제를 하지 않는게 학생들 입장에서는 가장 좋은 선택이지만요.)

 

위 문제는 다음과 같은 방식으로 정의할 수 있습니다. 학생들을 정점의 집합 \(V\)에 대응시키고, 두 학생이 서로를 자신의 명단에 올린 경우에 두 정점을 간선으로 연결하는 것이죠. 그렇게 얻은 간선의 집합을 \(E\)라고 하겠습니다. 두 학생을 한 조로 엮는 것은 그에 대응하는 간선을 선택하는 것으로 간주할 수 있습니다. 어떤 학생도 두 개 이상의 조에 속할 수는 없으므로 뽑힌 간선들은 서로 정점을 공유하면 안됩니다. 이에 대응하는 것이 무엇이 있을까요? 바로, 매칭(matching)입니다. 따라서 우리는 위 문제를 다음의 형태로 바꾸어 표현할 수 있습니다.

어떤 그래프 \(G = (V, E)\)가 주어졌을 때, 모든 정점이 참여하는 매칭, 다시 말해, 완전 매칭(perfect matching)이 존재하는가?

\(G\)가 이분 그래프(bipartite graph)일 때는 완전 매칭이 존재할 필요충분조건이 다음과 같다는 사실이 잘 알려져 있습니다.

정리 1. 이분 그래프에서 완전 매칭이 존재할 필요충분조건

---

어떤 이분 그래프 \(G = (A \cup B, E) \)에 완전 매칭이 존재할 필요충분조건은 \( |A| = |B| \)이고 임의의 \( A' \subseteq A \)에 대해, \(|A'| \leq |N(A')|\)을 만족하는 것이다. 이때, \( N(A') \)은 \(A'\)의 어떤 정점과 인접한 \(B\)의 모든 정점을 나타낸다.

이는 홀의 정리(Hall's theorem)를 통해 쉽게 유도할 수 있습니다. 더 자세한 내용이 궁금하시면 이전 포스트를 참조하세요.

2019/01/28 - [조합론적 최적화/Matching] - 홀의 정리 (Hall's Theorem)

홀의 정리 (Hall's Theorem)

하지만 안타깝게도 가젤 교수가 직면한 문제에서는 이분 그래프를 가정하기 힘들죠. 학생들이 자신의 '사랑의 작대기'를 어디에 어떻게 보낼지 모르기 때문입니다. 과연 이렇게 일반적인 그래프에 대해서도 완전 매칭이 존재할 필요충분조건이 있을까요? 놀랍게도 존재합니다.(없었다면 이 글을 적을리가 없었으니 그다지 놀랍지는 않겠군요.) 바로 텃의 정리(Tutte's theorem)입니다. 이번 포스트에서는 이 정리에 대해 함께 알아보도록 하겠습니다.

직관적으로 이해하기

어떤 그래프에 완전 매칭이 존재하기 위해서는 반드시 만족해야 하는 조건이 있습니다. 바로, 정점의 개수가 짝수라는 것이죠. 그렇지 않으면 정점을 어떻게 짝짓더라도 적어도 하나의 정점은 매칭에 참여하지 못하게 되기 때문이죠. 이는 매우 자명한 사실이지만, 이를 다음과 같이 확장하면 텃의 정리를 이해하는데 큰 도움이 됩니다.

 

그래프에 다음과 같은 장난을 쳐보겠습니다. 주어진 그래프 \(G=(V,E)\)에서 한 정점의 부분집합 \(S \subseteq V\)를 생각한 후 \(G\)에서 \(S\)의 정점들과 그에 딸린 간선들을 모두 제거해 보겠습니다. 이렇게 얻은 그래프는 연결 성분들(connected component)로 나뉘었을 겁니다. 이 연결 성분들 중에는 정점의 개수가 홀수인 것들도 있을 것이고, 짝수인 것들도 있을 겁니다.

그림 1. 완전 매칭이 존재할 수 없는 이유. \(S\)의 크기가 그래프에서 \(S\)를 제외한 후 홀수 크기의 연결 성분의 개수보다 작다.

여기서 흥미로운 점은 정점 개수가 짝수인 연결 성분들은 그 내부에서 완전 매칭을 형성할 수 있겠지만, 정점 개수가 홀수인 연결 성분들은 분명 최소한 하나의 정점은 매칭에 참여하지 못한 채 쓸쓸히 남아있게 된다는 점입니다. 따라서 원래 그래프에 완전 매칭이 존재하려면, 정점 개수가 홀수인 연결 성분들은 분명 \(S\)의 한 정점으로부터 짝을 구해와야 합니다. 그런데 정점 개수가 홀수인 연결 성분들의 수가 \(S\)의 크기보다 많다면 이 연결 성분 모두를 짝지어줄 방법 자체가 없으므로 해당 그래프에는 완전 매칭이 존재하지 않는다고 확신할 수 있습니다.

텃의 정리 (Tutte's Theorem)

위에서 확인한 바를 수학 기호와 함께 엄밀히 표현하면 다음과 같습니다. 어떤 그래프 \(G = (V, E)\)에서 한 정점의 부분집합 \(S \subseteq V\)에 대해, \(G\)에서 \(S\)와 이에 딸린 간선을 모두 제거한 그래프를 \(G-S\)라고 부르겠습니다. 만약 \(S := \{ v \}\)라면 편의 상 \(G-\{v\}\) 대신 \(G - v\)로 표현할 수 있습니다. \( G \)에서 \(S\)를 제거했을 때(즉, \(G-S\) 위에서) 정점의 개수가 홀수인 연결 성분들의 수를 \( q_G(S) \)로 표현하겠습니다. 그러면 위 절에서 보인 사실은 만약 \(G\)에 \(q_G(S) > |S|\)를 만족하는 정점의 부분집합 \(S \subseteq V\)가 존재한다면, \(G\)에는 완전 매칭이 존재할 수 없다는 것입니다. 이것의 대우 명제는 다음과 같습니다.

어떤 그래프 \(G = (V,E)\)에 완전 매칭이 존재하기 위해서는 임의의 \(S \subseteq V\)에 대해 \( q_G(S) \leq |S| \)를 만족해야 한다.

과연 그 역도 참일까요? 놀랍게도 그렇습니다. 그리고 그것이 바로 텃의 정리입니다.

정리 2. 텃의 정리(Tutte's theorem)

---

어떤 그래프 \(G = (V, E)\)에 완전 매칭이 존재하는 필요충분조건은 임의의 정점의 부분집합 \(S \subseteq V\)에 대해 \(G\)에서 \(S\)를 제외한 그래프에서 정점의 개수가 홀수인 연결 성분의 개수가 \(S\)의 크기를 넘지않는 것, 다시 말해, \( q_G(S) \leq |S| \)가 성립하는 것이다.

역 증명

따라서 남은 것은 다음의 역 명제를 보이는 것입니다.

어떤 그래프 \(G=(V,E)\)에서 만약 임의의 \(S \subseteq V\)에 대해 \( q_G(S) \leq |S| \)를 만족하면 \( G \)에는 완전 매칭이 존재한다.

이는 \(|V|\)에 대한 수학적 귀납법으로 증명하도록 하겠습니다. 기저 조건은 \( |V| = 1 \), 다시 말해, \( G=(\{v\}, \emptyset) \)인 경우입니다. 이때 \(G\)에는 완전 매칭이 존재하지 않습니다. 게다가 \(G\)에서 아무것도 제외하지 않아도 그 자체로 홀수의 정점 개수를 갖는 연결 성분이므로 \( q_G(\emptyset) = 1 \)입니다. 따라서 \(S = \emptyset\)에 대해, \( q_G(S) = 1 > 0 = |S|  \)를 알 수 있죠. 이는 위 명제의 대우 명제에 대한 증명이므로 기저 조건을 만족하게 됩니다.

 

따라서 이제부터는 어떤 그래프 \(G = (V, E)\)가 주어졌을 때, \( |V| \)보다 작은 개수의 정점을 갖는 모든 그래프에 대해 위 명제가 성립한다고 가정하겠습니다. \(G\)에 대해서 명제가 성립한다는 것을 보이면 증명이 완료되겠죠. 아래 보조정리는 아래 증명에서 요긴하게 사용됩니다.

정리 3. \(V\)와 \(q_G(S)-|S|\)의 홀짝성(parity)

---

임의의 그래프 \(G=(V,E)\)와 임의의 부분집합 \( S \subseteq V \)에 대해, \( q_G(S) - |S| \)와 \(|V|\)의 홀짝성은 같다. 즉, 둘 다 홀수이거나 짝수이다. 다시 말해, \[ q_G(S) - |S| \equiv |S| - q_G(S) \equiv |V| \pmod{2} \]를 만족한다.

[증명] 우리는 정점 집합 \(V\)를 다음의 세 경우로 파티션(partition)할 수 있습니다.

1. \(S\)에 속하는 경우
2. \(G-S\)에서 홀수의 정점 개수를 갖는 연결 성분에 속하는 경우
3. \(G-S\)에서 짝수의 정점 개수를 갖는 연결 성분에 속하는 경우

이때, 항목 2의 홀짝성은 \( q_G(S) \)의 그것과 같고, 항목 3은 항상 짝수이므로 홀짝성에 영향을 주지 않습니다. 따라서, \[ q_G(S) + |S| \equiv |V| \pmod{2} \]를 만족합니다. \(2|S|\)는 짝수이므로 이를 좌변에서 빼도 홀짝성에는 영향을 주지 않습니다. ■

 

증명을 시작해 보겠습니다. 먼저 우리는 일반성을 잃지 않고 \( |V| \)가 짝수라고 가정할 수 있습니다. 그렇지 않으면 기저 조건에서의 증명과 마찬가지로 \(G\)에는 완전 매칭이 존재하지 않고, \(S = \emptyset\)에 대해 \( q_G(S) = 1 > 0 = |S| \)가 되어 대우 명제가 성립하게 됩니다.

 

이제부터 \( q_G(X) = |X| \)를 만족하는 \(X \subseteq V\)를 생각해 보겠습니다. 일단 그러한 \(X\)가 존재하는 것은 쉽게 알 수 있는데, \(|V|\)가 짝수이기 때문에 \(V\)에서 임의의 정점을 빼면 홀수의 정점 개수를 갖는 연결 성분이 하나 생기기 때문입니다. 즉, 임의의 정점 \(v \in V\)에 대해서, \( q_G(\{v\}) = 1 = |\{v\}| \)가 만족합니다. 이를 만족하는 \(X\) 중에서 maximal한 것을 생각해 보겠습니다.

 

\(X\)가 maximal하기 때문에 우리는 두 가지 흥미로운 사실을 이끌어낼 수 있습니다. 첫 번째는 \(G - X\)에 짝수 크기의 연결 성분은 존재하지 않는다는 겁니다.

정리 4. \(X\)의 성질 1

---

\(G - X\)에는 짝수 개의 정점을 갖는 연결 성분이 존재하지 않는다.

[증명] 만약 \(G - X\)에 짝수 개의 정점을 갖는 연결 성분 \(C\)가 존재한다고 하겠습니다. 이때 \(C\)에는 지워도 다른 정점들은 모두 연결된 상태를 유지하는 정점 \(v \in V(C)\)가 존재합니다. 즉, \(C-v\)가 연결된(connected) 그래프인 것이죠. 이를 증명하는 것은 간단합니다. \(C\)는 연결 성분이므로 분명 \(C\)에는 스패닝 트리(spanning tree)가 존재합니다. 이 트리의 리프(leaf)에 해당하는 정점을 지우면 다른 정점들의 연결성에는 영향을 주지 않습니다.

그림 2. \(G - X\)에 짝수 크기의 연결 성분이 존재하는 경우. \(X \cup v\)가 \(X\)의 maximality에 모순을 일으킨다.

이제 \(v\)를 \(G - X\)에서 지워보도록 하겠습니다. 연결 성분끼리는 서로 연결되어 있지 않기 때문에, \(v\)는 \(C\)에만 영향을 줍니다. 따라서 \(G - X - v\)는\(G - X\)보다 정점 개수가 홀수인 연결 성분이 정확히 하나 더 많이 존재합니다. 따라서 \( q_G(X \cup \{v\}) = q_G(X) + 1 = |X| + 1 = |X \cup \{v\}| \)를 만족하게 되며 이는 \(X\)가 maximal하다는 사실에 위배됩니다. ■

 

다음은 \(G - X\)의 모든 연결 성분은 거의 완전한 매칭을 갖는다는 사실입니다. 이 증명은 위 증명에 비해 상대적으로 어려운 편입니다.

정리 5. \(X\)의 성질 2

---

\(G - X\)의 임의의 연결 성분 \(C\)에 대해, \(C\)에서 아무 정점 \(v \in V(C)\)를 제거하면 해당 그래프 \(C-v\)에는 완전 매칭이 존재한다.

[증명] 똑같이 귀류법으로 보이도록 합시다. 만약 어떤 정점 \(v\)에 대해 \(C - v\)에 완전 매칭이 존재하지 않는다고 합시다. 그러면 \(|V(C - v)| < |V|\)이기 때문에 귀납 가설(induction hypothesis)에 의해 분명 \[q_{C-v}(Y) > |Y| \]가 되는 \( Y \subseteq V(C - v) \)가 반드시 존재할 것입니다. 이때, 정리 3에 의해 \( q_{C-v}(Y) - |Y| \)의 홀짝성은 \( |V(C-v)| \)의 그것과 같고, \( |V(C-v)| \)는 짝수이므로 우리는 \[ q_{C-v}(Y) \geq |Y| + 2 \tag{1} \]라는 사실을 이끌어낼 수 있습니다. 만약 \( q_{C-v}(Y) = |Y| + 1 \)이라면 \( q_{C-v}(Y) - |Y| = 1 \)은 홀수가 되기 때문입니다.

그림 3. \(G-X\)의 한 연결 성분에 거의 완전한 매칭이 존재하지 않는 경우. \(Z = X \cup Y \cup \{v\}\)가 \(X\)의 maximality에 모순을 일으킨다.

이제 \( Z := X \cup Y \cup \{ v \} \)가 \( q_G(Z) = |Z| \)를 만족한다는 것을 보이겠습니다. 먼저, \(q_G(Z) \leq |Z|\)는 우리가 처음 조건에서부터 가정한 사실입니다. 따라서 \( q_G(Z) \geq |Z| \)를 보이면 모든 증명이 완료됩니다. 먼저 정리 4의 증명과 마찬가지로, \( Y \cup \{v\} \)는 \(C\)에만 영향을 미치기 때문에 다음이 성립합니다.

\[ q_G(Z) = q_G(X \cup Y \cup \{ v \}) = q_G(X) - 1 + q_C(Y \cup \{v\}) = q_G(X) - 1 + q_{C - v}(Y) \]

그러면 식 1에 의해 다음의 부등식을 이끌어낼 수 있습니다.

\[ q_G(Z) \geq q_G(X) - 1 + |Y| + 2 = |X| + |Y| + 1 = |Z| \]

이는 \(X\)의 maximality에 모순이 됩니다. ■

 

이제 \(G\)에 완전 매칭이 존재함을 보이도록 하겠습니다. 이를 위해 다음과 같은 보조 그래프 \(H = (A \cup B, F) \)를 만들어 보겠습니다. (그림 4)

• \(A\)에는 \(G - X\)의 각 연결 성분 \(C\)에 대해 \(a_C\)를 만든다. \(B\)는 \(X\)와 동일하다.
• 만약 \(G\) 위에서 어떤 연결 성분 \(C\)의 한 정점이 \(X\)의 한 정점 \(v \in X\)와 인접(adjacent)하다면 \((a_C, v) \in F\)이다.

만약 \(H\)에 완전 매칭이 존재하면 \(G\)에도 완전 매칭이 존재하게 됩니다. 그 이유는 어렵지 않습니다. \(H\)의 한 완전 매칭에 \( (a_C, v) \in F \)가 들어 있다면, 분명 \( (u, v) \in E \)를 만족하는 \( u \in V(C) \)가 존재할 겁니다. 정리 5에 의해, \(C - u\)에는 완전 매칭이 존재하고, 따라서 각 \(v \in X\)에 대해 \((u, v)\)와 \(C - u\)의 완전 매칭을 구해 모두 합치면 이는 \(G\)에서의 완전 매칭이 되겠습니다.

그림 4. \(G\)와 \(H\)의 관계. 왼쪽이 \(G\)를 오른쪽이 \(H\)를 나타내고 있다.

\(H\)는 이분 그래프(bipartite graph)입니다. 따라서 정리 1이 만족하는지를 따져 보면 됩니다. 만약 \(H\)에 완전 매칭이 존재하지 않는다면 분명 \( |A'| > N(A') \)을 만족하는 \( A' \subseteq A \)가 존재할 것입니다.(단, \(N(A')\)은 \(A'\)의 어떤 정점에 인접한 \(B\)의 정점의 부분집합)

그림 5. \(H\)에 \(\mid A' \mid > \mid N(A') \mid\)인 경우. \(G - N(A') \)에는 최소한 \( \mid A' \mid \) 개의 홀수 크기를 갖는 연결 성분이 존재한다.

만약 \(H\)에서 \(N(A')\)을 지운다면 \(A'\)의 모든 원소들은 고립(isolated)되게 됩니다. 즉, 다른 어느 정점에도 인접하지 않는다는 뜻이죠. 같은 맥락으로 \(G\)에서 \(N(A') \subseteq X \)을 지우면 홀수 크기의 연결 성분이 \(G - N(A')\)에 적어도 \(|A'|\) 개 생기게 됩니다. (그림 5) 따라서, \[ q_G(N(A')) \geq |A'| > N(A') \]를 이끌어낼 수 있습니다. 이는 원래 명제의 조건에 위배되는 사실이므로 모순입니다. 따라서 \(H\)에는 완전 매칭이 존재합니다.

텃-베르주 공식 (Tutte-Berge Formula)

이것으로 임의의 일반적인 그래프에 완전 매칭이 존재하는 필요충분조건인 텃의 정리에 대해서 모두 알아보았습니다. 마치기 전에 텃의 정리의 일반화된 형태인 텃-베르주 공식(Tutte-Berge formula)을 소개하겠습니다. 텃의 정리는 그래프에 완전 매칭이 존재하는지 하지 않는지에 대한 정보만을 알려줍니다. 따라서, 만약 완전 매칭이 존재하지 않는다면, 최대 매칭(maximum matching)의 크기는 얼마큼 될지는 정리의 명제만을 통해서는 알 수 없습니다. 흥미롭게도 텃의 정리가 최대 매칭을 구하는 데도 큰 도움을 준다는 사실이 잘 알려져 있습니다.

정리 6. 텃-베르주 공식 (Tutte-Berge formula)

---

어떤 그래프 \(G = (V, E)\)가 주어졌을 때, 그것의 최대 매칭을 \(M^\star \subseteq E\)라고 하자. 그러면, \[ |M^\star| = \frac{1}{2} \left[ |V| - \max_{S \subseteq V} \{ q_G(S) - |S| \} \right] \tag{2} \]가 항상 만족한다.

[증명] 먼저 좌변이 우변보다 작거나 같다는 것을 보이겠습니다. 직관적으로 이해하기 절에서 살펴 보았듯이, 임의의 \(S \subseteq V\)에 대해, 적어도 \( q_G(S) - |S| \) 개수의 정점은 어떤 매칭이든지 간에 참여할 수 없습니다. 따라서,

\[ |M^\star| \leq \frac{|V| - (q_G(S) - |S|)}{2} \]

임을 알 수 있습니다. 위 식은 임의의 \(S\)에 대해 성립하기 때문에 식 2의 좌변이 우변보다 크지 않다는 것을 곧바로 보여줍니다.

그림 6. 그래프 \(G\)가 주어졌을 때, 보조 그래프 \(G'\)을 만드는 방법.

반대의 경우를 보이겠습니다. 먼저 \( k := \max_{S \subseteq V} \{ q_G(S) - |S| \} \)라고 하겠습니다. 그후, 다음과 같이 정의되는 새로운 보조 그래프 \(G' = (V', E')\)을 만들겠습니다. (그림 6)

• \(k\) 개의 새로운 정점의 집합 \( U := \{u_1, \cdots, u_k\} \)을 만든다. \(V' := V \cup U'\)이다.
• \(E'\)은 \(E\)와 함께, \( U \)의 각 정점은 \(V\)의 모든 정점과 인접한다. 다시 말해, \[ E' := E \cup \{ (u, v) : u \in U,  v \in V \} \]을 만족한다. \(U\)의 정점들 끼리는 인접하지 않는다.

이제, \(G'\)에는 완전 매칭이 존재함을 보이겠습니다. 만약 \(G'\)에 완전 매칭이 존재하지 않는다면, 텃의 정리에 의해 분명 \[ q_{G'}(S') > |S'| \]을 만족하는 \(S' \subseteq V'\)이 존재할 것입니다. 정리 3에 의해 \( k \)의 홀짝성은 \(|V|\)와 동일하므로, \( |V'| = |V| + k \)는 반드시 짝수입니다. 따라서 \( q_{G'}(\emptyset) = 0 \)입니다. 그러므로 \( S' \neq \emptyset \)이라는 사실을 알 수 있습니다.

그림 7. \(U \nsubseteq S'\)인 경우 \(q_{G'}(S') \leq 1\)이다.

게다가, \( S' \supseteq U \)라는 사실도 이끌어낼 수 있습니다. 임의의 \(u \in U\)는 모든 \(V\)의 정점에 인접하기 때문에, 만약 \(S'\)에 \(u\)가 들어가지 않는다면 \(G' - S'\)에는 하나의 연결 성분만 존재할 것이기 때문입니다. 따라서, \( q_{G'}(S') \leq 1 \leq |S'| \)이 만족하게 됩니다. (그림 7)

그림 8. \(U \subseteq S'\)인 경우, \( q_{G'}(S') = q_G(S) \)를 만족한다.

따라서 우리는 \(S'\)을

\[ S' = S \cup U \text{ where } S \subseteq V \]

로 표현할 수 있고, \( G' - S' \)은 \(G - S\)와 동일하다는 것도 알 수 있습니다. 이를 통해,

\[ q_G(S) = q_{G'}(S') > |S'| = |S| + |U| = |S| + k \]

를 이끌어낼 수 있습니다. 그러면 \( q_G(S) - |S| > k \)가 되고, 이는 \(k\)가 좌변들의 최댓값이라는 사실에 모순이 됩니다.

그림 9. \(G'\)에서의 완전 매칭 \(M'\)에서 \(U\)에 연결된 간선을 제거하면 \(G\)에서의 한 매칭 \(M\)을 얻을 수 있다.

따라서 \(G'\)에는 완전 매칭이 존재합니다. 이를 \(M' \subseteq E'\)이라고 부르겠습니다. 완전 매칭이기 때문에 알 수 있는 사실은 \(|M'| = \frac{|V'|}{2} = \frac{|V| + k}{2}\) 라는 점이죠. 이때 \(M'\)에서 \( U \)의 정점에 붙은 간선을 모두 제거한 매칭 \(M\)은 \(G\)에서도 가능한 매칭이 됩니다. (그림 9) 따라서,

\[ |M^\star| \geq |M| = |M'| - k = \frac{|V| - k}{2}\]

를 만족하게 됩니다. 이는 곧 식 2에서 좌변이 우변보다 작지 않다는 사실을 증명합니다. ■

마치며

이번 시간에는 일반적인 그래프에서 완전 매칭이 존재할 필요충분조건을 논의한 텃의 정리와 최대 매칭의 크기를 정확히 규명한 텃-베르주 공식에 대해서 공부하였습니다. 이 결과들은 주로 이분 그래프에서만 깊이 연구되어 온 매칭 이론의 저변을 일반적인 그래프로 확장시키는데 큰 공헌을 하였습니다. 다만, 아쉬운 점은 빠른 시간에 최대 매칭을 실제로 구하는 방법에 대해서 알려 주지는 못한다는 것입니다. 실지로 텃의 정리에 의거하여 완전 매칭이 존재하는지를 판단하기 위해서는 모든 정점의 부분집합 \(S\)에 대해 \( q_G(S) \leq |S| \)를 만족하는지를 따져 봐야 합니다. 과연 이를 다항 시간에 구하는 방법은 존재할까요? 다음 시간에는 이에 대해서 알아보도록 하겠습니다.

 

글에 오류가 있거나, 궁금하신 점이 있다면 언제든 알려주시기 바랍니다. 고맙습니다. :0

참조

[1] Bernhard Korte, Jens Vygen. Combinatorial optimization. 3rd ed. Springer, 2005.