Сеть. Поток в сети. Задача о максимальном потоке в сети. Алгоритм
нахождения максимального потока.
Сетью называется ориентированный граф G=(V,E), каждому ребру (u,v) E которого
поставлено в соответствие число c(u,v) 0, называемое пропускной способностью ребра.
В случае (u,v) E, полагаем c(u,v)=0.
В графе выделены 2 вершины: источник s и сток t. Граф связен, т.е. .
Пусть дана сеть G=(V,E), пропускная способность которой задаѐтся функцией с.
Потоком в сети G назовѐм функцию , обладающую следующими свойствами:
1. Ограничение, связанное с пропускной способностью: для всех u,v
изV;
2. Кососимметричность: для всех u,v из V;
3. Сохранение потока: для всех u из V - {s,t}.
Величина потока определяется как сумма потоков по всем рѐбрам выходящим из истока.
Дан ориентированный граф.
Будем рассматривать его как сеть труб, по которым некоторое вещество движется от
источника к стоку. Веса на рѐбрах - пропускная способность трубы.
Задача о максимальном потоке:
Найти максимально возможную скорость производства (и потребления) вещества, при
которой его ещѐ можно доставить от истока к стоку при данных пропускных способностях
труб. Или - для данной сети G с истоком s и стоком t найти поток максимальной величины.
Вершину сети v , для которой deg-(v)>0 (полустепень исхода) и deg+(v)=0 (полустепень
захода) будем называть источником, а вершину w, для которой deg+(w)>0 и deg–(w)=0 –
стоком.
Поток называется максимальным, если он имеет наибольшую величину (среди всех
потоков через данную сеть).
Назовѐм разрезом сети G=(V, E) разбиение множества V на две части S и T=V \ S, для
которых s S и t T.
Пропускной способностью разреза (S,T) называют сумму пропускных способностей,
пересекающих разрез рѐбер.
Для заданного потока f величина потока через разрез (S,T) определяется как сумма f(S,T)
по пересекающим разрез рѐбрам.
Минимальным разрезом называется разрез наименьшей пропускной способности (среди
всех разрезов сети).
Теорема Форда-Фалкерсона:
Во всякой сети величина максимального потока равна пропускной способности любого
минимального разреза.
Идея алгоритма состоит в нахождении сквозных путей с положительными потоками от
источника к стоку.
Рассмотрим ребро , с начальной пропускной способностью .
В процессе выполнения алгоритма части этих пропускных способностей «забираются»
потоками, проходящими через данное ребро. В результате каждое ребро будет иметь
остаточную пропускную способность.
(cij, cji) – остаточная пропускная способность .
Сеть, где все рѐбра имеют остаточную пропускную способность, называется остаточной.
Для произвольного узла j, получающего поток от узла i, определим метку [aj, i], где aj –
величина потока между узлами.
Алгоритм Форда-Фалкерсона нахождения максимального потока
Е V 1
f : V V R
f ( u ,v ) c ( u ,v )
f (u , v ) f (v , u )
v V
f (u , v ) 0
v V
f f ( s ,v )
( i , j ) ( С ,C ) ij ji
1. Для всех рѐбер (i,j) положить остаточную пропускную способность равной
первоначальной:
Назначим a1= и пометим узел 1 меткой [ ,-].
Полагаем i=1.
2. Определить множество Si, как множество узлов j, в которые можно перейти из i по
ребру с положительной остаточной пропускной способностью.
Если Si , выполняем шаг 3, иначе шаг 4.
3. В множестве Si находим узел k, такой, что
Положим ak=cik и пометим узел k меткой [ak,i].
Если последней меткой помечен узел стока (k=n), сквозной путь найден, переходим к
шагу 5.
Иначе полагаем i=k и возвращаемся к шагу 2.
4. (Откат назад). Если i=1, сквозной путь невозможен, переходим к шагу 6.
Если i 1, находим помеченный узел r, непосредственно предшествующий узлу i, и
удаляем узел i из множества узлов, смежных с узлом r.
Полагаем i=r и возвращаемся к шагу 2.
5. (Определение остаточной сети).
Обозначим через множество узлов, через которые проходит p-й
найденный сквозной путь от источника к стоку.
Тогда максимальный поток, проходящий по этому пути равен:
Остаточные пропускные способности рѐбер, составляющих сквозной путь, уменьшаются
на fp в направлении движения потока и увеличиваются на fp в противоположном
направлении.
Для ребра (i,j), входящего в сквозной путь, текущие остаточные стоимости будут равны:
a) , если поток i j;
b) , если поток j i.
Восстанавливаем все узлы, удалѐнные на шаге 4. Полагаем i=1. Возвращаемся к шагу 2.
6. (Решение).
a) При m найденных сквозных путях максимальный поток вычисляется по формуле:
b) Имея значения начальных и конечных пропускных способностей
ребра (i,j) вычисляем оптимальный поток через это ребро.
Положим
Если >0, то поток, проходящий через ребро (i,j), равен .
Если >0, то поток равен .
Случай, когда одновременно >0 и >0 невозможен.