Метод определения неизоморфности графов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Сайфуллина Елена Фаридовна

• Сайфуллина Елена Фаридовна
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Сайфуллина Елена Фаридовна

Введение

Глава 1 Задача проверки изоморфности графов и подходы к её решению

1.1 Понятие инварианта графа. Примеры инвариантов

1.2 Существующие подходы к решению задачи проверке изоморфности графов

1.2.1 Алгоритм распознавания изоморфизма графов, использующий поиск с возвратом

1.2.2 Эвристический подход к решению задачи установления изоморфности графов

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

1.3 Связь задачи определения изоморфности графов с понятием репрезентативности

Глава 2 Вычисление инвариантов графов

2.1 Вычисление хроматического числа графа

2.2 Программная реализация вычисления инвариантов графа

2.3 Вычисление индекса Винера, диаметра и других

инвариантов графа

2.4 Вектор степеней второго порядка

Глава 3 Генерация графов с заданным вектором степеней

3.1 Связь генерации графов с заданным вектором степеней с сетевыми моделями

3.2 Существующие алгоритмы генерации графов с заданным вектором степеней и их модификации

3.2.1. Алгоритм, основанный на теореме Гавела - Хакими

3.2.2 Алгоритм, основанный на цепи Маркова и методе Монте-Карло

3.2.3 Алгоритмы, основанные на моделях с выбором пары вершин

3.2.4 Последовательные алгоритмы для построения графов и деревьев с заданным вектором степеней

3.3. Генерация случайных графов с помощью метода

ветвей и границ с дополнительными эвристиками

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

3.3.2 Подход к случайной генерации графов на основе вектора степеней второго порядка

3.3.3 Турнирные графы и подход к их случайной генерации

Глава 4 Подход к построению эвристических алгоритмов проверки неизоморфности графов

4.1 Вычислительный эксперимент с двумя алгоритмами сортировки массива

4.2 Вычислительный эксперимент с двумя алгоритмами

генерации

4.3 Применение функций риска для получения оценок,

показывающих способность различных инвариантов

распознавать неизоморфные графы

4.4 Вычислительный эксперимент с 5 алгоритмами генерации

4.5 Особенности реализации программной системы для проведения вычислительных экспериментов

4.6 Применение разработанного подхода определения

неизоморфности графов в теории формальных языков

4.7 Практическое применение и внедрение результатов работы

Заключение

Список литературы

Приложение А. Результаты вычислительных экспериментов

Приложение Б. Свидетельства о государственной регистрации программ для ЭВМ

Приложение В. Акт о внедрении

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

Введение

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

Из многочисленных примеров областей применения алгоритмов решения проблемы определения изоморфности графов отметим задачу синтаксического и структурного распознавания образов, некоторые проблемы математической химии и хемоинформатики (исследование молекулярных структур химических соединений [7, 40]), задачи, связанные с исследованием социальных сетей (например, связывание нескольких аккаунтов одного пользователя в Facebook).

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

Легко можно показать, что отношение изоморфизма между графами рефлексивно, симметрично и транзитивно, т. е. является отношением эквивалентности ([27] и мн. др.). Поэтому класс всех графов можно разбить на непустые и попарно непересекающиеся подклассы, называемые классами изоморфизма или классами изоморфных графов. Два произвольных графа принадлежат одному и тому же классу изоморфизма тогда и только тогда, когда они изоморфны друг другу. На

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

Задача проверки изоморфности имеет широкое практическое применение и является важной проблемой в теории сложности алгоритмов. Эта задача принадлежит классу ИР, но неизвестно, принадлежит ли она классу Р - если предположить, что Р^ЫР. На настоящий момент неизвестно, является ли эта задача ЫР-полной [9], но, например, известно, что ЫР-полной является задача поиска изоморфного подграфа в графе (входными данными для этой задачи являются графы О и Н, требуется определить, содержит ли граф О подграф, изоморфный графу Н) [12]. Таким образом, актуальными являются проводимые в настоящее время исследования, которые направлены на решение задачи проверки изоморфности как для произвольных графов, так и для графов специального вида (на практике для подобных исследований могут применяться как точные, так и эвристические алгоритмы, примеры которых приводятся в главе 1 ).

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

Степень разработанности

