Сайфуллина Елена Фаридовна Метод определения неизоморфности графов

Краткое описание

Сайфуллина Елена Фаридовна Метод определения неизоморфности графов
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Сайфуллина Елена Фаридовна
Введение

Глава 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 Практическое применение и внедрение результатов работы

Заключение

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

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

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

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