6

グラフG（V、E）と頂点vが与えられた場合、正確にkの長さの単純なパス（パス上に頂点が繰り返されない）を介して到達可能なすべての頂点を見つけるにはどうすればよいですか。

隣接行列の累乗は、頂点間のパスの数を示しますが、単純ではないパスが含まれます。

この問題は多項式時間で解決できますか？そうでない場合は、既知の近似アルゴリズムはありません。文学へのポインタは素晴らしいでしょう。

4

2 に答える 2

1

私は最初の質問にのみ答えています：「それは多項式時間で解けるか？」。

多項式時間で解けると仮定します。次に、それを解いて、k=|V|-1結果の頂点を選択します。この頂点を削除し、この問題を解決しk=|V|-2ます。結果として得られる頂点のセットには、最後に削除された頂点に接続された頂点が少なくとも1つ含まれている必要があります。この頂点を削除しk=|V|-i、単一の開始頂点が残るまで処理を続行します。多項式時間アルゴリズムを使用した元のグラフのハミルトンパスを見つけました。

ハミルトン閉路問題はNP完全であるため、OPの問題も多項式時間で解ける可能性はほとんどありません。

于 2012-11-12T11:03:47.987 に答える
0

k以下に示すアルゴリズムは、開始ノードからの最小距離が等しいノードのリストを検索しますv。EG：次の場合に三角形グラフv、A、およびBが与えられます。

  • kが0の場合、結果はv
  • kが1の場合、結果にAはB
  • kが2以上の場合、結果はempty

擬似コード：

FindNodesWithShortestPath_K(G, v, k):
    create empty list R
    create empty queue Q

    mark v as visited
    set v.distance to 0
    add v to Q

    while Q is not empty:
        t <- dequeue node from Q
        if t.distance == k:
            add t to R
        else if t.distance > k:
            break
        else                
            for all neighbors u of t:
                if u is not marked as visited:
                    mark u as visited
                    u.distance = t.distance + 1
                    enqueue u onto Q

    return result

ノート：

  • ノードが訪問済みとしてマークされているかどうかを確認すると、単純なパスが保証されます
  • ノードの初期距離は関係ありません
  • t.distance == kの場合、tはRに属し、t個の近傍（Qではalredyではありません）は属しません
  • t.distance> kの場合、Qが空でなくてもアルゴリズムは停止します。アルゴリズムの実装を考えると、Qのノードの距離は減少していません
  • RおよびQに対する操作は、実装に応じてO（1）で実行できます。アルゴリズムには、O（| E | + | V |）の最悪のシナリオがあります
于 2012-11-12T01:51:03.877 に答える