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

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

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