5

私は、隣接行列として与えられた n-partite (無向) グラフを持っています。たとえば、次のようになります。

  あいうえお
0 1 1 0
b 0 0 0 1
c 0 0 0 1
日 0 0 0 0

このマトリックスに適用できる一連のマトリックス操作があるかどうかを知りたいです。これにより、このグラフのすべてのパス (長さ n、つまりすべてのパーティションを通る) を「リスト」するマトリックスが得られます。上記の例では、パス a->b->d および a->c->d があります。したがって、結果として次のマトリックスを取得したいと思います。

あいうえお
1 1 0 1
1 0 1 1

最初のパスにはノード a、b、d が含まれ、2 番目のパスにはノード a、c、d が含まれます。必要に応じて、次のように、結果のマトリックスにすべて 0 の行が含まれる場合があります。

あいうえお
1 1 0 1
0 0 0 0
1 0 1 1
0 0 0 0

ありがとう！

PS私は推移閉包を計算するためのアルゴリズムを見てきましたが、これらは通常、2つのノード間にパスがあるかどうかのみを示し、どのノードがそのパス上にあるかを直接示しません。

4

2 に答える 2

4

できることの 1 つは、行列 A の n 乗を計算することです。その結果から、ある頂点から他の頂点までの長さ n のパスがいくつあるかがわかります。

パスに沿ったすべての頂点を知りたい場合は、純粋に行列演算を使用する方法は適切ではないと思います。n-partite グラフがあることを念頭に置いて、次のようにデータ構造をセットアップします。

各列には、グラフ内の各ノードのエントリが 1 つあります。n 番目の列には、指定された開始頂点または開始セットから n 回目の繰り返しでこのノードに到達できる場合は 1 が含まれ、それ以外の場合は 0 が含まれます。各列エントリには、n 番目の列のこの頂点につながった n-1 列の頂点へのバック ポインターのリストも含まれます。(これはビタビ アルゴリズムに似ていますが、1 つではなくエントリごとにバックポインタのリストを保持する必要があります。) これを行う複雑さは (m^2)*n です。ここで、m はエントリ内の頂点の数です。 n は目的のパスの長さです。

私はあなたの一番上の行列に少し混乱しています:無向グラフでは、隣接行列が対称であると予想されます。

于 2009-02-25T21:14:51.543 に答える
3

いいえ、すべてのパスを生成する純粋なマトリックスの方法はありません。純粋な組み合わせアルゴリズムを使用してください。

「実行できることの1つは、行列Aのn乗を計算することです。結果は、任意の1つの頂点から他の頂点までの長さnのパスの数を示します。」

matriaxの力は、パスではなくウォークを生成します。

于 2011-05-25T09:45:58.403 に答える