Прямой алгоритм проверки изоморфизма графов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Пролубников, Александр Вячеславович

• Пролубников, Александр Вячеславович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Пролубников, Александр Вячеславович

Содержание.

Введение.

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

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

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

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

2.3. Расщепление решений систем линейных уравнений и расщепление собственных значений спектров графов.

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

2.5. Пример, иллюстрирующий работу алгоритма.

3. Вычислительная эффективность алгоритма.

3.1. Локализация множеств решений.

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

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. Постановка задачи.

7.2. Применение шифра двойной перестановки к шифрованию видеоизображений.

7.3. Описание криптосистемы.

Введение диссертации (часть автореферата) на тему «Прямой алгоритм проверки изоморфизма графов»

Дискретные структуры являются фундаментальной основой информатики. Одними из важнейших таких структур являются графы. Сведения из теории графов широко используются не только в организации структур данных и разработке алгоритмов, но и во всех остальных разделах информатики. По мере развития информатики, все более и более сложные методы анализа оказывают влияние на научные и практические проблемы. Графы являются удобным языком для формулировки и эффективным инструментом для решения задач относяпщхся к широкому кругу этих проблем. Можно упомянуть в этой связи вопросы конструирования систем автоматизированного проектирования программирования для ЭВМ и создания операционных систем, исследования операций и управления, а также ряда задач экономики, статистики и теоретической физики, теории информации, социологии, математической лингвистики. Широкое распространение в последнее время получило использование графов в задачах распознавания образов.Задачи на графах и алгоритмы их решения играют одну из ключеBFJIX ролей при алгоритмизации комбинаторных задач. Формулировка той юш иной задачи дискретной математики па языке теории графов часто облегчает ее решение. В этом случае использование эффективных алгоритмов, существующих в теории графов, позволяет найти конструктивное решение рассматриваемой задачи.Возможность приложения теории графов к широкому кругу задач из различных научных областей заложена, в сущности, уже в самом понятии графа, сочетающего в себе теоретико-множественные, комбинаторные и тогюлогические аспекты, и, поскольку графы представляют собой гибкую структуру для представления других структур, задача проверки изоморфизма графов имеет фундаментальное значение.Необходимо уметь отвечать на вопрос, являются ли некоторые конечные структуры внутренне, принципиально различными, или же они являются лишь различными представлениями одной и той же структуры. По этой причине необходимость решать задачу проверки изоморфизма графов возникает в различных областях естествознания, и методы ее решения имеют множество приложений в практической деятельности.Несмотря на десятилетия попыток решения задача проверки изоморфизма графов принадлежит к тем задачам, которые до сих пор не удается классифицировать относительно их сложности. Задача попрежнему не может быть номепдена ни в один из подклассов класса NP, как отмечено в [1]. Тогда как доказано, что задача проверки изоморфизма подграфу является Л'^ Р-полной [1,2], и к ней очевидным образом полиномиально сводятся такие МР-полиые задачи, как задача о максимальной клике в графе и задача проверки графа на наличие в нем гамильтонова цикла, о задаче проверки изоморфизма графов, являющиеся ее сужением, можно сказать только то, что она принадлежит классу NP: любое взятое наугад биективное отображение множества вершин одного графа на множество вершин другого за полиномиальное время может быть проверено на предмет того, является оно изоморфизмом или нет. Действительно, формируем в соответствии с проверяемым биективным отображением матрицу перестановки и обратную к ней матрицу (транспонированную матрицу перестановки). Производим преобразование подобия матрицы смежности второго графа, являющееся перестановкой строк его матрицы, соединенной с такой же перестановкой ее столбцов, и сравниваем получ(мпп:.1е матрицы. Если матрицы поэлементно равны, то указанное биективное отображение - изоморфизм, и графы изоморфны. Иначе биективное отображение изоморфизмом не является. Указанная п1)оцедура, очевидно, полиномиальна.В целом, не получено ответа гга па один из следуюпщх вопр()с;он: 1. Задача принадлежит классу Р? 2. Задача является ТУР-полной? 3. Задача принадлежит классу co-NP? Не построено алгоритмов, решавших бы задачу без каких-либо ограничений на структуру проверяемых на изоморфизм графов. Более того, как указывалось еще в [3], до сих пор не известно алгоритмов, которые для графов с п вершинами имели бы верхнюю оценку сложности, меньшую чем 0{п\/п'^), где с - некоторая константа. Рекордным результатом в оценке сложности задачи является теорема Земляченко, в которой утверждается, что изоморфизм графов может быть установлен со сложностью exp(n•^'^ ), где с - некоторая положительная константа [4]. Указывается константа с = 1/3-|-о(1).Нет доказательств и того, что задача принадлежит классу co-NP, то есть нет ответа на вопрос: принадлежит ли классу NP дополнение к задаче, а именно следующая задача: даны два графа; необходимо показать, что между этими графами не существует изоморфизма.Необходимо отметить, что сложность задачи не меняется при переходе от проверки изоморфизма невзвешенных неориентированных графов к проверке изоморфизма взвешенных графов, ориентированных графов [5], мультиграфов [6] .В ходе попыток классифицировать задачу по сложности был введен новый класс задач - класс изоморфизм-полных задач. Этот класс включает в себя задачи, полиномиально сводимые к задаче проверки изоморфизма графов, и к которым полиномиально сводится сама задача проверки изоморфизма графов. Этот класс включает в себя такие задачи, как задача проверки равенства термов [7], задача проверки самодополнительности графов [8], задача проверки дробного изоморфизма, представляющего формальное алгебраическое расширение понятия изоморфизма [9]. В [10] показано, что полиномиально сводимы друг к другу задача проверки изоморфизма графов и следующая задача. Дан такой набор всех подграфов регулярного графа, что каждый подграф получается из исходного графа путем удаления из него о/(,ной вершины. Требуется восстановить исходный граф. В [10| также: гюказано, что полиномиально сводимы друг к другу на машине Тьюринга задача проверки изоморфизма графов и такая же задача, как предыдущая, но без условия регулярности графа. То есть из супд,ествоваиия полиномиального алгоритма для одной задачи следуе-]' существование полиномиального алгоритма для другой.За полиномиальное время к задаче сводимы задача проверки изоморфизма структур, где под структурой понимается множество с набором отношений на нем, и задача проверки изоморфизма групп [5].В [11] найдены необходимые и достаточные условия изоморфизма двух графов, которые сводятся к существованию в симметрической группе порядка 2 т элемента с заданным свойством, где т число ребер в графе. Показано также [11], что группа автоморфизмов Г1)афа изоморфна некоторой подгруппе симметрической группы порядка 2т.Вместе с тем, отдельные ограничения задачи проверки изоморфизма графов, связанные с ограничениями на структуру проверяемых на изоморфизм графов, также являются изоморфизм-полными задачами.Это такие задачи, как задача проверки изоморфизма двудольных графов, регулярных графов [7], хордальных графов, ациклических ориентированных графов [12]. Если какая-либо из этих задач будет помещена в некоторый подкласс класса NP^ то в него будет помещена и задача проверки изоморфизма графов в целом.Поскольку не удается построить полиномиальный алгоритм решения задачи проверки изоморфизма графов, одно из направлений исследований составляет разработка алгоритмов, решающих за полиномиальное время задачи, получаемые выделением из множества всех графов отдельных классов графов с определенными структурными свойствами.Полиномиальные алгоритмы разработаны для планарных графов [13], наиболее часто используемых в приложениях. Алгоритм [14| устанавливает изоморфизм двух деревьев с п вершинами в каждом, заданных списками своих ребер, за время, оцениваемое как 0{п), и требует объема памяти, оцениваемого как 0{п) двоичных log2 п-разрядных ячеек. В [15] представлен алгоритм распознавания изоморфизма планарных графов, требующий 0{п^) операций.Планарные графы представляют собой наиболее; простой cj/учай графов с ограничением на род графа, равный в данном cjiynae нулю. В работе [16] представлен полиномиальный алгоритм для проверки изомо1)физма графов, не стягиваемых на К^д. Указанный класс содержит в себе класс графов рода, не превосходящего д. Построенный ал1Х)ритм применим также к распознаванию изоморфизма графов с ограниченной степенью вершин. Предложенный в [16] метод является обобщением комбинаторного и теоретико-группового подхода к решению задачи. В [17] приведен алгоритм и показано, что изоморфизм графов ограниченного рода д может быть установлен им за время 0{п^^^^).Задача является полиномиально разрешимой для интервальных графов. В [18] представлен алгоритм решения задачи для этого типа графов с трудоемкостью 0{п + т), где п - число вершин в графе, а т число ребер.Полиномиальный алгоритм для графов с ограниченными степенями (валентностями) представлен в [19].Разработаны полиномиальные алгоритмы решения задачи проверки изоморфизма графов с ограниченной кратностью собственных значений спектра матрицы смежности графа. Этот класс графов является одним из наиболее широких классов, для которых разработаны полиномиальные алгоритмы решения задачи. Классический алгоритм, решающий задачу с таким ограничением, представлен в [20]. Алгоритм состоит из двух частей. В первой части, основанной па методах линейной алгебры, вычисляются все собственные значения матриц смежности графов и проекции базисных векторов М" на собственные пространства матриц смежности. Требуется значительная точность для установления равенства собственных значений, равенства проекций и равенства углов между проекциями. Во второй, комбинаторной и теоретико-групповой части алгоритма эта информация используется для установления изоморфизма, если он суш,ествует. или для заключения вывода о его отсутствии.Возникает естественный вопрос, почему на указанных классах графов задача проверки изоморфизма может быть рентена за полиномиальное время? Сун;ествуют ли какие-либо общие свойства графов из этих классов, основываясь на которых можно было бы построить алгоритм, который бы охватывал как можно более широкий класс, оставаясь при этом полиномиальным? Существует ли эффективный концептуально простой алгоритм, удовлетворяющий постав;кип1()му условию на ограниченность некоего фиксированного параметра, обндего для всех указанных классов? Если такой алгоритм сугцествовал вы, то, возможно, он смог бы привести к эффективному рен1ению задачи для новых классов графов, не содержащихся среди извес1Т1ых.Были произведены попытки построения таких алгоритмов. Миллер [21] построил алгоритм решения задачи на классе, объединяюпдем классы графов с ограниченной степенью и ограниче1п-1ым родом. Пономаренко в [22] представил алгоритм, за полиномиальное время проверяющий изоморфизм для графов из всех указанных классов, за исключением класса графов с ограниченной кратностью собственных значений матрицы смежности. Для последнего класса задача может быть решена за полиномиальное время только в том случае, если группы автоморфизмов графов тривиальны, что является весьма суп1,ественным ограничением.Основные трудности в задаче проверки изоморфизма графов возникают в ситуации, когда графы обладают группами автоморфизмов значительной мощности. Наиболее эффективные алгоритмы, построенные для решения задачи, используют информацию о специальном строении группы автоморфизмов и теорию групп подстановок. В [22] приводятся доказательства полиномиальности некоторых таких алгоритмов для графов с ограниченными степенями вершин и их умеренной экспоненциальности (0(ехр(п^'^)), с > 0) для всех графов.Любая конечная группа изоморфна группе автоморфизмов некоторого графа [23]. В [24] показано, что любая конечная группа изоморфна также и группе автоморфизмов некоторого сильно регулярного графа, а как раз изоморфизм регулярных и особенно сильно регулярных графов распознается тяжело. В [25] рассматриваются связи задачи с вопросом о мощности и структуре группы автоморфизмов графа. Показано, что задача проверки изоморфизма графов полиномиально эквивалентна задаче о порядке группы автоморфизмов графа, а также задаче нахождения систем образующих этой группы. Показано, что задача может быть решена за полиномиальное время, если верптины графов, проверяемых на изоморфизм, разбиты на классы ограниченной мопцюсти. В [26[ доказана Л/'Р-полнота задач, связанных с группой автоморфизмов графов, родственных задаче проверки изоморфизма графов. Показано, в частности, что задача проверки наличия в группе автоморфизмов графа автоморфизма без неподвижных точек остаеч-ся Л/'Р-полной, если ограничить ее только автоморфизмами порядка 2.Доказано также, что общая проблема определения, имеет ли г'раф на п вершинах автоморфизм, не оставляюндий на месте по крайней мере £п^^^ верптин, является NР-иолиой для произвольно мaJюгo фиксированного £ И произвольно большого фиксированного к. в [27] вводится задача, состоящая в определении, является ли к делителем количества автоморфизмов графа. Показывается, что введенная задача в иерархии сложности занимает промежуточное положение между задачами проверки изоморфизма графов и поиска всех автоморфизмов графа.Одним из подходов к решению задачи проверки изоморфизма графов могла бы быть непосредственная проверка возможности получения матрицы смежности одного из графов некоторой перестановкой рядов матрицы смежности другого графа. В наихудшем случае нам необходимо проверить все возможные перестановки рядов одной из матриц смежности, что неизбежно влечет экспоненциальность любого из алгоритмов такого типа. Однако, рассмотрение таких инвариантов матриц смежности графов как характеристический многочлен, спектр и собственные векторы приводит к спектральному подходу к рептнию задачи проверки изоморфизма графов [28], существенно более эффективному.Теорию графов можно отождествить с теорией матричных классов, состоящих из матриц смежности изоморфных графов, и их инвариантами. Одними из наиболее содержательных инвариантов такого матричного класса являются характеристический многочлен матрицы PGAW = Ио - А/| и ее спектр Sp{Ao) = {Ль . . . , Л„}, где AQ одна из матриц,, принадлежащая такому классу. Вместе с тем, как и все остальные инварианты, спектр матрицы смежности графа и ее характеристический многочлен не являются полными инвариантами, то есть совпадение их для графов не является достаточным условием их изоморфизма.В [29] представлен алгоритм установления изоморфизма графов, основанный на использовании собственных значений матриц смежности графов в качестве инварианта.В [30] приводится эвристический алгоритм, основанный на использовании введенных в [31] инвариантов графов. В вычислительной части алгоритма сравниваются инварианты исследуемых графов. В с:лучае совпадения этих инвариантов в проверочной части осуществляется поиск подстановки, устанавливающей изоморфизм. Если ни (удной такой подстановки не найдено, то графы составляют контрпример к алгоритму. Аналогично решается задача определения орбит rpyinn:>i.Инвариант, приводимый в [32], представляет собой некоторую каноническую матрицу, элементы которой характеризуют связи мс^ жду ярусами графа при подвешивании его за некоторую вернлину. Вершины графа могут разбиться на классы по составу строк капоничснжой матрицы. Известно, однако, что для сильно регулярных графов разбиения не происходит.В [33] представлено построение оптимального кода для извлечения свойств, определяющих изоморфизм графов. Кодом неориентированного графа без петель при заданной нумерации верпшн называется двоичное число, полученное последовательным приписыванием строк верхнего треугольника матрицы смежности вершин. Та из нумераций вершин, для которой получаемое двоичное число является наибольшим, реализует оптимальный код. Излагаются два алгоритма нахождения оптимального кода. Второй алгоритм применим только к регулярным графам. Необходимая информация представлена матрицей смежности вершин и матрицей минимальных расстояний между вершинами. Для изоморфных графов получаемые оптимальные коды совпадают. в [33] вводится следующий инвариант. Пусть G^ - граф, А его матрица смежности. Если граф GA изоморфен графу GB, то |Л—Л/| = = \В — Л/| . Матрице А сопоставляется два многочлена от п переменных, коэффициенты первого из которых являются инвариантами относительно перестановки строк Л, коэффициенты второго инварианты относительно перестановки ее столбцов.В [34] описывается алгоритм установления изоморфизма графов, основанный на использовании матриц расстояний и матриц кратностей кратчайших цепей между всеми парами вершин. В том случае, когда эти средства не дают возможности различать проверяемые на изоморфизм графы, происходит обраи;ение к вычислению характеристических полиномов матриц смежности графов, и, наконец, к канонизации и полному перебору.В [35,36] излагается метод исследования инвариантов изоморфных графов, который базируется на представлении графов полиномами над конечными полями.Подчеркнем, что полной системы вычисляемых за пoлинoмиaJп>нoe время инвариантов изоморфных графов построить пока не удалось.Помимо ограничений на структуру проверяемых графов получил распространение подход, состояП1,ий в построении а;п'ори'1'мов ориентированных на уменьшение вычислительной сложносгги за счет адекватного представления процесса поиска изоморфизма и отсечении заведомо неудачных путей в пространстве поиска. В этом случае не налагается никаких ограничений на структуру проверяемых на изоморфизм графов, однако трудоемкость таких алгоритмов может брять оценена только статистически, что является существенным минус;ом.Одной из первых публикаций, представляющих собой такой подход, была работа Корнейла и Готлиба [37], в которой был представлен алгоритм, осуществлявший некоторые преобразования графов, позволяющие ускорить процесс проверки изоморфизма. Однако, в [38] было показано, что предположение, на котором основан метод, ис. всегда справедливо, что ограничивает его применимость.Значительная часть эффективных в среднем алгоритмов основана на прямом построении в ходе работы алгоритма отображения множества вершин одного графа на множество вершин второго графа, являющегося изоморфизмом. В основе такого подхода лежит идея, заключающаяся в таком выборе на каждой итерации алгоритма вершин из каждого графа, который сохранял бы изоморфизм подграфов, col l стоящих из уже выбранных вершин и всех инцидентных им ребер проверяемых на изоморфизм графов, соединяюш,их выбранные вершины.Выбор пар по одной вершине из каждого графа продолжается до тех пор, пока подграфы не будут достроены др собствеьпю самих графов, изоморфизм которых проверяется. Алгоритмы, использующие подобный подход, представляют собой некоторые вариации реализации процедуры backtracking (рекурсии с возвратом): в ходе работы подобных алгоритмов поиск происходит согласно некоторому дереву поиска, и в наихудшем случае такой, пусть и сокращенный перебор, приводит к экспоненциальности данного алгоритма.В [39] описывается алгоритм, рекурсивно разбивающий на классы эквивалентности параллельно множество вершин и множество ребер графа. Исходное разбиение может быть выбрано произвольным образом (например, разбиение множества вершин по степеням). Число действий алгоритма оценивается в среднем как 0{п^).Алгоритмом, значительно сужающим на каждой и']х-;рации H])OC'I^ ранство перебора, является алгоритм, предложенный Улльманом |4()|.Этот алгоритм предназначен как для задачи проверки изоморфизма графов, так и для задачи проверки изоморфизма подграфу. Этот алгоритм до сих пор является одним из наиболее применяемых алгоритмов для решения задачи проверки изоморфизма графов. Он является одним из тестовых алгоритмов при проверке эффективности д})угих алгоритмов решения задачи.Другая реализация схемы перебора с возвратом - ал1юритм, разработанный Шмидтом и Дрюффелем [41]. Этот алгоритм испо;п>зует информацию, содержащуюся в матрице расстояний графа, для формирования начального разбиения вершин графа. Под матрицей расстояний графа понимается матрица, в (г, j)-пoзиции которой находится длина кратчайшей цепи между вершинами i и j . Построенное с использованием матрицы расстояний начальное разбиение иси();н>зуется в дальнейшем для уменьшения дерева поиска при реализации рекурсии с возвратом. Относительно более поздний алгоритм, использующий целый набор правил, позволяющих существенно уменьншть дерево поиска, - VF-алгоритм [42].Алгоритм, основанный на backtracking'e, предлагается в [43j. На каждом этапе подразбиения текущего разбиения множества вершин графа на классы, инвариантные относительно автоморфизма графа, используется алгоритм с числом действий 0 ( п l o g п ) , минимизирующий число состояний в конечном автомате.Одним из наиболее эффективных на данный момент является алгоритм NAUTY МакКэя [44]. Основа алгоритма - построение поискового дерева с вершинами, являющимися упорядоченными разбиениями множеств вершин исходного графа [45]. Начальное разбиение состоит из одного класса - самого множества вершин графа, окончательные разбиения содержат по одной вершине в каждом классе. Следующее разбиение в поисковом дереве получается из предыдущего выделением некоторой вершины в отдельный класс и применением к полученному таким образом промежуточному разбиению оператора продолжения разбиения. В качестве этого оператора используется обычная процедура многократного итерирования разбиения множества вершин графа по степеням. Алгоритм содержит некоторые средства, позволяющие исключить из рассмотрения части поискового дерева. Хотя алгоритм NAUTY рассматривается как один из наиболее эффективных, было показано, что есть категории графов, проверка изоморфизма которых имеет для него экспоненциальную сложность [461.Другой возможный подход к решению задачи представлен в |47|.Вместо снижения сложности сравнения двух графов, авторы пытаюч'ся снизить общую вычислительную сложность алгоритма, сравни15ая граф с большим набором графов-прототипов. Этот метод имеет сложность 0{п^) вне зависимости от количества имеюпщхся ripo'i'OTHrioi3, но объем необходимой для храпения графов-прототипов памя']'и возра^;тает экспоненциально с ростом числа верншн графов, проверяемых на изоморфизм, в связи с чем этот метод является эффективным только для графов с небольшим числом вершин.Все указанные выше алгоритмы нацелены на точный поиск изоморфизма графов, то есть они предъявляют биективное отображение, являющееся изоморфизмом, в случае если таковое суп1,ествует. В последнее время, растет число алгоритмов, способных находит1:> приближенные решения задачи. Такие алгоритмы, представленные в |48"50], имеют полиномиальную вычислительную сложность, но они не гарантируют нахождения точного решения поставленной задачи.В данной работе предлагается алгоритм проверки изоморфизма графов, основанный на применении методов линейной алгебры и ее численных методов, являющийся продолжением работы [51]. Предлагаемый алгоритм всегда дает решение задачи проверки изоморфизма для двух графов из класса графов, определяемого в представляемой работе. Определение данного класса графов тесно связано с понятием изоморфизма графов. Проверить, принадлежит ли проверяемые на изоморфизм графы данному классу можно в ходе работы алгоритма.Отметим, однако, что в ходе многочисленных вычислительных экспериментов не было найдено ни одного графа, который бы данному классу не принадлежал. В частности, классу принадлежат графы дог"гупные из электронных библиотек тестовых задач проверки изоморфизма графов, на которых тестируются наиболее эффективные алгоритмы реп1ения задачи. В класс входят и графы, являющиеся традиционно наиболее сложными для проверки изоморфизма графов.В ходе итератщй алгоритма происходит согласованное возмундение модифицированных матриц смежности, представляюп1,их графы. Группа автморфизмов графов с простым спектром может состоять только из инволюций, что упрощает задачу проверки изоморфизма графов, хотя расщепление всех собственных значений матриц смежности при некоторых их возмущениях, еще не свидетельствует о тривиальности группы автоморфизмов графов. Тогда как именно для графов с тривиальной группой автоморфизмов установление изоморфизма происходит наиболее эффективно. На приведении исходных невзвеше[П1Ых неориентированных графов к графам, содержащим петли с заданными на них весами, которые обладали бы тривиальной группой автоморфизмов, основывается алгоритм, предлагаемой в данной работ(\ Вычисление всех собственных значений и собстве1пп>1х векторов с необходимой точностью является задачей, обладающей значи^'ельной вычислительной сложностью. Поэтому предлагаемый ajH'opn'i'M i^ . качестве эвристики использует не собственные значения и собственные векторы матриц, поставленных в соответствие графам, а обратные матрицы к модифицированным матрицам смежности графов и их согласованные изменения, происходящие при возмущениях. Связь подхода, предлагаемого в [51], и изложенного в этой работе рассматривается в параграфах 2.1 и 2.3 работы.Алгоритм работает с модифицированными до положителыкз определенных матрицами смежности графов и основан на рептнии связанных с ними систем линейных уравнений. Алгоритм является прямым в том смысле, что при решении задачи проверки изоморфизма графов не происходит перебора вариантов в соответствии с некоторым деревом поиска, рост которого па некотором этапе работ1>1 алго})итма мог бы стать неконтролируемым. Изоморфны графы или нет ycTanaejmвается не более чем за п итераций алгоритма, где п - число верншн в графе. В случае изоморфизма графов предъявляется один из возможных изоморфизмов.Материал диссертации расположен следующим образом.В главе 1 приведена постановка задачи проверки изоморфизма графов и введены основные термины, используемые в рабочее.В главе 2 изложен предлагаемый алгоритм проверки изоморфизма графов и приведено его теоретическое обоснование. Рассмотрена трудоемкость алгоритма, как величина, зависяндая от количества итераций решения систем линейных уравнений. Приведен пример, иллюстрирующий работу алгоритма.В главе 3 исследована вычислительная эффективность алго])итма и получена оценка его трудоемкости, справедливая для (пирокого класса графов.В главе 4 показана возможность приложения построенного алгоритма для проверки изоморфизма взвешенных неориентированных графов, решения задачи проверки эквивалентности ма^'риц с точностью до перестановок строк и столбцов и задачи деилифрования нплфра двойной перестановки.В главе 5 показана возможность приложения пост^зоенного алгоритма для проверки изоморфизма ориентированных 1'рафов и Myjn.тиграфов.В главе б производится построение алгоритма приближенного поиска оптимального вложения графа.В главе 7 рассматривается возможность использования ал1Х)ритмов решения задачи проверки изоморфизма графов (в том числе и предложенного в работе алгоритма) для построения защищенного видеоканала.В заключении содержатся основные выводы работы.Основные результаты диссертации: 1. Построен прямой алгоритм проверки изоморфизма графов, основанный на методах линейной алгебры, решающий задачу для ninpoKoго класса графов не более чем за п итераций, где п число вершин в графах, проверяемых на изоморфизм.2. Доказано утверждение, характеризующее вычиcлитeJн^пyю CJЮжность алгоритма. Показано, что алгоритм является полиномиальным по используемой памяти, являясь также полиномиальным по времени, вне зависимости от структурных особенностей проверяемых на изоморфизм графов: те из графов с ограниченной степенью верил ин и графов с ограниченной кратностью собственных значений, которые находятся в классе графов, для которого алгоритм дает решение задачи, не имеют при решении задачи представляемым алгоритмом специфики, обычной для других алгоритмов решения задачи.3. Показана применимость модификации алгоритма к решению задач проверки изоморфизма ориентированных, взвенленных графо!', и мультиграфов.4. Предлагается применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок их ст]юк и столбцов. Возможность решения этой задачи, в свою очередь, позволяет реншть задачу дешифрования шифра двойной перестановки.5. На основе эвристики, используемой для проверки изоморфизма графов, построен алгоритм приближенного решения задачи поиска оптимального вJЮжeния графа.6. Предложено приложение задачи проверки изомо])физма графов и предложенного ajn^pnTMa к репюнию задачи построения защищенного видеоканала.Основные результаты работы опубликованы автором в работах |5261]. Результаты докладывались на конференции «Дискре^[Т1ый анализ и исследование операций» (г. Новосибирск, 2002 г., 2004 г.), на сс^минаре академика РАН К. Годунова, на ХП-й Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2003), на семинаре Института систем обработки изоб])ажений РАН (г. Самара), на 11-й Всероссийской конференции «Математические методы распознавания образов» (г. Пущино, 2003), на с;еминарах кафедры информационной безопасности Омского государсл'венного университета.Все результаты, выносимые на защиту, получены автором лично.В заключении введения автор выражает благодарность научному руководителю Р.Т. Файзуллину за постоянное внимание к работе.

