1

2 つのグラフを指定して、共通のサブグラフを取得しようとしています。2 つのグラフ G1=(v1,e1) と G2=(v2,e2) がある場合、G1 の別の共通部分グラフなどの共通部分グラフ G=(V,E) を見つける必要があり、G2 にはそれ以上含まれてはなりませんEアリスの枢機卿。

グラフ 1 が

A - B

交流

B - D

ニ - エ

グラフ2は

A - B

あ～え

B - D

アルゴリズムが返すよりも

A - B

B - D

どのステップに参加するかを教えてくれるアルゴリズムを教えてもらえますか? ありがとう！

4

1 に答える 1

3

問題を正式に説明しているわけではありませんが、例1から、 edgeの最大の共通サブセットを探しているようです。

それを達成するには、単にE1 と E2の交点が必要です。

証拠：

(->)が にあると仮定(a,b)しE1 [intersection] E2ます。集合交差の定義により、これは E1 と E2 の両方に共通であり、したがって G1 と G2 にも共通です。

(<-)は(a,b)G1 と G2 に共通であると仮定 します。(a,b)E1(a,b)E2(a,b)E1 [intersection] E2

(1)(A,C)は「一般的」ではなく(A,B)、サブグラフ内にあるため、これは、目的のサブグラフを作成できる頂点のサブセットを見つけることの制限ではないことを意味します (A結果から除外する必要があるため)。

于 2012-12-10T18:01:37.790 に答える