В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких науках, как физика, электротехника химии, она проникла и в науки считавшиеся раньше далекими от нее,—экономику, социологию лингвистику и др. Давно известны тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов, исследованием операций, теорией кодировании, теорией игр). Широко используется теория графов при решении различных задач на вычислительных машинах. За последние годы тематика теории графов стала значительно разнообразней; резко увеличилось количество публикаций. Предлагаемая книга написана одним из видных специалистов по дискретной математике. Несмотря на небольшой объем и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безусловно, будет полезна студентам университетов и технических вузов и, несомненно, заинтересует широкие круги научных работников, занимающихся приложениям к дискретной математики.

 

Название:

Размер: 4,64 Мб

Описание: Ф. Харари Теория графов Перевод с английского В. П. Козырева Под редакцией Г. П. Гаврилова Издательство «МИР» Москва 1973

Ссылка для скачивания файла:

 

 

ОГЛАВЛЕНИЕ
Предисловие редактора перевода . . 6
Введение 9
Глава 1 Открытие! .... 13
Задача о кенигсбергских мостах .. .... 13
Электрические цепи  ... 14
Химические изомеры . . 15
«Вокруг света» . . 16
Гипотеза четырех красок . 17
Теория графов в двадцатом веке . .18
2 Графы . .21
Типы графов ... . . . . , , 21
Маршруты и связность 26
Степени ... 27
Задача Рамсея  28
Экстремальные графы 30
Графы пересечений .... 33
Операции над графами .  35
Упражнения 38
3 Блоки  .... 41
Точки сочленения, мосты и блоки . 41
Графы блоков и графы точек сочленения  ... 45
Упражнения 46
Главл 4 Деревья . .  48
Описание дерекьеп . .  . 48
Центры и центроиды , , . . . 51
Деревья блоков и точек сочленения . 53
Независимые циклы и коциклы 54
Матроилы 57
Упражнения . 59
Глава 5 Связность . . . 60
Связность и реберная связность .... ... 60
Графические варианты теоремы Ментера 64
Другие варианты теоремы Менгера 70
Упражнения . . . 74
Глава 6 Разбиения 76
Упражнения , 81
Глава 7. Обходы графов . 83
Эйлеровы графы 83
Гамильтоновы графы . 86
Упражнения . . 88
Глава 8 Реберные графы . ... 91
Некоторые свойства реберных графов , 91
Характеризация реберных графов 94
Специальные реберные графы 99
Реберные графы и обходы 101
Тотальные графы ... 103
Упражнения 104
Глава 9 Факторизация . , 106
1 факторизации 106
2 факторизация Ш
Древесность 1 13
Упражнения . 116
Гтава 10 Покрытия ... 117
Покрытия и независимость , 117
Критические вершины и ребра 120
Реберное ядро ... 122
Упражнения ... . 124
Глава II Планарность . . 126
Плоские и планарные графы . 126
Внешнепланарные графы 131
Георема Понтрягина — Куратовского . . 133
Другие характеризяцки планарных графов . . 138
Род, толщина, крупность число скрещиваний 141
Упражнения . ... 148
12 Раскраски 151
Хроматическое число 152
Теорема о пяти красках 15э
Гипотеза четырех красок ... 156
Теорема Хивуда о раскраске карт . 162
Однозначно раскрашиваемые графы 164
Критические графы 167
Гомоморфизмы 6 9
Хроматический многочлен 172
Упражнения ... 175
13. Матрицы . 178
Матрица смежностей . 178
Матрица инциденций . . 180
Матрица циклов 183
Обзор дополнительных свойств матроидов 186
Упражнения . . .187
Группы  автоморфизмов графа . 193
Операции на группах подстановок 194
Группа графа-композиции 195
Графы с данной группой 198
Симметрические графы . 201
Графы с более сильной симметрией 204
Упражнения 206
Перечисления 200
Помеченные графы . . 209
Теорема перечисления Пойа 211
Перечисление графов . . 216
Перечисление деревьев . . . 219
Теорема перечисления степенной группы , , . 224
Решенные к нерешенные задачи перечисления графов 225 
Упражнения 230 
Орграфы . . . 232
Орграфы и соединимость . . . 2°-2
Ориентированная двойственность и бесконтурные орграфы . 234
Орграфы и матрицы 237
Обзор по проблеме восстановления турниров 244
Упражнения . 244
Приложение I Диаграммы графов 248
Приложение II Диаграммы орграфом 200
Приложение III Диаграммы деревьев 26G
Список литературы и именной указатель 2Ь8
Указатель обозначений 291
Предметный указатель

 

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
валентность вершины Т7
вершина графа 22, 126
— изолированная 28
— инцидентная ребру
— концевая 28
— критическая 121
— неподвижная 201
— орграфа 232
— периферическая 51
— центральная 51
центроидкая 52
вершинная база 237
вершины подобные 201
— смежные 22 213
вес вершины 52
вес функции 213
ветвь 56
— к вершине о 2
вихрь 187
внешность цикла 134
выпуклый полиэдр