Заключение диссертации по теме «Теоретические основы информатики», Пролубников, Александр Вячеславович

ЗАКЛЮЧЕНИЕ

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

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

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

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

На основе эвристики, используемой для проверки изоморфизма графов, построен алгоритм поиска в графе подграфа, изоморфному данному. Данный алгоритм представляет собой подход к решению задачи распознавания образов. Так изображению в соответствие ставится его некоторый скелетный граф, и проверяется его близость в смысле предложенной эвристики к одному из предложенных шаблонов. Как показал вычислительный эксперимент, в случае если скелетный граф изображения и граф шаблона имеют одинаковое количество вершин, то разница в количестве ребер графа шаблона и скелетного графа изображения может составлять до 20-30% от общего количества ребер в скелетном графе изображения при устойчивой работе алгоритма.

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

Список литературы диссертационного исследования кандидат физико-математических наук Пролубников, Александр Вячеславович, 2004 год

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи М.: Мир, 1982. С. 194.

2. Cook, S.A. The complexity of theorem-proving procedures // Proc. of the 3rd Annu. ACM Symp. on Theory of Comput., Shaker Heights, Ohio, United States, 1971. PP. 151-158.

3. Земляченко B.H. Об алгоритмах идеификации графов // Вопросы кибернетики. Вып. 15. М., 1975. С. 33-41.

