28. Задача о длиннейшем пути в графе

Требуется найти длиннейший путь во взвешенном ориентированном графе между двумя выделенными вершинами. Задача решается алгоритмом Форда, только с небольшими отличиями.

1). Начальный шаг. Первая вершина получает начальную метку (0; Х; ∞). Все остальные вершины получают временные метки (-∞; Х∞)

2). Общий шаг. Решение с временной меткой; присваивается метка по правилу

l(хj) = max (l(хj), l*(хj)+lij)

Среди всех временных меток выбирается максимальная.

Алгоритм работает до тех пор, пока 2-ая из выделенных вершин не получит окончательной метки.

29. Поток на сети. Задача о максимальном потоке в сети. Алгоритм Форда-Фалкерсона.

Сетью называется связный граф (обычно, не орграф и не мультиграф), в котором заданы “пропускные способности” ребер, т. е. числа q_ij.  Потоком в сети между вершиной t (источником) и s (стоком) называется набор чисел с_ij, (т. е. количество условного “груза”, перевозимого из вершины с номером i в вершину с номером j),удовлетворяющих четырем условиям:

1) числа с_ij   0, причем если с_ij > 0, то с_ji = 0 (нет встречных перевозок);

2) числа c_ij   q_ij (соответствующих пропускных способностей ребер);

3) если вершина с номером i – промежуточная (не совпадает с источником и стоком), то

,

т. е. количество “груза”, вывозимого из вершины i, равно количеству “груза”, ввозимого в эту вершину;

4)  количество “груза”, вывозимого из источника t, должно быть равно количеству груза, ввозимого в сток s:

.

Число А называется величиной данного потока или просто потоком между t и s.

Пусть имеется некоторое сечение между вершинами t и s. Тогда величиной сечения называется сумма пропускных способностей ребер, входящих в это сечение. Сечение называется минимальным (максимальным), если его величина минимальна (максимальна).

Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его ещё можно доставить от истока к стоку при данных пропуск­ных способностях труб.

Теорема Форда – Фалкерсона (1955). Максимальный поток между вершинами t и s равен величине минимального сечения между этими вершинами.

Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур:

1) Процедура помечивания вершин

2) Процедура изменения потока

1) Процедура помечивания вершин.

Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:

- если дуга направлена из i в j и поток по этой дуге (f_ij) меньше пропускной способности дуги (c_ij), то вершине j присваивается метка (i⁺,min(e,c_ij-f_ij))

- если дуга направлена из j в i и поток по этой дуге (f_ji) больше нуля, то вершине j присваивается метка (i^-,min(e,f_ji))

Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д.

Процесс помечивания заканчивается в двух случаях:

1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается.

2) Помечается сток. В этом случае производится изменение потока.