Графы. Поиск маршрутов

Путь: Математика » Графы и маршруты

Графы. Поиск маршрутов


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

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

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


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

На правах рекламы

Экономьте время, быстрый поиск - автопродажа online в АvtoМagazine.ua
Посмотрите ПИФы и доходность управления активами.
Рекомендуем подъемники для различных работ
перевод и оформление документов для: иммиграции, ПМЖ, Грин Кард, Green Card
Разработка, Warcraft все для создания сайта.