4. Babai, L. Modei^ately exponential bound for graph isomorphism // Lect. Notes in Comput. Sci., 1981, 117. PP. 34-50.

5. Miller, G.L. Graph isomorphism, general remarks // Conf. rec. 9th Annu. ACM Symp. Theory Comput., Boulder, Colo, 1977. New York, 1977. PP. 143-150.

6. Fontet, M. Automorphisms de graphs et planarite // Asterisque, 3839, 1976. PP. 73-90.

7. Hoffmann, C.M., Group-Theoretic Algorithm,s and Graph Isomorphism /7 Lect. Notes in Comput. Sci., Chapter V, 1982. PP. 127-138.

8. Colbourn, M.J., Colbourn, C.J. Graph isomorphism and self-complementary graphs // SIGAST News 10, № 1, 1978. PP. 25-29.

9. Ramana, M.V., Scheinerman, E.R., Ullman, D. Fractional isomorphism of graphs // Discrete Mathematics. 132, № 1-3, 1994. PP. 247-265.

10. Mansfield, A. The relationship between the computational complexities of the legitimate deck and isomorphism problems // Quart. J. Math., 33, № 131, 1982. PP. 345-347.

11. Островерхая JI.Д., Островерхий Н.А. Критерий изоморфизма и группа автоморфизмов графа // Теория графов. Киев, 1977. С. 63* 70.

