2

たとえば、すべて青のノードと 1 つの赤のノードを持つグラフ G があるとします。また、すべて青で 1 つの赤のノードを持つグラフ F もありました。

これら 2 つのグラフが色付きのノードに関して同形であることを確認するために実行できるアルゴリズムは何ですか?

4

3 に答える 3

2

多項式グラフ同型アルゴリズムを作成しようと何度か試みましたが、すべてのケースで多項式であることが証明されているアルゴリズムをまだ作成していませんが、私が思いついた 1 つのアルゴリズムは、この目的に特に適しています。これは、DFA 最小化アルゴリズムに基づいています (特定のアルゴリズムはhttp://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithmです。ウィキペディアの説明はわかりにくいため、他の場所から説明を見つけることをお勧めします)。

元のアルゴリズムは、次数に基づいて頂点を個別のグループ (次数 1 の頂点に 1 つのグループ、次数 2 の頂点に 1 つのグループなど) に編成することによって初期化されました。目的のために、次数とラベルの両方に基づいて頂点をグループに編成する必要があります。これにより、ラベルが異なる場合に 2 つのノードがペアになることはありません。各グラフには、そのようなグループを含む独自の構造が必要です。両方のグラフのグループのコレクションを確認してください。2 つのグラフには同じ数のグループが存在し、一方のグラフの各グループには、同じ次数とラベルの同じ数の頂点を含むグループがもう一方のグラフに存在する必要があります。そうでない場合、グラフは同形ではありません。

メイン アルゴリズムの反復ごとに、次のステップで使用する頂点グループの 2 つのグラフのそれぞれに新しいデータ構造を生成する必要があります。グループごとに、問題の頂点に隣接する頂点に対応するグループ インデックス/ID の各頂点のリストを生成します (このリストには重複するグループを含めます)。各グループをチェックして、含まれている各頂点のソートされたグループ インデックス/ID リストが同じかどうかを確認します。この場合、次のステップのグループ構造にこのグループの未変更のコピーを作成します。そうでない場合は、そのグループ内のグループ インデックス/ID の一意のリストごとに、そのリストを生成した元のグループ内の頂点の新しいグループを作成し、この新しいグループを次のステップのグループ構造に追加します。特定の反復でどちらのグラフのグループも細分化しない場合は、このアルゴリズムの主要部分の実行を停止します。少なくとも 1 つのグループを細分化する場合は、2 つのグラフのグループ構造が互いに対応していることをもう一度確認する必要があります。このチェックは、アルゴリズムの初期化の最後に実行されるものと似ています (両方に同じ関数を使用することもできます)。このチェックが失敗した場合、グラフは同型ではありません。チェックに合格した場合、現在のグループ構造を破棄/解放し、新たに作成されたもので次の反復を開始します。このチェックは、アルゴリズムの初期化の最後に実行されるものと似ています (両方に同じ関数を使用することもできます)。このチェックが失敗した場合、グラフは同型ではありません。チェックに合格した場合、現在のグループ構造を破棄/解放し、新たに作成されたもので次の反復を開始します。このチェックは、アルゴリズムの初期化の最後に実行されるものと似ています (両方に同じ関数を使用することもできます)。このチェックが失敗した場合、グラフは同型ではありません。チェックに合格した場合、現在のグループ構造を破棄/解放し、新たに作成されたもので次の反復を開始します。

「対応するグループ」を決定するプロセスを簡単にするために、構造にグループを追加するための予測可能なスキームを使用することを強くお勧めします。たとえば、初期化中に (次数、ラベル) 順でグループを追加し、グループをインデックスの昇順で細分化し、細分化したグループをグループ インデックス リストの順序に基づいて新しい構造に追加する場合 (つまり、最初にリストされたインデックス、次に 2 番目など)、2 つのグループ構造間で対応するグループは常に同じインデックスを持つため、どのグループが互いに対応しているかを追跡するプロセスがはるかに簡単になります。

アルゴリズムが完了したときにすべてのグループに 3 つ以下の頂点が含まれている場合、グラフは同型です (2 つまたは 3 つの頂点を含む対応するグループの場合、任意の頂点のペアリングが有効です)。そうでない場合 (これは、すべてのノードの次数とラベルが等しいグラフで常に発生し、そのプロパティを持つサブグラフで発生することもあります)、グラフはまだ同型または非同型であると判断されていません。2 つのケースを区別するには、最初のグラフの最大グループの任意のノードを選択し、それを独自のグループに分けます。次に、他のグラフの最大グループの各ノードについて、そのノードを独自のグループに分けてアルゴリズムを再度実行してみてください。本質的に、最初のグラフからペアになっていないノードを選択し、推測とチェックによって、まだもっともらしいペアリングである 2 番目のグラフのすべてのノードにペアリングしています。フォークされた反復のいずれかが同型を返す場合、グラフは同型です。どれもそうでない場合、グラフは同形ではありません。

一般的なケースでは、このアルゴリズムは多項式です。まれなケースでは、アルゴリズムが指数関数的である可能性があります。これが当てはまるかどうかは、グラフ入力とノード選択の両方の最悪のケースでアルゴリズムが強制的にフォークされる頻度に関連しています。たとえば、アルゴリズムは 2 つの完全なグラフを比較するときにすべてのステップでフォークしますが、そのツリーのすべての枝は同型を生成します。したがって、この場合、アルゴリズムは多項式時間で戻りますが、実行ツリーの 1 つのブランチのみをトラバースするには多項式時間がかかるため、実行ツリー全体をトラバースするには指数時間が必要になります。

いずれにせよ、このアルゴリズムは目的に応じてうまく機能するはずです。私の説明が分かりやすかったことを願っています。そうでない場合は、単純なケースを処理するアルゴリズムの例を提供するか、代わりに疑似コードとして表現してみてください。

于 2013-06-16T20:39:31.233 に答える
1

何年も前に、私はまさにこの問題 (ラベル付きグラフ同形) のためのシンプルで柔軟なアルゴリズムを作成しました。

私はそれを「Powerhash」と名付けました。このアルゴリズムを作成するには、2 つの洞察が必要でした。1 つ目は、PageRank でも使用されるベキ反復グラフ アルゴリズムです。2 つ目は、ベキ反復の内側のステップ関数を必要なものに置き換える機能です。これを、反復ごと、およびノー​​ドごとに次のことを行う関数に置き換えました。

  • ノードの隣接ノードの (前の反復からの) ハッシュを並べ替えます
  • 連結されたソート済みハッシュをハッシュする
  • ノードのハッシュを新しく計算されたハッシュに置き換える

最初のステップでは、ノードのハッシュは直接隣接するノードの影響を受けます。2 番目のステップでは、ノードのハッシュは、そこから 2 ホップ離れた近隣の影響を受けます。N 番目のステップでは、ノードのハッシュはその周囲の近隣の N ホップの影響を受けます。したがって、Powerhash を N = graph_radius ステップだけ実行し続ける必要があります。最終的に、グラフ センター ノードのハッシュはグラフ全体の影響を受けます。

最終的なハッシュを生成するには、最終ステップのノード ハッシュを並べ替えて、それらを連結します。その後、最終的なハッシュを比較して、2 つのグラフが同形かどうかを確認できます。ラベルがある場合は、ノードごとに計算する内部ハッシュにラベルを (最初の反復で) 追加します。

詳細については、こちらの私の投稿をご覧ください。

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

上記のアルゴリズムは、「madIS」機能リレーショナル データベース内に実装されました。アルゴリズムのソース コードは次の場所にあります。

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

于 2017-03-19T15:04:43.520 に答える
-1

チェックしてるだけ; 厳密なグラフ同形性または何か他のことを意味しますか? 同型グラフは同じ隣接関係を持ちます (つまり、あるグラフでノード A がノード B に隣接している場合、ノード g(A) は、変換 g を最初のグラフに適用した結果である別のグラフでノード g(B) に隣接しています)。 ...) あるグラフが別のグラフと同じタイプとノード数を持っていることを確認したい場合は、カウントを比較するだけです。

于 2013-04-20T17:12:59.160 に答える