3

G = (V,E) の 2 つの頂点 u と v と正の整数 k を与えて、u から v への ak 辺の互いに素な経路が存在するかどうかを決定するアルゴリズムを説明してください。決定問題の答えが「はい」の場合、その方法を説明してくださいk 個の辺が素な経路のセットを計算します。

解決策 : u から v への最大フローを実行し (グラフ G のすべてのエッジに 1 の重みを与えて、1 つのエッジが u から v への 1 つのパスのみの一部になるようにします)、フローの値を取得します。フローの値が k の場合、決定問題の答えは「はい」になります。

このようなすべてのパスを見つけるために、u から BFS を実行して最小カットを見つけます。したがって、最小カットの両側に 1 つずつ、頂点を 2 つのセットに分割する頂点のパーティションがあります。

次に、最小カットから取得した 2 つのパーティション セットにあるこれらの頂点のみを持つすべてのパスを探して、u から v への DFS を再度実行する必要がありますか。

または、他のよりクリーンな方法はありますか？すべての k エッジの素なパスを取得します。

4

1 に答える 1

4

フローを取得したら、フローに従ってエッジの素なパスを抽出できます。

開始ノードには、k エッジに沿って u を残す k の流れがあります。

これらのエッジのそれぞれについて、v に到達するまでパスを抽出するために外向きの流れの方向に移動し続けることができます。必要なことは、エッジの重複を避けるために既に使用したエッジをマークすることだけです。

フローの k ユニッ​​トごとに繰り返し、u を残してすべての k パスを抽出します。

疑似コード

repeat k times:
  set x to start node
  set path to []
  while x is not equal to end node:
      find a edge from x which has flow>0, let y be the vertex at the far end
      decrease flow from x->y by 1 unit
      append y to path
      set x equal to y
  print path
于 2016-04-27T20:36:52.223 に答える