Изоморфизм графов

Ответ 1

Это чертовски сложная проблема.

В общем, основная идея состоит в том, чтобы упростить граф в каноническую форму, а затем выполнить сравнение канонических форм. С этой целью генерируются связующие деревья, но связующие деревья не уникальны, поэтому вам нужно создать канонический способ их создания.

После того, как у вас есть канонические формы, вы можете выполнить сравнение изоморфизма (относительно) легко, но это только начало, так как неизоморфные графы могут иметь одинаковое остовное дерево. (например, подумайте о охватывающем дереве T и о единственном добавлении к нему ребра для создания T. Эти два графика не изоморфны, но имеют одинаковое остовное дерево).

Другие методы включают в себя сравнение дескрипторов (например, количество узлов, количество ребер), которые в целом могут генерировать ложные положительные значения.

Я предлагаю вам начать со страницы wiki о проблеме изоморфизма графа. У меня также есть книга, чтобы предложить: "Теория графов и ее приложения" . Это тома, но стоит каждой страницы.

Как и из вашего следствия, любое возможное пространственное распределение заданных вершин графа является изоморфным. Таким образом, два изоморфных графа имеют одинаковую топологию и, в конце концов, один и тот же граф, с топологической точки зрения. Другое дело, например, найти эти изоморфные структуры, обладающие определенными свойствами (например, с не пересекающимися ребрами, если существует), и это зависит от свойств, которые вы хотите.

Ответ 2

Одним из лучших алгоритмов для нахождения изоморфизмов графа является VF2.

Я написал высокоуровневый обзор VF2 применительно к химии - там, где он широко используется. Сообщение касается различий между VF2 и Ullmann. Существует также с нуля реализация VF2, написанная на Java, которая может быть полезна.

Ответ 3

Очень похожая проблема - автоморфизм графа - может быть решена с помощью saucy, который доступен в исходном коде. Это находит все симметрии графика. Если у вас есть два графика, соедините их в один, и любой изоморфизм можно обнаружить как автоморфизм объединения.

Отказ от ответственности: я один из соавторов дерзкого.

Ответ 4

Есть алгоритмы для этого - однако у меня еще не было причин серьезно их расследовать. Я считаю, что Дональд Кнут написал или написал на эту тему в своей серии "Искусство вычислить" во время своего второго прохода в (ре), написав их.

Что касается простого способа сделать что-то, что может на практике работать на небольших графах, я бы рекомендовал подсчитать градусы, то для каждой вершины также обратите внимание на набор степеней для смежных вершин. Тогда это даст вам набор потенциальных изоморфизмов вершин для каждой точки. Затем попробуйте все это (с помощью грубой силы, но выбрав вершины в порядке возрастания потенциальных множеств изоморфизма вершин) из этого ограниченного множества. Интуитивно, большинство геометрических изоморфизм можно практически вычислить таким образом, хотя, очевидно, будут вырожденные случаи, которые могут занять много времени.

Ответ 5

Мой проект - Griso - на sf.net: http://sourceforge.net/projects/griso/ с этим описанием:
Griso - утилита для тестирования изоморфизма графа, написанная на С++. Он основан на моем собственном алгоритме ПОЛИНОМИАЛЬНО-ВРЕМЯ (в этом пункте - соль проекта). См. Ввод/вывод образца Griso на странице http://funkybee.narod.ru/graphs.htm.

Ответ 6

Недавно я наткнулся на следующую статью: http://arxiv.org/abs/0711.2010 В этой статье предлагается "Алгоритм полиномиального времени для изоморфизма графа"

Ответ 7

• nauty и Traces

nauty и Traces - это программы для вычисления групп автоморфизмов графов и орграфов [*]. Они также могут создавать канонические этикетки. Они написаны в переносном подмножестве C и работают на значительном числе различных систем.

• Команда AutGroupGraph в пакет GRAPE GAP.
• bliss: еще одна программа симметрии и канонической маркировки.
• conauto: пакет смиморфизма графа.

Ответ 8

Что касается эвристики: я фантазировал о модифицированном алгоритме Ульмана, в котором вы не только используете первый поиск по ширине, но и смешиваете его с глубиной первого поиска таким образом, что сначала вы интенсивно используете интенсивный поиск по ширине, чем вы устанавливаете предел для анализа широты и углубляться после проверки нескольких соседей, и вы уменьшаете каждый шаг на определенную сумму. Это практически то, как я нахожу свой путь на карте: сначала найдите себя с первым поиском по ширине, затем найдите маршрут с глубиной первого поиска - в основном, и это лучшая эволюция моего мозга, когда-либо изобретенная.:) В долгосрочной перспективе некоторый интеллект может быть добавлен для увеличения ширины первого соседнего счетчика поиска в критических вершинах - например, если имеется большое количество соседних вершин с одинаковым количеством граней. Как и проверка фактического маршрута иногда с автомобилем (без GPS).

Ответ 9

Я выяснил, что алгоритм принадлежит к категории k-мерных алгоритмов Вайсфейлера-Лемана, и он терпит неудачу с регулярными графами. Подробнее здесь:

http://dabacon.org/pontiff/?p=4148

Исходное сообщение следует:

Я работал над проблемой, чтобы найти изоморфные графики в базе данных графиков (содержащих химические составы).

Вкратце, алгоритм создает хэш графика, используя метод итерации мощности. Могут быть ложноположительные хэш-столкновения, но вероятность этого чрезвычайно мала (у меня не было таких столкновений с десятками тысяч графиков).

Как работает алгоритм:

Пусть N (где N - радиус графика) итераций. На каждой итерации и для каждого node:

• Сортировка хэшей (с предыдущего шага) соседей node
• Хеширование конкатенированных сортированных хэшей
• Заменить хэш node с вновь вычисленным хешем

На первом шаге на хеш node влияют прямые его соседи. На втором этапе хеш node зависит от окрестности 2-х прыжков от него. На N-м шаге на хеш node будет влиять окрестность N-хэпов вокруг него. Поэтому вам нужно продолжить выполнение шагов Powerhash для N = graph_radius. В итоге на весь граф будет влиять хеш графа node.

Чтобы создать окончательный хеш, соберите последний шаг node хэшей и объедините их вместе. После этого вы можете сравнить финальные хэши, чтобы найти, являются ли два графика изоморфными. Если у вас есть метки, добавьте их (на первом шаге) во внутренние хэши, которые вы вычисляете для каждого node.

Здесь больше фона:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

Здесь вы можете найти исходный код:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py