12. Schnitzler, М. Graph grammars and the complexity gap in the isomorphism problem for acyclic digraphs // Lect. Notes in Comput. Sci., Chapter V, 100, 1981. PP. 137-149.

13. Hopcroft, J., Wong, J. A linear time algorithm for isomorphism of planar graphs jj Proc. of the 6til Annu. ACM Symp. on Theory of Comput, 1974. PP. 172-184.w

14. Земляченко B.H. Установление изоморфизма деревьев // Вопросы кибернетики. М, 1973. С. 54-60.

15. Попков В.К. Об одном способе проверки изоморфизма плоских графов // Вычислительные системы. Вып. 54. Новосибирск, 1973. С. 139-145.

16. Пономаренко И.Н. Полиномиальный алгоритм проверки изоморфизма для графов, не стягиваемых на К^д // Записки научных семинаров Ленингр. отд. инст. математики АН СССР, 137. Л.: Наука. 1984. С. 99-114.

17. Земляченко В.Н., Корнеенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов Записки научных семинаров Ленингр. отд. инст. математики АН СССР, 118. Л.: Наука. 1982. С. 83-158.

18. Lucker, G. S., Booth, К. S. A linear time algorithm for detecting interval graph isomorphism //J. Comput. Mach., 26, 2, 1979. PP. 183-195.

