Зыков А.А. Основы теории графов

Зыков А.А. Основы теории графов.- М.: Вузовская книга, 2004. — 664 c.
Систематическое введение в теорию графов, построенное в соответствии с внутренней логикой ее развития. Основные положения доказываются и иногда иллюстрируются примерами прикладного характера. Многие результаты, не являющиеся необходимыми для последовательного развертывания теории, приводятся в виде упражнений и дополнений. Для студентов и аспирантов по специальностям "Математика" и "Прикладная математика", а также научных работников и инженеров.
ОГЛАВЛЕНИЕ
От автора............................. -
ВВЕДЕНИЕ. ............................
ГЛАВА I ИДЕНТИФИКАЦИЯ
§1.1 Обыкновенные графы..........................................1
§1.2 Изоморфизм....................................................19
§ 1.3. Инварианты . .................................................27
§ 1.4. Вычисление инвариантов......................................39
§1.5. Проблема изоморфизма........................................53
§1.6. Некоторые применения плотности и неплотности.....61
§ 1.7. Алгоритмы для плотности, неплотности и изоморфизма 70
§1.8 Оценки плотности и неплотности. Граф Турана............86
§ 1.9. Оптимальные и критические графы..........................97
§ 1.10. Проблемы восстановления..................108
ГЛАВА 2 СВЯЗНОСТЬ
§2.1. Маршруты...........................128
§2.2. Блоки..............................145
§2.3. Деревья.............................158
§2.4. Паросочетания и двудольные графы............168
§2.5. l-связные графы........................186
§ 2.6 Взвешенные графы и метрика................202
§ 2.7. Мультграфы..........................220
§ 2.8. Эйлеровы цепи и циклы...................232
§ 2.9. Раскраски ребер........................ 238
ГЛАВА 3 ЦИКЛОМАТИКА
§3.1. Каркасы и разрезы.......................252
§ 3.2. Пространство суграфов....................265
§3.3. Матрицы инциденций, разрезов и циклов.........272
§ 3.4. Графы с заданными разрезами и циклами.........283
§ 3.5. Топологические графы....................301
§3.6. Планарность..........................313
§ 3.7. Борьба с пересечениями....................336
§ 3.8 Гипотеза Хадвигера.....................349
§ 3.9. Раскраски плоских триангуляций..............367
§ 3.10. Совершенные графы.....................391
ГЛАВА 4. ОРИЕНТАЦИЯ
§4.1. Конечные графы общего вида................411
§ 4.2. Достижимость.........................424
§ 4.3. Ядра...............................450
§4.4. Ориентируемость.......................464
§ 4.5. Транзитируемость.......................472
БУЛЕВЫ МЕТОДЫ В ТЕОРИИ ГРАФОВ. . . 489
ДОБАВЛЕНИЕ!. ПРОСТРАНСТВО ГРАФОВ И ЕГО
ФАКТОРИЗАЦИИ...............508
ЗАКЛЮЧЕНИЕ..........................512
ЭПИЛОГ..............................520
УКАЗАТЕЛЬ-СПРАВОЧНИК...................526
Часть 1

Часть 2

Дополнительные исправления
(22, 5) ti = sn–i+1
(45, середина) вычислений, в отли-
(55, 4сн) Подлипенский [80, 8B321; 81#
(68, середина) каждым Hi . И.М.Горгос
(72, 4сн) A3  {45}
(79, 5) переходом
(143, 2сн) G <курс.>
(177, 9сн) образованная
(197, 7сн) в (  q)-связном
(256, 13, 18 и 19) UR <три раза>
(263, 10сн)  k 
(366, 14сн)  G , G2 , …
(420, 6сн) x  {(i, j) /
(475, конец формулы (4)) x  z);
(501, низ) <после предпоследней и перед последней матрицами надо не  , а  >
(514, 3–2сн) < переместить f: в следующую строку>
(515, 5сн) 21843]; Кибернетика, 1979, №5, 15–20; Методы
(552, 6сн) графа k-расстояний означает
(556, 13сн) графоидальные <с начала строки>
(571, 4) <не р, а  греч. два раза>
(580, середина) одной из них. J.I.Hall
(602, 7) (k-separability)
(616, 5–4сн) (mod 4), восстанавливаемость имеет место,
при п  4 – нет, а для
(622, 5сн) (i-colorings)
(623, 9сн) (extendable)
(626, 11–12) Quilliot
(632, 12) собственные числа <с начала строки>
(632, 13сн) 15(1891)
(636, 15) сшивание <с начала строки>
(645, 14сн) критерии <единств. число)>
(651, 1) §1.3