:: алгоритмы и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::
Путь: Математика » Графы и маршруты
  Графы. Поиск маршрутов

Задача о кратчайших путях
Рассмотрены различные варианты задачи нахождения кратчайших путей, в том числе - различных условиях на данные.

Поиск на графе и его обход
Стандартные алгоритмы обхода/поиска вширь и вглубь Пример использования.

Нахождение на графе минимального остовного дерева
Остовное дерево связного графа - наименьший связный подграф без циклов, содержащий все вершины данного (лишние ребра убираются) Находим дерево с наименьшей суммой стоимостей ребер.

Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа
Связная компонента - часть графа, в которую можно добраться из некой точки, проходя по ребрам в любую сторону.

Нахождение максимального пропускного потока
Ребрам двунаправленного графа приписаны пропускные способности Потоком называется совокупность путей из 'истока' к 'стоку', где каждому пути приписана величина - сколько груза перемещается (при этом суммарное кол-во груза не должно превышать пропускной способности ребра).

Алгоритмы нахождения максимального потока
Сборник различных алгоритмов решения этой задачи, собранный Александром Труфановым..

Информацию о решении интересных задач можно также найти в разделе Олимпиадные задачи: задачи на графах.

  Дополнительные материалы:

Graphs: Weiss, Chapter 9 z i p
Очень хорошая статья про графы, их реализации и различные алгоритмы на графах. Есть достаточно много интересных методов, дается их оценка. Исходники на Си++.
На правах рекламы