Kőnig's theorem은 다음과 같이 정의된다.
이분 그래프에서 최대 매칭과 최소 정점 덮개의 크기는 동일하다.
증명 과정을 간략하게 설명한다.
우선 이분 그래프를 적절히 유량 그래프로 변환한다.
이분 그래프에서의 최대 매칭과 유량 그래프에서의 최대 유량의 크기는 동일하다.
Max-Flow Min-Cut theorem에 의하여 최대 유량과 최소 컷의 크기는 동일하다.
최소 컷 (S, T)에서 다음 집합은 최소 컷과 크기가 동일한 정점 덮개이다.
{소스와 인접한 정점 중 T에 속하는 정점 및 싱크와 인접한 정점 중 S에 속하는 정점}
또한 최대 매칭보다 크기가 작은 정점 덮개는 존재할 수 없다.
따라서 이분 그래프에서 최대 매칭과 최소 정점 덮개의 크기는 동일하다.
여담으로 최소 정점 덮개의 여집합은 최대 독립 집합이다.
따라서 이분 그래프에서 최대 매칭과 최대 독립 집합의 크기의 합은 정점의 개수와 동일하다.
끝
'알고리즘' 카테고리의 다른 글
| Network Flow 알고리즘 (0) | 2022.10.12 |
|---|---|
| Euler's theorem (0) | 2022.10.06 |
| Euler's phi function (0) | 2022.10.05 |
| Union-Find (0) | 2022.10.04 |
| Order Statistic Tree (0) | 2022.10.01 |
