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