19. Luks, E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time // Journ. of Comput. System Sci., 1982. PP. 42-65.

20. Babai, L., Grigoryev, D.Y., Mount, D.M. Isomorphism of graphs with bounded eigenvalue multiplicity // Proc. 14th ACM Symp. on Theory of Comput,., STOC, 1982. PP. 310-324.

21. Miller, G. Isomorphism of k-contractible graphs, a generalization of bounded valence and bounded genus // Information and Control, 56, 1983. PP. 1 20.

22. Пономаренко И.Н. Задача проверки изоморфизма для класов графов 11 Доклады АН СССР. 304, № 3, 1989. С. 552-556.

23. Frucht, R. Herstellung von graphen mit vorgegebener abstrakten gruppe // Compositio math., 6, 1938. PP. 239-250.

24. Mendelsohn, E. Every (finite) group is the group of automorphisms of a (finite) strongly regular graph // Ars combinatoria, 6, 1978. PP. 7586.

25. Babai, L. Isomorphism testing and symmetry of graphs. Combinatories' 79. Part 1. Amsterdam e.a., 1980. PP. 101-109

26. Lubiw, A. Som,e NP-complete problems similar to graph isomorphism 11 SIAM J. Comput., 10, № 1, 1981. PP. 11-20.

27. Arvind, V., Beigel, R., Lozano, A. The complexity of modular graph isomorphism SIAM J. Comput., 30, № 4, 2000. PP. 1299-1320.

