0

2つの色付き平面グラフが同型であるかどうかを推測するアルゴリズムは何ですか？同型写像は一般的にグラフにとって難しい問題であることを私は知っていますが、ウィキペディアによれば、グラフが平面であるかどうかを解決することは可能です。

このアルゴリズムの適用は、グラフベースのデータ構造で表される2つの平面分子が同じ（同形）であるかどうかを推測することです。ノードは原子を表すため、グラフの色は単に原子のタイプ（水素、炭素、窒素など）です。

4

3 に答える 3

2

あるグラフのノードは、2つのノードの次数が同じである場合にのみ、グラフ同型を介して別のグラフのノードにマップできると主張します。

そのノードを中央に配置し、その周囲の次数を構成するノードを配置し、中央ノードと他のすべてのノードの間にリンクを作成することにより、任意の次数のノードを含む小さな平面グラフを作成できます。これを好きなだけ小さく縮小することで、これを非平面にすることなく、特定の平面グラフの任意のノードにサブグラフとして追加するように調整できます。

色付きのノードを持つ平面グラフが与えられた場合、その中のノードの最大次数を見つけ、これより上の次数の小さなサブグラフを作成して、カラーマーキングとして機能させます。各色に独自の次数を与え、その次数の個別の小さなサブグラフを各ノードにリンクします。その色の。

ここで、この拡張グラフの平面グラフ同型を解くと、元のグラフの解が得られます。同様に、元のグラフのソリューションは、拡張グラフのソリューションに簡単に変換できます。

于 2012-10-11T17:59:21.390 に答える
1

NetworkXライブラリをお試しください

興味のあるプログラミング言語については触れていませんが、Python用のNetworkXライブラリには、同型を見つけるための複数のアプローチがあります。問題の原子要素のマッチングに対処する「セマンティック」評価をサブクラス化して定義する機能を含むVF2アルゴリズムの実装を確認することをお勧めします。セマンティック評価はすでにアルゴリズムに含まれていますが、常にtrueを返すプレースホルダー関数を使用しているため、プレースホルダー関数をアトミック要素を評価する関数に置き換えると、アルゴリズムクラスが変更されずに機能する場合があります。

または、アルゴリズムを実行して形状を一致させてから、GM.mappingパラメーターを確認し（実装リンクを参照）、各同型の同等ノードの要素を比較して、要素が同等かどうかを確認します。

プログラミングライブラリの代わりに一般的なアルゴリズムを探している場合は、このペーパーを試してください（PDFはこちら、ペイウォールなし）：

LP Cordella、P。Foggia、C。Sansone、M。Vento、「大きなグラフを照合するための改善されたアルゴリズム」、パターン認識におけるグラフベースの表現に関する第3回IAPR-TC15ワークショップ、Cuen、pp。149-159、2001

2015年11月の更新：どうやら教授はサブNP時間でこれを行う方法を理解しました！彼はまだ出版していませんが、純粋数学へのそれらのためのスターターリンクがここにあります。

于 2012-10-25T18:19:00.097 に答える
0

この論文（私がciteseerで見つけた）は、アルゴリズム（の概要）と他のアルゴリズムとのおそらく有用なベンチマーク比較の両方を含み、書誌参照も提供するため、有用であるように思われます。しかし、あなたが見ている問題の大きさは、Kukluketal。のプロファイルにはないのではないかと思います。グラフマッパーは他のアルゴリズムに勝ちます。

汎用平面グラフ同型アルゴリズムは、ノードの「色」を利用しようとさえしません（私は通常、エッジに適用される色を考えているので、ラベルと言いますが、それはそれほど重要ではありません）。追加情報を使用して、より良い結果を出します。しかし確かに、無着色/無標識の同型がない場合、有色/無標識の同型はあり得ません。残念ながら、単一の同型を構築できるだけでは、色/ラベルの同型があるかどうかを判断するのに十分ではありません。考えられるすべての同型を試す必要があります。この検索を単純化するのに十分な情報が分解から残っていると思いますが、よくわかりません。それは興味深い問題のようです。

あなたが特定のプログラミングの問題を念頭に置いていることを理解しています。それは解決策の検索にバイアスをかけます（そしてそうすべきです）。したがって、次の点を無視してかまいません。すべてのノードが同じ色/ラベルを持つことが有効であるため、色付き/ラベル付き同型は一般的な同型よりも理論的に簡単ではありません。（これはあなたの環境とはまったく関係がない、と私は思います。あなたのターゲット分子はどれも単一の元素で構成されていないからですよね？）

于 2012-10-11T04:28:36.480 に答える