В монографии систематически изложены программно реализованные алгоритмы задач теории графов. Рассмотрены задачи упаковки, покрытия, раскраски, связности и изоморфизма графов, их приложения, в частности, задачи связности случайных графов и изоморфного вложения графов. Алгоритмы оформлены в виде текстов 140 подпрограмм на языках ПЛ-1 и Фортран. Для многих подпрограмм приведены оценки сложности. Обширная терминология теории графов упорядочена в терминологическом словаре. Описан широкий спектр операций над графами, с помощью которых расширен класс решаемых классических и прикладных задач. Показаны варианты сведения этих задач к описанным программам.
Издание предназначено для специалистов, использующих методы теории графов в своей работе, аспирантов и студентов соответствующих специальностей.
------------------------------ ------------------------------ --------------------
ОГЛАВЛЕНИЕ
От редактора..................... ......
Предисловие................... .....
Список обозначений................... ......
лава 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.
