二部グラフの最大マッチング問題
二部グラフにおいて、それぞれのグループに属する頂点を他方のグループの頂点とマッチングさせ、そのマッチングを最大化する問題のこと。マッチングは辺が存在する頂点どうしでのみ行われる。 この問題は最大フロー問題と見做して解くことができることで有名。具体的には始点と終点のノードを追加し、始点から片方のグループの全頂点に容量$ 1の辺を張り、もう片方のグループの全頂点から終点に向かって容量$ 1の辺を張る。あとは始点から終点に向かって流せる最大フローを計算すると、その値が最大マッチング数に等しくなる。 Ford-Fulkersonを使って解いた場合の計算量は$ O(E \min(A, B))となる。ここで$ A、$ Bはそれぞれのグループの頂点の数、$ Eは辺の数。