Одним из распространённых подходов к задаче проверки изоморфности графов является применение эвристик. Эвристики для решения задачи изоморфизма обычно состоят в попытках показать, что рассматриваемые графы неизоморфны [57]. Для этого составляется список различных инвариантов в порядке, определяемом обычно сложностью вычисления этого инварианта. Затем последовательно сравниваются значения параметров представленных графов. При обнаружении двух различных значений одного и того же параметра заключается, что представленные графы неизоморфны. Такой алгоритм установления изоморфности двух

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

Ещё один из направлений исследования является решение задачи определения изоморфности для определённых классов графов. В настоящее время неизвестно, является ли задача проверки изоморфности графов разрешимой за полиномиальное время [11, 31], но известно, что эту задачу возможно решить за полиномиальное время для некоторых классов графов. Для

• планарных графов;

• графов с ограниченной степенью вершин;

• графов с ограниченной кратностью собственных значений из спектра матрицы смежности

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

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

Совсем недавно, в конце 2015 г., известный математик Ласло Бабай ВаЬа^ представил новый быстрый алгоритм для решения задачи изоморфизма графов [17, 55]. Предлагаемый алгоритм позволяет за меньшее (по сравнению с используемыми в настоящее время методами) число шагов установить изоморфность двух графов. Более детальное описание этого алгоритма Ласло Бабай обещает обнародовать в ближайшем будущем. В случае подтверждения успешной его работы этот алгоритм позволит более эффективно оперировать большим массивом дан-

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

Цель и задачи исследования

Объектом исследования представленной работы являются графы, а также характеристики графов, являющиеся их инвариантами.

Предметом исследования являются алгоритмы вычисления инвариантов графов, а также алгоритмы генерации графов.

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

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

Основные задачи исследования.

1. Разработать метод решения задачи проверки неизоморфности графов на основе выбираемого предположения о применённом алгоритме генерации.

2. Описать введённый автором новый инвариант графа - вектор степеней второго порядка.

3. Разработать алгоритм генерации графов по заданному вектору степеней первого порядка с помощью метода ветвей и границ с дополнительными эвристиками.

4. Разработать алгоритм генерации графов по заданному вектору степеней второго первого порядка с помощью метода ветвей и границ с дополнительными эвристиками.

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

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

• Разработан алгоритм генерации графов с заданным вектором степеней на основе метода ветвей и границ с дополнительными эвристиками.

• Описан введённый автором новый инвариант графа - вектор степеней второго порядка.

• Разработан алгоритм генерации графов с заданным вектором степеней второго порядка.

• Разработан алгоритм генерации турнирных графов с заданной последовательностью исходящих степеней.

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

Научная новизна

Новизна работы заключается в разработке эвристических алгоритмов генерации графов, а также в применении для задачи генерации графов расширенного ва-

рианта метода ветвей и границ. Новым также является применение вектора степеней второго порядка в качестве одного из инвариантов графов и в качестве заданного условия для случайной генерации графа. Новым также является разработанный метод проверки неизоморфности графов в зависимости от применённого алгоритма генерации.

Теоретическая и практическая значимость работы

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

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

Методология и методы исследования

При решении задач диссертации были применены различные эвристические алгоритмы, объединенные в единый программный пакет, а также статистические методы анализа алгоритмов.

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

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

лось, какая из этих последовательностей проверки инвариантов является более эффективной для ответа на вопрос о возможной неизоморфности графов из сгенерированного тестового множества.

Степень достоверности и апробация результатов

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

Материалы, описанные в работе, были представлены (в том числе - опубликованы в виде тезисов) на:

1. научном семинаре при диссертационном совете Тольяттинского государственного университета (июнь 2012 г.);

2. пятнадцатой международной научно-технической конференции «Моделирование, идентификация, синтез систем управления - 2012» (пос. Канака, Крым, сентябрь 2012);

3. XII Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 25-26 октября 2012);

4. научно-практической Intemet-конференции «Междисциплинарные исследования в области математического моделирования и информатики» (Тольятти, 18-19 июня 2013 г.);

5. 3-й научно-практической Intemet-конференции «Междисциплинарные исследования в области математического моделирования и информатики» (Тольятти, 20-21 февраля 2014 г.);

6. XIV Международной заочной научно-практической конференции «Научная дискуссия: вопросы технических наук» (Москва, сентябрь 2013 г.);

7. научном семинаре при диссертационном совете Казанского (Приволжского) федерального университета (2 раза, апрель 2014 г. и июнь 2014 г.);

8. научном семинаре при диссертационном совете Самарского государственного аэрокосмического университета (декабрь 2014 г.);

