König's theorem

König's theorem states : In a bipartite graph, (Maximum matching) = (Minimum vertex cover)

임의의 vertex cover는 모든 간선을 cover해야 한다.
임의의 matching은 일부의 간선을 cover한다.
따라서 vertex cover의 갯수는 항상 어떤 matching의 갯수보다 크거나 같다. (각각의 매칭된 간선에서 점을 하나씩 고른다고 생각해보자.)
즉 (Minimum vertex cover) ≥ (Maximum matching).
따라서 어떤 Maximum matching M에 대해서, 크기가 \(|M|\)인 vertex cover를 만든다면 그것이 최소일 것이다.

크기가 |M|인 vertex cover를 만드려면 일단 M이라는 매칭을 사용해서 생각할 필요가 있겠다.
매칭된 모든 간선들에 대해, 두 끝점 중 L에 포함된 점을 vertex cover로 잡아보자. 이제 매칭된 간선들은 모두 cover 된다.

(빨간색은 Maximum matching, 파란색은 L을 선택함, 회색은 이 vertex cover에 의해 cover되는 간선)

매칭되지 않은 간선들은 cover되지 않았다.
매칭되지 않은 간선들은 항상 어떤 매칭된 간선과 꼭짓점을 공유한다. 그렇지 않으면 그 간선을 매칭에 포함시킬 수 있기 때문에 최대가 아니다.
그럼 위에서 선택한 정점들 중 일부를, 그 간선의 반대편 끝에 있는 점(즉 R에 포함)으로 바꾼다고 생각해보자. 여기서는 b 대신 x를 선택하는 것이 한 방법이다.
일부를 잘 바꿨을 때 모든 간선이 cover될 수 있을까?

일단, 문제가 되는 것은 매칭되지 않은 간선이다.
이 간선이 L에서 p, R에서 q를 잇는다고 하자.
1) p가 매칭되어있고 이를 선택할 거라면 자연스럽게 이 간선 또한 매칭되므로 큰 상관이 없다.
2) p가 매칭되어있지 않다면 반드시 q가 매칭되어있다. 따라서 q는 반드시 선택되어야 한다.
그렇다면, q와 매칭된 간선이 r-q를 잇는다고 하면, r은 선택되지 못한다.
그렇다면 r과 연결되어있고 매칭되지 않은 간선은 (1)에 어긋난다. 따라서
3) r이 매칭되어있으나, 그 반대편이 이미 선택되어 r을 선택하지 못하면 그 반대편의 q를 선택해야 한다.
이 방법에서, R에서 선택되는 점들을 살펴보자.

(L에 포함되어있고 매칭되지 않은 정점)의 집합을 \(X_{0}\)이라고 하자.
\(X_{0}\)과 (매칭되지 않은 간선)들로 연결되어있는 점들의 집합을 \(X_{1}\)이라고 하자.
\(X_{1}\)과 (매칭된 간선)들로 연결되어있는 점들의 집합을 \(X_{2}\)라고 하자.
\(X_{2}\)와 (매칭되지 않은 간선)들로 연결되어있는 점들의 집합을 \(X_{3}\)이라고 하자.
...
이 때, \(X_{1}\), \(X_{3}\), \(X_{5}\), ...은 R의 부분집합이고, 여기에 포함되어있는 점들은 반드시 선택해야 한다.
\(X_{0}\), \(X_{2}\), \(X_{4}\), ...은 L의 부분집합이고, 여기에 포함되어있는 점들 중 매칭된 간선 위에 있는 점들은 반드시 선택하지 말아야 한다.
이때 \(X_{i}\)들의 집합은, (L에 포함되어있고 매칭되지 않은 정점들의 집합)과, 그와 alternating path로 연결된 모든 정점들의 집합을 의미한다.
즉 \(\displaystyle{X = \bigcup X_{i}}\)일 때, \(\displaystyle{C = (L-X) \cup (R \cap X)}\)를 cover로 생각해보자.

이제 C가 모든 간선을 cover함을 검토해보자.

1) 모든 매칭되지 않은 간선은 커버된다.

a-b가 매칭되지 않았다고 하자.

a가 매칭되어있다면, (그 점을 c라고 하자)

a-c가 어떤 alternating path에 포함된다면,

a-c는 매칭, a-b는 매칭이 아니므로, c-a까지의 alternating path에 a-b가 연결될 수 있다.

따라서 \(a,b \in X\)이고,, b가 \(R \cap X\)에 속하므로 \(b \in C\). 따라서 a-b는 커버된다.

a-c가 alternating path에 포함되지 않는다면,

c를 선택할 이유가 없으므로 a를 선택한다. 따라서 a-b는 커버된다.

a가 매칭되어있지 않다면,

a-b는 어떤 alternating path의 시작이다. 따라서 b가 \(R \cap X\)에 속하므로 \(b \in C\). 따라서 a-b는 커버된다.

2) 모든 매칭된 간선은 커버된다.

a-b가 매칭되어있다고 하자.
a-b가 어떤 alternating path에 포함된다면,

a와 b는 X에 속하고, b가 \(R \cap X\)에 속하므로 \(b \in C\). 따라서 a-b는 커버된다.

a-b가 alternating path에 포함되지 않는다면,

b를 선택할 이유가 없으므로 a를 선택한다. 따라서 a-b는 커버된다.

이제 C의 크기를 생각해보자.
앞에서 생각한 것처럼 모든 매칭된 간선의 양쪽 중 한 개의 정점만 선택되어야 한다.
모든 매칭된 간선을 생각해보자.

alternating path에 포함된 간선 a-b는, (L-X)에서 \(a \notin C\), \((R \cap X)\)에서 \(b \in C\)이므로 성립.
alternating path에 포함되지 않은 간선 a-b는,

a나 b는 (alternating path에 포함되고 매칭되지 않은 간선)에 포함되지 않아야 한다.

왜냐하면, 포함된다면 그 path에 a-b를 추가하여도 alternating path이기 때문이다.

따라서 \(a,b \notin X\)이고, \(a \in C, b \notin C\)이므로 성립.

따라서 C는 minimum한 vertex cover이다.