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

ПРОЛУБНИКОВ Александр Вячеславович

На правах рукописи

оф^

ПРЯМОЙ АЛГОРИТМ ПРОВЕРКИ ИЗОМОРФИЗМА ГРАФОВ

05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Самара - 2004

Работа выполнена на кафедре информационной безопасности Государственного образовательного учреждения высшего профессионального образования "Омский государственный университет"

Научный руководитель: доктор технических наук, доцент

Рашит Тагирович Файзуллин

Официальные оппоненты: доктор физико-математических наук,

профессор

Владимир Михайлович Чернов

кандидат физико-математических наук, доцент Виктор Петрович Цветов

Ведущее предприятие: Институт математики и механики

Уральского отделения РАН

Защита состоится "3" ^С^саЬ^^ 2004 г. в часов на заседании диссертацйонного совета Д 212.215.07 при ГОУ ВПО "Самарский государственный аэрокосмический университет имени академика СП. Королева" (СГАУ) по адресу 443086, Самара, Московское шоссе, 34, ауд. 209.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан 2004

Ученый секретарь диссертационного совета

И.В. Белоконов

г

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Дискретные структуры являются фундаментальной основой информатики. Одними из важнейших таких структур являются графы. Сведения из теории графов широко используются не только в организации структур данных и разработке алгоритмов, но и во всех остальных разделах информатики. Графы являются удобным языком для формулировки и эффективным инструментом для решения задач относящихся к широкому кругу проблем. Можно упомянуть в этой связи вопросы конструирования систем автоматизированного проектирования программирования для ЭВМ и создания операционных систем, исследования операций и управления, а также ряда задач экономики, статистики и теоретической физики, теории информации, социологии, математической лингвистики.

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

Задача проверки ИГ принадлежит к тем задачам, которые не удается классифицировать относительно их сложности [1]. До сих пор не разработано полиномиальных алгоритмов проверки изоморфизма произвольных, без ограничений на структуру графов. Не доказано, однако, что данная задача является TVP-полной. Не доказано также, что задача принадлежит классу еа-ЫР.

Распространенным подходом к решению задачи проверки ИГ является определение классов графов таких, что ограничение на них задачи принадлежит классу Р. К таким классам относятся планарные графы и вообще графы с ограничением на род графа, графы с ограниченной степенью вершин, графы с ограниченной кратностью собственных значений спектра матрицы смежности и некоторые другие [2], [3].

Возникает вопрос, что именно позволяет решать задачу проверки ИГ для этих классов графов, есть ли в этих классах нечто общее, что дает возможность эффективного нахождения решения задачи? Существует ли эффективный, концептуально простой и общий алгоритм для объединения некоторых классов графов или для всех них? Если бы такой алгоритм существовал, то он привел бы к появлению некоторых новых классов графов, для которых задача решается эффективно. Под «эф-

Г'ЧЙКЯЯГ

I ¿тем

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

Наиболее эффективными алгоритмами решения задачи, дающими решение задачи для произвольных графов, являются алгоритм, предложенный Улльманом [4], алгоритм, разработанный Шмидтом и Дрюффе-лем [5], УБ-алгоритм [б], алгоритм NAUTY МакКэя [7]. Однако, все эти алгоритмы экспоненциальны для общего случая задачи.

Полиномиальный алгоритм (Бабаи, Григорьев, Маунт) [8], имеет наиболее широкую область эффективного применения (графы с ограниче-ной кратностью собственных значений спектра), более широкую, нежели у любого из других разработанных полиномиальных алгоритмов проверки ИГ.

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

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

Основные задачи работы:

• построить алгоритм решения задачи проверки ИГ, основанный на методах линейной алгебры; использование комбинаторых методов при этом должно быть сведено к минимуму;

• исследовать вычислительную эффективность построенного алгоритма как относительно зависимости времени работы алгоритма от количества вершин в графах, проверяемых на изоморфизм, так и относительно объёма памяти, используемого алгоритмом в ходе работы;

• исследовать возможность применения построенного алгоритма к различным типам графов;

• исследовать возможность модификации построенного алгоритма до алгоритма решения задачи проверки изоморфизма подграфу;

• реализовать алгоритм программно и опробовать его для приклад-

ных задач, непосредственно связанных с задачей проверки ИГ.

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

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

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

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