9. научном семинаре кафедры «Прикладная математика и информатика» Толь-яттинского государственного университета (многократно, 2011-2015 гг.);

10. научном семинаре кафедры «Прикладная математика и информатика» Толь-яттинского государственного университета (многократно, 2013-2015 гг.);

11. научном семинаре при диссертационном совете Института проблем управления РАН (2015 г.);

12. Международной конференции и молодежной школе «Информационные технологии и нанотехнологии» (ИТНТ-2016) (Самара 17-19 мая 2016 г.);

13.111 научно-практической всероссийской конференции (школы-семинара) молодых ученых «Прикладная математика и информатика: современные исследования в области естественных и технических наук» (Тольятти, 24-25 апреля 2017 г.).

Глава 1

Задача проверки изоморфности графов и подходы к её

решению

В общем случае задача проверки изоморфности графов может быть сформулирована так: даны графы О} и О2 с множествами вершин У(ОД У(О2) и множествами рёбер Е(ОД ЕО). \ У(ОД = | У(О2)| = п, |Е(ОД = |Е(О2)|. Требуется определить, существует ли биективное отображение - изоморфизм - ф: УА ^ Ув такое что (¡,у) ЕЕ(О}) ^ (ф(г), фЦ))ЕЕ(О2). То есть необходимо определить, существует ли отображение ф, сохраняющее смежность вершин. Если графы изоморфны, такое отображение необходимо представить, в противном случае необходимо показать его отсутствие.

1.1 Понятие инварианта графа. Примеры инвариантов

Очевидный способ проверки изоморфизма вытекает из определения отношения изоморфизма двух п-вершинных графов: необходимо просмотреть все п! взаимно-однозначных соответствий между множествами вершин и проверить, совпадают ли полностью множества рёбер графов хотя бы при одном соответствии. Но на практике это решение оказывается непригодным. Например, уже при п = 20 перебор всех п! вариантов потребовал бы на современных вычислительных системах около 40 лет машинного времени [43].

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

Инвариантом графа О называется число (или упорядоченный набор чисел), связанное с О, которое принимает одно и то же значение на любом графе, изоморфном О [39].

Наиболее очевидными инвариантами графа О являются: число вершин п(О), число рёбер т(О). Значения этих инвариантов вычисляется тривиально.

Одной из важных характеристик графа (которая широко будет использоваться в представленной работе) является степень его вершины. Степенью 8 вершины V графа О = (V, Е) называется число его вершин, смежных с V, или, что то же самое, число рёбер, инцидентных этой вершине. Очевидно, что при всяком изоморфизме графов Ь и Ь соответствующие друг другу вершины должны иметь одинаковую степень.

Пусть О = (V, Е) - п-вершинный граф, а ¿1, ¿2, ..., ¿п - степени его вершин, выписанные в порядке неубывания: ¿1 < ¿2 < < ¿п (возможно использовать вариант, в котором степени вершин упорядочены в порядке невозрастания).

Упорядоченную систему (¿1, ¿2, ..., ¿п) будем называть вектором степеней графа G (ещё одно из возможных названий - графическая последовательность [52]) и кратко обозначать ¿(О).

Вектор степеней ¿(О) = (¿1, ¿2, ..., ¿п) даёт ещё два числовых инварианта: тт(¿V) и тш^), (/ = 1,2,.,п). Второй из них часто называется степенью графа.

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

Итак, для изоморфизма графов О и О' необходимо совпадение векторов их степеней: ¿(О) = ¿(О').

Однако достаточным это условие не является: на рисунке 1.2 мы видим две пары неизоморфных графов с одинаковыми векторами1: б = (1, 2, 2, 2, 2, 3).

1 Далее в работе будет приведён и другой пример неизоморфных графов, у которых совпадают значения некоторых инвариантов (см. раздел 1.4.).

Рисунок 1.1 - Пример изоморфных графов

Рисунок 1.2 - Пример неизоморфных графов с одинаковыми векторами

степеней

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

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

Во-вторых, если s(О) = s(О'), то для проверки графов О и О' на изоморфизм требуется перебор не всех п! соответствий между вершинами, а лишь тех, при которых сопоставляются вершины одинаковой степени. Так в рассмотренном здесь примере надо перебрать лишь 4!=24 соответствия вместо 720.

Тем не менее, существуют примеры, когда при выяснении изоморфизма графов их векторы степеней практически бесполезны: речь идёт например об однородных графах, в которых степень всех вершин одна и та же. Однородные графы также называют регулярными. Если для однородного графа существуют целые числа А и ¡, такие что у любых двух смежных вершин графа G число общих соседних вершин

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

На рисунке 2а приведён пример графа, степени всех вершин которого равны

3.

#

а) б> в)

