|
ОГЛАВЛЕНИЕ
От редактора........................... Предисловие........................ Список обозначений......................... лава 1. Графы, их применение и сложность решения задач 1.1. Термины и определения..................... 1.2. Сложность алгоритмов..................... 1.2.1. Основные понятия (16). 1.2.2. Максимальный поток в сети (17). 1.2.3. Максимальное паросочетание (18). 1.2.4. Минимальное остовное дерево (19). 1.2.5. Кратчайший путь (20). 1.2.6. Изоморфизм графов (21). 1.2.7. Топологические свойства графов (24)... 1.3. Теоретико-графовые модели систем............... 1.3.1. Задача о кратчайшей цепи и ее приложения (25). 1.3.2. Задача о максимальном потоке и ее приложения (27). 1.3.3. Задачи об упакоз-ках ипокрытинх и их приложения (31). 1.3.4. Раскраска в графах (33). 1.3.5. Связность графов и сетей (34). 1.3.6. Изоморфизм графов и сетей (36). 1.3.7. Изоморфное вхождение и пересечение графов (40). 1.3.8. Автоморфизм графов (42). Глава 2. Операции над графами 2.1. Представление графов..................... 2.1.1. Базовые представления (45). 2.1.2. Преобразование базовых представлений (46). 2.1.3. Структура входных и выходных данных в подсистеме анализа изоморфизма графов и сетей (47). 2.2. Генерация графов...................... 2.2.1. Генерация изоморфных графов (50). 2.2.2. Систематическая генерация графов (53). 2.2.3. Генерация случайных графов (55). 2.3. Преобразование графов.................... 2.3.1. Теоретико-множественные операции (56). 2.3.2. Алгебраические операции над графами (57). 2.3.3. Специальные теоретико-графовые операции (58). Глава 3. Сети и задачи оптимизации 3.1. Метрика и пути в графах................... 3.1.1. Кратчайшие цепи и расстояния (64). 3.1.2. Кратчайшие пути с дополнительными условиями и ограничениями (671. 3.1.3. Задачи размещения и метрические характеристики графов (70). 3.2. Потоки в сетях........................ 3.2.1. Поиск максимальных потоков в сетях (74). 3.2.2. Потоки и их стоимость (78). лава 4. Части графов с заданными свойствами 4.1. Упаковки и покрытия..................... 4.1.1. Классификация задач упаковок и покрытий в графах и сетях (82). 4.1.2. Задачи покрытия в обыкновенных графах (85). 4.1.3. Задачи покрытия во взвешенных графах (87). 4.1.4. Задачи упаковки в обыкновенных графах (89). 4.1.5. Наибольшая упаковка во взвешенных графах (90).......... 4.2. Раскраски........................... 4.2.1. Точная раскраска вершин графа (92). 4.2.2. Приближенная раскраска (93). 4.2.3. Реберная раскраска (95). 4.2.4. Оценки хроматического числа (95). 4.2.5. Специальная раскраска (96). 4.2.6. Раскраска специальных графов (96)...
Глава 5. Связность
5.1. Достижимость, соединимость и отделимость..........
5.1.1. Достижимость (98). 5.1.2. Отделимость (102). 5.1.3. Соединимость (107). 5.1.4. Реберная соединимость (110).
5.2. Случайные графы.......................
5.2.1. Анализ случайных графов (113). 5.2.2. Вычисление вероятности связности (114). 5.2.3. Характеристики связности случайного графа (118). 5.2.4. Оптимальные случайные графы (121).
Глава 6. Изоморфизм, изоморфное вложение и пересечение
6.1. Изоморфизм графов и сетей..................
6.1.1. Два подхода к разработке алгоритмов (123). 6.1.2. Распознавание изоморфизма непереборным методом (137). 6.1.3. Распознавание изоморфизма методом направленного перебора (141).
6.2. Изоморфное вложение....................
6.2.1. Задачи распознавания изоморфного вложения (144).
6.2.2. Алгоритм распознавания изоморфного вложения (145).
6.2.3. Модули для распознавания изоморфного вложения (149).
6.3. Изоморфное пересечение...................
6.3.1. Задачи определения изоморфного пересечения (151).
6.3.2. Алгоритмы определения максимального изоморфного пересечения (152). 6.3.3. Модули для определения максимального изоморфного пересечения (156).
Глава 7. Симметрия
7.1. Алгебраические задачи в теории графов.............
7.1.1. Прикладные задачи (158). 7.1.2. Задачи построения характери-зации и исследования групп автоморфизмов (160).
7.1.3. Задачи перечисления (165). 7.1.4. Задачи классификации графов на основе свойств регулярности и симметрии (168)
7.1.5. Задачи построения графов и генерации семейств (172).
7.1.6. Задачи различения графов на основе инвариантов (176).
7.2. Сокращение перебора на основе симметрии при решении NP-полных задач на графах..........................
7.2.1. Методы поиска, использующпе дерево решений (181).
7.2.2. Задачи определения V- и Е-соединимости (184).
Список литературы.........................
Словарь терминов и определений...................
Приложение............................
Программы к главе 2........................
Программы к главе 3........................
Программы к главе 4........................
Программы к главе 5.........................
Программы к главе 6.........................
Программы к главе 7........................
|