- Артикул:00-01105604
- Автор: Басакер Р., Саати Т.
- Обложка: Твердая обложка
- Издательство: Наука (все книги издательства)
- Город: Москва
- Страниц: 368
- Формат: 84х108 1/32
- Год: 1974
- Вес: 593 г
Развернуть ▼
Репринтное издание
Монография известных американских специалистов по исследованию операций посвящена теоретическим и прикладным вопросам теории графов. Книга состоит из двух частей. В первой части рассматриваются основные понятия и проблемы теории графов. Во второй части книги приводится множество интересных приложений теории графов в различных областях науки и техники, таких, как экономика, исследование операций, кибернетика, теория игр, лингвистика, передача данных и др. Книга снабжена подробной библиографией, упражнениями и ответами к ним.
Монография рассчитана на математиков, специалистов по исследованию операций, инженеров, научных работников и аспирантов, занимающихся теоретическими и прикладными вопросами теории графов.
Содержание
От редактора перевода
Предисловие
Часть 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.20. Печатные схемы
Естественные науки
6.21. Идентификация в химии
6.22. Простая модель из органической химии
6.2З. Два примера из статистической механики
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. Стохастические потоки в сетях
Литература
Ответы к упражнениям
Краткий терминологический словарь
Рекомендуем
