2

無向グラフ G = (V, E) が与えられた場合、G のエッジは非負の重みを持ちます。

[1] 2 つのノード s と t の間のすべてのエッジ独立パスと等コスト パスを見つける方法は?

[2] 2 つのノード s と t の間のすべてのエッジ独立パスを見つける方法は?

[3] 2 つのノード s と t の間のすべての頂点分離パスと等コスト パスを見つける方法は?

[4] 2 つのノード s と t の間のすべての頂点分離パスを見つける方法は?

代わりに近似アルゴリズムはありますか?

4

1 に答える 1

4

各ノードが単方向グラフを通るパスの表現であるツリーを構築します。

木もグラフですが、この回答では、次の用語をこの意味で使用します。

  • 頂点：単方向グラフの頂点です。それは私のツリーのノードではありません。
  • edge：単方向グラフのエッジです。それは私の木の一部ではありません。
  • ノード：グラフではなく、ツリー内の頂点。
  • ルート：親を持たない、ツリーの最上位の唯一のノード。
  • 葉：子を持たないツリー内のノード。

ツリーのエッジについては説明しないので、ツリーエッジの言葉はありません。この回答のすべてのエッジはグラフの一部です。

ツリーを構築するためのアルゴリズム

ツリーのルートは、頂点のみを含み、エッジを含まないパスの表現です。その重みを0とします。

そのツリー内のすべてのノードに対して実行します。

そのノード（私はそれを実際のノードと呼びます）によって表されるパスの端の頂点を取り、その端の頂点から離れるすべてのエッジを見つけます。
次の場合：この頂点から離れるエッジがない場合は、行き止まりに達しています。このパスが頂点tにつながることはありません。したがって、このノードをリーフとしてマークし、無限の重みを付けます。
そうしないと：

これらのエッジごと
に 、子ノードを実際のノードに追加します。実際のノードのコピーとします。エッジをパスの端に接続してから、エッジの端の頂点もパスに接続します。（したがって、各パスはパターンvertex-edge-vertex-edge-vertex -...に従います。）
次に、ツリーを上に移動してルートに戻り、先行するもののいずれかに、ちょうど同じである終了頂点があるかどうかを確認します。 end-vertexを追加しました。
一致するものがある場合、新しく生成されたノードは、ループを含むパスの表現です。このノードをリーフとしてマークし、無限の重みを付けます。
それ以外の場合ループがない場合は、新しく追加されたエッジの重みをノードの重みに追加するだけです。ここで、新しく生成されたノードの終了頂点が頂点tであるかどうかをテストします。
もしもこのノードによって表されるパスはsからtへの有効なパスであるため、実際には、このノードをリーフとしてマークします。

このアルゴリズムは常に有限の時間で終了します。最後に、ツリーには3種類の葉があります。

  • 無限の重みで行き止まりを表すノード
  • ループを表すノード、これも無限の重み
  • sからtへの有効なパスを表すノード。その重みは、このパスの一部であるすべてのエッジの重みの合計になります。

リーフで表される各パスには、個別のエッジシーケンスがあります（ただし、同じ頂点シーケンスが含まれる場合があります）。したがって、有限の重みを持つリーフは、sからtまでのエッジが互いに素なパスの完全なセットを表します。これが運動の解決策です[2]。

次に、有限の重みを持つすべてのリーフに対して実行します
。その重みとパスをリストに書き込みます。リストを重みで並べ替えます。これで、同じ重みを持つパスがリスト内の隣接パスになり、このソートされたリストで等コストパスのすべてのグループを見つけて抽出できます。これが運動の解決策です[1]。

次に、このリストの各エントリに対して実行します。
このリストの各パスに、その頂点のリストを追加します。これを実行すると、次の列を持つテーブルが作成されます。

  • 重さ
  • 道
  • 1番目の頂点（常にs）
  • 2番目の頂点
  • 3番目の頂点
  • ..。

このテーブルのレキシグラフィックを頂点で並べ替え、すべての頂点の後に重みで並べ替えます（1番目の頂点、2番目の頂点、3番目の頂点、...、重みで並べ替えます）この並べ替えられたテーブルの1つの行に、前の行と同じ頂点のシーケンスがある場合、次に、この行を削除します。

これは、2つのノードsとtの間のすべての頂点が互いに素なパスのリストであるため、演習[4]の解決策です。

そして、このリストでは、すべての等コストパスが隣接パスとして検出されるため、そのリストから2つのノードsとtの間の頂点が互いに素で等コストのパスのすべてのグループを簡単に抽出できるため、ここで演習の解決策が得られます[3 ]。

于 2012-07-24T10:31:43.143 に答える