Апробация работы. Результаты работы докладывались на конференции «Дискретный анализ и исследование операций» (г. Новосибирск, 2002, 2004 гг.), семинаре академика РАН С.К. Годунова, на ХИ-й Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2003), на семинаре Института систем обработки

изображений РАН (г. Самара), на 11-й Всероссийской конференции «Математические методы распознавания образов» (г. Пущино, 2003), на семинарах кафедры информационной безопасности Омского государственного университета.

Публикации. Основные результаты диссертации опубликованы в 10 печатных работах

Все выносимые на защиту результаты получены автором лично.

Основные положения, выносимые на защиту:

• алгоритм проверки ИГ и его теоретическое обоснование;

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

• приложения алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок строк и столбцов, к решению задачи дешифрования шифра двойной перестановки;

• предложенный алгоритм решения задачи поиска оптимального вложения графа.

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения и списка литературы. Общий объем работы составляет 99 страниц. Библиографический список насчитывает 76 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе диссертации дается постановка задачи и вводятся основные понятия, используемые в диссертации.

Постановка задачи 1. Даны два невзвешенных неориентированных графа £?л(Уа, Ед) и Сд(Ув, Ев), где Уа, Ув - множества вершин графов, Еа, Ев - множества ребер графов. |Уд| = \Ув\, \Еа\ = \Ев\- Графы (7 4 (Уд, Еа) и С?в(Ув, Ев) изоморфны тогда и только тогда, когда существует биективное отображение ф : Ув —У а такое, что {г, 2) € Ев

(viOiVCi)) ^ Ед. Требуется найти такое <р, или доказать, что его не существует.

Будем обозначать далее изоморфизм графов Ga и Gb как «Ga — Gq». Пусть Ао - матрица смежности невзвешенного неориентированного графа

q0 _ | 1, если (i,j) Е Еа,

- матрица смежности графа

Биективному отображению <р : Vb Va однозначно соответствует перестановка Р^,, действующая на множестве вершин графа Ga- Если Pv представлена матрицей перестановки (также обозначаемой Pv), то Р является изоморфизмом тогда и толвко тогда, когда .А = Р^ВР'1, где А - матрица смежности графа Ga, В - матрица смежности графа Gb-

Постановка задачи 2. Данв1 два невзвешеннвгх неориентированнвгх графа Ga{Va,Ea) и Gb{Vb,Eb). \Va\ = \VB\, \ЕА\ = \ЕВ\. Ао, В0 - мат-рицв1 смежности графов Ga, Gb. Требуется найти матрицу перестановки Р такую, что Ад = PBqPили показатв, что ее не существует.

Биективное отображение и соответствующая ему перестановка действующие на множестве вершин графа GA, называются автоморфизмом графа Ga, если они сохраняют смежность его вершин. Если Р представлена матрицей перестановки (также обозначаемой Р), то Р является автоморфизмом тогда и только тогда, когда А — РВР~где А - матрица смежности графа GA. Автоморфизмы графа GA образуют группу Г = Г^См), назвшаемую группой автоморфизмов г р а ф(ЗХр у п п а i автоморфизмов графа реализуется множеством всех матриц перестановок Р, коммутирующих с матрицей смежности А графа GA-

Орбитой вершинв1 г £ V относителвно Г(С?) графа G назвшается множество 0(г), состоящее из всех таких вершин j £ V, что 3ip G Г(С?) т.ч. ip(i) — j, то есть 0(i) = {у(г)| f € Г(С?)}. Орбиты вершин графа относительно его группы автоморфизмов представляют собой непересекающиеся классы эквивалентности вершин.

Во второй главе излагается предлагаемый алгоритм проверки ИГ, доказываются утверждения лемм, обосновывающих его работу.

В первом параграфе изложены используемые элементы спектрального подхода к решению задачи проверки ИГ и указаны главные стоящие перед ним сложности.

Во втором параграфе главы 2 дается постановка задачи в терминах рабочих матриц предлагаемого алгоритма проверки ИГ и доказывается

ее эквивалентность постановкам задачи, приведенным выше. Доказываются леммы, ключевые для теоретического обоснования работы алгоритма.

Матрицы смежности, представляющие графы, видоизменяются до положительно определенных. Пусть Ао - матрица смежности графа В соответствии с матрицей Ао строим диагональную матрицу И/^ со следующими элементами на диагонали:

где - максимальная степень вершин в графе - степень вер-

шины 1. Аналогично по матрице Во строится матрица Пд0. Матрицы, с которыми работает алгоритм, имеют следующий вид:

Постановка задачи 3. Даны два невзвешенных неориентированных графа Са(Уа,Еа) и Св{Ув,Ев). \Уа\ = |Ы \ЕА\ = \ЕВ\.А, В - матрицы вида (1) для графов С?в- Требуется найти матрицу перестановки Р такую, что А = РВР~1, или показать, что ее не существует.

Справедливость следующих двух лемм позволяет утверждать эквивалентность постановки 3 задачи постановкаам задачи 1 и 2.

Лемма 1. Если = Св, то существует матрица перестановки Р, такая что А = РВР~Х. ■

Лемма 2. Если Сд ^ Св, тоне существует матрицы перестановки Р такой, что А = РВР~Х. ■

Рассматриваются следующие системы линейных уравнений:

где е^- = (0,... ,0,1,0,... ,0) - ,7-ый орт в про стран с Же а матрицы А и - матрицы, построенные по матрицам смежности графов так, как показано выше. Матрицы - симметрические положитель-

но определенные матрицы. Каждая система линейных уравнений из (2) имеет решение, и решение единственно, так как матрицы - мат-

рицы с диагональным преобладанием и их определители не равны нулю. Обозначим как х^ решения систем уравнений Ах — как у к - решения

систем уравнений Ву = е*. х^, ук - столбцы обратных к А и В матриц, и А = РВР~1 тогда и только тогда, когда Л-1 = РВ~1Р~1.

Решая системы уравнений (2), в качестве решений мы получаем столбцы обратных матриц к матрицам Ли В, так как для 1-й компоненты вектора х] справедливо: Хц = Лу/|А|, где А,^ - алгебраическое дополнение элемента ау матрицы А.

