反例を見つけようとしていますが、存在しないようです。しかし、証拠も見つかりませんでした。多分誰かが何か考えを持っていますか？詳細は次のとおりです。
ゼロ以外の最大フロー値を持つすべての st フロー ネットワークには、そのエッジの容量を減らすと最大フローの値が減少するようなエッジが存在します。これは真か偽か？
3256 次
1 に答える
7
それは本当です。
Ford と Fulkerson は、グラフの最大フローが最小カットに等しいことを基本的に示す最大フロー最小カット定理を証明しました。
ここで、最小カットは、グラフ内のエッジのセットの容量の合計に対応します。これらのエッジの 1 つの容量を減らすことを選択した場合はどうなるでしょうか? (残りの証明はあなたに任せます。)
于 2013-11-11T03:52:59.630 に答える