12

誰かがグラフ同型のためのVF2アルゴリズムのステップを簡単な言葉で説明できますか？私はこのアルゴリズムを学んでいますが、実際の例がないと厳しいです。誰かが私を正しい方向に導くことができますか？ありがとうございました。

4

2 に答える 2

20

この質問に対する以前の回答を簡単に説明します。

VF2アルゴリズムの実例はありますか?

前の回答と同じ例を使用します。

ここに画像の説明を入力

上の 2 つのグラフは V と V' です (V' は図にはありませんが、右側のグラフです)。

VF2 アルゴリズムは、グラフで説明されています。

一歩一歩

V と V' が同形かどうか知りたいです。

次の表記法を使用します。 XV は V のノード X です。

VF2 アルゴリズムでは、V の各ノードを V' のノードと一致させようとします。

ステップ1 ：

空の V と空の V' を一致させます: 常に機能します

ステップ 2 : 1V を 1V'、2V'、または 3V' と一致させることができます

1V と 1V を一致させます ': 常に機能します

ステップ 3 :

2V を 2V' または 3V' と一致させることができます

2V と 2V' を一致させます: {1V 2V} と {1V' 2V} は同型なので動作します

ステップ 4 :

3V を V' のノードと一致させようとしました: できません! {V' のノード 3 と 2 の間にエッジがあり、3 と 1 の間にエッジがない場合は可能です)

だから私はステップ2に戻ります

ステップ 5:

2Vを3Vに合わせる」

ステップ 6:

ステップ4と同じ

ステップ 2 に戻ります。ステップ 2 には解決策がありません。ステップ 1 に戻ります。

ステップ 7:

1V と 2V を一致させます。

ステップ 8:

1Vに2Vを合わせる」

ステップ 9 :

3V'に3Vを合わせる

{1V 2V 3V} と { 2V' 1V' 3V'} を一致させました

グラフは同形です。

すべてのソリューションをテストしてもうまくいかない場合、グラフは同型ではありません。

お役に立てれば

「マッチング」に関するあなたの質問については、ウィキペディアのグラフ同型写像に関する記事をご覧ください。

http://en.wikipedia.org/wiki/Graph_isomorphism

これはグラフ G と H に一致する関数 f の良い例です: ここに画像の説明を入力

この図でこのアルゴリズムをよりよく理解していただければ幸いです。

于 2011-11-18T16:35:47.817 に答える
1

VF アルゴリズムの概要を以下に示します。

手順 マッチ
    INPUT: 中間状態 s; 初期状態 s0 は M(s0)=
    OUTPUT: 2 つのグラフ間のマッピング
    IF M(s) は G2 のすべてのノードをカバーします THEN
        出力 M(s)
    そうしないと
        M(s) に含めるペア候補のセット P(s) を計算します。
        FOREACH (n, m) P(s)
            IF F(s, n, m) THEN
                (n, m) を M(s) に加算して得られる状態 s' を計算します。
                CALL マッチ
            END IF
        END FOREACH
         データ構造を復元する
    END IF
終了手順
于 2017-01-10T20:01:35.370 に答える