Введем следующие обозначения. А1'~'к(е 1,..., £*) = А + X) , где

Е* - матрица с единственным ненулевым элементом - элементом на диагонали в уй строке, равным единице.

Будем обозначать как ..., £*) граф, с матрицей смежности

Будем называть графы = (Уа,Ед) и С?д(Уа, Ед) подобными и обозначать подобие как См ~ (?в, если существует биективное отображение Ч>-Ув-*УА такое, что для любого г = 1,п вектор х^ равен с точностью до перестановки компонент вектору - вектор-столбцы мат-

риц, обратных к матрицам А и В графов, то есть помимо отображения <р существуют отображения уг : Ув —> Уа такие, что для любого $ имеет место х^ = Уф),р,а),г,.7 = 1,п.

Будем называть граф восстановимым, если любой граф ему подобный является изоморфным ему графом.

Графы ОА И ОВ подобны тогда и только тогда, когда существуют отображения и графы имеют

спектры такие, что произведение всех собственных значений из одного спектра равно произведению всех собственных значений из второго, то есть

где Ла(С^), ~ собственные значения спектров матриц

вида

(1) графов <?1 Выполнение равенства свидетельствует

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

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

Лемма 3. Пусть Ga и Gb - восстановимые графы. Матрицы .А и В такие, что существует Р - матрица перестановки: А = РВР~1. Если матрица перестановки Р - не единственная такая матрица, то некоторые из столбцов матрицы А~г равны друг-другу с точностью до перестановки их компонент. ■

Очевидно, что отсутствие в матрице А~г столбцов, равных с точностью до перестановки компонент, влечет тривиальность группы автоморфизмов T{Ga) для произвольного, не обязательно восстановимого графа

GÁ.

Введем следующие обозначения: R(A) = R(B) = {укУьLj-

Множество ,R(A) (R(B)) будем называть простым, если Vj VP $I: Xj = = Pxt (Wk yP$i : уь = Pyi), где P - матрица перестановки. По построению матриц (1) равенство Xj = Pxi влечет равенство хц — Хц.

На каждой итерации алгоритм, представленный ниже, работает не с исходными матрицами . а с матрицами уже возмущенными в

ходе предыдущих итераций. Будем производить возмущения матриц (1) при помощи матриц Пусть обозначает устанавливаемое

алгоритма соответствие между вершинами графов.

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

Принципиальная схема

Шаг 0. j := 1, ki := 0. Перейти на Шаг 1.

Шаг 1. Если j > п, то перейти на Шаг 7, иначе выбрать £jt, I := 1, перейти на Шаг 2.

Шаг 2. Если I > п, то перейти на Шаг 6, иначе, если I = ks, 1 < s < j — 1, то перейти на Шаг 4, иначе перейти на Шаг 3.

Шаг 3. Если ...,£j)~ G*¿.....^"'''(ei,• • -,£}), то kj := l, перейти