гипотеза Улама 25, 26 48 58 202 244 —
— Хадпигера 161, 162
— четырех красок 151, 164, 167, 172
гомоморфизм графа 169
— полный, порядка n 159
— элементарный 169
гомоморфный образ графа 196
граничный оператор 54
грань 127
— внешняя 127
— внутренняя 127
граф асимметрический 190
- ациклический 48
— базисный 132
— бесконечный 36
— блоков 45
— — и точек сочленения 53
— вершинно-критический J1
— вершишю-симметрический 201
— внешнепланарный 131
максимальный 131
— вполне несвязный 2$
— гамильтонов 85
— геометрически двойственный 138
— Давида 29
— двудольный 31
— дополнительный 29
— интервалов 35
— клик 34
— комбинаторно двойственный 139
— критический 167
— кубический 28
— Леви 205, 206
— Мак-Джи 205
— направленный 23
— неразделимый 41
— несводимый 123
— однозначно раскрашишемый 164
одноциклический 58
— пересечений 33
— планарный 127
— — максимальный 128
— плоский 127
— подразбиении I01
— полный 29
граф полный двудольный 32
n-дольный 37
— пол у несводимый 123
— помеченный 23
— произвольно гамильтонов 89
проходимый 89
— простой 197
— реберно-критический 121
— реберно-регулярный 202
— реберно симметрический 201
— реберный 91, 94
— — итерированный 91
— регулярный 28
— самодополнитечьный 29
— сводимый 123
— симметрический 201
— составной 197
— тороидальный 142
— тотальный 103
— точек сочленения 45
— тривиальный 22
— Хивуда 204
— эйлеров 83
— n-раскрашиваемый 152
— n транзитивный 204
— n-унитранзитивный 204
— n-хроматический 152
— а-перестановочный 206
граф-композиция 196
графоид 58
графы гомеоморфные
— изоморфные 24 190
— коспектральные 168
группа 189
— графа 190
— вершинная 190
— диэдральная 195
— знакопеременная 195
— конфигураций 213
— парная 217
— — редуцированная 218
— подстановок 190
— реберная 191
— симметрическая 195
— степенная 194
— тождественная |95
— циклическая 195
гpуппы идентичные ISO
— изоморфные 190
дерево 
—  точек сочленения 54
— входящее 235
— выходящее 235
диагональ блока 47
«диаграмма Хассе» 73
диаметр 27
длина маршрута 31
добавление вершины 25
— ребра 25
дополнение графа 29
достижимость 133
древесность графа 113
дуга 23, 232
животное 227
замощение 2-решетки 227
звезда (лапа, гроздь) 32
изоморфизм 24
инвариант 24
инцидентность ребра и вершины 22
искаженность графа 149
источник 235
карта плоская 127
с корневым ребром 227
квадрат графа 27
кьадратпьш корень графа 38
клетка 204
количество очкоь 243
клика графа 34
кограница 55
ко граничный оператор 54
кодерево 56
колесо 63
комплекс 20
композиция графов 37, 196
— групп 194
компонента 27
— нечетная 108
— односторонняя 233
— сильная 233
— слабая 233
конденсация 234
контур 233
— эйлеров 240
конфигурация 2|3
конъюнкция 40, 243
корона графов 198
коцикл 55
лемма Вернсайда 212 214
лес 48
линия матрицы 71
линейный подграф графа 180
орграфа 179
маршрут 26
— замкнутый 26
— несовершенный 119
— открытый 26
— совершенный 119
— сводимый 120
матрица достижимостей 238
— инциденций 180
— коциклов 184
— обходов 238
— по чу степеней захода 239
— — исхода 239
— разреженная 241
— смежностей графа 179
орграфа 237
— циклов 183
матричная теорема о деревьях 178,
— бинарный 188
— графический 180
— ко графический 180
— коциклов графа. 57
— циклов графа 57
— эйлеров 188
многочлен деревьев графа 187
множество вершин 22
— внешне устойчивое 118
— внутренне устойчивое 118
— независимое 57, 108, 118
— разделяющее 64
— ребер 22
мост 41
мультиграф 23
наследственное свойство 119
надграф 24
независимые единицы матрицы 71
обхват 27
объединение графов 36
одноцветный ктасс 152
ожерелье 212—215, 224 225
окрестность вершины 197
— замкнутая 197
окружение 27
орбита 211
орграф 232
— бесконтурный 235
— контрафункциональныи 236
орграф несвязный 233
— обратный 234
— односторонний 233
— примитивный 246
— реберный 245
— сильный 233
— слабый 233
— строго односторонний 244
слабый 244
— функциональный 23G
— эйлеров 240
ориентация графа 246
остов 55
пара связностей 62
паросочетаиие 119
— наибольшее 119
перечисляющий ряд для конфигураций
— — — фигур 213
петля 23
подграф 24
— линейный 180
— остшиый 24
— порожденный 24
— четный 227
покрытие лершинное 117
— реберное 117
полиэдр 127
полная раскраска 170
помтный набор инвариантов 24
полугруппа графа 208
полуконтур 233
полумаршрут 233
полупуть 233
пол устелень захода 232
— исхода 232
порядок группы 190
последовательность пути 204
принцип ориентированной двойственности 234, 235
произведение графов 36
— групп 190
— поэлементное 239
пространство коциклов 55
— циклов 55
псевдограф 23
путь 233
разбиение графа 76
— графическое 76
— числа 76
разрез 55
— цикчический 55
размерность симплекса 20
расстояние в графе 27
— — орграфе 33
раскраска графа 152
— плоской карты 156
— полная 170
— ребер 159
—  цветами 172
ребра кратные 23
— независимые 108
— подобные 201
— смежные 22
ребро графа 22
— инцидентное вершине 22
— критическое 121
— подразбитое 101
— симметричное 221
род графа 142
— полиэдра 142
связность 60
— локальная 66
— односторонняя 233
— реберная 60
— сильная 233
— слабая 233
сеть 70
система различных представшей ей 12
стабилизатор 211
степень вершины 21
— графа 27
— группы 190
— ребра 202
сток 235
стягивание 137
— элементарное 17
— групп 193
теорема Бине — Коши
— об интерполяции гомоморфизмов 171
— о пяти красках 151, 155, 156
— перечисления Попа 211—215 217
— Хивуда о раскраске карт 162
— BEST 240
толщина графа 145
точка сочленении 41
транзитивная тройка 241
треугольник 26
— нечетный 90
— четный 95
турнир 24
турнир состязания
тэта граф 85 
удаление вершины 20
— ребра 25
укладка графа 126
уравнение характеристики неподобия
для деревьев 221
— Эйлера — Пуанкаре 57
фактор графа 106
факторизация графа 106
фигура 213
формула Оттера 222
— Эйлера для полиэдрoв 127
функция связности 62
хорда 55
хроматический класс
— многочлен 173
цветной граф группы
центр графа 51
центроид дерева 52
цепи непересекающиеся 64
— реберно непересекающиеся 64
цепь 26
— альтернирующая 109
— геодезическая 27
— простая 26
— гамильтона 85
— графоида 58
— матроида 57
— простой 26
— эйлеров 83
циклическая тройка 241
циклический вектор графа 54
цикловой индекс 212
число хроматическое 170
реберное 118
— пересечения 33
— покрытия 117
— — реберного 117
— Рамсея 30
— — реберное 104
— скрещиваний 148
— Хадвигера 177
— хроматическое 152
— n-хроматическое 177

 

 

 

Книги в бумажном виде. Дискретная математика в Интернет-магазине:

 

Ключевые слова: теория графов, виды графов, скачать учебник бесплатно, скачать книгу бесплатно, учебное пособие, курс лекций, граф, графы, связность графов, ориентированный граф, деревья, связность графов, кратчайший остов, кратчайший путь, задача о кратчайшем пути, фундаментальные, эйлеровы и гамильтоновы циклы, циклы в графе