x-uni.com
регистрация / вход
сейчас на линии 37 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 37 чел.
Дискретная математика, Графы, Матроиды, Алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 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. Решение задачи коммивояжера методом ветвей и границ
Литература
Предметный указатель.

Скачать бесплатно на сайте fileskachat.com

Предложения интернет-магазинов

Математика. Теория вероятностей и дискретная математика: Элементы теории, решение задач

Автор(ы): Баюк Олег Александрович, Маркарян Елена Георгиевна   Издательство: Просвещение, 2013 г.  Серия: Сложные темы ЕГЭ

Цена: 333 руб.   Купить

Пособие предназначено учащимся общеобразовательных учреждений (школ, гимназий, колледжей) для углублённого изучения теории вероятностей и связанных с ней разделов дискретной математики (теории множеств, математической логики, комбинаторики, теории графов и математической статистики) в целях успешной сдачи ЕГЭ по математике. В пособии изложены основные теоретические сведения, необходимые для решения задач, приводятся решения типичных заданий ЕГЭ, а также содержатся задания для самостоятельной работы (с ответами, указаниями к решению или решениями). Книга может быть использована в качестве сборника задач на подготовительных курсах, факультативных занятиях, при самостоятельной подготовке к поступлению в вуз и при последующем обучении в вузе.


Алгоритмы - ключ к решению задач. Математика. 5-6 классы

Автор(ы): Михайлова Жанна Николаевна   Издательство: Литера, 2014 г.  Серия: Средняя школа

Цена: 541 руб.   Купить

Книга адресована учащимся 5-6 классов, в том числе детям, обучающимся на дому. Книга содержит основные определения и формулы, алгоритмы решения задач и упражнений по курсу математики 5-6 классов, а также примеры решения заданий с помощью предложенных алгоритмов. К заданиям для самостоятельной работы даны ответы.


Алгоритмы - ключ к решению задач. Алгебра. 7-9 классы

Автор(ы): Михайлова Жанна Николаевна   Издательство: Литера, 2014 г.  Серия: Средняя школа

Цена: 688 руб.   Купить

Книга содержит справочные материалы: определения, формулы, алгоритмы решения типовых уравнений, неравенств и их систем и т. д. по всем разделам школьного курса алгебры, а также образцы решений заданий БГЭ. В пособии предложена методика работы с формулами, способствующая их лучшему применению и запоминанию.


Алгоритмы - ключ к решению задач. Алгебра и элементарные функции. 10-11 классы

Автор(ы): Михайлова Жанна Николаевна   Издательство: Литера, 2014 г.  Серия: Средняя школа

Цена: 656 руб.   Купить

Книга содержит справочные материалы: определения, формулы, алгоритмы решения типовых уравнений, неравенств и их систем и т. д. по всем разделам школьного курса алгебры и начала анализа, а также образцы решений заданий ЕГЭ. В пособии предложена методика работы с формулами, способствующая их лучшему применению и запоминанию.

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!