問題タブ [isomorphism]

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

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

VF2 アルゴリズムの実装に問題があります。多くの場合、すべてが完全に機能しているように見えますが、解決できない問題があります。

以下の例では、アルゴリズムは機能しません。この例では、2 つの同一のグラフを比較しています (下の画像を参照)。開始頂点は 0 です。s0 内で計算されるセット P は、頂点のすべてのペアのパワーセットを格納します。

以下は、実装のベースとなった VF2 に関する出版物に含まれている疑似コードです。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B51AD0DAEDF60D6C8AB589A39A570257?doi=10.1.1.101.5342&rep=rep1&type=pdf

http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20%28sub%29Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs. pdf

/* の右側のコメントは、コードの理解方法を説明しています。

以下で説明するように、 P() セットの作成が有効かどうかはわかりません。ペアのべき集合は、ペアの最初の値、次に 2 番目の値によって、辞書式順序で反復されます。

アルゴリズムが s4 に進むと、関数から戻るときに、適切な頂点の一致に関する情報が失われます。グラフが同型であっても、サブグラフ同型 ({(0,0),(1,1),(2,2),(5,3),(6,4)}) を検索することになります。

ここで何が間違っていますか？

私はこれをインターネット上で2、3日連続で検索してきましたが、今のところうまくいきません.

サブグラフ同型のライブラリと実装が世の中にたくさんあることは知っていますが、それらはすべて重み付けされていないグラフで機能します。たとえば、最も普及している 2 つのアルゴリズムは、VF2 と Uleman のアルゴリズムです。ここで、私の質問は次のとおりです。グラフ (G) とクエリ グラフ (g) が与えられた場合、g が G のサブグラフ (および同形) であるかどうかを確認できるメソッドはありますか? (以下はグラフのエッジ リスト表現であることに注意してください。)

この場合、g は部分グラフであり、G と同型ですが、次のようなものがあるとします。

g はもはや G のサブグラフではなく、同型ではありません。

UPDATE : どちらのグラフも無向です。

私は、文字列の配列で同形のペアの数を返すことを含む、この Java の問題に固執しています。私が書いたコードは、間違った数の同型語ペアを返し続けます。

同形語の定義は次のとおりです。1 つの単語の文字を再マッピングして 2 番目の単語を取得できる場合、2 つの単語は同形語と呼ばれます。文字の再マッピングとは、出現するすべての文字を別の文字に置き換えることを意味します。文字の順序は変更されません。2 つの文字が同じ文字にマップされることはありませんが、文字がそれ自体にマップされる場合があります。たとえば、「abca」と「zbxz」という単語は、「a」を「z」に、「b」を「b」に、「c」を「x」にマッピングできるため、同形です。関数で呼び出す getMap メソッドは含まれていません。getMap メソッドは任意の文字列を入力として受け取り、キーが文字列内の文字であり、対応する値が文字列内の文字の出現回数であるマップを返します。

このコードについてフィードバックをいただければ幸いです。

ありがとう、ジュナイド

Chuusai のこのブログ投稿を読むと、次のように書かれています。

2 つの型とそれらの値の間に同型性があるため、[Int, String] はユニオン型 Int ∨ String をモデル化できます。

「2 つの型とその値の間に同形性がある」とはどういう意味ですか?

Subgraph Isomorphism (SI) 問題は、2 つのグラフ G と H が入力として与えられる計算タスクであり、G に H と同型のサブグラフが含まれているかどうかを判断する必要があります。

これはNP 完全問題です。

SAT問題との関係を知りたいです。特に、この問題のインスタンスを SAT ソルバー ( miniSAT
など) 全体で解決できるようにしたいと考えています。SI から SAT 問題へのマッピングを多項式時間で実行できるアルゴリズムが必要であり、SAT 割り当てを使用してノードからマッピングを見つけることができます。 G から H のノードへ。

何か案が ？？？

これはよく研究された問題でなければなりませんが、私はそれを研究するのに苦労しています。

ここから始めましたが、研究して実装するアルゴリズムを探しています。 http://en.wikipedia.org/wiki/Graph_isomorphism_problem

たとえば、これらの DAG (Directe Acyclic Graphs) が 2 つある場合、そのうちの 1 つをマークまたは削除する必要があります。これは、最初の DAG の回転/反射にすぎないためです。同じ自己同形グループに属しているということは、それらを回転/反射して、まったく同じ隣接行列を持つことができるということですか?