Содержание к диссертации
Введение
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
- Постановка задачи. Группа автоморфизмов графа
- Принципиальная схема предлагаемого алгоритма проверки изоморфизма графов
- Расщепление множеств решений систем линейных уравнений
- Применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок строк и столбцов
Введение к работе
Дискретные структуры являются фундаментальной основой информатики. Одними из важнейших таких структур являются графы. Сведения из теории графов широко используются не только в организации структур данных и разработке алгоритмов, но и во всех остальных разделах информатики. По мере развития информатики, все более и более сложные методы анализа оказывают влияние на научные и практические проблемы. Графы являются удобным языком для формулировки и эффективным инструментом для решения задач относящихся к широкому кругу этих проблем. Можно упомянуть в этой связи вопросы конструирования систем автоматизированного проектирования программирования для ЭВМ и создания операционных систем, исследования операций и управления, а также ряда задач экономики, статистики и теоретической физики, теории информации, социологии, математической лингвистики. Широкое распространение в последнее время получило использование графов в задачах распознавания образов.
Задачи на графах и алгоритмы их решения играют одну из ключевых ролей при алгоритмизации комбинаторных задач. Формулировка той или иной задачи дискретной математики на языке теории графов часто облегчает ее решение. В этом случае использование эффективных алгоритмов, существующих в теории графов, позволяет найти конструктивное решение рассматриваемой задачи.
Возможность приложения теории графов к широкому кругу задач из различных научных областей заложена, в сущности, уже в самом понятии графа, сочетающего в себе теоретико-множественные, комбинаторные и топологические аспекты, и, поскольку графы представляют собой гибкую структуру для представления других структур, задача проверки изоморфизма графов имеет фундаментальное значение. Необходимо уметь отвечать на вопрос, являются ли некоторые конечные структуры внутренне, принципиально различными, или же они являются лишь различными представлениями одной и той же структуры. По этой причине необходимость решать задачу проверки изоморфизма графов возникает в различных областях естествознания, и методы ее решения имеют множество приложений в практической деятельности.
Несмотря на десятилетия попыток решения задача проверки изо морфизма графов принадлежит к тем задачам, которые до сих пор не удается классифицировать относительно их сложности. Задача по-прежнему не может быть помещена ни в один из подклассов класса NP, как отмечено в [1]. Тогда как доказано, что задача проверки изоморфизма подграфу является iVP-полной [1,2], и к ней очевидным образом полиномиально сводятся такие TVP-полные задачи, как задача о максимальной клике в графе и задача проверки графа на наличие в нем гамильтонова цикла, о задаче проверки изоморфизма графов, являющиеся ее сужением, можно сказать только то, что она принадлежит классу NP: любое взятое наугад биективное отображение множества вершин одного графа на множество вершин другого за полиномиальное время может быть проверено на предмет того, является оно изоморфизмом или нет. Действительно, формируем в соответствии с проверяемым биективным отображением матрицу перестановки и обратную к ней матрицу (транспонированную матрицу перестановки). Производим преобразование подобия матрицы смежности второго графа, являющееся перестановкой строк его матрицы, соединенной с такой же перестановкой ее столбцов, и сравниваем полученные матрицы. Если матрицы поэлементно равны, то указанное биективное отображение - изоморфизм, и графы изоморфны. Иначе биективное отображение изоморфизмом не является. Указанная процедура, очевидно, полиномиальна.
В целом, не получено ответа пи на один из следующих вопросов:
1. Задача принадлежит классу Р?
2. Задача является TVP-полной?
3. Задача принадлежит классу co-NP?
Не построено алгоритмов, решавших бы задачу без каких-либо ограничений на структуру проверяемых на изоморфизм графов. Более того, как указывалось еще в [3], до сих пор не известно алгоритмов, которые для графов с п вершинами имели бы верхнюю оценку сложности, меньшую чем 0(п\/пс), где с - некоторая константа. Рекордным результатом в оценке сложности задачи является теорема Земляченко, в которой утверждается, что изоморфизм графов может быть установлен со сложностью ехр(п1_с), где с - некоторая положительная константа [4]. Указывается константа с— 1/3 + о(1).
Нет доказательств и того, что задача принадлежит классу co-NP, то есть нет ответа на вопрос: принадлежит ли классу NP дополнение к задаче, а именно следующая задача: даны два графа; необходимо показать, что между этими графами не существует изоморфизма.
Необходимо отметить, что сложность задачи не меняется при переходе от проверки изоморфизма невзвешенных неориентированных графов к проверке изоморфизма взвешенных графов, ориентированных графов [5], мультиграфов [6] .
В ходе попыток классифицировать задачу по сложности был введен новый класс задач - класс изоморфизм-полных задач. Этот класс включает в себя задачи, полиномиально сводимые к задаче проверки изоморфизма графов, и к которым полиномиально сводится сама задача проверки изоморфизма графов. Этот класс включает в себя такие задачи, как задача проверки равенства термов [7], задача проверки самодополнительности графов [8], задача проверки дробного изоморфизма, представляющего формальное алгебраическое расширение понятия изоморфизма [9]. В [10] показано, что полиномиально сводимы друг к другу задача проверки изоморфизма графов и следующая задача. Дан такой набор всех подграфов регулярного графа, что каждый подграф получается из исходного графа путем удаления из него одной вершины. Требуется восстановить исходный граф. В [10 также: показано, что полиномиально сводимы друг к другу на машине Тьюринга задача проверки изоморфизма графов и такая же задача, как предыдущая, но без условия регулярности графа. То есть из существования полиномиального алгоритма для одной задачи следует существование полиномиального алгоритма для другой.
За полиномиальное время к задаче сводимы задача проверки изоморфизма структур, где под структурой понимается множество с набором отношений на нем, и задача проверки изоморфизма групп [5]. В [11] найдены необходимые и достаточные условия изоморфизма двух графов, которые сводятся к существованию в симметрической группе порядка 2т элемента с заданным свойством, где т число ребер в графе. Показано также [11], что группа автоморфизмов графа изоморфна некоторой подгруппе симметрической группы порядка 2т. Задаче проверки изоморфизма графов полиномиально эквивалентны также следующие задачи: изоморфизм конечно-определенных алгебр, изоморфизм полугрупп [1]. Задача об изоморфизме групп может быть решена за время 0{nlogn) и, видимо, проще задачи проверки изоморфизма графов.
Вместе с тем, отдельные ограничения задачи проверки изоморфизма графов, связанные с ограничениями на структуру проверяемых на изоморфизм графов, также являются изоморфизм-полными задачами. Это такие задачи, как задача проверки изоморфизма двудольных графов, регулярных графов [7], хордальных графов, ациклических ориентированных графов [12]. Если какая-либо из этих задач будет помещена в некоторый подкласс класса NP, то в него будет помещена и задача проверки изоморфизма графов в целом.
Поскольку не удается построить полиномиальный алгоритм решения задачи проверки изоморфизма графов, одно из направлений исследований составляет разработка алгоритмов, решающих за полиномиальное время задачи, получаемые выделением из множества всех графов отдельных классов графов с определенными структурными свойствами.
Полиномиальные алгоритмы разработаны для штанарных графов [13], наиболее часто используемых в приложениях. Алгоритм [14 устанавливает изоморфизм двух деревьев с п вершинами в каждом, заданных списками своих ребер, за время, оцениваемое как 0(п), и требует объема памяти, оцениваемого как 0(п) двоичных log2 п-разрядных ячеек. В [15] представлен алгоритм распознавания изоморфизма пла-нарных графов, требующий 0{пъ) операций.
Планарные графы представляют собой наиболее; простой случай графов с ограничением на род графа, равный в данном случае нулю. В работе [16] представлен полиномиальный алгоритм для проверки изоморфизма графов, не стягиваемых на К д. Указанный класс содержит в себе класс графов рода, не превосходящего д. Построенный алгоритм применим также к распознаванию изоморфизма графов с ограниченной степенью вершин. Предложенный в [16] метод является обобщением комбинаторного и теоретико-группового подхода к решению задачи. В [17] приведен алгоритм и показано, что изоморфизм графов ограниченного рода д может быть установлен им за время 0(п0 ).
Задача является полиномиально разрешимой для интервальных графов. В [18] представлен алгоритм решения задачи для этого типа, графов с трудоемкостью 0(п + т), где п - число вершин в графе, а т число ребер.
Полиномиальный алгоритм для графов с ограниченными степенями (валентностями) представлен в [19].
Разработаны полиномиальные алгоритмы решения задачи проверки изоморфизма графов с ограниченной кратностью собственных значений спектра матрицы смежности графа. Этот класс графов явля ется одним из наиболее широких классов, для которых разработаны полиномиальные алгоритмы решения задачи. Классический алгоритм, решающий задачу с таким ограничением, представлен в [20]. Алгоритм состоит из двух частей. В первой части, основанной на методах линейной алгебры, вычисляются все собственные значения матриц смежности графов и проекции базисных векторов Шп на собственные пространства матриц смежности. Требуется значительная точность для установления равенства собственных значений, равенства проекций и равенства углов между проекциями. Во второй, комбинаторной и теоретико-групповой части алгоритма эта информация используется для установления изоморфизма, если он существует, или для заключения вывода о его отсутствии.
Возникает естественный вопрос, почему на указанных классах графов задача проверки изоморфизма может быть решена за полиномиальное время? Существуют ли какие-либо общие свойства графов из этих классов, основываясь на которых можно было бы построить алгоритм, который бы охватывал как можно более широкий класс, оставаясь при этом полиномиальным? Существует ли эффективный концептуально простой алгоритм, удовлетворяющий поставленному условию на ограниченность некоего фиксированного параметра, общего для всех указанных классов? Если такой алгоритм существовал бы, то, возможно, он смог бы привести к эффективному решению задачи для новых классов графов, не содержащихся среди известных.
Были произведены попытки построения таких алгоритмов. Миллер [21] построил алгоритм решения задачи на классе, объединяющем классы графов с ограниченной степенью и ограниченным родом. Поно-маренко в [22] представил алгоритм, за полиномиальное время проверяющий изоморфизм для графов из всех указанных классов, за исключением класса графов с ограниченной кратностью собственных значений матрицы смежности. Для последнего класса задача может быть решена за полиномиальное время только в том случае, если группы автоморфизмов графов тривиальны, что является весьма существенным ограничением.
Основные трудности в задаче проверки изоморфизма графов возникают в ситуации, когда графы обладают группами автоморфизмов значительной мощности. Наиболее эффективные алгоритмы, построенные для решения задачи, используют информацию о специальном строении группы автоморфизмов и теорию групп подстановок. В [22] приводятся доказательства полиномиальное™ некоторых таких алгоритмов для графов с ограниченными степенями вершин и их умеренной экспоненциальное™ (0(ехр(п1_с)), с 0) для всех графов.
Любая конечная группа изоморфна группе автоморфизмов некоторого графа [23]. В [24] показано, что любая конечная группа изоморфна также и группе автоморфизмов некоторого сильно регулярного графа, а как раз изоморфизм регулярных и особенно сильно регулярных графов распознается тяжело. В [25] рассматриваются связи задачи с вопросом о мощности и структуре группы автоморфизмов графа. Показано, что задача проверки изоморфизма графов полиномиально эквивалентна задаче о порядке группы автоморфизмов графа, а также задаче нахождения систем образующих этой группы. Показано, что задача может быть решена за полиномиальное время, если вершины графов, проверяемых на изоморфизм, разбиты на классы ограниченной мощности. В [26[ доказана ІУР-полнота задач, связанных с группой автоморфизмов графов, родственных задаче проверки изоморфизма графов. Показано, в частности, что задача проверки наличия в группе автоморфизмов графа автоморфизма без неподвижных точек остается TVP-полной, если ограничить ее только автоморфизмами порядка 2. Доказано также, что общая проблема определения, имеет ли граф на п вершинах автоморфизм, не оставляющий на месте по крайней мере єп1/к вершин, является JVP-ПОЛНОЙ ДЛЯ произвольно малого фиксированного є и произвольно большого фиксированного к. В [27] вводится задача, состоящая в определении, является ли к делителем количества автоморфизмов графа. Показывается, что введенная задача в иерархии сложности занимает промежуточное положение между задачами проверки изоморфизма графов и поиска всех автоморфизмов графа.
Одним из подходов к решению задачи проверки изоморфизма графов могла бы быть непосредственная проверка возможности получения матрицы смежности одного из графов некоторой перестановкой рядов матрицы смежности другого графа. В наихудшем случае нам необходимо проверить все возможные перестановки рядов одной из матриц смежности, что неизбежно влечет экспоненциальность любого из алгоритмов такого типа. Однако, рассмотрение таких инвариантов матриц смежности графов как характеристический многочлен, спектр и собственные векторы приводит к спектральному подходу к решению задачи проверки изоморфизма графов [28], существенно более эффективному.
Теорию графов можно отождествить с теорией матричных классов, состоящих из матриц смежности изоморфных графов, и их инвариантами. Одними из наиболее содержательных инвариантов такого матричного класса являются характеристический многочлен матрицы PGA(X) — \Ло - XI \ и ее спектр Sp(A0) = {Ль ..., А„}, где Л0 одна из матриц, принадлежащая такому классу. Вместе с тем, как и все остальные инварианты, спектр матрицы смежности графа и ее характеристический многочлен не являются полными инвариантами, то есть совпадение их для графов не является достаточным условием их изоморфизма.
В [29] представлен алгоритм установления изоморфизма графов, основанный на использовании собственных значений матриц смежности графов в качестве инварианта.
В [30] приводится эвристический алгоритм, основанный на использовании введенных в [31] инвариантов графов. В вычислительной части алгоритма сравниваются инварианты исследуемых графов. В случае совпадения этих инвариантов в проверочной части осуществляется поиск подстановки, устанавливающей изоморфизм. Если ни одной такой подстановки не найдено, то графы составляют контрпример к алгоритму. Аналогично решается задача определения орбит группы. Инвариант, приводимый в [32], представляет собой некоторую каноническую матрицу, элементы которой характеризуют связи между ярусами графа при подвешивании его за некоторую вершину. Вершины графа могут разбиться на классы по составу строк канонической матрицы. Известно, однако, что для сильно регулярных графов разбиения не происходит.
В [33] представлено построение оптимального кода для извлечения свойств, определяющих изоморфизм графов. Кодом неориентированного графа без петель при заданной нумерации вершин называется двоичное число, полученное последовательным приписыванием строк верхнего треугольника матрицы смежности вершин. Та из нумераций вершин, для которой получаемое двоичное число является наибольшим, реализует оптимальный код. Излагаются два алгоритма нахождения оптимального кода. Второй алгоритм применим только к регулярным графам. Необходимая информация представлена матрицей смежности вершин и матрицей минимальных расстояний между вершинами. Для изоморфных графов получаемые оптимальные коды совпадают.
В [33] вводится следующий инвариант. Пусть G& - граф, А его матрица смежности. Если граф GA изоморфен графу GB, то \А XI\ = = \В — А/. Матрице А сопоставляется два многочлена от п переменных, коэффициенты первого из которых являются инвариантами относительно перестановки строк А, коэффициенты второго инварианты относительно перестановки ее столбцов.
В [34] описывается алгоритм установления изоморфизма графов, основанный на использовании матриц расстояний и матриц кратностей кратчайших цепей между всеми парами вершин. В том случае, когда эти средства не дают возможности различать проверяемые на изоморфизм графы, происходит обращение к вычислению характеристических полиномов матриц смежности графов, и, наконец, к канонизации и полному перебору.
В [35,36] излагается метод исследования инвариантов изоморфных графов, который базируется на представлении графов полиномами над конечными полями.
Подчеркнем, что полной системы вычисляемых за полиномиальное время инвариантов изоморфных графов построить пока не удалось.
Помимо ограничений на структуру проверяемых графов получил распространение подход, состоящий в построении алгоритмов ориентированных на уменьшение вычислительной сложности за счет адекватного представления процесса поиска изоморфизма и отсечении заведомо неудачных путей в пространстве поиска. В этом случае не налагается никаких ограничений на структуру проверяемых па изоморфизм графов, однако трудоемкость таких алгоритмов может быть оценена только статистически, что является существенным минусом.
Одной из первых публикаций, представляющих собой такой подход, была работа Корнейла и Готлиба [37], в которой был представлен алгоритм, осуществлявший некоторые преобразования графов, позволяющие ускорить процесс проверки изоморфизма. Однако, в 38] было показано, что предположение, на котором основан метод, не всегда справедливо, что ограничивает его применимость.
Значительная часть эффективных в среднем алгоритмов основана на прямом построении в ходе работы алгоритма отображения множества вершин одного графа на множество вершин второго графа, являющегося изоморфизмом. В основе такого подхода лежит идея, заключающаяся в таком выборе на каждой итерации алгоритма вершин из каждого графа, который сохранял бы изоморфизм подграфов, co стоящих из уже выбранных вершин и всех инцидентных им ребер проверяемых на изоморфизм графов, соединяющих выбранные вершины. Выбор пар по одной вершине из каждого графа продолжается до тех пор, пока подграфы не будут достроены др собственно самих графов, изоморфизм которых проверяется. Алгоритмы, использующие подобный подход, представляют собой некоторые вариации реализации процедуры backtracking (рекурсии с возвратом): в ходе работы подобных алгоритмов поиск происходит согласно некоторому дереву поиска, и в наихудшем случае такой, пусть и сокращенный перебор, приводит к экспоненциальное™ данного алгоритма.
В [39] описывается алгоритм, рекурсивно разбивающий на классы эквивалентности параллельно множество вершин и множество ребер графа. Исходное разбиение может быть выбрано произвольным образом (например, разбиение множества вершин по степеням). Число действий алгоритма оценивается в среднем как 0(п5).
Алгоритмом, значительно сужающим на каждой итерации пространство перебора, является алгоритм, предложенный Улльмапом 4(). Этот алгоритм предназначен как для задачи проверки изоморфизма графов, так и для задачи проверки изоморфизма подграфу. Этот алгоритм до сих пор является одним из наиболее применяемых алгоритмов для решения задачи проверки изоморфизма графов. Он является одним из тестовых алгоритмов при проверке эффективности других алгоритмов решения задачи.
Другая реализация схемы перебора с возвратом - алгоритм, разработанный Шмидтом и Дрюффелем [41]. Этот алгоритм использует информацию, содержащуюся в матрице расстояний графа, для формирования начального разбиения вершин графа. Под матрицей расстояний графа понимается матрица, в (г, -позиции которой находится длина кратчайшей цепи между вершинами і и j. Построенное с использованием матрицы расстояний начальное разбиение используется в дальнейшем для уменьшения дерева поиска при реализации рекурсии с возвратом. Относительно более поздний алгоритм, использующий целый набор правил, позволяющих существенно уменьшить дерево поиска, - VF-алгоритм [42].
Алгоритм, основанный на backtracking e, предлагается в [43). На каждом этапе подразбиения текущего разбиения множества вершин графа на классы, инвариантные относительно автоморфизма графа, используется алгоритм с числом действий 0(n logп), минимизирую щий число состояний в конечном автомате.
Одним из наиболее эффективных на данный момент является алгоритм NAUTY МакКэя [44]. Основа алгоритма - построение поискового дерева с вершинами, являющимися упорядоченными разбиениями множеств вершин исходного графа [45]. Начальное разбиение состоит из одного класса - самого множества вершин графа, окончательные разбиения содержат по одной вершине в каждом классе. Следующее разбиение в поисковом дереве получается из предыдущего выделением некоторой вершины в отдельный класс и применением к полученному таким образом промежуточному разбиению оператора продолжения разбиения. В качестве этого оператора используется обычная процедура многократного итерирования разбиения множества вершин графа по степеням. Алгоритм содержит некоторые средства, позволяющие исключить из рассмотрения части поискового дерева. Хотя алгоритм NAUTY рассматривается как один из наиболее эффективных, было показано, что есть категории графов, проверка изоморфизма которых имеет для него экспоненциальную сложность [461.
Другой возможный подход к решению задачи представлен в 47. Вместо снижения сложности сравнения двух графов, авторы пытаются снизить общую вычислительную сложность алгоритма, сравнивая граф с большим набором графов-прототипов. Этот метод имеет сложность 0(п2) вне зависимости от количества имеющихся прототипов, по объем необходимой для хранения графов-прототипов памяти возрастает экспоненциально с ростом числа вершин графов, проверяемых на изоморфизм, в связи с чем этот метод является эффективным только для графов с небольшим числом вершин.
Все указанные выше алгоритмы нацелены на точный поиск изоморфизма графов, то есть они предъявляют биективное отображение, являющееся изоморфизмом, в случае если таковое существует. В последнее время, растет число алгоритмов, способных находить приближенные решения задачи. Такие алгоритмы, представленные в [48-50], имеют полиномиальную вычислительную сложность, но они не гарантируют нахождения точного решения поставленной задачи.
В данной работе предлагается алгоритм проверки изоморфизма графов, основанный на применении методов линейной алгебры и ее численных методов, являющийся продолжением работы [51]. Предлагаемый алгоритм всегда дает решение задачи проверки изоморфизма для двух графов из класса графов, определяемого в представляемой работе. Определение данного класса графов тесно связано с понятием изоморфизма графов. Проверить, принадлежит ли проверяемые на изоморфизм графы данному классу можно в ходе работы алгоритма. Отметим, однако, что в ходе многочисленных вычислительных экспериментов не было найдено ни одного графа, который бы данному классу не принадлежал. В частности, классу принадлежат графы доступные из электронных библиотек тестовых задач проверки изоморфизма графов, на которых тестируются наиболее эффективные алгоритмы решения задачи. В класс входят и графы, являющиеся традиционно наиболее сложными для проверки изоморфизма графов.
В ходе итераций алгоритма происходит согласованное возмущение модифицированных матриц смежности, представляющих графы. Группа автморфизмов графов с простым спектром может состоять только из инволюций, что упрощает задачу проверки изоморфизма графов, хотя расщепление всех собственных значений матриц смежности при некоторых их возмущениях, еще не свидетельствует о тривиальности группы автоморфизмов графов. Тогда как именно для графов с тривиальной группой автоморфизмов установление изоморфизма происходит наиболее эффективно. На приведении исходных невзвешепных неориентированных графов к графам, содержащим петли с заданными на них весами, которые обладали бы тривиальной группой автоморфизмов, основывается алгоритм, предлагаемой в данной работе.
Вычисление всех собственных значений и собственных векторов с необходимой точностью является задачей, обладающей значительной вычислительной сложностью. Поэтому предлагаемый алгоритм в качестве эвристики использует не собственные значения и собственные векторы матриц, поставленных в соответствие графам, а обратные матрицы к модифицированным матрицам смежности графов и их согласованные изменения, происходящие при возмущениях. Связь подхода, предлагаемого в [51], и изложенного в этой работе рассматривается в параграфах 2.1 и 2.3 работы.
Алгоритм работает с модифицированными до положительно определенных матрицами смежности графов и основан на решении связанных с ними систем линейных уравнений. Алгоритм является прямым в том смысле, что при решении задачи проверки изоморфизма графов не происходит перебора вариантов в соответствии с некоторым деревом поиска, рост которого на некотором этапе работы алгоритма мог бы стать неконтролируемым. Изоморфны графы или нет устанавливается не более чем за п итераций алгоритма, где п - число вершин в графе. В случае изоморфизма графов предъявляется один из возможных изоморфизмов.
Материал диссертации расположен следующим образом.
В главе 1 приведена постановка задачи проверки изоморфизма графов и введены основные термины, используемые в работе.
В главе 2 изложен предлагаемый алгоритм проверки изоморфизма графов и приведено его теоретическое обоснование. Рассмотрена трудоемкость алгоритма, как величина, зависящая от количества итераций решения систем линейных уравнений. Приведен пример, иллюстрирующий работу алгоритма.
В главе 3 исследована вычислительная эффективность алгоритма и получена оценка его трудоемкости, справедливая для широкого класса графов.
В главе 4 показана возможность приложения построенного алгоритма для проверки изоморфизма взвешенных неориентированных графов, решения задачи проверки эквивалентности матриц с точностью до перестановок строк и столбцов и задачи дешифрования шифра двойной перестановки.
В главе 5 показана возможность приложения построенного алгоритма для проверки изоморфизма ориентированных графов и муль-тиграфов.
В главе б производится построение алгоритма приближенного поиска оптимального вложения графа.
В главе 7 рассматривается возможность использования алгоритмов решения задачи проверки изоморфизма графов (в том числе и предложенного в работе алгоритма) для построения защищенного видеоканала.
В заключении содержатся основные выводы работы.
Основные результаты диссертации:
1. Построен прямой алгоритм проверки изоморфизма графов, основанный на методах линейной алгебры, решающий задачу для широкого класса графов не более чем за п итераций, где п - число вершин в графах, проверяемых на изоморфизм.
2. Доказано утверждение, характеризующее вычислительную сложность алгоритма. Показано, что алгоритм является полиномиальным по используемой памяти, являясь также полиномиальным по времени, вне зависимости от структурных особенностей проверяемых на изоморфизм графов: те из графов с ограниченной степенью вершин и графов с ограниченной кратностью собственных значений, которые находятся в классе графов, для которого алгоритм дает решение задачи, не имеют при решении задачи представляемым алгоритмом специфики, обычной для других алгоритмов решения задачи.
3. Показана применимость модификации алгоритма к решению задач проверки изоморфизма ориентированных, взвешенных графов и мультиграфов.
4. Предлагается применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок их строк и столбцов. Возможность решения этой задачи, в свою очередь, позволяет решать задачу дешифрования шифра двойной перестановки.
5. На основе эвристики, используемой для проверки изоморфизма графов, построен алгоритм приближенного решения задачи поиска оптимального вложения графа.
6. Предложено приложение задачи проверки изоморфизма графов и предложенного алгоритма к решению задачи построения защищенного видеоканала.
Основные результаты работы опубликованы автором в работах 52-61]. Результаты докладывались па конференции «Дискретный анализ и исследование операций» (г. Новосибирск, 2002 г., 2004 г.), на семинаре академика РАН С.К. Годунова, на ХП-й Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2003), на семинаре Института систем обработки изображений РАН (г. Самара), на 11-й Всероссийской конференции «Математические методы распознавания образов» (г. Пущино, 2003), на семинарах кафедры информационной безопасности Омского государственного университета.
Все результаты, выносимые на защиту, получены автором лично.
В заключении введения автор выражает благодарность научному руководителю Р.Т. Файзуллину за постоянное внимание к работе.
Постановка задачи. Группа автоморфизмов графа
Под графом GA — (VA, ЕА) понимается конечное множество V\, элементы которого называются вершинами, совместно с множеством Е\ двухэлементных подмножеств этого множества, элементы которого называются ребрами. Аналогично, ориентированный граф GA = (VA, ЕА) определяется как конечное множество VA И множество ЕА упорядоченных пар элементов множества VA, которые называются ориентированными ребрами или дугами. Далее, говоря о графе GA — (VA, ЕА) часто будем обозначать его просто GA Графы с неориентированными или ориентированными кратными ребрами называются соответственно мультиграфами или мультиоргра-фами. В этих случаях допускается существование петель, где петля это ребро или дуга, обе вершины которой совпадают. Две вершины называются смежными, если они соединены ребром. Задача проверки изоморфизма невзвешенных неориентированных графов формулируется следующим образом. Постановка задачи 1. Даны два невзвешенных неориентированных графа GA — (VA,EA) И GB = (VB,EB), где VA,VB множества вершин графов, ЕА, ЕВ множества ребер графов. \VA\ = \VB\, \ЕА\ = = \Ев1 Графы GA = (VA, ЕА) И GB — (VB,EB) изоморфны тогда и только тогда, когда существует такое биективное отображение р : VB — VA-что (i,j) Є Ев = (ір(і), p(j)) Є ЕА- Требуется найти такое ір, или доказать, что его не существует. Изоморфизм графов далее будем обозначать как «GA — GB»- Очевидно, граф GA И граф GB С одинаковым количеством вершин изоморфны тогда и только тогда, когда их вершины можно занумеровать так, что соответствующие матрицы смежности будут равны.
Отношение изоморфизма является отношением эквивалентности, разбивающим множество всех графов на классы эквивалентности, которые можно рассматривать как абстрактные графы. Таким образом, изоморфные графы представляют собой один и тот же абстрактный граф. Пусть AQ - матрица смежности невзвешенного неориентированного графа GA, ТО есть AQ = (а ), где BQ - матрица смежности графа GB Абстрактный граф однозначно определяется матрицей смежности, но обратное утверждение, вообще говоря, не имеет места, так как упорядочение (нумерация) вершин графа произвольное: каждому графу соответствует класс матриц смежности; две матрицы А и В принадлежат одному классу тогда и только тогда, когда существует матрица перестановки Р такая, что А = РВР Х. (Учитывая, что матрицей, обратной к матрице перестановки Р, является матрица Рт, это условие равносильно А = РВРТ.) А это значит, что матрица А может быть получена из матрицы В при помощи некоторой перестановки строк матрицы, соединенной вместе с точно такой же перестановкой ее столбцов. Соединение перестановки строк в квадратной матрице с такой же перестановкой ее столбцов будем в дальнейшем называть перестановкой рядов матрицы. Биективному отображению ip : У# — VA однозначно соответствует перестановка Р , действующая на множестве вершин графа GB- Если Р представлена матрицей перестановки (также обозначаемой Р ). то Р является изоморфизмом тогда и только тогда, когда А = Р ВР где А - матрица смежности графа GA, В матрица смежности графа GB.
Любому биективному отображению р : Уд — VA может быть однозначно поставлена в соответствие некоторая матрица перестановки Р — {Pij)i задаваемая следующим образом: Умножение некоторой матрицы слева на матрицу Р задает перестановку ее строк, при которой j-я строка переходит в г-ю. Обратной матрицей к матрице Р р будет матрица Р - матрица, получаемая из матрицы Р ее транспонированием, то есть матрица со следующими элементами » : Умножение некоторой матрицы справа на матрицу Р задает перестановку ее столбцов, при которой j-й столбец переходит в г-й. Таким образом, следующая постановка задачи эквивалентна постановке задачи 1. или показать, что ее не существует. В постановке задачи выше матрица Р - матрица перестановки Pv соответствующая изоморфизму р : VB — VA, биекции, существование или отсутствие которой равносильно изоморфизму или, соответственно, неизоморфизму графов GA И GB- Везде далее, при рассмотрении некоторого изоморфизма (р индекс «р» соответствующей матрицы Р будет опускаться. Таким образом, между биективными отображениями ц : VB — — VA И матрицами перестановок Р размерности п х п может быть установлено взаимно однозначное соответствие. При этом если GA — GB, то ip : VB — VA - изоморфизм тогда и только тогда, когда. А0 P BQP . ТО есть Биективное отображение ср и соответствующая ему перестановка Р, действующие на множестве вершин графа G 4, называются автоморфизмом графа GA, если они сохраняют смежность его вершин. Если Р представлена матрицей перестановки (также обозначаемой Р). то Р является автоморфизмом тогда и только тогда, когда А = РАР 1, где А - матрица смежности графа GA- Автоморфизмы графа GA образуют группу Г = T(GA), называемую группой автоморфизмов графа GA, В терминах которой выражаются симметрии этого графа относительно перестановок вершин. Группа V(GA) автоморфизмов графа, GA Реализуется множеством всех матриц перестановок Р. коммутирующих с матрицей смежности А графа GA . Орбитой вершины і Є V относительно T(G) называется множество О(г), состоящее из всех таких вершин j Є V, что 3(р Є T(G) т.ч. р(г) — j, то есть О (і) = { р(г)\ (р Є V(G)}. Орбиты вершин графа относительно его группы автоморфизмов представляют собой непересекающиеся классы эквивалентности вершин.
Принципиальная схема предлагаемого алгоритма проверки изоморфизма графов
Следствием ограниченности памяти машины является то обстоятельство, что в ней не могут быть представлены числа, мантиссы которых содержат бесконечную последовательность 7-ичных ненулевых цифр в своем 7-ичном представлении. Под каждое число с плавающей точкой отводится место (ячейка) в памяти ЭВМ, достаточное для размещения к 7-ичных цифр мантиссы. В той же ячейке памяти размещается знак числа z, порядок Py(z). Это позволяет хранить в памяти машины числа, порядки которых удовлетворяют условию р Py(z) р+, где р 0 и р+ 0 некоторые числа не зависящие от z.
То есть машинные числа - это рациональные числа вида где р р р+, 1 z\ 7 — 1, 0 Zj 7 — 1 (2 j к). Число нуль также является машинным числом (р7(0) = 0, га7(0) = 0).
При численной реализации алгоритма необходимо, чтобы возмущения, выбираемые на итерациях алгоритма, были достаточно велики для выделения векторов из множеств. Необходимо, чтобы соответствующие компоненты векторов, равные до возмущения, были отделимы после возмущения как машинные числа. Иными словами, необходимо, чтобы точности нахождения векторов-решений систем линейных уравнений (2.2.3) и их представления машинными числами было достаточно для численной реализации расщепления множеств Rj(A).
Покажем, что на каждой j -й итерации может быть выбрано возмущение Ej = j(A), не приводящее к попаданию выделяемого из некоторого множества вектора Xj в другое множество, и при этом длина мантиссы к обрабатываемых машинных чисел, обеспечивающая необходимую точность, может быть задана на старте алгоритма, оставаясь неизменной на протяжении всей его работы.
Пусть г, j: x Xj Є Rj(A), то есть в множестве Rj(A) имеется как минимум два элемента, препятствующие установлению взаимно однозначного соответствия алгоритмом на j -й итерации. Для решений систем линейных уравнений (2.2.3), если ЭР : Х{ = PXJ, то то это означает выделение из множества Ri(A) вектора Xj, и уменьшения на единицу Я,;(Л), а если \/г Л?;(Л) = 1, то возможно установление взаимно однозначного соответствия между вершинами графов GA и GB Предложение 2. Если до j-u ит,ерации алгоритма существует такая матрица перестановки Р, что Xj — Pxi, XJJ = хц, и возмущение на j-u итерации алгоритма j 0, то
Доказательство. Пусть, если не оговаривается дополнительно, обозначения со штрихом - векторы, матрицы и множества, в которые пе реходят соответствующие нештрихованные векторы и множества после проведения j-й итерации, они же без штрихов - векторы, матрицы и множества, имеющиеся перед j-Pi итерацией.
Пусть решение систем линейных уравнений (2.2.3) осуществляется методом Гаусса-Зейделя. Помимо того, что для решаемых систем уравнений с заданными матрицами для этого метода присутствует геометрическая сходимость приближенных решений к решениям точным, применение этого метода позволяет оценить приближение по значащим разрядам мантиссы на каждой итерации. Справедлива 66 следующая теорема:
р 0 целое число, определяющее возмущение Ej = 1/пр. р вычисляется с целью предотвращения попадания выделяемого из множества Ri элемента Xj в другое, ближайшее к нему множество Ri+\, находящееся от Ri па расстоянии A?;,?;+i: р определяется из неравенства
То есть интервал, в котором происходит расщепление, может быть задан так, чтобы гарантированно не происходило попадания выделенного из одного множества Ri(A) вектора в другое множество R i+1(A), имеющееся на следующей итерации (рис. 3).
Рассмотрим случай, когда графы GA, GB - полные графы, то есть графы, любые две вершины которых соединены ребром. В этом случае имеется только одно множество решений, то есть т = 1, и \R\\ = п. поскольку все диагональные элементы обратной матрицы к матрице вида (2.2.1) полного графа равны друг другу, и все внедиагональ-ные элементы обратной матрицы равны друг другу. Число векторов в множестве R\ равно п. Проверка изоморфизма двух полных графов сама по себе является тривиальной задачей, поскольку любой полный n-вершинный граф, очевидно, изоморфен любому полному
n-вершинному графу. Пример ниже приводится приводится с целью иллюстрации эффективности алгоритма в данном, наиболее тяжелом для алгоритма случае, так как в данном случае необходимо расщепить единственную множество, содержащую все решения систем линейных уравнений типа (2.2.1).
Расщепление множеств решений систем линейных уравнений
В задаче проверки изоморфизма невзвешенных ориентированных графов даны два графа GA = (VA, ЕА) и GB = (VB,EB), где VA,VB множества вершин графов, ЕА, Ев - множества их ребер - упорядоченные пары вершин из VA и VB- Графы GA и GB изоморфны тогда и только тогда, когда существует биективное отображение (р : Vg — VA такое, что ребро (i,j) принадлежит множеству ребер Ев графа GB тогда и только тогда, когда ребро ( p(i), p(j)) принадлежит множеству ребер ЕА графа GA.
Аналогично задача может быть поставлена в терминах матриц смежности невзвешенных ориентированных графов, и эта постановка будет в свою очередь повторять соответствующую постановку задачи 2 для невзвешенных неориентированных графов.
Пусть А() - матрица смежности невзвешенного ориентированного графа GA модифицированная следующим образом. AQ = (аї-j). где
Отметим, что в общем случае матрица невзвешенного ориентированного графа несимметрическая. Если AQ - матрица смежности невзвешенного ориентированного графа GA, a BQ - матрица смежности невзвешенного ориентированного графа GB, то графы GA и GB изоморфны тогда и только тогда, когда существует такая матрица перестановки Р. что По матрицам AQ И BQ построим матрицы AQ И BQ:
Формулировка задачи проверки изоморфизма взвешенных ориентированных графов в точности повторяет формулировку задачи проверки изоморфизма невзвешенных ориентированных графов, с единственной поправкой на значения элементов матриц, представляющих графы, которые в данном случае не обязательно должны быть равны единице, в случае если между соответствующими вершинами имеется ребро. В приведенном выше сведении задачи проверки изоморфизма невзвешенных ориентированных графов к задаче проверки изоморфизма невзвешенных неориентированных графов нигде не используется равенство единице ненулевых элементов матриц, представляющих графы, а значит оно справедливо и в этом случае. То есть задача проверки изоморфизма взвешенных ориентированных графов может быть сведена к задаче проверки изоморфизма взвешенных неориентированных графов, к которой, как показано в первом пункте этой главы, может быть применен предлагаемый алгоритм проверки изоморфизма графов. Формулировка задачи проверки изоморфизма невзвешенных мульти-графов в точности повторяет формулировку задачи проверки изоморфизма взвешенных ориентированных графов, с единственной поправкой на значения элементов матриц, представляющих графы, которые в данном случае будут целочисленны. Так, ориентированный мульти-граф будет представлять матрица AQ — (а -), где
Отметим, что случай взвешенных мультиорграфов не рассматривается - между двумя вершинами может быть одно и только одно ребро, так как, в случае взвешенного ориентированного мультиграфа при представлении его в виде предложенной нами модификации матрицы смежности теряется уникальность ребер между одними и теми же вершинами, но имеющих разные веса, если в рассматривать группу ребер, соединяющих некоторые две вершины графа. Соответственно, заведомо невозможно при применяемом нами подходе гарантированное получение ответа на вопрос об изоморфизме пары таких графов, и представленный нами подход для решения данной задачи неприменим.
Применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок строк и столбцов
Надежно защитить видеоинформацию возможно только при использовании классических принципов криптографии, оперируя с цифровыми видеоизображениями. Из применяемых подходов к шифрованию наиболее приемлемым для сохранения качества изображения и поддержания необходимой трудоемкости несанкционированного дешифрования является подход, заключающийся в перестановке строк кадров видеоизображения [75]. Шифр двойной перестановки кадра состоит из некоторых перестановок строк и столбцов пикселей кадра видеоизображения. Поскольку процедура дешифрования шифра двойной перестановки может быть сведена к решению задачи проверки изоморфизма графов, то видится эффективным использование этой задачи и алгоритмов ее решения для построения криптосистемы, реализующей защищенный видеоканал.
Постановка задачи следующая. По открытому каналу связи от источника (абонента А) к приемнику (абоненту В) передается видеоизображение. Необходимо шифровать видеоизображение, чтобы избежать несанкционированного доступа к передаваемой видеоинформации при подключении третьих лиц (противника М) к каналу связи. При этом необходимо реализовать шифрование так, чтобы ключ к шифру динамически менялся при передаче кадров от источника к приемнику без передачи в явном виде по каналу связи ключа к шифру.
Для того, чтобы только абонент В (приемник) мог иметь доступ к посланному изображению, абонент А (источник) преобразует каждый кадр р видеоизображения с помощью функции шифрования Е и ключа клв в кадр с шифрованного видеоизображения: который и поступает в канал связи. Приемник восстанавливает исходный кадр видеоизображения с помощью функции дешифрования D и того же секретного ключа кАв Цель противника М - воспрепятствовать осуществлению намерений законных участников информационного обмена (абонентов А и В). В общем случае противник М может перехватывать шифрованные сообщения, модифицировать их, посылать фальсифицированные сообщения абоненту В якобы от имени абонента А. То есть имеют место три возможных типа угроз со стороны противника М: 1. Нарушение секретности информации - дешифрование (полное или частичное) переданного видеоизображения или получение информации о его сути. 2. Нарушение целостности видеоинформации - внесение в видеоизображение искажений, которых законный получатель не смог бы обнаружить. 3. Нарушение подлинности информации - формирование ложных сообщений, направляемых абоненту В противником М.
Дешифрование переданного по каналу связи видеоизображения противником М возможно в случае вычисления им ключа клв, либо в случае нахождения алгоритма, функционально эквивалентного D B И не требующего знания клв Кадр видеоизображения представляет собой набор пикселей. Будем считать, что пиксель полностью характеризуется его позицией и цветом, и каждому цвету, используемому при передаче видеоизображения, поставлен в соответствие его уникальный числовой код. Поэтому если каждый кадр видеоизображения представлен с разрешением п х п. он может быть представлен числовой квадратной матрицей, имеющей п строк, в позиции (г, j) которой находится числовой код соответствующего пикселя.
Шифром двойной перестановки кадра видеоизображения является соединение некоторой перестановки строк с некоторой перестановкой столбцов его пикселей. Если пикселям нешифрованного изображения соответствует матрица С, то шифру двойной перестановки изображения будет соответствовать матрица С = PiCPj, где Pi, Р2 - матрицы перестановок, реализующие перестановку строк (Pi) и перестановку столбцов (Р2) матрицы С. Будем далее в тексте обозначать перестановки и соответствующие им матрицы одинаково.
Матрицы Сг и С 2 - симметрические матрицы. Они могут рассматриваться как матрицы смежности некоторых взвешенных неориентированных двудольных графов. Таким образом, если один кадр является шифром двойной перестановки другого, то соответствующие им графы - графы с матрицами смежности Сі и С 2 изоморфные графы. Изоморфизм графов, задаваемый матрицей перестановки Р, задает перестановку строк и столбцов пикселей изображения - перестановки Pi и Р2. То есть дешифрование шифра двойной перестановки равносильно решению задачи проверки изоморфизма взвешенных неориентированных графов.
Вместо передачи абоненту В перестановок Р\ и Рг, необходимых тому для дешифрования зашифрованного кадра, абонент А будет передавать ему С. Обладая и С и С, ставя и решая задачу проверки изоморфизма графов, абонент В получает Р, и, следовательно, Рх и P i. Нетривиальность группы автоморфизмов графов, отвечающих Сч и С 2) влечет неединственность решения задачи поиска изоморфизма графов, то есть задачи поиска решающих перестановок Pi и Рг, что неприемлемо, поскольку для функционирования строимой нами криптосистемы абоненты Л и В должны обладать одной и той же перестановкой, дающей ключ к шифру - кдв- Поэтому изображения, предназначенные для неявной передачи ключа к шифру по открытому каналу связи (называемые в дальнейшем «сигнальными») должны быть такими, что группы автоморфизмов соответствующих им графов тривиальны.
Предлагаемый для данной задачи алгоритм проверки изоморфизма графов с тривиальной группой автоморфизмов имеет следующий вид. Шаг 1. Найти решение Xj0 системы линейных уравнений А\х = e,j0 для некоторого jo : 1 Jo п Шаг 2. Решить п систем линейных уравнений А2у = е&, к = 1,п, найти kj0 : ЗР - матрица перестановки: PXJ0 = yu ,.7 = 1, п. Шаг 3.
