Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 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 оценок |
Формат: | Книга |
Уже скачали: | 12751 раз |
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
Название: Маленькая Diana. Спецвыпуск Вязаные топыИздательство: Эдипресс-КонлигаГод издания: 2013Номер: 8Количество страниц: 30ISBN: 8-771-815-543-006 Язык: РусскийФормат: jpgРазмер: 27 MbЖурнал по в . . .
Название: Виртуальный мир. Книжная серия в 7 томахАвтор: Уильям Гибсон, Брюс Стерлинг, Аллен Стил, Майкл Суэнвик Год издания: 1997Издательство: АСТ, Terra FantasticaСтраниц: 30 . . .
Название: Загадки природы и человека. Внеклассная работа по биологииАвтор: Т. Н. Бондаренкова, И. В. ТкаченкоГод издания: 2008Издательство: Академия Развития, ВКТISBN: 978-5-7 . . .
В Москву возвращается беглый олигарх, экс-министр, успешный финансист Валерий Французов. Узнав об этом, свободный журналист, известный блогер Андрей Липский (свои статьи он подписывал псевдонимом Спа . . .
алентин Фалин с 1950 года находился на ответственной работе в МИД СССР, в семидесятых годах занимал пост Посла СССР в Бонне, в восьмидесятых - политический обозреватель газеты `Известия` и рук . . .
Этот роман является последним из трех самостоятельных произведений о сыщике по прозвищу Виртуоз («Виртуоз», «Дорога на голгофу»). Череда загадочных смертей и взрывы в офисах крупных фирм сплетены в т . . .
Название: Внутрифирменные стандарты аудита. Учебное пособиеАвтор: Э. А. Сиротенко Год издания: 2005Издательство: КноРусISBN: 5-85971-525-0Страниц: 224Формат: P . . .
Название: Невеста ДемонаАвтор: Светлана Жданова Год издания: 2011Издательство: СамиздатСтраниц: 390Формат: RTF, FB2Размер: 6,8 Мб (+3%)Я никогда не думала, что н . . .
Название: Наука побеждать в инвестициях, менеджменте и маркетинге Автор: Александр Шнейдер, Яков Кацман, Гиви Топчишвили Издательство: АСТ ISBN: ISBN 5-17-015166-7 Год издания: 2003 Страниц: 129 Язы . . .
Название: Черный PR. Защита и нападение в бизнесе и не только Автор: Антон Вуйма Издательство: БХВ-Петербург ISBN: 5-94157-771-0 Год издания: 2005 Страниц: 224 Язык: Русский Формат: pdf Качество: ср . . .
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.