1

接続された無向頂点ラベル付きグラフ、グラフ内のエッジ、およびいくつかの数n ≥ 2 が与えられた場合、そのエッジを含む次数nのすべての接続された (ただし、必ずしも誘導されたわけではない) サブグラフを見つける効率的なアルゴリズムはありますか?

当然のことは、特定のエッジから開始し、1 つのパスがエッジを 2 回以上使用しないように注意しながら (同じ頂点に複数回アクセスすることは許可されています)、一種のエッジの再帰的走査であると考えました。各エッジをトラバースした後、パス上にいくつの頂点があるかを確認します。n未満の場合は、トラバーサルを続行します。nに等しい場合は、パスに対応するサブグラフを生成し、トラバーサルを続行します。nより大きい場合は停止します。ただし、この方法は、同じサブグラフを何度も生成するため、非効率的です。

(問題があれば、元のグラフのすべての頂点は次数 8 であり、最大 15 までのサブグラフの次数を探します。)

4

1 に答える 1

1

私の質問に対する David Eisenstat のコメントは、彼の回答を同様の質問に適応させることを提案しました。次の疑似コードは、私が確認した適応であり、1 つのサブグラフを複数回生成することはありません。では、n返されるサブグラフの順序 (すべてのサブグラフを返したい場合は省略できるテスト) を参照neighbours(e)し、エンドポイントを共有するエッジのセットを意味しますe。関数が最初に呼び出されるとき、subgraphEdgesパラメーターには指定されたエッジが含まれている必要があり、残りのパラメーターはそれに応じて設定する必要があります。

GenerateConnectedSubgraphs(edgesToConsider,
                           subgraphVertices、
                           subgraphEdges、
                           neighbouringEdges):
    let edgeCandidates ← edgeToConsider ∩ neighbouringEdges
    エッジ候補 = ∅ の場合
        |subgraphVertices|の場合 = n
           yield (subgraphVertices, subgraphEdges)
    そうしないと
        いくつかの e ∈ edgeCandidates を選ぶ
        GenerateConnectedSubgraphs(edgesToConsider ∖ {e},
                                   subgraphVertices、
                                   subgraphEdges、
                                   neighbouringEdges)
        GenerateConnectedSubgraphs(edgesToConsider ∖ {e},
                                   subgraphVertices ∪ endpoints(e),
                                   subgraphEdges ∪ {e},
                                   neighbouringEdges ∪ neighbours(e))
于 2013-06-06T11:06:04.613 に答える