ГлавнаяРегистрацияВход Аворут
Четверг, 28.03.2024, 12:01
Форма входа
Меню сайта










Категории каталога
Экономическая статистика [4]
Книги по экономической статистике: статистика труда, статистика населения и трудовых ресурсов, статистика финансов, статистика кредитных операций и операций с ценными бумагами и тд. Вы можете скачать книгу бесплатно.
Логика [15]
Книги по логике и математической логике и тд. Вы можете скачать книгу бесплатно.
Дискретная математика [23]
Книги по дискретной математике и тд. Вы можете скачать книгу бесплатно.
Эконометрия (эконометрика) [16]
Книги по эконометрике (эконометрии)и тд. Вы можете скачать книгу бесплатно.
Исследование операций [10]
Книги по математическим методам и моделям, исследованию операций, математическому программированию и тд. Вы можете скачать книгу бесплатно.
Математические методы и модели [11]
Книги по математическим методам и моделям, исследованию операций, математическому программированию и тд. Вы можете скачать книгу бесплатно.
Теория графов [24]
Книги по теории графов и тд. Вы можете скачать книгу бесплатно.
Логистика [3]
Книги по логистике и тд. Вы можете скачать книгу бесплатно.
Математическое программирование [19]
Книги по математическим методам и моделям, исследованию операций, математическому программированию и тд. Вы можете скачать книгу бесплатно.
Другие книги [4]
В эту категорию вошли книги, для которых ещё не создан раздел или его было трудно определить
Сметное дело в строительстве [2]
Книги по сметному делу в строительстве и тд. Вы можете скачать книгу бесплатно.
Информатика. MS Excel [2]
Книги по информатике, программированию: табличный процессор MS Excel и тд. Вы можете скачать книгу бесплатно.
Информатика. MS Access [2]
Книги по информатике, программированию: система управления базами данных MS Access и тд. Вы можете скачать книгу бесплатно.
Психология. Принятие решений [3]
Книги по психологии принятия решений и тд. Вы можете скачать книгу бесплатно.
Психология. Коучинг [3]
Книги по психологии:коучинг и тд. Вы можете скачать книгу бесплатно.
Финансовый анализ [8]
Книги по финансовому анализу: технический и фундаментальный анализ, рекомендации для игры на бирже и тд. Вы можете скачать книгу бесплатно.
Финансовая математика [2]
Книги по финансовой математике и тд. Вы можете скачать книгу бесплатно.
Теория игр [7]
Книги по теории игр и тд. Вы можете скачать книгу бесплатно.
Теория вероятностей и математическая статистика [53]
Книги по теории вероятностей, математической статистике и тд. Вы можете скачать книгу бесплатно.
Информационные системы и технологии [14]
Книги по информационным системам, информационным технологиям и тд. Вы можете скачать книгу бесплатно.


Друзья сайта




Главная » Файлы » Книги скачать бесплатно » Теория графов

Конечные графы и сети, Басакер Р., Саати Т., перевод с английского, Главная редакция физико-математической литературы изд-ва «Наука», Москва
[ · Скачать удаленно (3,93 Мб) ] 09.03.2010, 14:13
Конечные графы и сети, Басакер Р., Саати Т., перевод с английского, Главная редакция физико-математической литературы изд-ва «Наука», Москва. 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руб.
 
Ключевые слова: теория графов, виды графов, скачать учебник бесплатно, скачать книгу бесплатно, учебное пособие, курс лекций, граф, графы, связность графов, ориентированный граф, деревья, связность графов, кратчайший остов, кратчайший путь, задача о кратчайшем пути, фундаментальные, эйлеровы и гамильтоновы циклы, циклы в графе
Категория: Теория графов | Добавил: avorut
Просмотров: 1593 | Загрузок: 475 | Рейтинг: 0.0/0 |
 


Заказ контрольной работы

www.ru yandex.ru rambler.ru google.com



Rambler's Top100

каталог сайтів Каталог україномовних сайтів Каталог україномовних сайтів


 
Поиск
Copyright MyCorp © 2024
Хостинг от uCoz