問題タブ [network-flow]

有向グラフがあり、各エッジに正の容量があるとします。C が正の定数である場合、つまり、すべてのエッジ容量に C を加算または減算すると、最大フローが変更されます (増加または減少する可能性があります)。私の質問は、すべてのエッジ容量を C に掛けると、最大フローが C 倍になるのはなぜですか?

なぜこれが真実なのですか？

sの入次数と出次数が に等しい2 つの頂点を持つ有向グラフ (重みなし) G(V, E) がtありsます。からへの個別エッジ パスの最大数を見つけたいとします。どのアルゴリズムを使用してこれを行うことができます。Bellman-Ford、Dijkestra、Huffman、および Network Flow。ハフマンはあまり関係ないと思いますが、他の人はどうですか？ネットワーク フローが答えだと思いますが、その理由がわかりません。スタックキーアー、助けてください！t0st

ネットワークには複数の最小カットが存在する場合があります。例えば：

には 4 つの最小カットがあり、Ford-Fulkerson は s (ソース) に「近い」ものを見つけます。すべてのネットワークについて同じことが言えますか? つまり、Ford-Fulkerson はソースに最も近いカットを見つけますか? もしそうなら、フローネットワークで「ソースに最も近い」という概念をどのように形式化しますか?

stackoverflow と google を検索しましたが、まったく同じタイプの問題を抱えている人は見つかりませんでした。

都市に発電所を最適に配置することは、この問題に対する最も近い解決策のように思えましたが、私の問題はそこでの質問よりも単純であり、したがって、ブルートフォースよりも優れた解決策があると思います。

問題はこれです: 私には 9 つの都市があり、それぞれが電力を生産し、電力を使用しています。各都市は他の 8 つの都市に接続されています。余剰電力を必要とする都市に最小限の電力量で送る最良の方法を決定するにはどうすればよいですか?

複数のソースとシンクを利用してネットワーク フローでこの問題を解決しようとしましたが、正しく機能します。

ありがとう！

なぜそれは間違っているのですか？

なぜ、どのようにフローが変化するのでしょうか?

ありがとうございました。