Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010
Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010.
В учебном пособии изложен ряд основных разделов теории графов и матроидов. Рассмотрены алгоритмы дискретной оптимизации на сетях и графах, наиболее часто используемые программистами.
Пособие предназначено для студентов и аспирантов, специализирующихся в области компьютерных наук и информационной безопасности, для практикующих программистов, для всех желающих изучить основы современной дискретной компьютерной математики.
БЛОКИ И ТОЧКИ СОЧЛЕНЕНИЯ.
Пусть G = (V, Е) — произвольный граф. Вершина v называется точкой сочленения, если граф G — v имеет больше компонент связности, чем граф G.
Связный граф называется неразделимым, если он не содержит точек сочленения.
В связном графе полезно выделить максимальные неразделимые подграфы. Это можно сделать подобно тому, как в произвольном графе были выделены максимальные связные подграфы (компоненты связности).
Блоком графа G называется любой его максимальный неразделимый подграф. На рис. 10,а показаны точки сочленения и, v некоторого связного графа, а на рис. 10,6 приведены его блоки.
Очевидно, любой неразделимый подграф графа содержится в некотором его блоке. Поэтому любое ребро лежит в некотором блоке; то же самое относится и к произвольному циклу. Ясно, что любой блок связного неодноэлементного графа сам неодноэлементен.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию
Предисловие к первому изданию
Глава 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. Планарность
§5.1. Укладки графов, планарные графы
§5.2. Формула Эйлера для плоских графов
§5.3. Критерий планарности графа
§5.4. Двойственные графы
Глава 6. Раскраски
§6.1. Хроматические числа
§6.2. Хроматические многочлены
§6.3. Коэффициенты хроматических многочленов
Глава 7. Введение в алгоритмы
§7.1. Алгоритмы и их сложность
§7.2. Запись алгоритмов
§7.3. Корневые и бинарные деревья
§7.4. Сортировка массивов
Глава 8. Поиск в графе
§8.1. Поиск в глубину
§8.2. Алгоритм отыскания блоков и точек сочленения
§8.3. Алгоритм отыскания компонент сильной связности в орграфе
§8.4. Поиск в ширину
§8.5. Алгоритм отыскания эйлеровой цепи в эйлеровом графе
Глава 9. Задача о минимальном остове
Глава 10. Пути в сетях
§10.1. Постановка задачи
§10.2. Общий случай. Алгоритм Форда-Беллмана
§10.3. Случай неотрицательных весов. Алгоритм Дейкстры
§10.4. Случай бесконтурной сети
§10.5. Задача о максимальном пути и сетевые графики
§10.6. Задача о maxmin-пути
§10.7. Задача о кратчайших путях между всеми парами вершин
Глава 11. Задача о максимальном потоке
§11.1. Основные понятия и результаты
§11.2. Алгоритм Форда-Фалкерсона
Глава 12. Паросочетания в двудольных графах
§12.1. Основные понятия
§12.2. Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа
§12.3. Задача о полном паросочетании. Алгоритм Куна
§12.4. Задача о назначениях. Венгерский алгоритм
§12.5. Вершинные покрытия и паросочетания
Глава 13. Задача коммивояжера
§13.1. Основные понятия
§13.2. Алгоритм отыскания гамильтоновых циклов
§13.3. Алгоритмы решения задачи коммивояжера с гарантированной оценкой точности
§13.4. Решение задачи коммивояжера методом ветвей и границ
Литература
Предметный указатель.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12740 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Венценосцы. Книжная серия в 7 книгах.
Название: Венценосцы. Книжная серия в 7 книгах Автор: Коллектив авторов Серия или выпуск: Венценосцы Издательство: Терра-Книжный клуб Год издания: 2002 - 2011 Страниц: 3000 Язык: Русский Формат: FB2 . . .
-
Крестное знамение.
Название: Крестное знамение Автор: Крис Кузнецки Издательство: АСТ, АСТ Москва ISBN: 978-5-17-049537-5, 978-5-9713-9685-7 Год издания: 2008 Страниц: 448 Язык: Русский Формат: RTF, FB2 Качество: отли . . .
-
Анекдоты с героями мультиков.
Название: Анекдоты с героями мультиков Автор: Под ред. Александра Алира Серия или выпуск: Наши любимые мультфильмы Издательство: Самовар ISBN: 978-5-85066-271-4 Год издания: 2007 Страниц: 95 Язык: Р . . .
-
Перспектива.
Название: Перспектива Автор: Ратничин В.М. Серия или выпуск: - Издательство: Киев: Вища школа ISBN: - Год издания: 1982 Страниц: 228 Язык: Русский Формат: djvu Качество: среднее Размер: 25,2 Мб Опис . . .
-
Юмористические рассказы (аудиокнига).
Название: Юмористические рассказы (аудиокнига) Автор: Ярослав Гашек Издательство: Союз Год издания: 2011 Язык: Русский Формат: MP3 Битрейт аудио: 160 kbps Время звучания: 6:59:29 Читает: А. Клюквин, . . .
-
Морской волк. В 2-х томах.
Название: Морской волк. В 2-х томах Автор: Влад Савин Издательство: Самиздат Год издания: 3011 Страниц: 900 Язык: Русский Формат: RTF, FB2 Качество: отличное Размер: 5,11 Мб Описание: Атомная подлод . . .
-
Историко-бытовой танец.
Название: Историко-бытовой танец Автор: Воронина И.А. Издательство: Искусство Год издания: 1980 Страниц: 128 Язык: Русский Формат: PDF Размер: 69,8 Мб Описание: С иллюстрациями. Предлагаемое учебно- . . .
-
Удивительные животные.
Название: Удивительные животные Автор: Эндрю Клив Серия или выпуск: Мир животных Издательство: Минск. "Белфакс" ISBN: 985-407-013-1 Год издания: 1995 Страниц: 80, с цв. илл. Язык: Русский Формат: dj . . .
-
Экономические и статистические работы (в 2-х томах).
Название: Экономические и статистические работы (в 2-х томах) Автор: В.Петти Издательство: Соцэкгиз, Москва Год издания: 1940 Страниц: 324 Язык: Русский Формат: DjVu Размер: 5,8 Мб Описание: ПЕТТИ, . . .
-
Белорусская история. Научно-популярный очерк.
Название: Белорусская история. Научно-популярный очерк Автор: Чигринов П.Г. Издательство: Минск: Современная школа ISBN: 978-985-513-625-6 Год издания: 2010 Страниц: 928 Язык: Русский Формат: pdf, d . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.