|
ОГЛАВЛЕНИЕ
От редактора перевода Предисловие Часть I ОСНОВЫ ТЕОРИИ Глава 1. Основные понятия: неориентированные графы. 1.1. Введение 1.2. Геометрические графы 1.3. Абстрактные графы 1.4. Изоморфизмы и реализации 1.5. Термины, описывающие локальные свойства 1.6. Маршруты, цепи и циклы 1.7. Связность 1.8. Деревья и леса 1.9. Разделяющие множества и разрезы 1.10. Некоторые специальные классы графов Литература Глава 2. Основные понятия: ориентированные графы 2.1. Введение 2.2. Ориентированные графы 2.3. Термины для описания локальной структуры 2.4. Ориентированные маршруты, пути и контуры 2.5. Сильная связность 2.6. Деревья и разрезы 2.7. Ориентированные графы и бинарные отношения Глава 3. Разбиения и расстояния на графах 3.1. Введение 3.2. Разбиения ребер 3.3. Разбиения дуг 3.4. Гамильтоновы цепи и циклы 3.5. Разбиения вершин 3.6. Радиус и диаметр 3 7 Задачи о минимальных расстояниях Литература Глава 4. Плоские и неплоские графы. Теорема о раскраске
4.1. Введение
4.2. Плоские графы
4.3. Дополнительный граф
4.4. Раскраска ребер графа
4.5. Раскраска граней и вершин. Задача о четырех красках
4.6. Графы и поверхности
Литература
Глава 5. Матричное представление графов
5.1. Введение
5.2. Матрица инциденций
5.3. Матрица циклов
5.4. Матрица разрезов
5.5. Матрица смежности вершин
5.6. Матрица путей
5.7. Реализуемость матриц циклов и разрезов.
5.8. Матрица графов и комбинаторная топология
Литература
ЧАСТЬ II. ПРИЛОЖЕНИЯ ТЕОРИИ ГРАФОВ
Глава 6. Прикладные задачи теории графов
6.1. Введение
Приложения к экономике и исследованию
операций
6.2. Экономика и снабжение
6.3. Линейное программирование и потоки в сетях
6.4. Задачи типа ПЕРТ
Комбинаторные задачи
6.5. Примеры комбинаторных задач в теории графов
6.6. Минимальное число аварий на кирпичном заводе
6.7. Минимальное число пересечений в полных графах
Головоломки и игры
6.8. Задача соединения раскрашенных кубов
6.9. Задачи изменения состояний системы
6.10. Матричная форма задачи о переправе
6.11. Задача деления треугольника
6.12. Игра двух лиц
6.13. Игры на шахматной доске
Паросочетания
6.14. Максимальные паросочетания
Технические приложения
6.15. Анализ технических систем
6.16. Сети связи
6.17. Граф потока сигналов
6.18. Переключательные сети (схемы)
6.19 Естественные науки
6.21. Идентификация в химии
6.22. Простая модель из органической химии
6.23. Два примера из статистической механики
6.24. Генетическая задача
Задачи изучения человека и общества
6.25. Графы и кибернетика
6.26. Применения в социологии
6.27. Математические модели разоружения
6.28. Лингвистика
Литература к разделу
6.28 Дополнительные приложения
6.29. Математические машины и цепи Маркова
6.30. Группы и обыкновенные графы
6.31. Построение деревьев минимальной общей длины
6.32. Графы и собственные значения неотрицательных матриц
6.33. Задача ранжирования
Литература
Глава 7. Потоки в сетях
7.1. Введение
7.2. Основная терминология
7.3. Отношения между потоками и операции над ними
7.4. Простые потоки
7.5. Другое представление потока
7.6. Потоки с ограничениями на дугах
7.7. Максимальный поток в транспортной сети
7.8. Максимальные потоки в сетях общего вида с ограниченными пропускными способностями дуг
7.9. Потоки минимальной стоимости
7.10. Некоторые специальные задачи о потоках
7.11. Задачи о многопродуктовых потоках
7.12. Стохастические потоки в сетях
Литература
Ответы к упражнениям
Краткий терминологический словарь
Томас Л. Саати — консультант правительств многих стран и крупного бизнеса в области решения сложных проблем. Разработанный им метод анализа иерархий (Analytic Hierarchy Process, AHP) — одна из немногих методик многокритериального выбора, признанная в мире. Аналитические сети (Analytic Network Process, ANP) — обобщение AHP на проблемы с зависимостями и обратными связями между элементами. Международные симпозиумы по AHP/ANP (ISAHP) проводятся раз в два года и собирают ученых и практиков со всего мира. Томас Л. Саати — автор множества книг по теории принятия решений и теории графов. Лауреат многих наград и премий в области математики. |