на Шаг 5, иначе перейти на Шаг 4. Шаг 4. I := 1-\т 1. Перейти на Шаг 2. Шаг 5. j := j + 1. Перейти на Шаг 1.

Шаг 6. Графы Ga и Gb неизоморфны. Работу алгоритма завершить. Шаг 7. Отображение такое, что - изоморфизм.

Работу алгоритма завершить.

В ходе работы алгоритма происходит последовательное возмущение матриц, представляющих графы - матриц графов с петлями

С7а и Св, имеющих матрицы смежности вида (1), до тех пор пока группы автоморфизмов графов СА и Св не станут тривиальными. После того, как группы автоморфизмов графов Сд и Св становятся тривиальными, возможно однозначное установление ИГ, в случае если исходные графы были изоморфны. В приведенной схеме алгоритма и везде далее в тексте используется евклидова норма в

Лемма 4. Пусть Р - некоторая матрица перестановки, <р :Ув - биекция, соответствующая Р. А*, В* - матрицы, последовательно получаемые из А и В последовательными возмущениями диагональных элементов этих матриц в соответствии с последовательностя-

Тогда

»

За п итераций алгоритма нам необходимо получить матрицы Л" и В" такие, что Ап = РВпР~и м н о ж(епс - простые. Тогда

матрица Р, с учетом лемм 3 и 4, может быть получена однозначно проверкой на равенство с точностью до перестановки компонент векторов из множеств Я{Ап) и Д(ВП).

Лемма 5. Пусть А — А'~1, В = В^,

и пусть X] - решение системы линейных уравнений А'х = е^, а ук -решения систем линейных уравнений В'^у = е^.

Тогда если для некоторой матрицы перестановки Р

то 31к : х= Рук■ ш

На итерациях алгоритма последовательно проверяется имеющее место для изоморфных графов совпадение произведений собственных значений из спектров не менее чем пХп(п—1)/2 графов, получаемых из исходных.

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

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

0(n2(Ns + n2 log га)) (3)

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

В пятом параграфе приводится численный пример, иллюстрирующий работу алгоритма.

В третьей главе исследуется вычислительная эффективность предложенного алгоритма, выделяются ключевые моменты, её определяющие.

В первом параграфе рассматриваются множества R, при помощи которых описывается сложность индивидуальной задачи проверки ИГ, определяемая мощностью групп автоморфизмов графов.

Индекс i присваивается этим множествам в соответствии с их упорядочением по невозрастанию норм векторов, входящих в них. При этом R{A) — U-Ri(A), где объединение берется по всем таким множествам векторов-столбцов обратной матрицы, в каждой из которых находятся только те векторы, которые могут быть получены друг из друга при помощи некоторой перестановки их компонент. Пусть количество таких множеств т. Тогда

Множество Д(.|4) является простым только тогда, когда Vi |ßj(A)| = 1, и, соответственно,

Под локализацией множества понимается возможнось опреде-

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

Теорема 1. Если 9 <1/3, то

11М1 - N1 < в

з

1 — 30

Доказывается лемма 6. Пусть А{ - г-й вектор-столбец рабочей матрицы А алгоритма перед его ^'-й итерацией, ^ - угол между вектором А1 и вектором

Лемма 6. Для произвольной матрицы А вида (1), представляющей невзвешенный неориентированный граф, для любого ]

Поскольку ||а;,|| = 1/||Л;|| С08 7,, указанная теорема и доказанная лемма позволяют говорить о локализованноепЬ множеств решений систем линейных уравнений при возмущениях матриц на итерациях алгоритма.

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

Утверждение о вычислительной эффективности алгоритма основано на доказанном в этом параграфе предложении.

Предложение. Если до ]-й итерации алгоритма ЗР - матрица перестановки: Xj = Рх{, Хц — хц, и возмущение на й итерации алгоритма > 0, то

3 6,

СОБТ* > ___.

11Ы - \Ы\ I > 14-

41 >

1

+ 1)'

Устанавливается, что для графов с количеством вершин, не превышающим п: необходимая длина мантиссы не превышает п; число необходимых итераций метода Гаусса-Зейделя решения систем линейных уравнений составляет O(nlogn), и количество элементарных машинных операций O(Ns), которые необходимо совершить для решения систем линейных алгебраических уравнений с заданной точностью, равно 0(п?logra). С учетом (3) общая трудоемкость алгоритма составляет 0(п6 log п)

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

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

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

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

В третьем параграфе показывается возможность применения алгоритма к задаче дешифрования шифра двойной перестановки, на основе метода, изложенного во втором параграфе.

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

В первом параграфе главы производится сведение задачи проверки изоморфизма невзвешенных ориентированных графов к задаче проверки изоморфизма невзвешенных неориентированных графов.

Во втором параграфе показывается возможность применения алгоритма к задаче проверки изоморфизма взвешенных ориентированных мультиграфов.

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

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

В седьмой главе предлагается применение предложенного алгоритма решения задачи проверки ИГ к задаче построения защищенного видеоканала.

Основные результаты диссертации:

• построен алгоритм проверки ИГ, не являющийся комбинаторным в том смысле, что при решении задачи проверки ИГ алгоритмом не происходит перебора вариантов в соответствии с некоторым деревом поиска, рост которого в ходе работы алгоритма мог бы стать неконтролируемым;

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

• показано, что графы, для которых алгоритм дает решение задачи проверки ИГ за полиномиальное относительно длины входа задачи количество машинных операций, не имеют при решении задачи представляемым алгоритмом специфики, определяемой их структурой, что является обычным для других алгоритмов решения задачи;

• предлагается применение алгоритма к решению задачи проверки эквивалентности матриц с точностью до перестановок их строк и столбцов; возможность решения данной задачи, в свою очередь, означает возможность решения задачи дешифрования шифра двойной перестановки;

• на основе алгоритма проверки ИГ, построен алгоритм поиска в графе подграфа, изоморфного данному (алгоритм поиска оптимального вложения графа);

• предложено приложение задачи проверки ИГ и предложенного алгоритма к решению задачи построения защищенного видеоканала.

ЛИТЕРАТУРА

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

2. Hopcroft, J., Wong, J. A linear time algorithm for isomorphism of planar graphs// Proc. ofthe 6th Annu. ACM Symp. on Theory ofComput., 1974. PP. 172-184.

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

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

5. 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.

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

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

8. 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.

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

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

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

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

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

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

15 Пролубников А.В., Файзуллин Р.Т. О вычислительной эффективности алгоритма спектрального расщепления для проверки изоморфизма графов II Информационный бюллетень Ассоциации мат. программирования, № 10 (Матриалы ХИ-й Всероссийской конф. «Математическое программирование и приложения»). Издательство Екатеринбургского ун-та, 2003 г. С. 206-207.

16. Пролубников А.В., Файзуллин Р.Т. Шифрование видеоизображений с применением алгоритма спектрального расщепления проверки изоморфизма графов // Развитие оборонно-промышленного комплекса на современном этапе: Материалы научн.-техн. конф. Часть 1. -Омск: Омск. Омский гос. ун-т., 2003. С. 133.

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

18. Пролубников А.В., Файзуллин Р.Т. Класс графов, задача проверки изоморфизма для которых разрешима за полиномиальное время алгоритмом спектрального расщепления // Математические структуры и моделирование: Сб. научн. тр. Под ред. А.К. Гуца. Омск: Омск. гос. ун-т, 2003. Вып. И. С. 28-57.

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

20. Пролубников А.В., Файзуллин Р.Т. Построение защищенного видеоканала с использованием изоморфизма графов // Вестник Томского гос. ун-та, № 9 (I). Материалы V Всероссийской конф. «Новые информационные технологии в исследовании сложных структур» - 1САМ'О4 и III Сибирской научной школы-семинара «Компьютерная безопасность и криптография» - SIBECRYPT'04. Иркутск, 2004 г. Томск, 2004 г. С. 71-74.

Отпечатано с оригинал-макета, предоставленного автором

Подписано в печать Формат60x84/16. Бумага офсетная. Отпечатано на ризографе. Усл. печ. л. 1,0 Уч.-изд. л. 1,0

Тираж 100 экз. Заказ № 140

Отпечатано в "Полиграфическом центре КАН" 644050, г. Омск, пр. Мира,д.32, к. 11

тел.: (3812) 65-47-31 Лицензия ПДЦ № 58-47 от 21.04.97 г.

№20 8 36

РНБ Русский фонд

2005-4 22549

Содержание.

Введение.

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% от общего количества ребер в скелетном графе изображения при устойчивой работе алгоритма.

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

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.