Конечные графы и сети, Басакер Р., Саати Т., перевод с английского, Главная редакция физико-математической литературы изд-ва «Наука», Москва. 1973, 368 стр. Скачать бесплатно
Монография известных американских специалистов по исследованию операций посвящена теоретическим и прикладным вопросам теории графов. Книга состоит из двух частей В первой части рассматриваются основные понятия и проблемы теории графов. Во второй части кинги приводится множество интересных приложений теории графов в различных областях науки и техники, таких, как экономика, исследование операций, кибернетика, теория игр, лингвистика, передача данных и др. Книга снабжена подробной библиографией, упражнениями и ответами к ним. Монография рассчитана на математиков, специалистов по исследованию операций, инженеров, научных работников и аспирантов, занимающихся теоретическими и прикладными вопросами теории графов.
Название:
Размер: 3,93 Мб
Описание: Конечные графы и сети, Басакер Р., Саати Т., перевод с английского, Главная редакция физико-математической литературы изд-ва «Наука», Москва. 1973, 368 стр.
Ссылка для скачивания файла:
ОГЛАВЛЕНИЕ От редактора перевода б Предисловие Часть I ОСНОВЫ ТЕОРИИ Глава 1. Основные понятия: неориентированные графы . . 11 Введение 11 1.2. Геометрические графы 12 1.3. Абстрактные графы 14 1.4. Изоморфизмы и реализации 16 1.5. Термины, описывающие локальные свойства ... 19 1.6, Маршруты, цепи и циклы 21 1.7. Связность 24 1.8. Деревья и леса 26 1.9. Разделяющие множества и разрезы 29 1.10. Некоторые специальные классы графов .... 32 Литература 35 Глава 2. Основные понятия: ориентированные графы . 37 2.1. Введение 37 2.2. Ориентированные графы 37 2.3. Термины для описания локальной структуры 40 2.4. Ориентированные маршруты, пути, и контуры ... 41 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. Матрица графов и комбинаторная топология . . .
Литература 164 Часть 2. ПРИЛОЖЕНИЯ ТЕОРИИ ГРАФОВ Глава 6. Прикладные задачи теории графов 166 6.1. Введение 166 Приложения к экономике и исследованию операций 6.2. Экономика и снабжение 167 6.3. Линейное программирование и потоки в сетях . . 172 6.4. Задачи типа ПЕРТ 173 Комбинаторные задачи 183 6.5. Примеры комбинаторных задач в теории графов . . 183 6.6. Минимальное число аварий на кирпичном заводе . . 197 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. Анализ технических систем 238 6.16. Сети связи 244 6.17. Граф потока сигналов 248 6.18. Переключательные сети (схемы) 254 6.19. Объединение электростанций в энергосистему . . 257 6.20. Печатные схемы 258 Естественные науки 269 6.21. Идентификация в химии 6.22. Простая модель нз органической химии . . . . 265 6.23. Два примера из статистической механики . . . 268 6.24. Генетическая задача 270 Задачи изучения человека и общества , 272 6.25. Графы и кибернетика 272 6.26. Применения в социологии 277 6.27. Математические модели разоружения .... 281 6.28. Лингвистика ... 284 Литература к разделу 6.28 2S9 Дополнительные приложения . . . . 289 6.29. Математические машины и цепи Маркова . . . 289 6.30. Группы и обыкновенные графы 295 6.31. Построение деревьев минимальной общей длины . 297 6.32. Графы и собственные значения неотрицательных матриц 298 6.33. Задача ранжирования 300 Литература 304 Глава 7. Потоки в сетях 309 7.1. Введение 309 7.2. Основная терминология 309 7.3. Отношения между потоками и операции над ними . 313 7.4. Простые потоки 314 7.5. Другое представление потока 315 7.6. Потоки с ограничениями на дугах 318 7.7. Максимальный поток в транспортном сети . . . 325 7.8. Максимальные потоки в сетях общего вида с ограниченными пропускными способностями дуг .... 327 7.9. Потоки минимальной стоимости 332 7.10. Некоторые специальные задачи о потоках . . . 338 7.11. Задачи о многопродуктовых потоках 349 7.12. Стохастические потоки в сетях 343 Литература 346 Ответы к упражнениям 348 Краткий терминологический словарь 352
Краткий терминологический словарь Ациклический граф. Ориентированный граф без контуров. Антисимметрический граф. Ориентированный граф, в котором нет дуги из w в v, если присутствует дуга из v в w. Ветвь. Ребро графа G, которое содержится в дереве Т, являющемся подграфом G; термин ветвь используется по отношению к определенному дереву Т. Вершина. См. граф и ориентированный граф. Граничные точки. Вершины, которым инцидентны ребра или дуги. Геометрический граф. Граф, вершины которого изображаются точками в двумерном или трехмерном пространстве и чьи ребра являются непересекающимися простыми кривыми, каждая из которых соединяет две вершины (или, в случае петли, замыкается на одной вершине) без промежуточных вершин. Геометрическое представление. Геометрический граф, изоморфный данному графу. Граф, Математическая система, состоящая из двух множеств V и Е и отображения Г множества Е в V&V (множество неупорядоченных пар элементов V). Элементы V и Е называются соответственно вершинами и ребрами графа, а Г называется отображением инцидентности. Если Г(е) «= (v&w), то вершины v н w называются граничными точками е. Граф бинарных отношений. Ориентированный граф, вершины которого соответствуют элементам множества, на которых определены отношения и дуги соединяют пары вершин с заданными отношениями. Гамильтонова цепь, цикл, контур или путь. Простые цепи, циклы, контура или пути, содержащие все вершины рассматриваемого графа. Граф без сочленений. Связный граф без точек сочленения. Дуга. См. ориентированный граф. Двудольный граф. Граф, вершины которого могут быть разбиты на два множества таким образом, что каждое ребро имеет по граничной точке в каждом из множеств. Дополнение графа. Обыкновенный граф, полученный путем удаления ребер данного обыкновенного графа G из полного графа, имеющего те же самые вершины. Доминирующее множество графа (внешнее устойчивое множество). Множество W вершин таких, что каждая вершина, не принадлежащая W, смежна с вершиной в W. Дерево, растущее из корня (прадерево). Ориентированный граф, который является деревом и имеет вершину v такую, что для любой другой вершины w дерева единственная цепь соединяет v www является фактически путем, ориентированным от него. В этом случае говорят, что дерево растет из корня и. Дерево. Связный граф без циклов. Инцидентное отображение. См. граф. Инцидентность. Связь между ребром (или дугой) е и вершинами, в которые оно отображается отношениями инцидентности графа. Изоморфные графы. Пара графов, чьи вершины и ребра (или дуги) могут быть поставлены во взаимно однозначное соответствие таким образом, что соотношения инцидентности сохраняются. В ориентированном графе знак инцидентности (положительный или отрицательный) также должен сохраняться. Источник. Вершина сети, в которой выходной поток больше входного. Компонента графа'. Связный подграф, который не принадлежит ни одному большему связному подграфу. Контур. Замкнутый ориентированный маршрут без повторяющихся вершин. Контурный граф. Ориентированный граф, содержащий, по крайней мере, один контур. Конечный граф. Граф, имеющий конечное число вершии и ребер (или дуг в случае ориентированного графа). Конечная вершина. См. ориентированный граф. Лес. Граф без циклов, каждая компонента которого является деревом. Матрица смежности. То же, что и матрица смежности вершин. Матрица циклов. Матрица, чьи строки и столбцы соответствуют простым циклам и ребрам графа, а каждый из ее элементов равен 1 или 0 в зависимости от того, содержится илн нет в соответствующем цикле соответствующее ребро. Матрица разрезов. Матрица, аналогичная матрице циклов, в которой простые циклы заменены простыми разрезами. Маршрут. Конечная последовательность (не обязательно различных) ребер таких, что одна из граничных точек первого ребра является также граничной точкой второго, оставшаяся граничная точку второго ребра является также граничной точкой третьего и т. д. Маршрут является замкнутым, если свободная граничная точки первого ребра совпадает со «свободной> граничной точкой последнего. Маршрут называется незамкнутым в противном случае. Матрица инциденций. Матрица, строка и столбцы которой соответствуют вершинам и ребрам графа. Каждый элемент матрицы равен 1 или 0 в зависимости от того, инцидентны нли нет соответствующие ему вершина и ребро. Матрица смежности вершин. Матрица, строки и столбцы которой соответствуют вершинам графа, а элементы означают число ребер, связывающих соответствующие пары вершин. Неупорядоченная цепь. Множество ребер, которые, будучи соответственно упорядоченными, образуют Цепь. В геометрическом графе это множество ребер, которые образуют незамкнутую кривую. Неупорядоченный цикл. Множество ребер, которые, будучи соответственно упорядоченными, образуют цикл. В геометрическом графе это множество ребер, которые образуют замкнутую кривую. Неупорядоченный контур. Множество дуг, которые будучи соответственно упорядоченными, образуют контур. В геометрическом графе это замкнутая кривая, образованная соответственно ориентированными дугами. Независимое множество вершин (внутреннее устойчивое множество). Множество вершин, в котором нет двух смежных вершин. Неупорядоченный путь. Множество дуг, которые будучи соответственно упорядоченными, образуют путь. Неориентированный граф. То же самое, что граф. Начальная вершина. См. ориентированный граф. Ориентированный маршрут. Конечная последовательность (не обязательно различных) дуг таких, что конечная вершина каждой дуги (исключая последнюю) является также начальной вершиной последующей дуги. Говорят, что маршрут является замкнутым, если начальная вершина первой дуги совпадает с конечной вершиной последней дуги, и незамкнутым в противном случае. Ориентированный эйлеров граф (псевдосимметрический граф). Ориентированный граф, в котором равны отрицательная и положительная степени каждой вершины. Ориентированный граф. Математическая система, состоящая из двух множеств V и Л и отображения Д множества А на VXV. Элементы V и Л называются соответственно вершинами и дугами ориентированного графа, а Д называется отображением ориентированной инцидентности. Если Д(а) = (о, w), то v называется начальной вершиной дуги а, в w — конечной вершиной. Отрицательная степень вершины. Число дуг, с которыми вершина отрицательно инцидентна. Отрицательная инцидентность. Отношение между дугой и ее конечной вершиной (дуга входит в вершину). Однородный граф. Граф, все вершины которого имеют одну и ту же степень. Обыкновенный граф. Неориентированный граф, который ие содержит параллельных ребер и петель; ориентированный граф, который не содержит строго параллельных дуг и петель. Полный граф. Граф, в котором каждые две различные вершины смежны. Поток. Целые числа, назначенные дугам сети, которые интерпретируются как скорости потока вещества но дугам. Петля. Ребро (или дуга), инцидентное только одной вершине. Паросочетание. Множество ребер графа, в котором нет двух смежных ребер. Параллельные ребра или дуги Ребра или дуги, имеющие общие граничные точки. Путь. Незамкнутый ориентированный маршрут без повторяющихся дуг. Перт—сеть. Ориентированный граф, используемый для отражения взаимосвязи операций проекта. Дуги соответствуют операциям, а их граничные точки выбираются так, чтобы отразить ограничения на порядок, в котором операции должны выполняться. Плоский граф. Граф, изоморфный геометрическому графу на плоскости. Подграф. Граф G'=(V, ?', Г') называется подграфом графа G{V, ?, Г), если V с V, ?' с Е и Г (е) =Г(е) для каждого ребра <=?'.
Необходимо, чтобы V включало все граничные точки (по отношению к G) ребер в ?'. Ориентированный подграф ориентированного графа определяется по существу аналогичным образом, если ? и Г интерпретировать соответственно как множество дуг и ориентированное инцидентное отображение. Покрывающее дерево. Подграф связного графа G, который является деревом и включает все вершины G. Положительная степень вершины. Число дуг, которые положительно инцидентны вершине. Положительная инциденция. Связь между дугой и ее начальной вершиной (дуга выходит из вершины). Примитивный граф. Ориентированным граф такой, что для некоторого целого числа k каждая пара разных вершин может быть соединена ориентированным маршрутом, состоящим точно из k элементов. Простой разрез. Разделяющее множество, которое не содержит собственного подмножества разделяющего граф. Простая цепь. Цепь, не содержащая повторяющихся вершин. Простой цикл. Цикл, не содержащий повторяющихся вершим. Простой контур. Контур, не содержащий повторяющихся вершин. Простой путь. Путь, не содержащий повторяющихся вершин. Разрез. Разделяющее множество, состоящее из всех ребер, которые соединяют некоторое множество вершин с его дополнением. Разделяющее множество. Множество ребер связного графа, после удаления которых граф становится несвязным. Ребро. См. граф. Рефлексивный граф. Ориентированный граф, каждой вершине которого инцидентна петля. Смежные ребра или дуги. Два ребра или дуги, имеющие, по крайней мере, одну общую граничную точку. Сеть с ограниченной пропускной способностью. Сеть, в которой поток по каждой дуге заключен между нулем и верхней границей, называемой пропускной способностью дуги. Связный граф. Граф, в котором каждая пара различных вершин соединяется, по крайней мере, одной цепью. Степень вершины. Число ребер (или дуг), инцидентных вершине. Петли считаются дважды. Сеть. Связный ориентированный граф без петель. Этот термин используется в теории потоков. Сток. Вершина сети, в которой входной поток больше выходного. Строго параллельные дуги. Дуги, имеющие одинаковые начальную и конечную вершины. Сально связный граф. Ориентированный граф, для каждой упорядоченной пары различных вершин (v, w) которого, существует, по крайней мере, один путь из и в w. Симметрический граф. Ориентированный граф, дуги которого могут быть сгруппированы в пары параллельных, но противоположно направленных дуг. Точка сочленения. Вершина связного графа, после удаления которой граф становится несвязен. Тотальный граф. Ориентированный граф такой, что для каждых двух различных вершин ниш существует путь из v к w или путь из и. к v (или оба пути). Транзитивный граф. Ориентированный граф, который содержит дугу из v к w всякий раз, когда существует дуга из и к и и дуга — ИЗ V К W. Унику реальный граф. Граф (ориентированный граф), совокупность ребер (дуг) которого образует цикл (контур) или цепь (путь). Хорда, Ребро графа G, которое не содержится в дереве Т, являющемся подграфом G; термин хорда употребляется по отношению к определенному дереву Т. Хроматическое число графа. Наименьшее k такое, что вершины графа могут быть разделены на k множеств, каждое из которых является независимым множеством вершин. Цепь, Незамкнутый маршрут, не содержащий повторяющихся ребер. Цикл, Замкнутым маршрут, не содержащий повторяющихся ребер. Эйлеров граф. Граф, не содержащий вершин нечетной степени.
Полезные ссылки по теории графов и смежным дисциплинам. Программы, курсовые, рефераты, книги в электронном виде:
Книги в бумажном виде. Дискретная математика в Интернет-магазине:
Название |
Автор |
Издательство |
Год |
Цена |
|
Фурасов |
Бином. Лаборатория знаний |
2009 |
153руб. |
|
Кузнецов |
Лань |
2009 |
543руб. |
|
Пономарев |
Горячая Линия-Телеком |
2009 |
380руб. |
|
Спирина |
Academia |
2009 |
514руб. |
|
Москинова |
Логос |
2007 |
275руб. |
|
Крылов |
Факториал Пресс |
2007 |
2414руб. |
|
Галушкина |
Айрис-пресс |
2008 |
88руб. |
|
Шапорев |
BHV |
2009 |
261руб. |
|
Тишин |
BHV |
2008 |
234руб. |
|
Окулов |
Бином. Лаборатория знаний |
2008 |
274руб. |
|
Плотников |
Новое знание (Минск) |
2008 |
232руб. |
|
Шевелев |
Лань |
2008 |
880руб. |
|
Плотников |
Новое знание (Москва) |
2005 |
146руб. |
|
Просветов |
БИНОМ |
2008 |
183руб. |
|
Баврин |
Высшая школа |
2007 |
290руб. |
|
Аляев |
Финансы и статистика |
2006 |
150руб. |
|
Макоха |
ФИЗМАТЛИТ |
2005 |
338руб. |
|
Редькин |
Лань |
2006 |
59руб. |
|
Белоусов |
Издательство МГТУ им.Н.Э.Баумана |
2006 |
252руб. |
Ключевые слова: теория графов, виды графов, скачать учебник бесплатно, скачать книгу бесплатно, учебное пособие, курс лекций, граф, графы, связность графов, ориентированный граф, деревья, связность графов, кратчайший остов, кратчайший путь, задача о кратчайшем пути, фундаментальные, эйлеровы и гамильтоновы циклы, циклы в графе
|