Рисунок 2 - Примеры графов: а) однородный граф (граф Петерсена); б) полный граф из пяти вершин; в)

граф из пяти вершин

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

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

2 Приведём определение простого цикла. Рассмотрим следующую последовательность, состоящую из вершин и рёбер графа G: ус, XI, VI, ..., Vn-l, хп, уп. Эта последовательность начинается и заканчивается вершиной. При этом каждое ребро в последовательности инцидентно двум вершинам, одна их которых ему предшествует, а другая следует за ним. Такая последовательность называется маршрутом в графе G. Если в маршруте все рёбра различны, а вершины vo и Vn смежные, то такой маршрут называется циклом. Простым циклом называется цикл, который не проходит ни через одну вершину графа более одного раза

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

А

и

А =

0 0 0 1 1 1

0 0 0 1 1 1

0 0 0 1 1 1

1 1 1 0 0 0

1 1 1 0 0 0

1 1 1 0 0 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

При перестановке в А2 второй и пятой строки и второго и пятого столбца получим матрицу А}.

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

А =

а11 а12

а2п а22

а

1п

а

2п

V ап1

а

а

п 2 ' ^ пп J

Пусть Е - единичная матрица размера п (элементы главной диагонали единичной матрицы равны единице, а все остальные элементы этой матрицы равны нулю). Теперь определим матрицу А - ХЕ, где А - это произвольное число.

А -ХЕ =

ац — Х

а

2 п

V ап1

а12 а22 — Х

а

1п

а

а

п2

2п

апп — ХУ

Определитель данной матрицы ёе1:( А -ХЕ) называется характеристическим многочленом матрицы. Уравнение ёе1:( А -ХЕ) = 0 называется характеристическим уравнением, а корни этого уравнения - корнями характеристического многочлена. Для матрицы А и произвольного числа X ненулевой вектор X, удовлетворяющий условию АХ=ХХ, называется собственным вектором матрицы А, при этом X называется соответствующим вектору X собственным значением матрицы А. Корни характеристического многочлена матрицы А соответствуют её собственным значениям. Совокупность корней характеристического многочлена матрицы смежности графа с учётом их кратности называется спектром матрицы смежности.

Как было упомянуто ранее, матрицы смежности изоморфных графов могут быть получены друг из друга перестановкой строк и столбцов. Любая функция от элементов а- матрицы, не меняющаяся при перестановках рядов матрицы смежности, является инвариантом графа О. Такими функциями являются, например, сумма всех элементов, неупорядоченный набор сумм элементов каждой строки или сумм элементов каждого столбца, определитель матрицы (один из инвариантов, которые были использованы в представленной работе), её характеристический многочлен и корни последнего и др.

Ещё одним из способов представления графа является матрица инцидентности. Строки этой матрицы соответствуют вершинам графа, а столбцы - его рёбрам. Ненулевое значение в ячейке матрицы инцидентности означает связь (инцидентность) между ребром и вершиной графа. В случае ориентированного графа, в столбце, соответствующем дуге <х, у>, указывается -1 в строке, соответствующей вершине х, и 1 - в строке, соответствующей вершине у.

На основании понятия изоморфизма и определений матрицы смежности и инцидентности можно сформулировать следующие утверждения.

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

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

Известными на сегодняшний день полными инвариантами являются мини-код и макси-код матрицы смежности. Значения этих инвариантов получается путём выписывания двоичных значений матрицы смежности в строчку; полученное двоичное число затем переводится в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным; макси-коду - соответственно максимально возможным. Определение значений мини-кода и макси-кода является вычислительно сложным. Приведём пример вычисления мини-кода и макси-кода. На рисунке 2с выше изображён граф из 5 вершин. Его матрица смежности равна

'01101Л 1 0 0 0 0 А =10 0 10 0 0 10 0 ч 1 0 0 0 0у

