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

Asanov__Diskretnaya_matematika

Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 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

загрузка...
Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: