0

私はRobertSedwickによって書かれたAlgorithmsの本を読んでいます。

注：「s」はソースで、「t」はタンクです。

フローと容量がネットワークの値に等しい「t」から「s」までのエッジを持つフローネットワークを拡張し、拡張されたネットワーク内のノードのセットの流入が流出に等しいことを確認します。このような流れは循環と呼ばれ、この構造は、maxflowの問題が、特定のエッジに沿った流れを最大化する循環を見つける問題に還元されることを示しています。

一連のサイクルと各サイクルのフロー値が与えられると、各サイクルをたどり、示されたフローを各エッジに追加することで、対応する循環を簡単に計算できます。逆の特性はもっと驚くべきものです。任意の循環に相当する一連のサイクル（それぞれのフロー値を含む）を見つけることができます。

流れ分解定理：任意の循環は、最大でE方向のサイクルのセットに沿った流れとして表すことができます。

上記の説明に関する私の質問

  1. 著者が何を意味し、「maxflowの問題は、特定のエッジに沿った流れを最大化する循環を見つける問題に還元される」をどのように減らすことができるかを例を挙げて説明するように要求します。

  2. 次の段落の簡単な例で誰でも説明できますか？

「一連のサイクルと各サイクルのフロー値が与えられると、各サイクルをたどり、示されたフローを各エッジに追加することで、対応する循環を簡単に計算できます。逆の特性はさらに驚くべきものです。一連のサイクルを見つけることができます。 （それぞれのフロー値を使用して）任意の循環に相当します。」

ありがとう！

4

1 に答える 1

3

  1. ソースsとシンクtにmaxflowの問題がある場合は、エッジt-> sを追加するだけで、この問題を最大循環の問題に変換できます。sからtへの元の最大フローは、最大循環s --->t->sに変換されます。

  2. サイクルのリスト（グラフ内の閉じたパス）があり、すべてのサイクルがフローNに関連付けられている場合、すべてのサイクルを通過し、サイクルが通過するエッジにフロー値Nを追加できます。このようにして、グラフのすべてのエッジにフロー値が計算され、これがグラフの総循環量になります。逆に、定理は、グラフ全体に循環があるときはいつでも、それをサイクルに分解できると言っています。最大循環の例を次に示します。すべてのエッジで、表記a（b）は、フローがaであり、エッジの最大容量がbであることを意味します。

      3(3)     2(2)
a ----> b -----> c 
^       |1(1)    |
|3(3)   V        V 2(4)
d<------e<-------f
   3(4)     2(3)

対応するサイクルは次のとおりです。フロー値1のabeda、およびフロー値2のabcfed。これらの2つのサイクルは、上記のように最大循環を定義します。

于 2012-05-11T06:19:22.777 に答える