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

Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск:, 2001, 288 стр.
Изложен ряд основных разделов теории грифон и матроидов. Рассмотрены алгоритмы дискретной оптимизации на сетях и графах, наиболее часто используемые программистами. Для студентов и аспирантов, специализирующихся в области компьютерных наук, для практикующих программистов, для всех желающих изучить основы современной дискретной компьютерной математики.
Оглавление
Предисловие 3
1. Основные понятия теории графов 5
1.1. Основные определения..........................................5
1.2. Маршруты, связность, циклы и разрезы......................9
1.3. Ориентированные графы........................................14
1.4. Матрицы, ассоциированные с графом ........................16
2. Деревья 22
2.1. Леса, деревья, остовы ..................... 22
2.2. Блоки и точки сочленения................... 25
2.3. Число остовов в связном обыкновенном графе.......30
3. Обходы графов 34
3.1. Эйлеровы графы ........................ 34
3.2. Гамильтоновы графы...................... 38
4. Матроиды 44
4.1. Полумодулярные решетки, условие Жордана-Дедекинда . 44
4.2. Конечномерные геометрические решетки и матроиды ... 47
4.3. Основные понятия теории матроидов ............56
4.4. Различные аксиоматизации матроидов............59
4.5. Двойственный матроид ........................................67
4.6. Жадный алгоритм ..............................................70
4.7. Изоморфизмы матроидов ......................................72
4.8. Пространство циклов бинарного матроида..........76
4.9. Пространство циклов и пространство разрезов графа ... 79
4.10. Монотонные полумодулярные функции. Индуцированный матроид..........................................................83
4.11. Трансверсальные матроиды....................................86
4.12. Дизъюнктное объединение и сумма матроидов.......93
5. Планарность 102
5.1. Укладки графов, планарные графы..............102
5.2. Формула Эйлера для плоских графов.............104
5.3. Критерий планарности графа.................107
5.4. Двойственные графы......................120
6. Раскраски 126
6.1. Хроматические числа .....................126
6.2. Хроматические многочлены..................131
6.3. Коэффициенты хроматических многочленов ........138
7. Введение в алгоритмы 144
7.1. Алгоритмы и их сложность..................145
7.2. Запись алгоритмов.......................147
7.3. Корневые и бинарные деревья.................149
7.4. Сортировка массивов......................152
8. Поиск в графе 159
8.1. Поиск в глубину ........................159
8.2. Алгоритм отыскания блоков и точек сочленения......163
8.3. Алгоритм отыскания компонент сильной связности в орграфе ...............................168
8.4. Поиск в ширину.........................173
8.5. Алгоритм отыскания эйлеровой цепи в эйлеровом графе . 177
9. Задача о минимальном остове 180
10. Пути в сетях 188
10.1. Постановка задачи.......................188
10.2. Общий случай. Алгоритм Форда-Беллмана.........188
10.3. Случай неотрицательных весов. Алгоритм Дейкстры . . . 193
10.4. Случай бесконтурной сети...................196
10.5. Задача о максимальном пути и сетевые графики......201
10.6. Задача о maxmin-пути.....................207
10.7. Задача о кратчайших путях между всеми парами вершин 210
11. Задача о максимальном потоке 213
11.1. Основные понятия и результаты...............213
11.2. Алгоритм Форда-Фалкерсона ................219
12. Паросочетания в двудольных графах 227
12.1. Основные понятия .......................227
12.2. Задача о наибольшем паросочетании. Алгоритм Хопкроф-
та-Карпа ............................228
12.3. Задача о полном паросочетании. Алгоритм Куна......244
12.4. Задача о назначениях. Венгерский алгоритм........249
13. Задача коммивояжера 259
13.1. Основные понятия .......................259
13.2. Алгоритм отыскания гамильтоновых циклов........260
13.3. Алгоритмы решения задачи коммивояжера с гарантированной оценкой точности ...................262
13.4. Решение задачи коммивояжера методом ветвей и границ . 270
Литература 278
Предметный указатель 282

Convert your PDF to digital flipbook ↗