Асанов М.О., Баранский В.А. Дискретная математика: Графы, матроиды, алгоритмы ОНЛАЙН

Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд.- СПб, 2010. - 368 c.
В учебном пособии изложен ряд основных разделов теории графов и матроидов. Рассмотрены алгоритмы дискретной оптимизации на сетях и графах, наиболее часто используемые программистами.
Пособие предназначено для студентов и аспирантов, специализирующихся в области компьютерных наук и информационной безопасности, для практикующих программистов, для всех желающих изучить основы современной дискретной компьютерной математики.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию................
Предисловие к первому изданию.................
Глава 1. Основные понятия теории графов...........
§ 1.1. Основные определения...............
§ 1.2. Маршруты, связность, циклы и разрезы.....
§1.3. Ориентированные графы..............
§ 1.4. Матрицы, ассоциированные с графом.......
Глава 2. Деревья.........................
§2.1. Леса, деревья, остовы ...............
§ 2.2. Блоки и точки сочленения.............
§ 2.3. Число остовов в связном обыкновенном графе . .
Глава 3. Обходы графов.....................
§ 3.1. Эйлеровы графы...................
§ 3.2. Гамильтоновы графы................
Глава 4. Матроиды........................
§4.1. Пол у модулярные решетки, условие Жордана-
Дедекинда......................
§ 4.2. Конечномерные геометрические решетки
и матроиды .....................
§ 4.3. Основные понятия теории матроидов.......
§ 4.4. Различные аксиоматизации матроидов......
§ 4.5. Двойственный матроид...............
§ 4.6. Жадный алгоритм..................
§ 4.7. Изоморфизмы матроидов..............
§ 4.8. Пространство циклов бинарного матроида ....
§ 4.9. Пространство циклов и пространство разрезов графа...........
§ 4.10. Монотонные полумодулярные функции.
Индуцированный матроид.............
§4.11. Трансверсальные матроиды ............
§ 4.12. Дизъюнктное объединение и сумма матроидов .
Глава 5. Планарность........................129
§5.1. Укладки графов, планарные графы.........129
§ 5.2. Формула Эйлера для плоских графов........132
§ 5.3. Критерий планарности графа ............135
§ 5.4. Двойственные графы.................152
Глава 6. Раскраски.........................160
§6.1. Хроматические числа.................160
§ 6.2. Хроматические многочлены.............167
§ 6.3. Коэффициенты хроматических многочленов .... 175
Глава 7. Введение в алгоритмы..................182
§7.1. Алгоритмы и их сложность.............183
§ 7.2. Запись алгоритмов..................186
§ 7.3. Корневые и бинарные деревья............189
§ 7.4. Сортировка массивов.................193
Глава 8. Поиск в графе.......................200
§ 8.1. Поиск в глубину ...................200
§ 8.2. Алгоритм отыскания блоков и точек
сочленения.......................205
§ 8.3. Алгоритм отыскания компонент сильной
связности в орграфе .................211
§ 8.4. Поиск в ширину....................218
§ 8.5. Алгоритм отыскания эйлеровой цепи в эйлеровом
графе..........................223
Глава 9. Задача о минимальном остове..............226
Глава 10. Пути в сетях.......................236
§ 10.1. Постановка задачи..................236
§ 10.2. Общий случай. Алгоритм Форда-Бе л л мана .... 237
§ 10.3. Случай неотрицательных весов. Алгоритм
Дейкстры .......................242
§ 10.4. Случай бесконтурной сети..............247
§ 10.5. Задача о максимальном пути и сетевые графики . 252
§ 10.6. Задача о maxmin-пути................259
§ 10.7. Задача о кратчайших путях между всеми парами
вершин.........................263
Глава 11. Задача о максимальном потоке.............267
§ 11.1. Основные понятия и результаты...........267
§ 11.2. Алгоритм Форда-Фалкерсона............275
Глава 12. Паросочетания в двудольных графах..........285
§ 12.1. Основные понятия ..................285
§ 12.2. Задача о наибольшем паросочетании. Алгоритм
Хопкрофта-Карпа...................287
§ 12.3. Задача о полном паросочетании. Алгоритм
Куна..........................306
§ 12.4. Задача о назначениях. Венгерский алгоритм .... 313
§ 12.5. Вершинные покрытия и паросочетания.......323
Глава 13. Задача коммивояжера ..................327
§ 13.1. Основные понятия ..................327
§ 13.2. Алгоритм отыскания гамильтоновых циклов .... 329
§ 13.3. Алгоритмы решения задачи коммивояжера
с гарантированной оценкой точности........331
§ 13.4. Решение задачи коммивояжера методом ветвей
и границ........................341
Литература.............................351
Предметный указатель.......................355

Created using FlowPaper Flipbook Maker ↗