ホールの定理

3行要約

1. 二部グラフにおいて、一方の頂点集合をもう一方へ完全にマッチングできる条件を述べた定理。
2. 結婚定理とも呼ばれ、各人が希望する相手の集合が十分な大きさを持つ必要があることを示す。
3. 組合せ論や最適化問題において、資源配分やスケジューリングの基礎となる。