二部グラフの最適化

Question

クラスのリストを含む2つのセットがあります。教師の一覧が含まれています。。この問題は、任意の最適化アルゴリズムに関連していますか？私は類似のアルゴリズムを見つけることができませんでした。ロジックを取得するのを助けてください。

Advaneのありがとう

Answer 1

これは real="nofollow">最大マッチング問題 最大フローアルゴリズム

最大流量の減少は簡単です：

• 元のグラフを（V、u、e）にしましょう。ここで、v、uはエッジです - 1つ 「授業」と「教師」のためのもの - 方向は先生 - >クラスです。
• 追加の2つの頂点を持つ新しいグラフG 'を作成します.s,t。
• sをすべての教師に接続し、すべてのクラスをtに接続します。
• 新しいグラフの各エッジに対して1の容量を与えます。
• 最大フローアルゴリズムを実行します。整数結果を返します（能力は整数ですので、行うことができます）。
• （利益）