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

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

Copyright 2000-2002 © Ilia Kantor, при поддержке проекта MANUAL.RU