私はこれをインターネット上で2、3日連続で検索してきましたが、今のところうまくいきません.
サブグラフ同型のライブラリと実装が世の中にたくさんあることは知っていますが、それらはすべて重み付けされていないグラフで機能します。たとえば、最も普及している 2 つのアルゴリズムは、VF2 と Uleman のアルゴリズムです。ここで、私の質問は次のとおりです。グラフ (G) とクエリ グラフ (g) が与えられた場合、g が G のサブグラフ (および同形) であるかどうかを確認できるメソッドはありますか? (以下はグラフのエッジ リスト表現であることに注意してください。)
G
1 2 c
1 3 d
1 4 c
2 3 a
...
g
1 3 d
2 3 a
この場合、g は部分グラフであり、G と同型ですが、次のようなものがあるとします。
g
1 3 t
2 3 a
g はもはや G のサブグラフではなく、同型ではありません。
UPDATE : どちらのグラフも無向です。
g={(1 2 a)} は G と同形ではありません。これは、G におけるこのエッジの重みが「a」ではなく「c」であるためです。
これは奇妙です。簡単に言えば、{G<->G'} からの何らかの関数 f が存在する場合、グラフ G、G' (実際には、任意の代数構造) は同型であり、任意の関係 R(g1, g2) (G の g1, g2) に対して, R'(f(g1), f(g2)) は G' にも当てはまり、その逆も成り立ちます。したがって、頂点の名前変更 (順列) によって G から得られるグラフ G' は、G と同形です。
お分かりのように、g の任意のマークされたエッジに対して、同じ頂点を接続し、G で同じマークを持つエッジが存在するかどうかを調べることに関心があるようです。これを行う最も簡単な方法は、G のエッジを複製し、それらをコンポーネントで並べ替えることです。次に、クエリ g の各エッジについて、G に同じエッジがあるかどうか (および同じマークがあるかどうか) を確認するには、O(log(|G|)) が必要です。したがって、合計時間は、グラフ G を準備するのに O(|G|*log(|G|))、後続の各クエリを処理するのに O(|g|*log(|G|)) です。
Upd: 「コンポーネントごとに G のエッジを並べ替える」とは、次のことを意味していました:最初の頂点で並べ替えられ、次に 2 番目の頂点で並べ替えられた、エッジの配列 (またはバイナリ ツリー) を構築します。エッジを簡単に検索するには、エッジを複製する必要があります。たとえば、エッジ (1, 2, c) は (1, 2, c) および (2, 1, c) として存在する必要があります。したがって、配列形式では、上記の例の G は次のようになります。
(1, 2, c)
(1, 3, d)
(1, 4, c)
(2, 1, c)
(2, 3, a)
(3, 1, d)
(3, 2, a)
(4, 1, c)
後から考えると、G と g の両方のエッジを、最初に番号の小さい頂点で記述する方がよい場合があります。この方法では、重複は必要ありません。