В случае неориентированных графов для вычисления макси-кода и мини-кода можно использовать только элементы матрицы смежности, расположенные выше главной диагонали [1]. Выпишем эти элементы матрицы построчно, затем преобразуем полученное двоичное число в десятичную форму: 11010001002 = 836. Для получения максимального значения необходимо, чтобы первая строка содержала максимальное число единиц вначале строки и расположенных по порядку, т.е. первой будет вершина с максимальной степенью (в рассматриваемом случае такая вершина одна - 5). Перебором всех возможных перестановок оставшихся четырёх вершин найдём матрицу с максимальным кодом:

'01110 Л 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 ч0 1 0 0 0,

Макси-код рассматриваемого графа равен 11100010002 = 904. Аналогичным образом можно найти мини-код: 00010011012 = 77.

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

Рассмотрим ещё несколько важных инвариантов графа [12, 39].

• Плотность ДО) - число вершин в максимальной клике графа О. Клика графа определяется как подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не включается ни в какое подмножество с тем же свойством. Инвариантность этой характеристики следует из того, что при изоморфном соответствии двух графов каждому подмножеству вершин одного графа, порождающему клику, соответствует в другом графе подмножество с тем же числом вершин и тоже порождающее клику.

• Неплотность е(О) - это наибольшее количество попарно несмежных вершин графа.

• Число Хардвигера к(О) - отображение, сопоставляющее графу О максимальное число к такое, что О стягиваем к полному графу на к вершинах. Граф О стягиваем к графу Н в том случае, если Н может быть получен из О с помощью последовательности стягиваний рёбер (для данного ребра (и, V) стягивание означает слияние его концов и и V и удаление образовавшейся петли). В результате стягивания графа Петерсена (рисунок 2а, стр. 9) получим например полный граф из пяти вершин (рисунок 2б, стр. 9). Поэтому число Хадви-гера графа Петерсена Н(О)=5.

• Индекс Хосойи - число паросочетаний рёбер графа плюс единица [56]. Паросочетание - множество рёбер графа, не имеющих общих вершин. Задача определения паросочетаний рёбер графа и алгоритмы её решения рассматриваются в [13].

Список литературы диссертационного исследования кандидат наук Сайфуллина Елена Фаридовна, 2019 год

Список литературы

1. Абросимов, М. Практические задания по графам, 2-е издание: Учебное пособие / М. Б. Абросимов, А. А. Долгов. - Саратов: Изд-во «Научная книга», 2009. - 76 с.

2. Баумгертнер, С. Дополнительные эвристики в задаче звёздно-высотной минимизации недетерминированного конечного автомата / С. Баумгертнер // Вектор науки Тольяттинского государственного университета. - 2010. - №3 (13). - С. 37-39.

3. Балинова, В. Статистика в вопросах и ответах / В. Балинова. - М.: ТК Велби, Изд-во Проспект, 2004. - 344 с.

4. Бельский, А. Теория графов и комбинаторика [Электронный ресурс]. - Режим доступа: http ://belsky. narod.ru/v2/rus/mathemat/tgik.html

(16.02.2015).

5. Большакова, Е. И. Алгоритмы построения компьютерного словаря русских буквенных паронимов и его применение / Е. И. Большакова, И. А. Большаков // Эвристические алгоритмы и распределённые вычисления. - 2015. - Том 2, № 3. - С. 8-22.

6. Бреер, В. В. Стохастические модели социальных сетей / В. В. Бреер // Управление большими системами. - 2009. - № 27. - C. 169-204.

7. Брюске, Э. Я. Химику о теории графов: графы в химической номенклатуре / Э. Я. Брюске // Вестник Тамбовского университета. Серия: Естественные и технические науки. - 2003. - т. 8, вып. 5. - С. 840-847.

8. Вычисление определителя методом Краута [Электронный ресурс]. - Режим доступа: http : //e-maxx.ru/al go/determinant crout

(12.04.2016).

9. Громкович, Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию

алгоритмов, рандомизацию, теорию связи и криптографию / Ю. Громкович. - СПб.: БХВ-Петербург, 2010. - 336 с.

10. Гудман, С. Введение в разработку и анализ алгоритмов / С. Гуд-ман, С. Хидетниеми. - М.: Мир, 1981. - 368 с.

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

12. Зыков, А. Основы теории графов / А. Зыков. - М.: Наука, 1986.

- 384 с.

13. Кирсанов, М. Н. Графы в Maple / М. Н. Кирсанов. - М.: Физматлит, 2007. - 168 с.

14. Кормен, Т. Алгоритмы - построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. - М.: Вильямс, 2005. - 1296 с.

15. Левитин, А. Алгоритмы: введение в разработку и анализ / А. Левитин. - М.: «Вильямс», 2006. - 576 с.

16. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. - M.: Мир, 1981. - 323 с.

17. Материалы портала «Научная Россия». Научный алгоритм обещает упростить проблему «изоморфизма графов». [Электронный ресурс].

- Режим доступа: http://scientificrussia.ru/articles/izomorfizm-grafov (08.09.2017)

18. Мельников, Б. Ф. Алгоритм проверки равенства бесконечных итераций конечных языков / Б. Ф. Мельников // Вестник Московского университета. Сер. Вычисл. матем. и киб-ка. - 1996. - № 4. - C. 49-54.

19. Мельников, Б. Ф. Мультиэвристический подход к задачам дискретной оптимизации / Б. Ф. Мельников // Кибернетика и системный анализ (НАН Украины). - 2006. - № 3. - C. 32-42.

20. Мельников, Б. Ф. Подклассы класса контекстно-свободных языков / Б. Ф.Мельников. - М.: МГУ, 1995. - 174 с.

21. Мельников, Б. Ф. Применение алгоритмов генерации случайных графов для исследования надёжности сетей связи / Б. Ф. Мельников, Е. Ф.

Сайфуллина, Ю. Ю. Терентьева, Н. Н. Чурикова // Информатизация и связь. - 2018. - № 1. - С. 71-80.

22. Мельников, Б. Ф. Применение мультиэвристического подхода для случайной генерации графа с заданным вектором степеней / Б. Ф. Мельников, Е. Ф. Сайфуллина // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2013. - № 3(27). -C. 69-82.

23. Мельников, Б. Эвристики в программировании недетерминированных игр / Б. Мельников // Программирование. Известия РАН. - 2001. -№ 5. - С. 63-80.

24. Мельникова, Е. А. Подход к проверке изоморфизма с помощью построения инвариантов / Е. А. Мельникова, Е. Ф. Сайфуллина // Вектор науки Тольяттинского государственного университета. - 2013. - № 1(23). - C. 113-120.

25. Мельникова, Е. А. Применение различных инвариантов графов к проверке изоморфизма некоторых видов графов / Е. А. Мельникова, Е. Ф. Сайфуллина // Проблемы информатики в образовании, управлении, экономике и технике: тр. XII Междунар. научно-техн. конф. - Пенза: Приволжский Дом знаний, 2012. - C. 40-42.

26. Молодцов, С. Г. Генерирование молекулярных графов с заданными структурными ограничениями: дис. ... канд. физ.-мат. наук : 05.13.16 : защищена 21.10.1997 / Молодцов Сергей Георгиевич. - Новосибирск: НИОХ СО РАН, 1997. - 79 с.

27. Общая алгебра / под общ. ред. Л. А. Скорнякова. - М.: Наука, 1990. - Т. 1. - 592 с.

28. Оре, О. Графы и их применение / О. Оре. - М.: URSS, 2006. - 168

с.

29. Остроумова, Л. А. Математические ожидания k-х входящих степеней вершин в случайных графах в модели Боллобаша-Риордана / Л. А. Остроумова // Труды Московского физико-технического института. -

2012. - Т. 4, № 1 (13). - C. 29-40.

30. Павлов, А.Н. Решение многокритериальных задач методом анализа иерархий: Учебное пособие / А. Н. Павлов. - М.: Изд-во РАГС, 2009.

- 111 с.

31. Пападимитру, Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитру, К. Стайглиц. - М.: Мир, 1985. - 512 с.

32. Пролубников А. Прямой алгоритм проверки изоморфизма графов / А. Пролубников // Компьютерная оптика. - 2007. - том 31, № 3.

- C. 87-92.

33. Райгородский, А. М. Математические модели Интернета / А. М. Райгородский // Квант. - 2012. - № 4. - C. 12-16.

34. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. - М.: Мир, 1980. - 476 с.

35. Рогова, О. А. Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов: дис. ... канд. физ.-мат. наук : 05.13.18 : защищена 13.04.2012 / Рогова О. А. - Тольятти: ТГУ, 2012. - 114 с.

36. Саати, Т. Аналитическое планирование / Т. Саати, К. Кернс. -М.: Радио и связь, 1991. - 215 с.

37. Сайфуллина, Е. Ф. Последовательности сравнения инвариантов графов в задаче проверки изоморфности / Е. Ф. Сайфуллина // Вектор науки Тольяттинского государственного университета. - 2013. - № 3(25).

