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

На практике часто возникает проблема определения максимальной проводимости некоторой реальной сети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самый дешёвый поток и т.д. Все эти и многие другие задачи решаются с помощью алгоритмов, которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимально возможную пропускную способность сети, алгоритм минимальной стоимости – самый дешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке.

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

Разрез S отделяет v_s от v_t, если вершины v_s, v_t принадлежат разным сторонам разреза: v_s V_s, v_t V_t, V = V_s V_t. Пропускной способностью с (S) разреза S называется сумма пропускных способностей дуг разреза, которые начинаются в V_s и заканчивается в V_t:

с (S) = .

2.3. Алгоритм размещения пометок для задачи

Дата добавления: 2015-08-09