Бесплатная библиотека - 1 338 003 изданий в библиотеке

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

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

Похожие Книги

Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!

  • Книга Условный переход

    Условный переход

    Название: Условный переходАвтор: Максим ДегтяревИздательство: АСТГод издания: 2004Страниц: 408Язык: РусскийФормат: rtfРазмер: 5.92 МбОписание:Детективу Федру Ильинскому, работающему в фаонском Отделе . . .

  • Книга Алексей Махров, Борис Орлов. Вставай, Россия! Десант из будущего (аудиокнига)

    Алексей Махров, Борис Орлов. Вставай, Россия! Десант из будущего (аудиокнига)

    Название: Вставай, Россия! Десант из будущегоАвтор: Алексей Махров, Борис Орлов, Сергей ПлетневИздательство: Аудиокнига своими рукамиГод выпуска: 2010Жанр: фантастика, альтернативная историяАудио ко . . .

  • Книга Антология. Вампиры: Опасные связи

    Антология. Вампиры: Опасные связи

    Новая антология серии "Лучшее" продолжает развивать неувядающую вампирскую тему. На этот раз вашему вниманию предлагаются тридцать пять историй о вампирах, принадлежащих как классикам жанра - Энн Райс . . .

  • Книга Макс Фрай. Сказки старого Вильнюса

    Макс Фрай. Сказки старого Вильнюса

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

  • Книга Право на смерть. Ярче тысячи солнц

    Право на смерть. Ярче тысячи солнц

    Если ты провалился в "перпендикулярный" мир, где Россия стерта с лица земли, а русских лишили даже права на жизнь; если на себе испытал звериную хватку всемирной Британской империи, куда более кроваво . . .

  • Книга Анатолий Радов - Изгой. Тропа Других

    Анатолий Радов - Изгой. Тропа Других

    Вновь судьба ведёт Анта-Изгоя по непроторенному пути. За спиной осталась и Зыбь с демонами, а впереди земли существ, которых даже твари Тьмы называют - Другие. Кто они? Как встретят пришлого? Нет отв . . .

  • Книга Симона Вилар. Ведьма в Царьграде

    Симона Вилар. Ведьма в Царьграде

    Отправляясь в далекий Царьград, княгиня Ольга берет с собой ведьму Малфриду. Ольга лелеет надежду сосватать за своего сына Святослава византийскую царевну. И без совета колдуньи, ее ворожбы кн . . .

  • Книга Реконструктор

    Реконструктор

    Волею случая он попал в этот чуждый мир. Мир, так похожий на родную планета начала 20-ого века и одновременно совершенно другой. Сможет ли простой реконструктор с Земли изменить течение его истории? С . . .

  • Книга Лайон Спрэг де Камп - Стена змей (аудиокнига)

    Лайон Спрэг де Камп - Стена змей (аудиокнига)

    Жил был на свете один психолог, и вывел он однажды занимательную формулу, которая позволила ему переноситься в иные миры. Только вот эти миры были совсем иными. Это были вселенные, созданные писате . . .

  • Книга Оракул Вселенной

    Оракул Вселенной

    Из далеких глубин космоса пришло древнее пророчество - явится однажды тот, которому предстоит стать Алзором, Оракулом Вселенной, тот, кому удастся провести горстку избранных по лезвию меча и острию иг . . .

Вы не зарегистрированы!

Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.

Войти Регистрация

Отзывы читателей

Ой!

К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.