Автор работы: Пользователь скрыл имя, 27 Ноября 2013 в 21:51, реферат
Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием – графы.
Введение . . . . . . . . . . . . . . . . . . . . 3
Алгоритмы на графах . . . . . . . . . . . . . . . . 3
Методы систематического обхода вершин графа . . . . . 4
Алгоритм поиска в глубину
Алгоритм поиска в ширину
Остовное дерево наименьшего веса. Задача Штейнера . . 7
Алгоритм Прима
Алгоритм Краскала
Задача плоской укладки . . . . . . . . . . . . . . 10
Гамма-алгоритм
Задача раскраски графа . . . . . . . . . . . . . . 13
Метод неявного перебора
Приближенный алгоритм
Нахождение кратчайших путей . . . . . . . . . . . . 15
Алгоритм Дейкстры
Алгоритм Флойда
Эйлеровы графы . . . . . . . . . . . . . . . . . 18
Задача о наибольшем потоке . . . . . . . . . . . . 19
Алгоритм Форда-Фалкерсона
Заключение . . . . . . . . . . . . . . . . . . . 20