Tool guide

最大流・最小カット・二部マッチング

Flow & matching パネルは、グラフ理論ワークベンチの共有キャンバス上で 3 つの関連する作業を扱います。Dinic または Edmonds–Karp によるソースからシンクへの最大流、グラフを彩色するか反例として奇数長閉路を返す二部判定、そして Kőnig の最小頂点被覆を伴うハンガリー最大マッチングです。フローの結果には最小カット容量、カット辺、カットのソース側が付くため、答えは自ら証明を伴います。

Updated 5 sources4 min read