Алгоритмические задачи на графах, Дехтярь М.И., 2012

Алгоритмические задачи на графах, Дехтярь М.И., 2012.

   Настоящее пособие написано по материалам курсов “Проектирование эффективных алгоритмов" и “Алгоритмы па графах”, которые автор неоднократно в 1990-2012гг. читал в Тверском государственном университете. Основное внимание уделено рассмотрению широко используемых в различных приложениях типовых алгоритмических задач, таких, как представления графов, отношение достижимости и транзитивное замыкание графа, компоненты сильной связности ориентированного графа и его базы, деревья и их обходы, минимальные остовные деревья, поиск в глубину, поиск кратчайших путей и потоки в транспортных сетях. Рассмотрены также многие сложные (NP-полные) задачи на графах и возможные подходы к их решению. В последней главе продемонстрировано применение теории графов к анализу социальных сетей. Каждая глава завершается разделом с задачами, которые могут служить материалом для проведения практических занятий и домашних заданий. Ряд задач содержат дополнительный материал, по тем или иным причинам нс вошедший в основной текст. Список литературы заведомо неполон, он включает лишь учебники, монографии и статьи, непосредственно использованные при написании этого пособия. В них можно найти дальнейшие ссылки на многочисленные источники, посвященные алгоритмам на графах.




Представления графов.
Из определения графа следует, что каждый граф G = (V, Е) можно задать, непосредственно перечислив его множество вершин V и множество ребер Е. Однако такое представление неудобно для решения многих задач о графах. Например, чтобы проверить наличие ребра между двумя вершинами, придется, вообще говоря, просмотреть все множество Е. Хорошее представление, по крайней мере, должно позволить легко переходить от вершины к ее соседу и перечислять всех ее соседей.

В этом параграфе мы рассмотрим три разных способа представления графов, которые более эффективны при решении типичных для теории графов задач.

ОГЛАВЛЕНИЕ.
1. Основные понятия.
2. Представления графов.
2.1. Матрица (таблица) смежности.
2.2. Матрица (таблица) инцидентности.
2.3. Списки смежности.
2.3.1. Графы с ограниченной полустепенью исхода.
2.3.2. Произвольные графы.
2.4. Задачи.
3. Неориентированные и ориентированные деревья.
3.1. Основные определения.
3.2. Представления деревьев.
3.2.1. Сылка на вершину-отца.
3.2.2. Скобочное представление.
3.2.3. Представление множеством путей.
3.2.4. Стандартное представление бинарного дерева.
3.2.5. Представление бинарного дерева с помощью массива.
3.2.6. Представление произвольного дерева с помощью бинарного.
3.3. Деревья и формулы (выражения).
3.4. Обходы деревьев.
3.5. Задачи.
4. Минимальное остовное дерево.
4.1. Алгоритм Крускала.
4.2. Задачи.
5. Алгоритмы обхода графов.
5.1. Поиск в глубину на неориентированном графе и задача о лабиринте.
5.2. Поиск в ширину на неориентированном графе.
5.3. Двусвязные компоненты неориентированных графов.
5.4. Компоненты сильной связности и базы ориентированного графа.
5.5. Задачи.
6. Задачи о путях на графе.
6.1. Достижимость и транзитивное замыкание графа.
6.1.1. Кратчайшие пути между всеми парами вершин.
6.2. Задача о кратчайших путях из одного источника.
6.2.1. Алгоритм Дейкстры.
6.2.2. О реализации алгоритма Дейкстры.
6.2.3. Алгоритм Беллмана-Форда.
6.2.4. Кратчайшие пути в ациклических графах.
6.3. Задачи.
7. Потоки в сетях.
7.1. Потоки и разрезы. Алгоритм Форда-Фалкерсона.
7.2. Алгоритм построения максимального потока за кубическое время.
7.3. Сети с единичными пропускными способностями.
7.4. Максимальные паросочетания в двудольных графах.
7.4.1. Паросочетания в общих графах.
7.5. Задачи.
8. NP-полные задачи для графов.
8.1. Полиномиальная сводимость и NP-полные задачи.
8.2. Полиномиальная разрешимость выполнимости 2-КПФ.
8.3. Клика, независимое множество, вершинное покрытие.
8.4. Гамильтонов цикл.
8.5. Задача коммивояжера.
8.6. Раскраска вершин графа.
8.7. Задачи.
9. Что делать с NP-полными проблемами?.
9.1. Аппроксимация для задачи ВЕРШИННОЕ ПОКРЫТИЕ.
9.2. Аппроксимации для задачи коммивояжера.
9.3. Метод “ветвей и границ” для задачи коммивояжера.
9.4. Задачи.
10. Применение графов в анализе социальных сети.
10.1. Социальные сети.
10.2. Параметры центральности акторов.
10.2.1. Близкая центральность (closeness centrality (Sabidussi, 1966)).
10.2.2. Срединная центральность (Betweenness Centrality).
10.2.3. Алгоритмы вычисления центральности.
10.3. Престижность.
10.3.1. Средняя престижность (Proximity Prestige).
10.3.2. Ранжированный престиж (Rank Prestige).
10.4. Ранжирование интернет-страниц. Алгоритм PageRank.
10.5. Обнаружение сообществ (Community Discovery).
10.6. Двудольное ядро сообществ.
10.6.1. Выявление двудольных ядер.
10.6.2. Сообщества максимального потока.
10.7. Задачи.
Список литературы.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмические задачи на графах, Дехтярь М.И., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Дехтярь