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

Название: Дискретная математика: графы, матроиды, алгоритмы. 2001.

Автор: Асанов М.О.,  Баранский В.А., Расин В.В.

Изложен  ряд  основных  разделов  теории  графов  и  матроидов.  Рассмотрены
алгоритмы  дискретной  оптимизации  на  сетях  и  графах,  наиболее  часто
используемых программистами.  
Для  студентов  и  аспирантов,  специализирующихся  в  области  компьютерных
наук.

Основой для данного учебного пособия послужили лекции, которые читались авторами для студентов математико-механического факультета Уральского государственного университета им. А. М. Горького, обучающихся по специальностям «Математика, прикладная математика», «Математика, компьютерные науки» и «Компьютерная безопасность».
В книге излагается ряд разделов теории графов и приводятся алгоритмы дискретной оптимизации на графах и сетях. Материал, посвященный теории графов, содержит достаточно обширное введение в теорию матроидов. Матроиды, в частности, составляют теоретическую основу для изучения и анализа алгоритмов, использующих «жадную» стратегию. Понимание же природы и областей применимости жадных алгоритмов безусловно необходимо каждому специалисту по компьютерной математике и ее приложениям.

Содержание
Предисловие
1. Основные понятия теории графов
Основные определения
Маршруты, связность, циклы и разрезы
Ориентированные графы
Матрицы, ассоциированные с графом
2. Деревья
Леса, деревья, остовы
Блоки и точки сочленения
Число остовов в связном обыкновенном графе
3. Обходы графов
Эйлеровы графы
Гамильтоновы графы
4. Матроиды
Полумодулярные решетки, условие Жордана--Дедекинда
Конечномерные геометрические решетки и матроиды
Основные понятия теории матроидов
Различные аксиоматизации матроидов
Двойственный матроид
Жадный алгоритм
Изоморфизмы матроидов
Пространство циклов бинарного матроида
Пространство циклов и пространство разрезов графа
Монотонные полумодулярные функции. Индуцированный матроид
Трансверсальные матроиды
Дизъюнктное объединение и сумма матроидов
5. Планарность
Укладки графов, планарные графы
Формула Эйлера для плоских графов
Критерий планарности графа
Двойственные графы
6. Раскраски
Хроматические числа
Хроматические многочлены
Коэффициенты хроматических многочленов
7. Введение в алгоритмы
Алгоритмы и их сложность
Запись алгоритмов
Корневые и бинарные деревья
Сортировка массивов
8. Поиск в графе
Поиск в глубину
Алгоритм отыскания блоков и точек сочленения
Алгоритм отыскания компонент сильной связности в орграфе
Поиск в ширину
Алгоритм отыскания эйлеровой цепи в эйлеровом графе
9. Задача о минимальном остове
10. Пути в сетях
Постановка задачи
Общий случай. Алгоритм Форда-Беллмана
Cлучай неотрицательных весов. Алгоритм Дейкcтры
Случай бесконтурной сети
Задача о максимальном пути и сетевые графики
Задача о maxmin-пути
Задача о кратчайших путях между всеми парами вершин
11. Задача о максимальном потоке
Основные понятия и результаты
Алгоритм Форда-Фалкерсона
12. Паросочетания в двудольных графах
Основные понятия
Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа
Задача о полном паросочетании. Алгоритм Куна
Задача о назначениях. Венгерский алгоритм
13. Задача коммивояжера
Основные понятия
Алгоритм отыскания гамильтоновых циклов
Алгоритмы решения задачи коммивояжера с гарантированной оценкой
точности 
Решение задачи коммивояжера методом ветвей и границ
Литература
Предметный указатель

Купить - Книгу - Дискретная математика: графы, матроиды, алгоритмы - Асанов М.О.,  Баранский В.А., Расин В.В. .com


Купить - Книгу - Дискретная математика: графы, матроиды, алгоритмы - Асанов М.О.,  Баранский В.А., Расин В.В. .net





Теги: книга по математике :: дискретная математика :: графа :: матроид :: алгоритм :: Асанов :: Баранский :: Расин