Задачи нахождения путей в графах
Задачи нахождения путей в графах
Пусть G = (V, E) – ориентированный граф.
Рефлексивным и транзитивным замыканием графа G называется граф G*, который содержит то же множество узлов, что и G, но в котором из v в w идет ребро тогда и только тогда, когда в G существует путь (длины 0 или больше) из v в w.
С задачей нахождения транзитивного замыкания тесно связана задача о кратчайшем пути.
Если Вам понравилась эта лекция, то понравится и эта - 4. Способы подготовки шахтных полей.
Поставим в соответствие каждому ребру e графа G = (V, E) неотрицательную стоимость c(e). Стоимость пути определяется как сумма стоимостей ребер, образующих этот путь. Задача о кратчайшем пути состоит в нахождении для каждой пары узлов (v, w) пути наименьшей стоимости среди всех путей из v в w.
Наряду с понятием стоимости пути применяется понятие метки пути. Определим метку пути как произведение меток ребер, составляющих этот путь. Причем метки берутся в порядке прохождения ребер. В частности, метка пути нулевой длины равна 1. Для каждой пары узлов (v, w) определим c(v, w) как сумму меток всех путей между v и w. Назовем c(v, w) стоимостью прохождения из v в w.
Например, рассмотрим ориентированный граф, в котором каждое ребро помечено элементом полукольца S1 = ({0, 1}, +, ·, 0, 1) (рис. 14).
Метка пути v1, v2, v3, равна 1. Простой цикл из v2 в v2 имеет метку 1 · 0 = 0. Вообще, каждый путь положительной длины имеет метку 0. Но стоимость пути нулевой длины из v2 в v2 равна 1. Следовательно, c(v2, v2)= 1.
Рис. 14. Метка пути и стоимость пути