Прямой алгоритм проверки изоморфизма графов

• Автор: Пролубников, Александр Вячеславович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Омск
• Количество страниц: 99 с.

СОДЕРЖАНИЕ
Содержание.
Введение.

1. Постановка задачи. Группа автоморфизмов графа.

2. Прямой алгоритм проверки изоморфизма графов.

2.1. Спектральный подход к решению задачи проверки изоморфизма графов.

2.2. Принципиальная схема предлагаемого алгоритма проверки изоморфизма графов

2.3. Расщепление решений систем линейных уравнений

и расщепление собственных значений спектров графов

2.4. Трудоемкость принципиальной схемы

предлагаемого алгоритма проверки изоморфизма графов

2.5. Пример, иллюстрирующий работу алгоритма.
3. Вычислительная эффективность алгоритма
3.1. Локализация множеств решений
32. Расщепление множеств решений систем линейных
уравнений
3.3. Трудоемкость алгоритма
4. Применение алгоритма к решению задачи
проверки изоморфизма взвешенных неориентированных графов
4.1. Задача проверки изоморфизма взвешенных неориентированных графов.
4.2. Применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок
строк и столбцов.
4.3. Применение алгоритма к решению задачи дешифрования шифра двойной перестановки
5. Применение алгоритма к решению задач
проверки изоморфизма некоторых других типов графов.
5.1. Невзвешенные ориентированные графы
5.2. Взвешенные ориентированные графы
5.3. Невзвешенные мультиграфы
6. Алгоритм нахождения приближенного решения задачи
поиска оптимального вложения графа.
6.1. Постановка задачи.
6.2. Функция расстояния между графами
6.3. Алгоритм
7. Использование алгоритмов решения задачи проверки изоморфизма графов для построения защищенного видеоканала
7.1. I Остановка задачи
7.2. Применение шифра двойной перестановки к шифрованию видеоизображений
7.3. Описание криптосистемы
Заключение.
Библиография


Необходимо отметить, что сложность задачи не меняется при переходе от проверки изоморфизма невзвешенных неориентированных графов к проверке изоморфизма взвешенных графов, ориентированных графов [5|, мультиграфов |6| . В ходе попыток классифицировать задачу по сложности был введен новый класс задач - класс изоморфизм-полных задач. Этот класс включает в себя задачи, полиномиально сводимые к задаче проверки изоморфизма графов, и к которым полиномиально сводится сама задача проверки изоморфизма графов. Этот класс включает в себя такие задачи, как задача проверки равенства термов |7], задача проверки самодополнительности графов [8], задача проверки дробного изоморфизма, представляющего формальное алгебраическое расширение понятия изоморфизма [9]. В [] показано, что полиномиально сводимы друг к другу задача проверки изоморфизма графов и следующая задача. Дан такой набор всех подграфов регулярного графа, что каждый подграф получается из исходного графа путем удаления из нет одной вершины. Требуется восстановить исходный граф. В || также показано, что полиномиально сводимы друг к другу на машине Тьюринга задача проверки изоморфизма графов и такая же задача, как предыдущая, но без условия регулярности графа. То есть из существования полиномиального алгоритма для одной задачи следует существование полиномиального алгоритма для другой. За полиномиальное время к задаче сводимы задача проверки изоморфизма структур, где под структурой понимается множество с набором отношений на нем, и задача проверки изоморфизма групп [5|. В |1 найдены необходимые и достаточные условия изоморфизма двух графов, которые сводятся к существованию в симметрической группе порядка 2т элемента с заданным свойством, где тп число ребер в графе. Показано также [], что группа автоморфизмов графа изоморфна некоторой подгруппе симметрической группы порядка 2т. Задаче проверки изоморфизма графов полиномиально эквивалентны также следующие задачи: изоморфизм конечно-определенных алгебр, изоморфизм полугрупп [1]. Задача об изоморфизме групп может быть решена за время 0(n,ogr') и, видимо, проще задачи проверки изоморфизма графов. Это такие задачи, как задача проверки изоморфизма двудольных графов, регулярных графов [7], хордальных графов, ациклических ориентированных графов ||. Если какая-либо из этих задач будет помещена в некоторый подкласс класса ЛГР, то в него будет помещена и задача проверки изоморфизма графов в целом. Поскольку не удается построить полиномиальный алгоритм решения задачи проверки изоморфизма графов, одно из направлений исследований составляет разработка алгоритмов, решающих за полиномиальное время задачи, получаемые выделением из множества всех графов отдельных классов графов с определенными структурными свойствами. Полиномиальные алгоритмы разработаны для планарных графов , наиболее часто используемых в приложениях. Алгоритм || устанавливает изоморфизм двух деревьев с п вершинами в каждом, заданных списками своих ребер, за время, оцениваемое как 0(? В [] представлен алгоритм распознавания изоморфизма планарных графов, требующий 0(п5) операций. Планарные графы представляют собой наиболее просіюй случай графов с ограничением на род графа, равный в данном случае нулю. В работе |1б| представлен полиномиальный алгоритм для проверки изоморфизма графов, не стягиваемых на К3д. Указанный класс содержит в себе класс графов рода, не превосходящего д. Построенный алгори тм применим также к распознаванию изоморфизма графов с ограниченной степенью вершин. Предложенный в [] метод является обобщением комбинаторного и теорети ко-груп нового подхода к решению задачи. В 7] приведен алгоритм и показано, что изоморфизм графов ограниченного рода д может быть установлен им за время 0(п°^). Задача является полиномиально разрешимой для интервальных графов. В [] представлен алгоритм решения задачи для этого типа графов с трудоемкостью 0(п 4- га), где п число вершин в графе, а т -число ребер. Полиномиальный алгоритм для графов с ограниченными степенями (валентностями) представлен в []. Разработаны полиномиальные алгоритмы решения задачи проверки изоморфизма графов с ограниченной кратностью собственных значений спектра матрицы смежности графа.