|  |
| Задача о кратчайших путях
Рассмотрены различные варианты задачи нахождения кратчайших путей, в том числе - различных условиях на данные.
|
| Поиск на графе и его обход
Стандартные алгоритмы обхода/поиска вширь и вглубь Пример использования.
|
| Нахождение на графе минимального остовного дерева
Остовное дерево связного графа - наименьший связный подграф без циклов, содержащий все вершины данного (лишние ребра убираются) Находим дерево с наименьшей суммой стоимостей ребер.
|
| Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа
Связная компонента - часть графа, в которую можно добраться из некой точки, проходя по ребрам в любую сторону.
|
| Нахождение максимального пропускного потока
Ребрам двунаправленного графа приписаны пропускные способности Потоком называется совокупность путей из 'истока' к 'стоку', где каждому пути приписана величина - сколько груза перемещается (при этом суммарное кол-во груза не должно превышать пропускной способности ребра).
|
| Алгоритмы нахождения максимального потока
Сборник различных алгоритмов решения этой задачи, собранный Александром Труфановым..
|
