ケーニヒの定理

3行要約

1. 二部グラフにおいて、最大マッチングのサイズは最小頂点被覆のサイズに等しいという定理。
2. 組合せ最適化における「最大流最小カット」の概念とも深く関連している。
3. デネス・ケーニヒによって1931年に証明された。