28. Цветкович Д. и др. Спектры графов. Теория и применение Киев: Наукова думка, 1984.

29. Johnson, C.R., Leighton, F.T. An efficient linear algebraic algorithmfor determination of isomorphism of directed graphs // J. Res. Nat. Bur. Stand, B80, № 4, (1976) 1977. PP. 447 483.

30. Кохов B.A., Лазарев В.А. Алгоритм идентификации обыкновенных графов Тр. Моск. Энерг. ин-та. Вып. 299, 1976. PP. 53-60.

31. Кохов В. А .Об одной инварианте графов Тр. Моск. Энерг. ин-та. Вып. 178, 1974. PP. 154-160.

32. Shah, Y.J, Davida, G.I. Construction of an optimum code for feature extraction to determine isomorphism of graphs // IEEE Syst, Man and Cybern. Soc. Proc. Int. Conf. Cybern and Soc. Boston, Mass, 1973. New York, N.Y, 1973. PP. 76-80.

33. Masuyama Motosaburo A test for graph isomorphism // Repts. Statist. Appl. Res. Union Jap. Sei. and Eng, 20, № 2, 1974. PP. 41-64.

34. Гринберг Э.Я, Кац А.О. Использование некоторых инвариантных характеристик для установления изоморфизма графов // Латвийский мат. ежегодник, 21, 1977. С. 124-135.

