ネットワークの最大フローについて質問があります。ソースとデスティネーションを切り離すことができるグラフのカット セットを見つけようとしていました。ソースから宛先まで、グラフ内のすべてのエッジに依存しないパスを調査しました。次に、これらのパスのそれぞれからエッジを選択し、それらをグループ化しました。基本的に、各パスから 1 つのエッジを取得するすべての可能な組み合わせを列挙しました。だから私はそのようなグループのセットを持っています。これは、最終的にその特定の送信元と送信先のネットワークのカット セットを見つけたことを意味しますか? これは効率的な方法ですか？
1 に答える
0
これは、指数関数的な複雑さを持っているように聞こえます。「すべてのエッジに依存しないパス」が何を意味するのかがわからないため、正確には言えません。例えば：
A
|
B
/ \
C D
\ /
E
A から E へのパスは 2 つありますが、エッジに依存しません。
グラフの最大フローは最小カットの双対であり、(小さな) 多項式時間でそれを見つけることができる標準アルゴリズムがたくさんあります。カットに満足している場合は、すべてのエッジを削除してください。これは時間 O(E) で実行されます。
あなたの制約は何ですか？
于 2012-11-28T02:06:04.743 に答える