二部グラフのマッチング [いかたこのたこつぼ]

2部グラフ 頂点集合をAとBの2つに分けたとき、全ての辺がAの1つとBの1つを結び、A同士・B同士を結ぶ辺がないような分け方ができるグラフ 以下の例でも出てくるが、「仕事と人員を最適に割り振る」「定員を超過しないようにできるだけ希望の部活に入部させる」など現実でも出てくる最適化問題を解く際、仕事をA、人員をBとしたグラフに見立てて考えることができ、グラフ理論の様々なセオリーを使える。