Читать онлайн «Теория графов»

А. В. Омельченко Теория графов Москва Издательство МЦНМО 2018 УДК 519. 17 ББК 22. 176 057 Омельченко А. В. 057 Теория графов. — М. : МЦНМО, 2018. —416 с. ISBN 978-5-4439-1247-9 В основу данного учебника легли материалы семестрового курса лекций, читающегося автором в течение нескольких лет студентам первых курсов бакалавриата Санкт-Петербургского Академического университета. В учебник включены все основные разделы современной теории графов — деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы. В конце каждого параграфа приводятся задачи, дополняющие изложенный в учебнике теоретический материал. Все утверждения снабжены подробными доказательствами, изложение иллюстрируется большим количеством рисунков. Учебник рассчитан на студентов младших курсов, изучающих математику и информатику, а также на специалистов из смежных областей, желающих самостоятельно изучить основные разделы теории графов. Большая часть материала не предполагает специальных предварительных знаний и может быть использована школьниками, изучающими программирование и дискретную математику. Наконец, этот учебник может быть полезен преподавателям, ведущим соответствующие курсы. ББК 22. 176 ISBN 978-5-4439-1247-9 © А. В. Омельченко, 2018 © МЦНМО, 2018 Оглавление Предисловие 5 Глава 1. Основные понятия 8 § 1. Основные понятия и определения теории графов 8 § 2. Маршруты, пути, циклы в графе. Связные графы и орграфы 27 § 3. Подграф графа G. Основные операции над графами 41 § 4. Изоморфизм и автоморфизм графов 54 Глава 2. Деревья и их перечисление 73 § 1. Основные свойства деревьев 73 § 2. Перечисление деревьев. Формула Кэли 89 § 3. Подсчет остовных деревьев в графе. Матричная теорема о деревьях 98 Глава 3. Циклы в графах 117 § 1. Эйлеровы циклы 117 § 2. Гамильтоновы циклы 132 § 3. Линейное пространство ребер. Циклы и разрезы 147 § 4. Циркуляции и напряжения. Электрические сети 165 Глава 4. Связность в графах 181 § 1. Вершинная и реберная связность графа 181 § 2. Двусвязные графы . 188 § 3. k-связные графы. Теорема Менгера 200 § 4. Теорема Форда—Фалкерсона 209 Глава 5. Паросочетания в графах 222 § 1. Понятие паросочетания. Теорема Бержа. Независимые множества и покрытия графа 222 § 2. Паросочетания в двудольных графах. Алгоритм Куна поиска максимального паросочетания в двудольном графе 240 § 3. Совершенные паросочетания в произвольном графе. Теорема Татта 254 § 4. Максимальные паросочетания в произвольном графе. Структурная теорема Галлаи—Эдмондса. Алгоритм Эдмондса 273 4 Оглавление Глава 6. Раскраска графов 288 § 1. k-раскрашиваемые графы. Теорема Брукса 288 § 2. Нижние оценки на хроматическое число. Теорема Турана. Совершенные графы 307 § 3. Реберная раскраска графов 326 § 4. Хроматический многочлен графа 336 Глава 7. Планарные графы 347 § 1. Планарные графы и их основные свойства 347 § 2. Формула Эйлера для плоских графов 363 § 3. Карты на поверхностях 374 § 4. Критерии планарности графов. Теорема Куратовского 388 § 5. Раскраска плоских графов 401 Литература 410 Предметный указатель 412 Предисловие Теория графов является в настоящий момент одним из наиболее динамично развивающихся разделов дискретной математики.