0

アルゴリズムの解析について勉強しています。私は現在、Network Flowアルゴリズムについて読んでいます。最小コストのNetwork Flow発見に関するアルゴリズムの適用を検討しています。bipartite matchings

  • G対応するネットワーク フローを使用してみましょうG'
  • になろMうperfect matchingG
  • このマッチングG<sub>M</sub>にresidual graph関連付ける

Jon Kleinberg と Eva Tardos のAlgorithm Design 7.13 on page 406 から、

Theorem 7.62状態:

(7.62) M を完全一致とする。G Mに負のコスト有向サイクル C がある場合、M は最小コストではありません

この定理は理にかなっていますが、 abipartite flow network's residual graphの aperfect matchingが実際にサイクルをどのように含むことができるかについては混乱しています。サイクルを確認できる唯一の方法は、sinkまたはsourceが関係している場合です。

ただし、 にはperfect matching、sourceそこから出るエッジは含まれず、 にsinkは入るエッジは含まれません。また、内部ノードで発生するサイクルは、 a の定義と矛盾するように見えBipartite graphます。

誰かが残差グラフでそのようなサイクルの例を提供できますか?

4

1 に答える 1

1

もちろん。a = コスト、c = 容量のグラフを考えてみましょう。

  a=3,c=1
Ao----->oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co----->oD
  a=3,c=1

したがって、明らかに 2 つの可能な最大フローがあります。1 つは水平方向のエッジを使用し、もう 1 つは対角線を使用します。

水平線に沿ったフローについては、残差グラフがあります。

  a=-3,c=1
Ao<-----oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co<-----oD
 a=-3,c=1

容量が 1 でコストが -3 + 1 -3 + 1 = -4 のサイクル B->A->D->C に注目してください。

このサイクルの直感的な説明は、サイクルのエッジに沿って流れる 1 つのユニットのフローが増加するたびに、または逆にそのエッジに沿って反対方向に流れるフローが減少するたびに、フローの総コストが 4 減少するということです。比較的高価な水平エッジに沿った流れを安価な対角エッジに沿った流れに置き換えます。

最小コスト フローの拡張パス アルゴリズムでは、このサイクルに沿って 1 単位のフローをプッシュし、対角線に沿って新しい安価なフローになります。これにより、新しい残差グラフが提供されます。

  a=3,c=1
Ao----->oB
  ^    /
   \  /a=-1,c=1
    \/
    /\
   /  \a=-1,c=1
  v    \
Co----->oD
  a=3,c=1

ここで、サイクルは A->B->C->D であり、コストは 3 - 1 + 3 - 1 = 4 であるため、対角線に沿った最大フローは最小コスト最大フローです。

于 2014-04-08T04:55:38.260 に答える