Следуя пожеланиям одного из рецензентов польского издания — профессора Антони Смолюка, — в первом параграфе книги изменен порядок изложения, — двуосновная система Мальцева дается не в начале параграфа. <...> В курсе теории множеств при рассмотрении бинарных отношений для наглядности используются графы Бержа, а диаграммы Хассе применяются при обсуждении частично упорядоченных множеств, в частности, решеток подструктур алгебраических структур. <...> Случайные блуждания по графам являются естественным методом наглядного обучения теории вероятностей. <...> В то же время дано краткое введение в методы идемпотентного анализа на графах, поскольку это позволяет единообразно изложить уравнения Беллмана. <...> Авторы согласились с высказанными им пожеланиями по терминологии и обменяли в первоначальном тексте термины «простой граф» и «обычный граф», хотя сделали это не без сомнений. <...> Множество W будем называть множеством вершин, а множество U — множеством веток. <...> Кожана [17M Первая аксиома (1.1) означает, что каждое ребро «соединяет», по крайней мере, две (возможно, одинаковые) вершины, а другая (1.2) ограничивает эту возможность парами вершин, отличающимися разве что послеw ;; довательностью: () w ;; и 24w w= 12 или 14w w= и 23w w= С другой стороны отсутствуют ограничения на множество веток (){ u Uw u w P∈∈ соединяющих данные две uw и () . <...> Бесконечные, полубесконечные, конечные и пустые графы Из условия (1.6) следует, что если множество веток U UUU =∪ ∪ не пусто, то множество вершин W тоже не пусто. <...> Граф из примера 2.4 имеет кратность אo, поскольку с вершиной () 0, 1 инцидентно именно столько веток, а число веток, инцидентных любой другой вершине, не превышает אo. <...> Граф из примера 3.3 Этот граф можно задать в виде () 13 } W,, Γ где :2W W Γ→ — мультифункция*, отображающая W во множество его подмножеств и сопоставляющая каждой вершине из W множество соседних с ней вершин. <...> Заметим теперь, что вместо определения графа с помощью двухосновной системы Мальцева, данного <...>
Избранные_главы_теории_графов.pdf
УДК 519.17
ББК 22.174.2
О-421
Одинец В. П., Шлензак В. А.
Избранные главы теории графов / Авториз. пер. с польск. В. П. Одинца при
участии М. В. Поспелова / Под ред. П. А. Головача. — М.–Ижевск: Институт
компьютерных исследований, НИЦ «Регулярная и хаотическая динамика»,
2009. — 504 с.
Книга В. П. Одинца и В. А. Шлензака является связующим звеном между
классической (детерминированной) теорией графов и современной теорией стохастических
процессов на графах. Наряду с изложением необходимого математического
аппарата книга содержит приложения к информатике, технике, физике,
управлению.
Книга представляет интерес как для профессиональных математиков, так
и для информатиков, инженеров, управленцев, специалистов по проблемам безопасности.
ISBN
978-5-93972-748-8
© В. П. Одинец, В. А. Шлензак, 2009
© В. П. Одинец, М. В. Поспелов, перевод на русский язык, 2009
© В. П. Одинец, М. В. Поспелов, приложение B, 2009
© НИЦ «Регулярная и хаотическая динамика», 2009
http://shop.rcd.ru
http://ics.org.ru
Стр.4
Оглавление
Предисловие к русскому изданию ..........................................................
Предисловие ................................................................................................
ЧАСТЬ I. ДЕТЕРМИНИРОВАННЫЕ ГРАФЫ
ГЛАВА I. Взаимная определяемость графов ..........................................
§ 1. Графы — двухосновные системы Мальцева ................................
§ 2. Бесконечные, полубесконечные, конечные и пустые графы .....
§ 3. Графы ориентированные и неориентированные ..........................
§ 4. Степень вершины и степень графа ...............................................
§ 5. Графы Бержа и бинарные отношения ...........................................
§ 6. Гиперграфы как модели систем Мальцева ...................................
ГЛАВА II. Морфизмы графов ....................................................................
§ 7. Гомоморфизм графов как модель систем Мальцева ...................
§ 8. Изоморфизмы графов и их инварианты .......................................
§ 9. Группа автоморфизмов графа ........................................................
ГЛАВА III. Решетка подсистем графа ......................................................
§ 10. Части графа как подсистемы системы Мальцева ......................
§ 11. Число внутренней устойчивости и плотность графа ................
§ 12. Операции на графах ......................................................................
ГЛАВА IV. Связность графа ......................................................................
§ 13. Маршруты и дороги в графе ........................................................
§ 14. Различные виды связности графа ................................................
§ 15. Метрики и квазиметрики на графе ..............................................
14
14
18
20
23
27
40
45
45
48
57
65
65
67
74
79
79
86
89
§ 16. Цепи и циклы Эйлера ................................................................... 111
§ 17. Цепи и циклы Гамильтона ........................................................... 117
ГЛАВА V. Цикломатика графов ............................................................... 123
§ 18. Цикломатическое число графа. Деревья .................................... 123
8
9
Стр.6
ОГЛАВЛЕНИЕ
7
§ 19. Каркасы и разрезы графа ............................................................. 132
§ 20. Пространство суграфов ................................................................ 140
§ 21. Матрицы инциденций, разрезов и циклов .................................. 149
§ 22. Совершенные графы ..................................................................... 176
ГЛАВА VI. Ориентация графов ................................................................. 195
§ 23. Достижимость в ориентированных графах ................................ 195
§ 24. Ядра графов и игры на графах ..................................................... 207
ПРИЛОЖЕНИЕ А. Идемпотентный анализ на графах ............................ 223
ПРИЛОЖЕНИЕ B. Элементы теории матроидов ...................................... 250
ЧАСТЬ II. СТОХАСТИЧЕСКИЕ ГРАФЫ
ГЛАВА VII. Стохастические процессы на графах ................................. 262
§ 25. Случайные графы ......................................................................... 262
§ 26. Случайные блуждания на графах ................................................ 295
§ 27. Преследование на графах ............................................................. 358
§ 28. Графы потока сигнала и их редукция ......................................... 403
§ 29. Процессы марковские и полумарковские ................................... 424
Литература .................................................................................................. 467
Именной указатель .................................................................................... 485
Предметный указатель ............................................................................. 492
Указатель обозначений ............................................................................. 502
Стр.7