Математика : Графы.

Определение графа

Иногда в задачах даже не указывается такого понятия, а алгоритмы работают именно с ними. Это просто, но в школе не дается.

Задача о кратчайших путях

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

Поиск на графе и его обход

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

Нахождение на графе минимального гамильтонова контура. Метод ветвей и границ

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

Нахождение на графе минимального остовного дерева

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

Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа

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

Топологическая сортировка

Приводит представление орграфов в ЭВМ к виду, при котором все ребра направлены в одну сторону.

Архив статей.

[in English] Графы, их представления в программах и алгоритмы на графах. C++

Очень хорошая статья про графы, их реализации и различные алгоритмы на графах. Есть достаточно много интересных методов, дается их оценка. Исходники на Си++.

Вверх по странице, к оглавлению и навигации