41. Проблема изоморфизма графов и ее временная сложность. Инварианты при проверке графов на изоморфность. Метод сравнения порядков смежности. Временная сложность проверки на изоморфность двух деревьев

 

Изоморфизм

 

            «Напомним, что два графа F(V,E) и F*(V*,E*) изоморфны, если существует взаимно-однозначное соответствие между множествами вершин V и V*, такое, что любые две вершины в графе F смежны тогда и только тогда, когда смежны соответствующие им вершины в графе F*.

 

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

 

            Пусть |V|=n. Проставим в графе F нумерацию вершин [1,2,...,n] и составим для него матрицу смежности С. Затем вершины графа F* пронумеруем в соответствии с некоторой перестановкой списка  [1,2,...,n] и составим его матрицу смежности С*. Если С=С*, то графы изоморфны, если нет, то снова нумеруем вершины графа F* в соответствии с другой перестановкой списка [1,2,...,n], снова составляем матрицу смежности, и процесс сравнения матриц повторяется.

 

            Понятно, что если графы не изоморфны, то придется проверить все n! перестановок из n элементов, т.е. сложность этого алгоритма составляет T(n)=O(n!).

 

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

 

            Инвариантом графа F называется параметр, имеющий одно и то же значение для всех графов, изоморфных графу F. Среди самых очевидных инвариантов отметим следующие:

            1. Число вершин   |V|=n.

            2. Число ребер |E|=m.

            3. Число компонент связности.

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

 

            Эвристики для решения задач изоморфизма обычно состоят в попытках показать, что два рассматриваемые графа не изоморфны. Для этого составляется список различных инвариантов в порядке, определяемом сложностью вычисления инварианта. Затем последовательно сравниваются значения параметров графов. Как только обнаруживаются два различных значения одного и того же параметра, приходят к заключению, что данные графы не изоморфны.

 

            Множество инвариантов, которое позволило бы этой процедуре установить изоморфность графов за полиномиальное время, наз. кодом графа. К сожалению, на сегодняшний день такое множество не найдено.

 

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

 

            Пример. Для графов на  рис.1 все четыре из перечисленных выше инвариантов совпадают, но эти графы не изоморфны.

 

            Рассмотрим теперь пример достаточно сложной эвристики, работающей с матрицей смежности С(F). Сама по себе матрица смежности не является инвариантом”, хотя графы F и F* изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов (эта теорема была доказана в курсе ДМ).

            “Описываемая ниже полиномиальная процедура достаточно хорошо справляется с задачей отсеивания неизоморфных сетей.

 

            Вычисляется С2(Fi) для i=1,2. Затем переставляются строки и столбцы матриц С2(F1) и С2(F2) так, чтобы элементы на главной диагонали оказались в нисходящем порядке. Если F1 и F2 изоморфны и все диагональные элементы различны, то при этой перестановке должны получиться идентичные матрицы. Если нет, то данные два графа не могут быть изоморфными.

     Рис. 1.

           

            Если матрицы идентичны, то можно продолжить проверку с

С4(Fi)= С2(Fi)* С2(Fi),           С8(Fi)= С4(Fi)* С4(Fi),   ...     ,           С2 k(Fi)= Сk(Fi)* Сk(Fi),

для i=1,2. Значение k=2s определяется имеющимся бюджетом машинных ресурсов.

 

            Если все из проверенных матриц совпадают, то весьма правдоподобно, но не обязательно истинно, что Если F1 и F2 изоморфны. Эту процедуру называют СПС (сравнение порядков смежности).

 

            Работа метода СПС проиллюстрирована на примере двух графов с рис. 1.

 

C(F1)=;     C(F2)=;     C2(F1) ;    C2(F2)=.

           

            Элементы на главных диагоналях матриц C2(F1) и C2(F2) будут расположены в нисходящем порядке, если поменять местами элементы с22=2 и с33=3. Для этого в обеих матрицах необходимо поменять местами вторую и третью строку, а также второй и третий столбец:

 

Переупорядоченная C2(F1)=;   Переупорядоченная C2(F2)=.

 

            Диагонали переупорядоченных матриц совпали; поэтому снова возведем матрицы C2(F1) и C2(F2) в квадрат:

C4(F1)=;          C4(F2)= .

 

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