Каталог / ТЕХНИЧЕСКИЕ НАУКИ / Теоретические основы информатики
скачать файл: 
- Название:
- Сайфуллина Елена Фаридовна Метод определения неизоморфности графов
- Альтернативное название:
- Сайфулліна Олена Фаридівна Метод визначення неізоморфності графів
- ВУЗ:
- ТОЛЬЯТТИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
- Краткое описание:
- Сайфуллина Елена Фаридовна Метод определения неизоморфности графов
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Сайфуллина Елена Фаридовна
Введение
Глава 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 Практическое применение и внедрение результатов работы
Заключение
Список литературы
Приложение А. Результаты вычислительных экспериментов
Приложение Б. Свидетельства о государственной регистрации программ для ЭВМ
Приложение В. Акт о внедрении
- Стоимость доставки:
- 230.00 руб