6.9. Определение изоморфизма графов

Большое число комбшаторно-логических инженерньк задач на графах требует установления изоморфизма или изоморфного вложения между заданными структурами [124, 159, 160]. Данная проблема, как и все остальные рассмотренные выше проблемы, является NP-полной. Поэтому разрабатываются различные эвристики для получения приемлемых практически результатов.

Задача распознавания изоморфизма графов состоит в следующем. Для заданных графов Gi = (Хі,І7і) и (?2 = (^^"2,^2) требуется определить, существует ли взаимно однозначное отображение (р: Хі ^ Х2 такое, что

= {х,у) ^ и тогда и только тогда, когда (99(ж), 99(^)) е U2 [159].

В настоящее время известны полиномиальные алгоритмы для следующих классов графов: графы ограниченной степени; графы с ограниченной кратностью собственных значений; ^-разделимые графы; ^-стягиваемые графы и так далее [188-192].

Особое внимание заслуживают сильнорегулярные графы. Граф G = = (X, /), riJi, Till), |X| = гі, называется гі-вершинным регулярным графом степени р, если в нем любая пара смежных вершин имеет п\^ общих соседей, а любая пара несмежных вершин — riJi. Известно [188], что сильнорегулярные графы образуют класс наиболее трудных задач для распознава-

ния изоморфизма графов. Для сильнорегулярных графов известен алгоритм с временной сложностью 0{logn2).

Существует ряд задач, которые полиномиально сводятся друг к другу и к задаче распознавания изоморфизма графов Gi и G2 [188]:

1.   Распознавание изоморфизма графов и построение порождающего множества для группы автоморфизмов графа, где G = G1UG2.

2.   Распознавание изоморфизма графов и существование изоморфной подстановки (временная сложность алгоритма 0{п2)).

3.   Распознавание изоморфизма графов и число симметрии графа (временная сложность алгоритма 0{п2)).

4.   Распознавание изоморфизма графов и автоморфное разбиение множества вершин графа (временная сложность алгоритма 0{п2)).

5.   Распознавание изоморфизма графов и число изоморфизмов графов (временная сложность алгоритма ^ О(п2)).

6.   Распознавание изоморфизма графов и определение существования автоморфизма для пары фиксированных вершин графа G (временная сложность алгоритма О (п2)).

Известно, что задача изоморфного вложения графа также является NP- полной задачей [161]. Она имеет много сходства и в то же время существенно (по сложности) отличается от задачи распознавания изоморфизма графов. Например, для решения задачи изоморфизма подграфа Gi подграфу (?2 графа G с использованием известных алгоритмов распознавания изоморфизма графов необходимо разработать процедуру выделения в графе G подмножества Хі С X, равномощного с множеством вершин Х2 графа (?2-

Данная процедура включает jfei действий, где jfei = f ^ ^ = |Х|, гі2 =

\n2j

= |Х2|. Следовательно раз надо применять и алгоритм распознавания изоморфизма графов. Поэтому при выделении каждого подграфа G± в графе

G необходимо выполнять ^2 действий, где ^2 = 1 1 — количество

\Tn2J

ребер в подграфе G±, m2 — в графе G2, тпі > m2). Следовательно, даже если есть полиномиальный алгоритм распознавания изоморфизма графов, с его помощью невозможно решить задачу изоморфного вложения за полиномиальное время. Она может быть решена за полиномиальное время, если Gi — лес, а (?2 — дерево.

Наибольшую трудоемкость представляет установление изоморфизма однородных графов, имеющих автоморфные подграфы. Для решения таких задач используются методы разбиения исследуемых графов на различные уровни. При этом временная сложность алгоритма алгоритма снижается с 0(гі!) до 0{к1), где п — число элементов в графе, — число элементов в наибольшем автоморфном подграфе, т. е. в таком подграфе, где не имеет значения выбор вершин для установления соответствия.

Основная идея таких алгоритмов заключается в следующем [ 18]. В графах, исследуемых на изоморфизм, выбираются две предполагаемо изоморфные вершины. Относительно них производится разбиение всех остав-

шихся вершин на два класса. В первый класс включаются вершины, смеж- ные предполагаемо изоморфным, а во второй нет.

Например,нарис.6.70,а,бпоказаныдваграфа(?,(?'.Пусть(? = (X, 17), G' = (vY',17'), |vY| = |vY'| = 6, \U\ = |I7'| = 9, локальные степени всех вершин графа равны трем. Необходимо установить изоморфизм графов G и G'. Другими словами, необходимо определить, существует ли отношение эквивалентности:

Покажем на примере реализацию эвристики разбиения для установления изоморфизма однородных графов. Выберем одну вершину в графе G и одну в графе G'. И относительно них выполним указанное выше разбиение:

Знак (1+) означает, что в данном разбиении вершины Х4, xq смежны вершине , а знак (1 -) означает, что вершины жз, х^ не смежны вершине хі графа G. Аналогичное разбиение выполнено для графа G'. Здесь считается, что вершины хі и х[ предполагаемо изоморфны (П-изоморфны). Далее, выбираются подмножества меньшей мощности и внутри них проверяется смежность вершин. В нашем примере вершины жз, х^ и х'2, х'^ не смежны. Поэтому процесс разбиения продолжается:

Продолжая процесс аналогично, получим, что граф G изоморфен графу G'. Подстановка вершин запишется

В рассматриваемом примере подмножества вершин {ж2, Ж4, xq} и {^4, Ж5, являются автоморфными, т. е. каждая вершина в одном подгра-

фе может быть изоморфна любой вершине второго подграфа. В примере (рис. 6.70) временная сложность алгоритма распознавания изоморфизма графов 0(6!) была сведена к временной сложности алгоритма распознавания изоморфизма графов 0(3!). В алгоритмах такого типа необходим перебор между элементами автоморфных подграфов, причем, как следует из рассмотренного примера, такой перебор здесь выполняется последовательно для всех вершин, кроме последней в подграфе. В этой связи применение новых архитектур генетического поиска с адаптацией, совместные эволюции Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера и локальный поиск позволяют повысить скорость установления изоморфизма графов.

Предлагается в рассматриваемом методе распознавания изоморфизма графов после получения разбиения в подмножествах наибольшей мощности выполнять все модифицированные генетические операторы. Наилучшие результаты дало применение новых модифицированных генетических, операторов, основанных на жадной стратегии, метода дихотомии, минимального кластера, метода золотого сечения и метода Фибоначчи. Это позволяет параллельно анализировать все подмножества автоморфных вершин и повышает время нахождения результата.

Например, на рис. 6.71, а, б показаны нетривиальные, неоднородные графы G и G'.

В этж графах |Х| = |Х'| = 7, \U\ = \U'\ = 8, р± = 1, р2 = 3, рз = 3, Р4 — 3, /?5 — 3, Pq — 2, Pj — 1, Ра — 1, Pf) — 3, Рс — 3, Pel — 3, /)g — 3, Pf = 2, pg = 1. Вершина 1 может быть П-изоморфна вершине g или а. В первом случае нас ждет тупик, а во втором — успех. Мы предположили, что вершина 1 П-изоморфна вершине а. Тогда на основе связности графа и эвристики разбиения следует, что вершина 7 П-изоморфна вершине g. После этого вытекает, что вершина 6 П-изоморфна вершине /. Далее необходимо установить, существует ли соответствие между подмножествами автоморфных вершин {2, 3, 4, 5} и {6, с, d, е}. В этом случае, как отмечалось выше, в общем необходимо выполнить полный перебор между этими подмножествами вершин. Для этих подмножеств это — 4!. Выполняя такие преобразования получим, что вершина 2 П-изоморфна вершине Ь, вершина 3 П-изоморфна вершине d, 4 — с и 5 — е. Отсюда следует, что графы G и G' (рис. 6.71, а, б) изоморфны, а подстановка изоморфизма, переводящая один граф в другой, запишется:

Как видно, наличие вершин с различными локальными степенями упро- щает процесс распознавания изоморфизма графов. Это позволяет выбирать начальные условия для эвристики разбиения. В примере (рис. 6.71, а, б) всего два способа для выбора разбиения, в то время, как в графах (рис. 6.70, а, б) шесть возможных способов разбиения. В однородных графах все степени вершин одинаковы, поэтому начальные условия выбираются произвольно случайным образом. В этой связи при установлении изоморфизма в однородных графах временная сложность алгоритма в самом лучшем случае равна 0(гі), в самом худшем случае — 0(гі!). Если графы неизоморфны, то за одну итерацию установить результат невозможно. Необходимо провести сравнение на изоморфизм одной случайно выбранной вершины из одного графа со всеми остальными вершинами другого графа.

Например, пусть заданы два графа (рис. 6.72, а, б) G и G'. Нри этом G = (Х,1/), G' = (Х',1/'). 1-^1 = = 6, \и\ = \и'\ = 9, локальные степени всех вершин графа равны трем.

Для распознавания изоморфизма графов применим эвристику разбиения. Предположим, что вершина 1 графа G П-изоморфна вершине а графа G'. Тогда получим:

Для дальнейшего анализа выбираем соответствующие подмножества наименьшей мощности {3, 5} и {е, с}. Вершины (3, 5) в графе G (рис. 6.72, а) смежны, а вершины (с, е) в графе G' — нет. Следовательно, вершина 1 не может быть изоморфна вершине а. В этой связи необходимо провести аналогичные операции для проверки изоморфизма вершины 1 с остальными вершинами графа G'. Далее получим:

Вершины (3,5) в графе G (рис. 6.72, а) смежны, а вершины (d, /) в графе G' — нет. Следовательно, вершина I не может быть изоморфна вершине Ь. Продолжая аналогичные построения, имеем, что вершина 1 не может быть изоморфна вершинам с, d, е. Наконец, предположим, что вершина 1 графа G

П-изоморфна вершине / графа G'. Тогда получим:

Вершины (3, 5) в графе G (рис. 6.72, а) смежны, а вершины (6, d) в графе G' — нет. Следовательно, вершина 1 не может быть изоморфна вершине Ь. Проанализированы все вершины графа G' на предмет изоморфизма с вершиной 1 графа G. Во всех случаях ответ отрицательный. Поэтому граф G неизоморфен графу G'.

 

Рассмотрим пример распознавания изоморфизма графов (рис. 6.73, а, 6)GhG'. При этом G = (Х,и), G' = (Х',1/'), 1-^1 =  \U\ =

= 117'I = 15, локальные степени всех вершин графа равны трем. Предположим, что вершина 1 графа G П-изоморфна вершине а графа G'. Тогда получим:

Для дальнейшего анализа выбираем соответствующие подмножества наименьшей мощности {2, 5, 6}и{6, е, /}. Предположим, что вершина 2 П-изоморфна вершине Ь. В этом случае получим:

Как видно, П-изоморфизм сохраняется. Продолжая далее, запишем:

Так как вершины (h, d) в графе G' (рис. 6.73, б) смежны, а вершины (4, 8) в графе G (рис. 6.73, а) — нет, то вершина 1 не может быть изоморфна вершине а, вершина 2 — 6, вершина 7 — g и вершина 3 — с. Продолжая аналогично, получим, что граф G не изоморфен графу G'.

Предлагается подход на основе микро-, макро-, и метаэволюции для нахождения подстановки изоморфизма графов, если она существует. На эта-

пе микроэволюции эвристика разбиения позволяет получить строительные блоки. Перераспределение генетического материала на основе генетических операторов и их модификаций выполняется внутри каждого строительного блока. За счет этого уменьшается размер хромосом в популяции и сокращается время реализации основного алгоритма. Например, в хромосоме рі'. 2, 3, 4, 5, которая является строительным блоком для графа G (рис. 6.71, а), определим точку мутации между 3 и 4 геном. Выполнив ОМ, получим хромосому потомок видар2:2,4,3,5. Она определяет подстановку 2-6, 4-с, З-сі и 5-е.

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

На этапе метаэволюции происходит миграция хромосом из одной популяции в другую и различные модифицированные генетические операторы над популяциями.

Приведем структурную схему генетического поиска для решения переборных комбинаторно логических задач на графах (рис. 6.74) на основе информирующих обратных связей и концепции объединенной эволюции. После реализации ГА на рисунке 6.74 компенсатор при взаимодействии с внешней средой реализует синергетические принципы, а фильтр хромосом поддерживает гомеостаз. При этом лучшие хромосомы отправляются для смешивания популяций и выхода из локальных оптимумов. Редуктор уменьшает размер популяции, устраняя хромосомы со значением ЦФ ниже средней. Блоки сумматор, редуктор и фильтр хромосом позволяют повысить эффективность реализации эволюции и скорость распознавания изоморфизма графов. Следует отметить, что в графах большой размерности с нетривиальными автоморфизмами (К > 100) процесс установления изоморфизма резко усложняется, но использование таких схем поиска на порядок снижает временную сложность алгоритма.

Приведенные структурные схемы управления генетическим поиском позволяют повысить качество решения и уменьшить время поиска. Временная сложность алгоритма такого класса лежит в пределах 0(п2)^0(п?у).