ネットワークフローの最小限の検索

Question

ソースから始まるDFS/BFSを使用して最小カットを見つけることができます。しかし、各ノードから始まるBFS/DFSを使用して、最小カットを見つけるためにシンクに到達できるかどうかを確認できますか？ または、最小限のカットをすべて見つけるにはどうすればよいですか？

Answer 1

私はあなたの質問を理解していません。最小カットを見つけるために、最大流量を見出し、それを用いて最小カット（max cut max flow定理）を見つける。

残っているネットワークを取得した後で、複数の分カットがあるかどうかを確認したい場合は、BFS(s) - sで始まり、このグループの頂点をXとします。次に、残余ネットワークのエッジを反転してBFS(t)を実行し、このグループの頂点をYとします。 Xとの和集合がすべてグラフの頂点である場合、カットは1つだけです。それ以外の場合は、複数選択してください（Zミニカットを見つけるには、少なくとも(Z|V|)