35. Малов K.M., Бариева H.A. Об инвариантах изоморфизма орграфов Тр. Моск. Энерг. ин-та, № 499, 1980. С. 111-118.

36. Малов K.M., Бариева H.A. Об одной системе инвариантов изоморфизма графов Кибернетика, № 6. Киев, 1988. С. 116-117.

37. Cornell, D.G, Gotlieb, С.С. An efficient algorithm for graph isomorphism //J. Assoc. Comput. Mach, 17, 1970. PP. 51-64.

38. Math on, R. Sample graphs for isomorphism testing / / Congressus Numeratium, 21, 1978. PP. 499-517.

39. Levi, G. Graph isomorphism: a heuristic edge-partitioning-oriented algorithm // Computing, 12, № 4, 1974. PP. 291-313.

40. Ullmann, J.R. An algorithm, for subgraph isomorphism, //J. Assoc. Comput. Mach, V. 23, 1976. PP. 31-42.

41. Schmidt, D.C, Druffel, L.E. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices // J. Assoc. Comput. Mach, vol. 23, 1976. PP. 433-445.

42. Cordella, L.P, Foggia, P, Sansone, C, Vento, M. Evaluating perfomance of the VF graph matching algorithm// Proc. of the 10i/l Int. Conf. on Im. Anal, and Process, IEEE Computer Society Press, 1999. PP. 1172-1177.

43. Kubo Noboru, Shirakawa Isao, Osaki Hiroshi A fast algorithm for testing graph isomorphism // Int. Symp. Circuits, and Syst. Proc, Tokyo, 1979. PP. 641-644.

