Введение
1. Постановка задачи. Группа автоморфизмов графа 17
2. Прямой алгоритм проверки изоморфизма графов 21
2.1. Спектральный подход к решению задачи проверки изоморфизма графов 21
2.2. Принципиальная схема предлагаемого алгоритма проверки изоморфизма графов 23
2.3. Расщепление решений систем линейных уравнений и расщепление собственных значений спектров графов 36
2.4. Трудоемкость принципиальной схемы предлагаемого алгоритма проверки изоморфизма графов 40
2.5. Пример, иллюстрирующий работу алгоритма 41
3. Вычислительная эффективность алгоритма 47
3.1. Локализация множеств решений 47
3.2. Расщепление множеств решений систем линейных уравнений 53
3.3. Трудоемкость алгоритма 59
4. Применение алгоритма к решению задачи проверки изоморфизма взвешенных неориентированных графов 62
4.1. Задача проверки изоморфизма взвешенных неориентированных графов 62
4.2. Применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок строк и столбцов 67
4.3. Применение алгоритма к решению задачи дешифрования шифра двойной перестановки 69
5. Применение алгоритма к решению задач проверки изоморфизма некоторых других типов графов 72
5.1. Невзвешенные ориентированные графы 72
5.2. Взвешенные ориентированные графы 73
5.3. Невзвешенные мультиграфы 74
6. Алгоритм нахождения приближенного решения задачи поиска оптимального вложения графа 75
6.1. Постановка задачи 75
6.2. Функция расстояния между графами 76
6.3. Алгоритм 78
7. Использование алгоритмов решения задачи проверки изоморфизма графов для построения защищенного видеоканала 84
7.1. Постановка задачи 84
7.2. Применение шифра двойной перестановки к шифрованию видеоизображений 85
7.3. Описание криптосистемы 87
Заключение 92
Библиография 94
