Алгоритм VF2 шаги с примером - PullRequest
Новая
       68

Алгоритм VF2 шаги с примером

9 голосов
/ 18 ноября 2011

Может кто-нибудь объяснить шаги алгоритма VF2 для изоморфизма графов простыми словами? Я изучаю этот алгоритм, но он груб без рабочего примера. Может ли кто-нибудь привести меня в правильном направлении? Спасибо.

Ответы [ 2 ]

15 голосов
/ 18 ноября 2011

Я постараюсь дать вам быстрое объяснение моего предыдущего ответа на этот вопрос:

Какой-нибудь рабочий пример алгоритма VF2?

Я буду использовать то же самоеПример как тот, что в моем предыдущем ответе:

enter image description here

2 приведенных выше графика - это V и V '(V' не на чертеже, но это справа)

Алгоритм VF2 описан на графике.

Шаг за шагом

Я хочу знать, изоморфны ли V и V '.

Я буду использовать следующие обозначения: XV - это узел X в V

В алгоритме VF2 я попытаюсь сопоставить каждый узел в V с узлом в V '.

шаг 1:

Я сопоставляю пустой V с пустым V ': он всегда работает

шаг 2: Я могусопоставить 1 В с 1 В ', 2 В' или 3 В '

Я сопоставлю 1 В с 1 В': оно всегда работает

шаг 3:

Я могусопоставить 2V с 2V 'или 3V'

Я сопоставлю 2V с 2V ': это работает, потому что {1V 2V} и {1V' 2V} изоморфны

шаг 4:

Я пытаюсь сопоставить 3V с узлом в V ': я не могу!{было бы возможно, если бы было ребро между узлами 3 и 2 в V ', и не было ребра между 3 и 1)

Поэтому я возвращаюсь к шагу 2

step5:

Я сопоставляю 2 В с 3 В '

шаг 6:

так же, как шаг 4

Я идувернуться к шагу 2. решения на шаге 2 нет, я возвращаюсь к шагу 1

, шаг 7:

Я сопоставляю 1 В с 2 В '

шаг 8:

Я сопоставляю 2 В с 1 В '

Шаг 9:

Я сопоставляю 3 В с 3 В'

это работает, я сопоставил {1V 2V 3V} с {2V '1V' 3V '}

Графики изоморфны.

Если я проверю все решение, и оно никогда не будетработает, граф не будет изоморфным.

Надеюсь, что это поможет

По поводу вашего вопроса "соответствия", посмотрите статью в Википедии об изоморфизме графа:

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

это хороший пример функции f, которая соответствует графу G и H: enter image description here

Надеюсь, выможно лучше понять этот алгоритм с помощью этой иллюстрации.

0 голосов
/ 10 января 2017

представлен общий обзор алгоритма VF: 

PROCEDURE Match(s)
    INPUT: an intermediate state s; the initial state s0 has M(s0)=
    OUTPUT: the mappings between the two graphs
    IF M(s) covers all the nodes of G2 THEN
        OUTPUT M(s)
    ELSE
        Compute the set P(s) of the pairs candidate for inclusion in M(s)
        FOREACH (n, m) P(s)
            IF F(s, n, m) THEN
                Compute the state s´ obtained by adding (n, m) to M(s)
                CALL Match(s )
            END IF
        END FOREACH
         Restore data structures
    END IF
END PROCEDURE
...