44. McKay, B.D. Practical graph isomorphism / Congressus Numeratium, 30, 1981. PP. 45-87.

45. McKay, B.D. Computing automorphisms and canonical labelings of graphs. // Lect. Notes Math., № 686, 1978. PP. 223-232.

46. Miyazaki, T. The complexity of McKay's canonical labeling algorithm // Groups and Computation, II, Amer. Math. Soc., Providence, RI, 1997. PP. 239-256.

47. Bunke, H., Messmer, B.T. Efficient attributed graph matching and its application to image analysis // Image Analysis and Processing, Springer, Berlin Heidelberg, 1995. PP. 45-55.

48. Christmas, W.J., Kittler, J., Petrou, M. Structural matching in computer vision using probabalistic relaxation // IEEE Trans. Pattern and Machine Intelligence, V. 17, № 8, 1995. PP. 749-764.

49. De Jong, K.A., Spears, W.M. Using genetic algorithms to solve NP-complete problems // Genetetic Algorithms, Morgan Kaufmann, Los Altus, CA, 1989. PP. 124 132.

50. Kuner, P., Ueberreiter, B. Pattei-n recognition by graph matching combinatorial versus continuous optimization // Int. J. Pattern Recognition and Artif. Intell., V. 2, № 3, 1988. PP. 527-542.

51. Кикина А.Ю., Файзуллин P.Т. Алгоритм проверки изоморфиости графов Деп. ВИНИТИ 21.06.95 1789 В95.

52. Пролубников А.В., Файзуллин Р.Т. Эвристический алгоритм; дешифрования шифра двойной перестановки // Математические структуры и моделирование. Сб. научн. тр. Под ред. А.К. Гуца. Омск: Омск. гос. ун-т, 2002. Вып. 9. С. 62-69.

53. Пролубников А.В., Файзуллин Р.Т. Алгоритм спектрального расщепления для дешифрования шифра двойной перестановки // Материалы конференции «Дискретный анализ и исследование операций». Новосибирск, изд. инст. математики. 2002. С. 216.

54. Faizullin R., Prolubnikov A. An algorithm of the spectral splitting for the double permutation cipher // Pattern Recognition and Image Analysis. MAIK, Nauka. Vol. 12, No. 4, 2002. PP. 365-375.

55. Пролубников А.В., Файзуллин Р.Т. О вычислительной эффективности алгоритма спектрального расщепления проверки изоморфизма графов // Компьютерная оптика. Сб. научн. тр. Изд. Самарского гос. университета, 2002. Вып. 24. С. 136-143.

56. Пролубников A.B. Алгоритм поиска приближенного решения задачи проверки изоморфизма подграфов // Математические структуры и моделирование: Сб. научн. тр. Под ред. А.К. Гуца. Омск: Омск. гос. университет, 2003. Вып. 10. С. 59-66.

57. Пролубников A.B., Файзуллин Р.Т. Алгоритм спектрального расщепления проверки изоморфизма графов и его прилошсения // Математические методы распознавания образов. Доклады 11 -й Всероссийской конференции. Москва, 2003. С. 162 164.

58. Като Т. Теория возмущений линейных операторов М.: Мир, 1972.

59. Годунов С.К. и др. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах Новосибирск: Наука, 1988.

60. Беллман Р. Введение в теорию матриц М.: Наука, 1976.

61. Гантмахер Ф.Р. Теория матриц М.: Наука, 1976.

62. Бахвалов Н.С. Численные методы М.: Наука, 1975. Т. 1.

63. Baker, B.S. Approximation algorithms for NP-complete problems on planar graphs //J. Assoc. Comput. Mach. 1994. V. 41. P. 153-180.

64. Васильков В.В. О задаче определения изоморфности двух графов // Инж.-мат. методы в физ. и кибернет. М.: Атомиздат, 1973. Вып. 3. С. 47-48.

65. Bunke, Н. On a relation between graph edit distance and maximum common subgraph // Pattern Recogn. Lett. 1997. V. 18, N. 8. P. 689694.

66. Bunke, H., Schearer, K. A Graph distance metric based on the maximal common subgraph // Pattern Recogn. Lett. 1998. V. 19, N. 3-4. PP. 255 259.

67. Foudree, R.J., Schelp, R.H., Lesniak, L., Gyarfas, A., Lehel, J. On the rotation distance of graphs Discrete Math., 126, № 1-3, 1994. PP. 121 135.

68. Корнеенко H.M. О слоэюности вычисления расстояния между графами Изв. АН БССР. Сер. физ.-мат. н. № 1, 1982. С. 10-13.

69. Шикин Е.В., Боресков А.В. Компьютерная графика М.: Мир, 1995.

70. Sobik, F., Sommerfcld, Е. Klassifikation strukturievter objekte auf der izomorphie von untergraphen // Rostock Math. Kolloq., № 10, 1978. PP. 97-102.

71. Володин А.А., Митько В.Г., Спинко Е.Н.Обработка видео в системах телевизионного наблюдения // Вопросы защиты информации. М.: 2002. С. 34-47.

72. Иванов М.А.Криптографические методы защиты информации в компьютерных системах и сетях М.: КУДИЦ-ОБРАЗ, 2001, С. 365-375.