3

へのエッジを許可しないように残差ネットワークを再定義するとしsます。手順 FORD-FULKERSON が依然として最大フローを正しく計算していることを主張してください。

パスを拡張すると、リバース エッジの残りの容量が増加し、必要に応じてそのエッジのフローを減らすために使用できる (ただし、ネットワーク フローは全体的に増加する) と考えていました。したがって、エッジを許可しない場合は、エッジsのフローの減少を許可しないことを意味しますs- x(xは に隣接するノードsです)。したがって、エッジを許可すると、次sのようなサイクルを持つことができます

s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t

しかし、再びエッジを許可しないsと、サイクルなしで同じパスを見つけることができます。上記はすべて直感的なアイデアですが、正式な証明が必要です。

質問は、Cormen らによるアルゴリズム入門からのものです。

4

1 に答える 1

0

あなたの直感的なアイデアは、証明にはすでに十分だと思います。2つのグラフを考えてみましょう。グラフG1ではエッジをsに許可し、グラフG2では許可しません。

ここで、Ford-FulkersonアルゴリズムがG1でG2よりも大きなフローを検出するとします。G2のすべての拡張パスはG1でも有効であるため、両方のグラフで同じ拡張パスをできるだけ長く使用してから、G1に拡張パスがあるが、G1にはない残りのネットワークの状態を取得できます。 G2。

ただし、ご指摘のとおり、sへの最後のアクセスの前に来るすべてのエッジを削除することを条件として、G1で有効な拡張パスはG2でも有効です。したがって、私たちの仮定は間違っており、そのような状況は存在できません。フォード・ファルカーソンは、G1とG2の両方で同じ出力を生成します。

于 2012-10-04T16:17:46.827 に答える