ОГЛАВЛЕНИЕ
Предисловие редактора перевода 5
Предисловие 7
1. Введение 9
§ 1. Что такое граф? 9
2. Определения и примеры 17
§ 2. Определения 17
§ 3. Примеры графов 24
§ 4. Укладки графов 31
3. Цепи и циклы 36
§ 5. Новые определения 36
§ 6. Эйлеровы графы 43
§ 7. Гамильтоновы графы 48
§ 8. Бесконечные графы 51
4. Деревья 57
§ 9. Элементарные свойства деревьев 57
§ 10. Перечисление деревьев 62
§ 11. Некоторые приложения теории графов ... 67
5. Плаиарность и двойственность 74
§ 12. Пленарные графы 74
§ 13. Теорема Эйлера о плоских графах ... . 81
§ 14. Графы на других поверхностях 87
§ 15. Двойственные графы . 91
§ 16. Двойственность по Уитни 98
6. Раскрашивание графов 101
§ 17. Хроматическое число 101
§ 18. Два доказательства 106
§ 19. Раскрашивание карт . ПО
§ 20. Реберная раскраска 115
§ 21. Хроматические многочлены 120
7. Орграфы . 126
§ 22. Определения 126
§ 23. Эйлеровы орграфы и турниры 131
§ 24. Цепи Маркова . ... 138
8. Паросочетания, свадьбы и теорема Менгера . . . 144
§ 25. Теорема Холла о свадьбах 144
§ 26 Теория трансверсалей . . ... 148
§ 27. Приложения теоремы Холла 151
§ 28. Теорема Менгера 157
§ 29. Потоки в сетях 163
9. Теория матроидов 173
§ 30. Введение в теорию матроидов 173
§ 31. Примеры матроидов 178
§ 32. Матроиды и теория графов 184
§ 33. Матроиды и теория трансверсалей 191
Послесловие 198
Приложение 200
Список литературы .... 201
Предметный указатель 202

 

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Автоморфизм 30
алгоритм Краскала 69
— нахождения максимального потока 168
— Флёри 45
база матроида 174
бесконечная квадратная решетка 52
валентность 20
вектор вероятностей 140
векторное пространство, связанное с графом 24
— — — с матроидом 191
величина потока 165
вероятность перехода 139
вершина 9, 17, 18, 19, 51
— висячая 20
— изолированная 20
— конечная 36
— концевая 20
— начальная 36
вершинно непересекающиеся простые цепи 157
выигрыш 137
гамильтонов цикл 48
гаммой д 184
гипотеза Хадвигера 105
— четырех красок 14, 104
— — — для карт 111
головоломка «мгновенное помешательство» 70
гомеоморфные графы 77
грань 81
грань бесконечная 81
— содержащая точку 81
граф 9, 18
— бесконечный 20, 51
— вполне несвязный 24
— гамильтонов 13, 49
— двойственный 91
— двудольный 26
— звездный 27
— критический 105
— кубический 25
— локально конечный 52
— — счетный 52
— многогранника 83
— несвязный 28, 38
— общий 18
— ориентированный 11, 19, 126
— ориентируемый 129
— Петерсена 25
— пленарный 13, 34, 74
— плоский 74
— полный 25
— — двудольный 27
— полугамильтонов 49
— полуэйлеров 43, 54
— помеченный 63
— произвольно вычерчиваемый 47
-- простой 11, 17
— пустой 24
— 6-раскрашиваемый 101
— реберно ft-раскрашиваемый 115
— реберный 24
— регулярный 25
— — степени г 25
— рода g 88
— самодополнительный 3 0
— связный 13, 28, 38
граф /г-связный 163
— счетный 51
— тороидальный 88
— трехвалентный 25
— fe-хроматический 101
— циклический 28
— эйлеров 13, 43, 54
ft-граф 24
группа автоморфизмов графа 30
двойственность 14, 91
— абстрактная 94
— алгебраическая 97
— геометрическая 91
— по Уитни 98
дерево 13, 39, 57
— остовное 59
диаграмма 9, 31
диаметр 42
длина маршрута 37
додекаэдр 26
дополнение графа 29, 60
дуга 19
— насыщенная 165
— ненасыщенная 165
жордаиова дуга 32
— кривая 32
— — замкнутая 32
задача о гареме 147
— о кёнигсбергских мостах 43
— о коммивояжере 70
— о свадьбах 144
— о соединении городов 69
— о составлении расписаний 124, 155
замыкание множества 178
изоморфные графы 11, 21
— — помеченные 63
— матроиды 179
— орграфы 127
икосаэдр 26
инцидентная ребру вершина 20, 127
инцидентное вершине ребро 20,
источник 132
карта ПО
— fe-раскрашиваемая ПО
кобаза 187
колесо 28
компонента связности 28, 38
коранг 187 °
коцикл 187
кратные ребра 11
куб 26
латинский квадрат 152
— прямоугольник 151
лемма о рукопожатиях 20
лес 57
— остовный 59
линия 17
лист Мёбиуса 90
маршрут 36
— бесконечный 52
— конечный 52
— ориентированный 127
матрица иициденций 23, 153
— перехода 139, 140
— смежности 21, 127
матричная теорема о деревьях 67
матроид 174, 175
— бинарный 181
— векторный 174
— графический 180
— двойственный 185
— двудольный 183
— дискретный 179
— кографический 181, 187
— ft-однородный 179
— пленарный 181
— представимый 181
— — над полем 181
— разрезов 180
— регулярный 181
— трансверсальный 182
— тривиальный 179
— Фано 184
— циклический 174
матроид эйлеров 183
мера 69
метка 63
минор 183
множество вершин 17, 125
— зависимое 175
— замкнутое 178
— конезависимое 187
— независимое 174, 175, 184
— отделяющее 184
— -отделяющее 158
— разделяющее 40
— разделяющее 158
— ребер 17
— — независимое 42
мост 40
набор выигрышей 137
начальная вершина маршрута 36
обхват 41
объединение графов 27
— матроидов 178
ограничение матроида 182
октаэдр 26
орграф 7, 19, 126
— ассоциированный 140
— гамильтонов 133
— обратный 130
— полугамильтонов 133
— полуэйлеров 133
— простой 127
— связный 128
— сильно связный 128
— слабо связный 128
— эйлеров 132
орлемма о рукопожатиях 132
орцепь 128
— простая 128
— эйлерова 132
орцикл 128
основание 126
пара параллельных элементов 177
пересечение 33
перечисление графов 62
перешеек 40
петля 11, 18, 177
подграф 21
подпространство разрезов 48
— циклическое 191
— циклов 48
полустепень захода 132, 165
— исхода 132, 165
поток 165
— максимальный 166
— нулевой 165
пропускная способность дуги 164
— — разреза 166
радиус 42
размерность 35
разрез 40, 166
ранг коциклический 60
— матроида 174
— множества 151, 176
— разреза 60
— словарный 153
— циклический 59
ранговая функция 176
раскрашивание графов 101
— карт 110
распределение меток 63
расстояние 42
реберная раскраска графов 115, 154
реберио непересекающиеся простые цепи 157
реберно-хроматическое число 116
ребро 9, 17, 18, 51
— ориентированное 19
род 88
связанные вершины 38
связка 64
семейство 17
— дуг 126
сеть 164
система различных представителей 148
случайное блуждание 138
смежные вершины 20, 127
— ребра 20
совершенное паросочетание 145
соединение графов 27
состояние цепи Маркова 140
состояние цепи Маркова возвратное 141
— — — невозвратное 141
— — — непериодическое 142
— — — периодическое 142
— — — с периодом t 142
— — — поглощающее 142
— — — рекуррентное 141
— — — эргодическое 142
степень 9, 20, 52
сток 132
стягиваемый граф 78
стягивание 78
— элементарное 78
сужение матроида 182
сумма мер 69
трансверсаль общая 155
треугольник 37
турнир 133
— двудольный 138
— несвязный 137
— транзитивный 137
узел 17
укладка 33
фундаментальная система разрезов 60
— — циклов 60
таблица графов 200
теорема Брукса 103
— Визинга 116
— Дирака 49
— Жордана о кривой 32
— Кёнига — Эгервари 153
— Куратовского 77
— Кэли 64
— о максимальном потоке и минимальном разрезе 166
— о пяти красках 104
— о целочисленности 161
— Радо 192
— Турана экстремальная 42
— Эйлера 83
теория матроидов 15
тетраэдр 26
тождественные с точностью до вершин степени 2 графы 77
толщина 85
тор 87
тороидальная толщина 91
точка 17
трансверсаль 148
— независимая 192
характеристическое число 31
хроматическая функция 120
хроматический индекс 116
— класс 116
— многочлен 122
хроматическое число 101
центр 42
цепь 37
— замкнутая 37
— Маркова 140
— — неприводимая 141
— — эргодическая 142
— простая 37
— эйлерова 43, 54
цикл 12, 37, 175, 178
цикломатическое число 59
число скрещиваний 80
эквивалентные вершины 38

 

 

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

 

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