- C. 87-90.

38. Труфанов, А. Моделирование Web-графа [Электронный ресурс].

- Режим доступа: http: //www.referat.ru/referat/modelirovanie-web-grafa-22432 (11.07.2014)

39. Харари, Ф. Теория графов / Ф. Харари. - М.: Мир, 1973. - 302 с.

40. Химические приложения топологии и теории графов / под ред. Р. Кинга - М.: Мир, 1987. - 560 с.

41. Эккель, Б. Философия Java / Б Эккель. - М.: Питер, 2009. - 640 с.

42. Эляшберг, М. Математический синтез и анализ молекулярных структур / М. Эляшберг, Л. Грибов, В. Серов. - М.: Наука, 1980. - 307 с.

43. Язык программирования C++. Динамические структуры данных. Шаг 117. Изоморфизм [Электронный ресурс]. - Режим доступа: http://it.kgsu.ru/C DIN/din 0117.html (22.08.2015).

44. Berg, B. Markov Chain Monte Carlo Simulations and Their Statistical Analysis / B. Berg. - Singapore: World Scientific Publ., 2004. - 361 р.

45. Blitzstein J., Diaconis P. A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees [Электронный ресурс]. - Режим доступа: http://statweb.stanford.edu/~cgates/PERSI/pa-pers/degrees.pdf (17.04.2014).

46. Bollobas B. Random Graphs / B. Bollobas. - Cambridge: Cambridge Univ. Press, 2001. - 498 p.

47. Bollobas, B. Mathematical results on scale-free random graphs / B. Bollobas, O. Riordan // Handbook of graphs and networks. - Weinheim: Wiley-VCH, 2005. - P. 1-34.

48. Bondy, J. Graph Theory / J. Bondy, U. Murty. - Springer, 2007. - 582

p.

49. Corneil, D. An Efficient Algorithm for Graph Isomorphism / D. Cor-neil, C. Gotlieb // - J. of the Association for Computing Machinery. - 1970. -Vol.17, №.1. - P. 51-64.

50. Directed Graphs [Электронный ресурс] - Режим доступа: http://www.math.umaine.edu/~farlow/sec35.pdf (16.11.2016).

51. Douglas C. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices / С. Douglas, E. Larry // Journal of the ACM. - 1975. - 23 (3). - P. 433-445.

52. Erdos, P. A Simple Havel-Hakimi Type Algorithm to Realize Graphical Degree Sequences of Directed Graphs / P. Erdos, I. Miklos, Z. Toroczkai // Electr. J. Comb. - 2010. - V. 17, № 1. - P. 1-10.

53. Frank, H. Circuit Theory / H. Frank, S. Hakimi // IEEE Transactions

on. - 1965. - Vol. 12, № 3. - P. 44-51.

54. Graph Isomorphism [Электронный ресурс]. - Режим доступа: https: //sourceforge.net/p/sayfullinaelena/code/ci/master/tree/ (25.02.2018).

55. Graph Isomorphism in Quasipolynomial Time [Электронный ресурс]. - Режим доступа: https://arxiv.org/pdf/1512.03547.pdf (12.09.2017).

56. Hosoya, H. The Topological Index Z Before and After 1971 / H. Ho-soya // Internet Electronic Journal of Molecular Design. - 2002. - № 1. - P. 428-442.

57. Hromkovi^ J. Algorithmics for Hard Problems / J. Hromkovk // Introd. to Combinatorial Optimization, Randomization, Approximation, and Heuristics. - Springer, 2004. - 548 p.

58. Ivanyi. A. Reconstruction of complete interval tournaments / A. Ivanyi // ActaUniversitatisSapientiae, Informatica. - 2009. - Vol. 1, № 1. - P. 71-88.

59. Landau, H. On dominance relations and the structure of animal societies. II. The condition for a score sequence / H. G. Landau // - Bulleton of Mathematical Biology. - 1953. - 15(2). - P. 143-148.

60. Melnikov, B. Discrete optimization problems - some new heuristic approaches / B. Melnikov // Proc. of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, IEEE Computer Society. - Washington, 2005. - P. 73-80.

61. Melnikov B. Once more on the edge-minimization of nondeterminis-tic finite automata and the connected problems / B. Melnikov // Fundamenta Informaticae. - 2010. - Vol. 104, № 3. - P. 267-283.

