Ответы: Теормин (перечисление без определений)

Файл скачан с сайта StudIzba.com

При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник

9 алгоритмов:

Поиск в глубину / ширину - обход графа

Алгоритм Краскала / Прима - минимальное, оставное дерево

Алгоритм Флёри - построениец цикла Эйлера

Алгоритм Дейкстры (можно ориентированный граф, вес > 0) - кратчайший путь от вершины до остальных

Алгоритм Флойда-Уоршелла (можно ориентированный граф, вес > 0) - кратчайший путь от всех вершин до всех вершин

Алгоритм Белмана-Форда (можно ориентированный граф, вес > 0 или < 0) - кратчайший путь от вершины до остальных

Алгоритм Форда-Фалкерсона - максимаьный поток в сети от одной вершины к другой (есть модификация - Карпа)

Задача целочисленного программирования

Задача Кратчайшего пути

Задача Комивояжёра

Задача о максимальном потоке в сети

Теория графов (1 курс, Дискретная математика)

Алгоритм поиска в глубину

Алгоритм поиска в ширину

Теорема о числе различных каркасов (деревьев) для графа (<= n^(n-2))

Разрез графа

Безопасные рёбра

Метод Краскапа для построения минимального каркаса

Алгоритм Прима (построение минимального каркаса)

Эйлеров цикл, Эйлеров граф

Теорема, что граф - эйлеров <=> связен и каждая вершина имеет чётную степень

Алгоритм Флёри построения эйлерова цикла

Гамильтонов цикл, гамильтонов граф

Достаточный критерий Гамильтоновости графа

Теоремы Дираха и Поша

Алгоритм Дейкстры (поиск пути в графе)

Алгоритм Флойда-Уоршелла (поиск кратчайшего пути между всеми упорядоченными вершинами)

Алгоритм Белмана-Форда (поиск кратчайшего пути из одной вешины во все остальные)

Потоковая сеть, условие неразрывности потока, разрез множества, пропускная способность разреза, увеличивающий путь

Поиск максимлаьной пропускной способности от одной вершины в другую:

Алгоритм Пометок Форда-Фалкерсона

Алгоритм поиска максимлаьной пропускной способности в графе - алгоритм Карпа (это за пределами лекций)