Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 19. Потоки в сетях. Алгоритм Форда-Фалкерсона.

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

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

Дадим несколько формальных определений.

Назовем сетью ориентированный граф G = (V,E), каждому ребру (u,v) которого поставлено в соответствие число c(u,v)>=0, называемое пропускной способностью ребра. В случае отсутствия ребра (u,v) в графе мы полагаем c(u,v)=0. В графе выделены две вершины: исток s и сток t.

Потоком в сети G назовем функцию f: VxV->R, обладающую следующими свойствами:

• f(u,v)<=c(u,v)
• f(u,v)=-f(v,u)
• сумма по всем v из V f(u,v) равна 0 (для всех u из V\{s,t})

Величина потока определяется как сумма значений f(s,v) по всем v из V.
Задача о максимальном потоке состоит в следующем: для данной сети G с истоком s и стоком t найти поток максимальной величины.

Остаточной пропускной способностью из u в v называется величина
c_f(u,v) = c(u,v) - f(u,v)
Она определяет,сколько еще вещества может пропустить ребро из u в v.
Сеть, составленную из ребер с пропускной способностью, равной остаточной пропускной способности c_f(u,v), назовем остаточной сетью сети G, порожденной потоком f. Ее ребра называются остаточными ребрами.

Дополняющем путем назовем простой путь (т.е. путь проходящий по каждой вершине не более одного раза) из истока s в сток t в остаточной сети G_f.
Остаточной пропускной способностью дополняющего пути p назовем величину
c_f = min {c_f(u,v): (u,v) принадлежит p}.

Рассмотрим теперь один из алгоритмов построения максимального потока.

Алгоритм Форда-Фалкерсона:

• Положить начальный поток равным 0.
• Пока существует путь p в остаточной сети G_f, пустить по нему поток велиины c_f(p).

Времы работы данного алгоритма зависит от того, как ищется путь p. В принципе, алгоритм может вообще не остановиться, если величина потока будет расти все более и более мелкими шагами, так и не достигнув максимума. Однако, если выбирать дополняющий путь поиском в ширину, времы работы алгоритма будет O(VE²) (V - количество вершин в сети, а E - количество ребер).