Раздел 2 Задача установления изоморфизма
2.1 Алгоритм установления изоморфности
Графовые структуры широко применяются для представления отношений объектов и
концепций. При графовом представлении вершины графа обычно представляют
объекты, в то время как ребра представляют отношения между этими объектами. К
примеру, в компьютерных сетях вершины графов могут соответствовать узлам
вычислительной среды, а ребра - сетевым соединениям [37]. Некоторые
инвариантные свойства графов и удобство описания моделей типа объекты-отношения
привели к широкому использованию графов в различных областях науки и
технических приложениях, таких как системы распознавания образов, систмемы
моделирования, прогнозирования и планирования, сравнения молекулярных структур,
тестирование интегральных схем, оптимизация микроконтроллеров, анализ китайской
письменности, планирование движений роботов, семантическом сетевом поиске и
распознавании многогранных объектов [38].
Проверка на изоморфность двух графов играет в алгебре графов примерно такую же
роль, как проверка отношения равенства в математике. Задачу установления
изоморфной эквивалентности двух графов принято относить к разряду NP-трудных
[39], хотя строгого доказательства этого нет. Далее приводится описание
алгоритмов определения изоморфизма и граф-подграф изоморфизма двух графов,
которые по сложности вычислений максимально приближены к полиномиальным.
2.1.1 Обзор современных алгоритмов решения задач изоморфизма на графах.
На сегодняшний день предложен широкий спектр алгоритмов решения задачи проверки
изоморфизма и граф-подграф изоморфизма [40-44]. Стандартом де-факто в
практических приложениях является алгоритм, предложенный Улманом [45], который
основан на процедуре поиска с возвратом на базе эффективной функции
«заглядывания вперед», уменьшающей пространство поиска. Этот алгоритм пригоден
для двух видов морфизмов (изоморфизма и граф-подграф изоморфизма), и является
одним из наиболее широко применяемых алгоритмов для точного сравнения графов
[40].
Одними из последних и наиболее эффективных алгоритмов, разработанных для задач
изоморфизма и граф-подграф изоморфизма, являются алгоритмы VF и VF2 [46,47],
разработанные Паскалем Фогия. Это точные алгоритмы, основанные, как и алгоритм
Улмана, на поиске в пространстве состояний, но в качестве ограничивающего
условия используется количество входящих и исходящих дуг, инцидентных уже
совмещенным вершинам графов. Этот алгоритм входит в состав библиотеки для
работы с графами LEDA [48,49]. Алгоритм VF2 отличается от предшественника, в
основном, измененными структурами для хранения данных и промежуточных
результатов. В обоих алгоритмах используется функция ограничения глубины поиска
на основе совпадения суммарного числа инцидентных ребер уже совмещенной части
вершин обоих графов. По результатам исследований [50] это один из самых быстрых
алгоритмов проверки на изоморфность среди современных переборных алгоритмов.
Алгоритм SD (Шмидта-Дрюфеля) – назван в данной работе по именам авторов [51].
Это достаточно известный и хорошо зарекомендовавший себя алгоритм переборного
характера. Основу его составляет функция ограничения глубины поиска на базе
матрицы расстояний между вершинами. К недостаткам данного алгоритма следует
отнести то, что его функция ограничения глубины поиска практически не работает
на сильнорегулярных графах.
Одним из наиболее эффективных алгоритмов отечественных авторов является
алгоритм В.П. Пинчука, основанный на ПНВ-методе (методе последовательного
наложения с возвратом) [52,53]. Функция ограничения глубины поиска строится
только на проверке совпадения ребер между уже наложенными вершинами графов.
Отсутствует функция заглядывания вперед (look ahead). Для ускорения работы
алгоритма в случаях, когда графы изоморфны, применяется ряд предварительных
преобразований, преследующих целью сортировку вершин в порядке, наиболее
предпочтительном для совмещения. Не смотря на свою простоту, алгоритм позволил
произвести расчет полного набора неизоморфных графов до 11 вершин
включительно.
Постановка задачи установления изоморфности графов. Пусть даны графы и . Граф
изоморфен графу (обозначается, как ), если существует подстановка , такая, что
для каждой пары вершин , если и только если .
2.1.2 Алгоритм установления изоморфности
Разработанный алгоритм основан на идее поиска с возвратом. Наиболее
распространенным методом ускорения работы алгоритмов, основанных на поиске с
возвратом, является метод ветвей и границ, суть которого сводится к тому, что
после просмотра каждого узла анализируется перспективность дальнейшего анализа
текущей ветви дерева возможных решений. Если, согласно выбранным критериям,
можно сделать вывод о том, что в данной ветви дерева решение найдено не будет
(или оно будет слабее одного из уже найденных, например, при вычислении степени
изоморфности графов), то данная ветвь решения признается бесперспективной и ее
дальнейший анализ прекращается.
Наиболее важным в методе ветвей и границ является выбор функции анализа
перспективности текущей ветви решения. Поскольку алгоритмы, основанные на этом
методе, как правило, имеют не полиномиальную вычислительную сложность и
основаны на рекурсивной процедуре перебора всех возможных решений, то, чем
раньше (т.е. при наименьшем числе исходных данных) можно будет распознать
бесперспективность текущей ветви решения, тем больше времени удастся
сэкономить. Причем, зависимость последних двух величин тоже нелинейная, т.к.
нелинейно растет время вычислений с ростом размерности исходных данных.
При разработке функции анализа перспективности текущей ветви
- Київ+380960830922