이분 매칭에 관한 몇 가지 반례들

매칭(matching), 특히 이분 매칭(bipartite matching)은 제 주된 연구 분야 중 하나입니다. 제 블로그에 매칭 관련된 포스트가 가장 많은 것을 보면 쉽게 유추할 수 있으시리라 생각합니다. 최근 개인적으로 이분 매칭과 관련하여 몇 가지 명제를 세워 증명해 보려고 했습니다. 만약 참으로 밝혀진다면 제가 요즘 하는 연구에 도움이 될 명제들이었습니다. 하지만 안타깝게도 모두 반례가 존재하였습니다. 어디 가서 써 먹을 곳도 없다 보니 약간은 울적한 마음에 블로그에라도 적어 보려고 합니다. 혹여 비슷한 주제를 고민하시는 분들이 계시다면 이 글이 약간의 도움이 되었으면 합니다.

차수와 간선 서로소인 최대 매칭의 개수

첫 번째 명제는 다음과 같았습니다.

어떤 이분 그래프의 최소 차수(degree)가 2 이상이면, 그 그래프에는 적어도 두 개 이상의 간선 서로소(edge-disjoint)인 최대 매칭이 존재한다.

여기서 두 매칭이 간선 서로소 관계에 있다는 뜻은 두 매칭이 공유하는 간선이 없다는 뜻입니다. 이러한 명제를 생각한 이유는 다음의 명제가 잘 알려져 있었기 때문입니다.

정리 1. 이분 정규 그래프의 간선 서로소인 완벽 매칭의 개수

---

어떤 이분 그래프의 모든 정점의 차수가 \(r\)로 동일하다면, 즉, 이분 \(r\)-정규 그래프(bipartite \(r\)-regular graph)라면, 그 그래프에는 \(r\) 개의 간선 서로소인 완벽 매칭(perfect matching)이 존재한다.

[증명] \(r\)에 대한 귀납법으로 보이겠습니다. 만약 \(r = 1\)이라면 해당 그래프는 정확히 완벽 매칭과 동일합니다. 따라서 명제가 자명하게 성립합니다. 이제 임의의  이분 \((r - 1)\)-정규 그래프는 \(r - 1\) 개의 간선 서로소인 완벽 매칭이 존재한다고 합시다. 모든 이분 정규 그래프에는 완벽 매칭이 하나 존재합니다. 이분 \(r\)-정규 그래프에서 해당 완벽 매칭을 하나 찾아 제거해 보겠습니다. 그러면 모든 정점의 차수가 정확히 1씩 감소하므로 그 결과는 이분 \(r-1\)-정규 그래프입니다. 귀납 가정(induction hypothesis)에 의해 여기에는 \(r-1\) 개의 간선 서로소인 완벽 매칭이 존재합니다. 이는 처음에 찾은 완벽 매칭과도 간선 서로소를 이룹니다. ■

 

하지만 다음과 같은 반례가 존재하였습니다.

그림 1. 첫 번째 명제에 대한 반례.

그림 1의 그래프의 모든 정점의 차수는 2 이상입니다. 정확히는 두 정점은 3의 차수를 갖고 나머지는 2의 차수를 갖습니다. 최대 매칭은 완벽 매칭이라는 것을 쉽게 확인할 수 있습니다. 이때, 간선 \((x, y)\)를 넣지 않고서는 완벽 매칭을 만들 수 없습니다. 그러므로 위 그래프에서는 간선 서로소인 최대 매칭을 두 개 이상 선정할 수 없습니다.

이분 세제곱 그래프에서의 극대 매칭의 크기

다음 명제를 소개하기 전에 이분 세제곱 그래프에 대해서 정의하겠습니다. 어떤 이분 그래프 \(G=(L \cup R, E)\)가 주어졌을 때, 동일한 정점 집합을 갖고, 임의의 두 정점 \(x \in L\), \(y \in R\)에 대해, \(G\)에서 \(x\)와 \(y\)의 거리가 1 또는 3이면 \((x, y)\)를 간선으로 갖는 그래프를 이분 세제곱 그래프라고 부르며, \(G^3\)으로 표기하겠습니다. 이때 거리가 2인 정점 쌍을 잇지 않는 이유는 \(G^3\)을 이분 그래프로 만들기 위해서입니다.

 

이제 제가 생각했던 두 번째 명제를 소개하겠습니다.

어떤 이분 그래프 \(G\)에 대해, 그것의 이분 세제곱 그래프 \(G^3\)의 극대 매칭(maximal matching)의 크기는 최대 매칭의 크기에 \(\frac{2}{3}\)이다.

어떤 이분 그래프의 극대 매칭의 크기는 항상 최대 매칭의 크기의 절반은 된다는 것은 잘 알려진 사실입니다. 이에 대한 증명은 아래에서 확인하실 수 있습니다.

2020.05.03 - [수학적 도구/Basic] - Maximal & Maximum

Maximal & Maximum

그런데 만약 이분 세제곱 그래프의 정의를 확장하여 이분 \(n\)-제곱 그래프를 생각해 본다면, 이는 분명 완전 이분 그래프(complete bipartite graph)가 될 것이고, 따라서 자명하게 극대 매칭의 크기가 최대 매칭의 크기와 동일하게 됩니다. 따라서 저는 이분 세제곱 그래프에서의 극대 매칭의 크기 비율은 \(\frac{1}{2}\)과 1 사이의 \(\frac{2}{3}\) 정도가 될 것으로 예측하였습니다.

 

하지만 이 또한 다음의 반례가 존재하였습니다.

그림 2. 두 번째 명제에 대한 반례.

그림 2-(a)는 처음에 주어지는 그래프 \(G\)를 나타냅니다. 그림 2-(b)는 \(G^3\)에서의 극대 매칭 하나를 나타낸 것입니다. 이 매칭이 극대 매칭인 이유는 쉽게 확인할 수 있습니다. 원래 그래프 \(G\)에서 왼쪽의 하얀색 정점과 오른쪽의 검정색 정점의 거리는 5이기 때문입니다. \(G\)에 완벽 매칭이 존재한다는 것은 어렵지 않게 보일 수 있습니다. 따라서 \(G^3\)에서도 완벽 매칭이 존재합니다. 하지만 그림 2-(b)의 극대 매칭은 완벽 매칭의 크기의 절반보다 약간 좋은 크기를 갖습니다. 그마저도 층이 깊어질수록 절반에 한없이 가까워집니다.

 

위 분석을 확장하면 (비슷한 방식으로 정의한) \(G^5, G^7, \cdots\)에 대해서도 극대 매칭의 크기가 최대 매칭의 절반을 넘지 못하는 경우가 존재함을 알 수 있습니다.

 

앞에서 \(G^n\)은 완전 이분 그래프가 되므로 극대 매칭의 크기가 최대 매칭의 크기와 동일하다고 했습니다. 그렇다면 어느 순간부터 극대 매칭의 크기가 유의미하게 커지는 것일까요? 그림 2에서 극대 매칭의 크기가 완벽 매칭의 크기에 절반을 넘지 못함을 보이기 위해서는 엄청난 수의 정점을 필요로 합니다. 따라서 정점의 크기에 따라 같이 커지는, 예를 들어 \(\frac{n}{2}\)나 \(\log n\) 정도의 제곱 작업을 거친다면 극대 매칭의 크기가 절반보다 좋을 것을 기대해 볼 수 있겠습니다. 관련하여 최소 극대 매칭(minimum maximal matching)이라는 개념이 있더군요. 대개 특정 근사비 이내로 해결하기 어렵다는 결과가 많았습니다. 시간이 나면 그쪽도 공부해 볼까 합니다.