Я новичок в изучении теории графов. Сейчас я изучаю изоморфизм (под) графа. есть два важных алгоритма: алгоритм Ульмана и vf2.
Я прочитал статью Ульмана: Алгоритм изоморфизма подграфов. Я также гуглил его, и гугл дал мне много приложений, но я не могу понять процедуры алгоритма.
Не могли бы вы дать мне простое объяснение?
Этот ответ на связанный вопрос дает исходный код алгоритма Ульмана.
Эти слайды дают пример, но основной ингредиент алгоритма упоминается только без примера на слайде «Алгоритм Ульмана V2».
Поэтому я приведу пример ниже. Мы хотим знать, есть ли в GB подграф, изоморфный GA. То есть мы будем пытаться сопоставить вершины GA с вершинами GB, чтобы ребра GA отображались на ребрах GB.
Обратите внимание, что и в оригинальной статье, и в слайдах используется матрица с именем M, а в коде — нет. Это потому, что матрица представляет то же самое, что и Possible_assignments[i] в коде. M[i][j] ровно равно 1, если i-я вершина может быть отображена на j-ю вершину GB. Я буду использовать кандидатов (u) и т. д. для набора вершин GB, где вершина u GB может быть отображена.
Первое наблюдение состоит в том, что вершина GA может быть отображена только в вершину GB по крайней мере такой же степени. Таким образом, изначально кандидаты (u) = кандидаты (v) = {a, b, e, f, g}, кандидаты (w) = {f} и кандидаты z — все вершины GB.
Теперь мы впервые выполняем процедуру «уточнения М», которая является основным компонентом алгоритма Ульмана. То есть мы проверяем, что всякий раз, когда вершина x из GB входит в число кандидатов на вершину y из GA, каждый сосед y имеет хотя бы одного кандидата среди соседей x. Если эта проверка не удалась, то мы удаляем x из кандидатов y. Мы проверяем эти удаления до тех пор, пока дальнейшие удаления не станут возможны.
Например, h входит в число кандидатов на z. Однако w является соседом z, но ни один из соседей h (то есть g) не входит в число cadidates(w)={f}. Следовательно, мы никогда не сможем сопоставить z с h, потому что ребро {w,z} будет отображено на неребро. Таким образом, мы можем безопасно удалить h из кандидатов (z). Результат уточнения: кандидаты (u) = кандидаты (v) = кандидаты (z) = {a, e, g} и кандидаты (w) = {f}.
Теперь начинаем отступать.
Сначала мы пытаемся сопоставить u с a. То есть мы устанавливаем кандидатов(и) = {а} и удаляем из других наборов кандидатов. Refine обнаруживает, что ни e, ни g не являются соседями a, поэтому мы удаляем e и g из кандидатов (v). Кандидаты(v) остаются пустыми, поэтому мы возвращаемся из этой ветки; отменить изменения, внесенные в кандидатов.
Теперь попробуем сопоставить u с e. Опять же, кандидаты (v) окажутся пустыми.
Наконец, мы пытаемся сопоставить u с g с тем же результатом.
Делаем вывод, что GA не является подграфом GB. Без необходимости пробовать все задания 8*7*6*5.
Я забыл, что Ульман изначально упорядочивает вершины GA в порядке убывания степени. Но это не будет иметь большого значения — мы только сначала обнаружим, что w может быть отображено только в f, а затем мы продолжим ветвление на u с точно такими же результатами, которые мы получили.
