Алгоритмы оптимизации на графах (учебное пособие)

Ростов-на-Дону: ФГОУ ВПО «Южный федеральный университет», 2008. – 87 с.В учебном пособии излагаются различные алгоритмы на графах. В первой части описаны методы систематического обхода вершин и ребер графа, такие как поиск в ширину и глубину, алгоритмы нахождения некоторых подграфов графа и орграфа. Во второй части пособия рассмотрены оптимизационные алгоритмы построения остова графа минимальной стоимости, нахождения кратчайших путей в графе, построения максимального потока и максимального паросочетания, построения максимального взвешенного независимого множества вершин. Все алгоритмы записаны в виде «псевдокода», снабжены комментариями и проиллюстрированы примерами.
Пособие разработано на основе курсов лекций («Алгоритмы оптимизации на графах», «Алгоритмы, построение и анализ»), читаемых автором в ЮФУ и ДГТУ.Содержание:
Основные определения. Возможные представления графов в ЭВМ.
Поиск в графе.
Поиск в ширину.
Поиск в глубину.
Алгоритмы нахождения некоторых подграфов графа и орграфа.
Компоненты связности графа.
Точки раздела, мосты, блоки.
Сильно связные компоненты орграфа.
Цикломатическое число графа. Фундаментальные циклы и разрезы графа.
Алгоритмы построения остова графа минимальной стоимости.
Алгоритм Краскала.
Алгоритм Прима.
Кратчайшие пути в графе.
Случай неотрицательных весов. Алгоритм Дейкстры.
Общий случай. Алгоритм Форда-Беллмана.
Алгоритм Форда-Фалкерсона построения максимального потока
Алгоритм построения максимального паросочетания и задача о назначении.
Задача о максимальном независимом множестве вершин и древовидный поиск.