Конечные графы и сети

Автор(ы)

Басакер Р, Саатн Т

Год

1973

Язык

rus

Теги

Математика Программирование Экономика

Аннотация

Конечные графы и сети Год : 1973 Автор : Басакер Р., Саатн Т. Издательство : Наука Язык : Русский Формат : DjVu Качество : Отсканированные страницы + слой распознанного текста Количество страниц : 367 Описание : Монография известных американских специалистов по исследованию операций посвящена теоретическим и прикладным вопросам теории графов. В первой части книги рассматриваются основные понятия и проблемы теории графов. Во второй -- приводится множество интересных приложений теории графов в различных областях науки и техники. Примеры страниц Оглавление От редактора перевода б Предисловие ? часть I ОСНОВЫ ТЕОРИИ Глава 1. Основные понятия: неориентированные графы . . 11 Введение 11 1.2. Геометрические графы 12 '.3. Абстрактные графы 14 .4. Изоморфизмы и реализации 16 .5. Термины, описывающие локальные свойства ... 19 .6, Маршруты, цепи и циклы 21 ,7. Связность 24 .8. Деревья и леса 26 .9. Разделяющие множества и разрезы 29 .10. Некоторые специальные классы графов .... 32 Литература 35 Глава 2. Основные понятия: ориентированные графы , . 37 2.1. Введение 37 2.2. Ориентированные графы 37 2.3. Термины для описания локальной структуры , . , 40 2.4. Ориентированные маршруты, пути, и контуры ... ^1 2.5. Сильная связность .'.... 43 2.6. Деревья и разрезы 44 2.7. Ориентированные графы и бинарные отношения . , 46 ГлаваЗ. Разбиения и расстояния на графах 49 3.1. Введение . 49 3.2. Разбиения ребер 49 3.3. Разбиения дуг 54 3.4. Гамильтоновы цепи и циклы 61 3.5. Разбиения вершин 75 3.6. Радиус и диаметр 80 3 7. Задачи о минимальных расстояниях 82 Литература 89 Глава 4. Плоские и неплоские графы. Теорема о раскраске 90 4.1. Введение 90 4.2. Плоские графы 91 4.3. Дополнительный граф 108 4.4. Раскраска ребер графа 112 4.5. Раскраска граней и вершин. Задача о четырех красках 115 4.6. Графы и поверхности 127 Литература 133 Глава 5. Матричное представление графов 136 5.1. Введение 136 5.2. Матрица инцидепций 139 5.3. Матрица циклов 143 5.4. Матрица разрезов 144 5.5. Матрица смежности вершин 149 5.6. Матрица путей 157 5.7. Реализуемость матриц циклов и разрезов .... 158 5.8. Матрица графов и комбинаторная топология . . . i-oi Литература 164 часть и. ПРИЛОЖЕНИЯ ТЕОРИИ ГРАФОВ Глава 6. Прикладные задачи теории графов '66 6.1. Введение 166 Приложения к экономике и исследованию операций '"' 6.2. Экономика и снабжение 167 6.3. Линейное программирование и потоки в сетях . . '72 6.4. Задачи типа ПЕРТ 173 Комбинаторные задачи 183 6.5. Примеры комбинаторных задач в теории графов . . '83 6.6. Минимальное число аварий на кирпичном заводе . . '97 6.7. Минимальное число пересечений в полных графах . . 202 Головоломки к игры 205 6.8. Задача соединения раскрашенных кубов .... 205 6.9. Задачи изменения состояний системы 207 6.10. Матричная форма задачи о переправе . ... . 213 6.11. Задача деления треугольника 219 6.12. Игра двух лиц 220 6.13. Игры на шахматной доске 224 Паросочетания 226 6.14. Максимальные паросочетания 226 Технические приложения 238 6.15. Ана