Определение максимальной пропускной способности сети

∙ 1 источник, 1 сток. Каждой дуге приписана пропускная способность. d_ij – пропускная способность дуги ij. x_ij – количество вещества, пропускаемого по дуге ij в единицу времени

0≤ x_ij ≤ d_ij

∙ Для любой вершины, кроме истока I и стока S, количество поступающего вещества в эту вершину, равно количеству вещества, вытекающего из нее. В промежуточных вершинах потоки не создаются и не исчезают.

∙ Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S

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

∙ Каждое неориентированное ребро (u, v) заменяем на пару ориентированных рёбер (u, v) и (v, u).

∙ Для произвольной сети максимальная величина потока из v_s в v_t равняется минимальной пропускной способности разреза, который отделяет v_s от v_t

∙ Алгоритм Форда — Фалкерсона

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .
2. Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему — уменьшаем на .
3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4. Возвращаемся на шаг 2.

 

Алгоритм поиска кратчайшего пути при наличии дуг с отрицательной стоимостью – я у него спросила про этот пункт, он сказал, что, наверняка, уберет его)

G {E,V}, d_ij стоимость перехода из I в j

Найти путь из начальной вершины в конечную с минимальной суммарной стоимостью

N – множество непомеченных вершин

П – множество помеченных вершин

Шаг 0. ε₀ т.к. мы находимся в этой точке, то переход в нее =0

П=v₀

N={v₁:v_n}

Шаг 1.

Находим начальные дуги (I,j), такие что

V_i ∊ П, v_j ∊ N для каждой такой дуги определенное число N_ij = ε_i + d_ij

Шаг 2.

έ=min{h_ij}

Выделяем дуги, на которых этот минимум достигается. Конечную вершину помечаем ε_i =έ

Шаг 3.

Поверяем выполнение условия ε_i + d_ij≥ ε_d для всех дуг, вершины которого ∊П (V_i ∊ П, v_j ∊ П) - проверка на то, не существует ли более короткого пути, чем найденный

∙ если неравенство выполняется, то – Шаг 5

∙ если неравенство не выполняется, то – Шаг 4

Шаг 4.

ε_j* = ε_i + d_ij*

У дуги, на которой достигалась старая ε пометка отменяется, помечается новая дуга ij

Пусть

То есть появляется более короткий путь. Необходимо отменять пометку в мин (в нач.) и отметить дугу

 

Шаг 5.

Определяем помечена ли последняя вершина V_n ∊ П

Если v_n - конечная вершина помечена, то ответ

Если конечная вершина непомечена, то к Шаг 1

Кратчайший путь ищется из конечной вершины

Определение кратчайшего пути (2 пункта)

Задача о потоке минимальной стоимости

Расписаны в учебнике «Теория игр. Исследование операций» Костевича и Лапко