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

Размещено на http://www.allbest.ru/

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

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

Задача распознавания изоморфизма графов (РИГ) состоит в следующем. Для заданных графов G₁ = (X₁, U₁) и G₂ = (X₂, U₂) требуется определить, существует ли взаимно однозначное отображение : X₁ X₂ такое, что ребро u = (x, y) U₁ тогда и только тогда, когда ((x), (y)) U_2.

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

Особое внимание заслуживают сильнорегулярные графы (СГ). Граф G = (X, , n¹₁₁, n⁰₁₁), |X| = n называется n-вершинным регулярным графом степени , если в нем любая пара смежных вершин имеет n¹₁₁ общих соседей, а любая пара несмежных вершин - n⁰₁₁. Известно, что СГ образуют класс наиболее трудных задач для РИГ.

Задача изоморфного вложения графа является NP- полной задачей. Она имеет много сходства и в то же время существенно (по сложности) отличается от РИГ. Например, для решения задачи изоморфизма подграфа G₁ с использованием известных алгоритмов РИГ необходимо разработать процедуру выделения в графе G подмножества X₁ X равномощного с множеством вершин X₂ графа G₂.

Данная процедура включает k₁ действий, где, n = |X|, n₂ = |X₂|. Следовательно k₁ раз надо применять и алгоритм РИГ:

.

Поэтому при выделении каждого подграфа G₁ в графе G необходимо выполнять k₂ действий:

,

где m₁ - количество ребер в подграфе G₁, m₂ - в графе G₂, m₁ > m₂.

Следовательно, даже если есть полиномиальный алгоритм РИГ, с его помощью невозможно решить задачу изоморфного вложения за полиномиальное время. Она может быть решена за полиномиальное время, если G₁ - лес, а G₂ - дерево.

Наибольшую трудоемкость представляет установление изоморфизма однородных графов, имеющих автоморфные подграфы. Для решения таких задач используются методы разбиения исследуемых графов на различные уровни. При этом ВСА алгоритма снижается с О(n!) до О(k!), где n - число элементов в графе, а k - число элементов в наибольшем автоморфном подграфе, т.е. в таком подграфе, где не имеет значения выбор вершин для установления соответствия.

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

Необходимо установить изоморфизм графов G и G'. Другими словами, необходимо определить, существует ли отношение эквивалентности Х Х', U U' такое, что, если ребро (x_i, x_j) ребру (x_i', x_j'), тогда x_i x_i', x_j x_j', x_i, x_j, X, x_i', x_j', X'.

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

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

{х₁} {х₂, х₄, х₆}₁₊ {х₃, х₅}_1- (G),

{х₁'} {х₄', х₅', х₆'}_1'+ {х₂', х₃'}_1'- (G').

В данном разбиении вершины х₂, х₄, х₆ смежны вершине х₁, а вершины х₃, х₅ не смежны вершине х₁ графа G. Аналогичное разбиение выполнено для графа G'. Здесь считается, что вершины х₁ и х₁' предполагаемо изоморфны (П - изоморфны). Далее, выбираются подмножества меньшей мощности и внутри них проверяется смежность вершин. В нашем примере вершины х₃, х₅ и х₂', х₃' не смежны. Поэтому процесс разбиения продолжается.

{х₁} {х₃}_1- {{х₂, х₄, х₆}₃₊}₁₊ {{х₅}_3-}_1-,

{х₁'} {х₂'}_1'- {{х₄', х₅', х₆'}_2'+}_1'+ {{х₃'}_2'-}_1'-

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

В рассматриваемом примере подмножества вершин {х₂, х₄, х₆} и {х₄', х₅', х₆'} являются автоморфными, т.е. каждая вершина в одном подграфе может быть изоморфна любой вершине второго подграфа.

Следовательно G' изоморфен G'.

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

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

В этой связи при установлении изоморфизма в однородных графах ВСА в самом лучшем случае О(n), в самом худшем случае О(n!). Если графы неизоморфны, то за одну итерацию установить результат невозможно. Необходимо провести сравнение на изоморфизм одной случайно выбранной вершины из одного графа со всеми остальными вершинами другого графа.

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

{1} {2, 4, 6}₁₊ {3, 5}_1- (G),

{a} {b, d, f}_1'+ {e, c}_1' (G').

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

{1} {2, 4, 6}₁₊ {3, 5}_1- (G),

{b} {a, c, e}_1'+ {d, f}_1'- (G').

Вершины (3, 5) в графе G смежны, а вершины (d, f) в графе G' - нет. Следовательно, вершина 1 не может быть изоморфна вершине b. Продолжая аналогичные построения, имеем, что вершина 1 не может быть изоморфна вершинам c, d, e. Наконец, предположим, что вершина 1 графа G П - изоморфна вершине f графа G'. Тогда получим:

{1} {2, 4, 6}₁₊ {3, 5}_1- (G),

{f} {a, c, e}_1'+ {b, d}_1'- (G').

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

Рассмотрим пример работы алгоритма распозвания изоморфизма для графов G и G' G = (Х, U), G' = (Х', U'), |Х| = |Х'| = 10, |U| = |U'| = 15, локальные степени всех вершин графа равны трем. Предположим, что вершина 1 графа G П - изоморфна вершине a графа G'. Тогда получим:

{1} {2, 5, 6}₁₊ {3, 4, 7, 8, 9, 10}_1- (G),

{a} {b, e, f}_1'+ {c, d, h, g, k, i}_1'- (G').

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

{1} {2}₁₊ [{5, 6}₁₊]_1- [{7, 3}₁₊,{4, 8, 9, 10}_1-]_1- (G),

{a} {b}_1'+ [{e, f}_1'+]_1'- [{g, c}_1'+,{d, h, g, k, i}_1'-]_1'- (G').

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

{1} {2}₁₊ [{5, 6}₁₊]_1- [[{7}₁₊,{3}₁₊]₁₊,[{9, 10}_1-,{4, 8}_1-]_1-]_1- (G),

{a} {b}_1'+ [{e, f}_1'+]_1'- [[{g}_1'+,{c}_1'+]_1'+,[{i, k}_1'-,{h, d,}_1'-]_1'-]_1'- (G').

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

Определение изоморфизма графов позволяет определять одинаковые графы, которые расположены на плоскости по-разному.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. В каком случае два графа называются изоморфными.

2. В чем состоит задача распознавания изоморфизма графов.

3. К какому классу задач относятся задачи распознавания изоморфизма.

4. Какова временная сложность алгоритмов распознавания изоморфизма.

5. Каким образом решается задача определения изоморфизма двух графов.

6. Что означает запись о том, что два графа П-изоморфны.

7. Для чего может использоваться процедура определения изоморфизма графов.

8. В чем состоит основная идея приведенных алгоритмов определения изоморфизма.

9. Каким образом выбираются вершины в алгоритме определения изоморфизма для однородных графов.

10. Что такое изоморфное вложение графов.

Размещено на Allbest.ru