62. Melnikov, B. Some special heuristics for discrete optimization problems / B. Melnikov, A. Radionov, V. Gumayunov // 8th International Conference on Enterprise Information Systems. - Paphos, Cyprus, 2006. - Р. 360-364.

63. Plastria, F. Tables of tournaments core sequences [Электронный ресурс]. - Режим доступа: http://homepages.vub.ac.be/~faplastr/Tourna-ments.html (17.05.2015).

64. Social circles: Facebook [Электронный ресурс]. - Режим доступа: http://snap.stanford.edu/data/egonets-Facebook.html (01.12.2015).

65. Steger, A. Generating random regular graphs quickly / A. Steger, N. Wormald // Combinatorics, Probab. а^ Comput. - 1999. - № 8. - P. 377-396.

66. Wolpert, D. No free lunch theorems for optimization / D. Wolpert, W. Macready // IEEE Transactions on Evolutionary Computation. - 1997. - vol. 1, № 1. - P. 67-82.

Приложение А. Результаты вычислительных экспериментов

Время построения Графа (т5)

6000 5000 4000 5000 2000 1000 о

I 1

Шк..

Времк построения Графа [ть)

№ турнирной последовательности

Рисунок 19 - Результаты вычислительного эксперимента для п = 10

Рисунок 20 - Результаты вычислительного эксперимента с двумя

алгоритмами генерации

Рисунок 21 - Результаты вычислительного эксперимента. Биноминальное

распределение

Р(к) =

п -1

\рк (1 - р)п-1-к, р = 0.01К=100

Рисунок 22 - Результаты вычислительного эксперимента. Распределение Пуассона

2к

р(к) = ^ к = 1.25, N = 100

^ ' к!

Рисунок 23 - Результаты вычислительного эксперимента.

1 /к5

Распределение Ципфа/(к, я, N = „

1£=1(1 /п5)

я = 5, N - размерность графа

Рисунок 24 - Результаты вычислительного эксперимента. Алгоритм

генерации 1

Рисунок 25 - Результаты вычислительных экспериментов. Алгоритм

генерации 2

Рисунок 26 - Результаты вычислительных экспериментов для примера графа, предназначенного для распознавания лиц

Рисунок 27 - Результаты вычислительных экспериментов для графа молекулы

фуллерена с числом атомов равным 60

Рисунок 28 - Результаты вычислительных экспериментов для графа,

описывющего соответствия между состояниями канонического автомата и состояниями автомата, канонического к зеркальному

Приложение Б. Свидетельства о государственной регистрации программ для ЭВМ

мультиэвристического подхода

Авторы: Пивнева Светлана Валентиновна (RU) Сайфуллина Елена Фаридовна (RU)

Заявка № 2015612622

Врио руководителя Федеральной службы

щшш

о государственной регистрации программы для ЭВМ

№ 2015616142

Генерация турнирных графов на основе

Правообладатели: Сайфуллина Елена Фаридовна (RU), Пивнева

Светлана Валентиновна (RU)

Дата поступлений 03 ЛПрСЛЫ 2015 Г.

Дата государственной регистрации

I! Реестре программ .тля ЭВМ 01 июня 2015 г.

по интеллектуальной собственности

Л. Л. Кирий

Приложение В. Акт о внедрении

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение

высшего образования Тольяттинский государственный университет

результатов диссертации Сайфуллиной Е. Ф. на тему «Мультиэвристический подход к проблеме определения изоморфно сти графов»

Мы, нижеподписавшиеся, комиссия в составе председателя комиссии -заведующего кафедрой «Прикладная математика и информатика», кандидата технических наук, доцента, Очеповского Андрея Викторовича и членов: специалиста по методической работе кафедры «Прикладная математика и информатика» Кувшиновой Натальи Александровы и ответственного исполнителя - доцента кафедры «Прикладная математика и информатика», кандидата физико-математических наук, доцента Тырыгиной Галины Алексеевны удостоверяем, что результаты диссертационного исследования Сайфуллиной Е. Ф. «Мультиэвристический подход к проблеме определения изоморфности графов» внедрены в учебный процесс кафедры при разработке курсов лекций направления подготовки 01.04.02 «Прикладная математика».

Председатель:

Заведующий кафедрой

«Прикладная математика и информатика:

акт

внедрения в учебный процесс кафедры «Прикладная математика и информатика»

кандидат технических наук, доцент

Очеповский А. В.

Члены комиссии: Специалист по методической работе

Щ-' Кувшинова Н. А.

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

Тырыгина г.А.