Максимальный поток

по которым некоторое вещество движется от истока к стоку, или

как движение тока по проводам, информации по линиям связи или товаров от производителя к потребителю и т.д. Пометки ребер будем рассматривать, напрмер, как ширину дороги, или пропускную способность трубы.
Будем считать, что в вершинах вещество не накапливается — сколько приходит, столько и уходит (если вершина не является истоком или стоком). Это свойство называется «законом сохранения потока» (flow conservation).
Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его ещё можно доставить от истока к стоку при данных пропускных способностях труб.

ребру (и, v)  Е которого поставлено в соответствие число

с(и, v) ≥ 0, называемое
пропускной способностью ребра.
В случае (и, v)  Е полагаем с(и, v) = 0.
В графе выделены две вершины: исток s и сток t.

задаётся функцией с. Сеть имеет исток s и сток t.
Потоком

в сети G назовём функцию f : V X V —> R, удовлетворяющую трём свойствам:
1) Ограничение, связанное с пропускной способностью:
f(u, v) ≤ c(u, v) для всех и, v из V.
Поток из одной вершины в другую не превышает пропускной
способности ребра.
2) Кососимметричность: f(u,v) = —f(v,u) для всех и, v из V.
Величина f(u,v) может быть как положительной, так и отрицательной, отрицательные значения соответствуют движению в обратную сторону.
 f(и, и) = 0 для любой вершины и.
3) Сохранение потока: ∑vV f(u,v) = 0 для всех и  {V – {s, t}}.
Для любой вершины и (кроме стока и истока) сумма потоков во все другие вершины равна нулю.

как |f|.
Cкладываем потоки по всем рёбрам, выходящим из истока.

Учитывая кососимметричность,

свойство 3) можно
переписать как ∑uV f(u,v) = 0, т.е. сумма всех потоков из
других вершин равна нулю.

Задача о максимальном потоке состоит в следующем:
для данной сети G с истоком s и стоком t найти поток
максимальной величины.

f(и, v);
если f(и, v) = 0, поток не указывается.

ребром, то поток между ними равен нулю.
Действительно, если (и,

v)  Е и (v, и)  Е, то с(и, v) = c(v, и) = 0. Тогда из первого свойства следует, что f(u,v) ≤ 0 и f(v,u) ≤ 0. Вспоминая, что f(u,v) = —f(v,u) получим: f(u,v) = f(v,u) = 0.
Разделим вещество, поступающее в данную вершину v и вещество, из неё выходящее, то есть положительные и отрицательные значения f(u,v).
Сумму ∑uV f(u,v) назовём входящим (в вершину v) потоком.
f(u,v)>0
Аналогично определим выходящий поток.

Тогда свойство 3): для любой вершины, кроме истока и стока, входящий поток равен исходящему.

и складирует их в городе B (сток t). Она арендует

место в грузовиках другой фирмы, и место это ограничено: из города и в город v можно доставить не более с(и, v) ящиков в день. Ограничения с(и,v) показаны на рисунке. Задача состоит в том, чтобы перевозить максимально возможное количество изделий из г. A в г. В ежедневно. При этом путь может занимать несколько дней, и ящики могут ждать отправки в промежуточных пунктах, но необходимо, чтобы для каждого пункта число ежедневно прибывающих ящиков было равно числу увозимых, иначе ящиков нехватит или они будут накапливаться. Тем самым выполнено свойство сохранения потока. Величиной потока будет число изделий, ежедневно отгружаемых из г. А, и нас интересует поток максимальной величины.

f(u, v) > 0, после косой черты стоит пропускная способность

c(u,v).

Пример

v2 ежедневно везут восемь ящиков, а из v2 в v1

ежедневно везут три ящика, чему должны быть равны f(v1,v2) и f(v2,v1)?

Эти величины должны быть противоположны.

Мы полагаем f(v1,v2) = 8 — 3 = 5, a f(v2,v1)= —5.
Те же значения функции f соответствуют ежедневным перевозкам пяти ящиков из v1 в v2, так что в модели
встречные перевозки автоматически сокращаются.
Это разумно, экономика должна быть экономной.

v1) = 4.

Сначала из v1 в v2 возили ежедневно 8

ящиков.

Затем стали возить 3 ящика в обратном направлении.
Потом уменьшили число перевозимых в обратную сторону ящиков на 3.
Эти две различные (в жизни) ситуации соответствуют одной и той же
функции f, в обоих случаях f(v1,v2) = 5, a f(v2, v1) = –5.

Если требуется начать перевозки дополнительных 7 ящиков в день из
v2 в v1, то нужно прежде всего отменить перевозки 5 ящиков в обратную
сторону, после чего назначить перевозку дополнительных 2 ящиков.

сводится к обычной построением эквивалентной сети с одним истоком и

одним стоком. А именно: в сеть добавляется общий исток s, из которого ведут рёбра бесконечной пропускной способности во все прежние истоки. Аналогичным образом из всех прежних стоков проведены рёбра в общий сток t.
Добавленные рёбра имеют бесконечную пропускную способность.

В примере (след. слад) легко видеть, что каждый поток в сети (а) соответствует потоку в сети (Ь) и наоборот.

стоит множество вершин, то имеется в виду сумма по всем

элементам этого множества (неявное суммирование).
Это относится и к случаю нескольких переменных. Например, если X и Y — множества вершин, то
f(X,Y) = ∑xX ∑yY f(x,y)

В этих обозначениях закон сохранения потока запишется как f(u,V) = 0 для всех и  V – {s,t}.

Кроме того, в неявных суммах мы опускаем фигурные скобки.

Тогда для любого X  V выполнено
f(X,X) = 0.

Для

любых X, Y  V выполнено
f(X,Y) = – f(Y,X).

Для любых X, Y, Z  V из X ∩ Y = ø следует
f(XUY, Z) = f(X, Z) + f(У, Z) и
f(Z, XUY) = f(Z, X) + f(Z,Y).

s и стоком t. Пусть f — поток в
этой сети.

Для любой пары вершин и и v определяется остаточная пропускная способность из и в v:
cf (u,v) = c(u,v) – f (u,v).
Она определяет, сколько ещё потока можно направить из и в v.
Например, если c(u,v) = 16, a f(u,v) = 11 то мы можем переслать
ещё cf (и, v) = 5 единиц по ребру (и, v).
Остаточная пропускная способность cf (и, v) может
превосходить с(и, v), если в данный момент поток f(и, v)
отрицателен.
Например, если с(и, v) = 16, а f(и, v) = —4, то cf (u,v) = 20.
Мы можем увеличить поток на 4, отменив встречный поток,
и ещё отправить 16 единиц, не превышая пропускной
cпособности ребра (и, v).
Неформально говоря, остаточная сеть состоит из тех рёбер, поток
по которым можно увеличить.

 V x V: cf (u, v) > 0 }
назовём

остаточной сетью сети G, порождённой потоком f.
Её рёбра, называемые остаточными рёбрами, допускают
положительный поток.
Заметим, что остаточное ребро (и,v) не обязано быть ребром
сети G, может оказаться, что Ef  Е.
Такое ребро из и в v появляется, когда f(и, v) < 0, то есть когда
имеется имеется поток вещества в обратном направлении
(по ребру (v, и)) — ведь этот поток можно уменьшить.
Если ребро (и, v) принадлежит остаточной сети, то хотя бы одно
из рёбер (и, v) и (v, и) было в исходной сети.
Получаем оценку Ef ≤ 2 E.

в сети G, на рис. б) – остаточная сеть Gf
и

выделен путь p, по которому можно еще пропустить 4 единицы.
Рёбер (v1, s) и (v2,v3) не было в исходной сети.

c(v1, v2) = 10; c(v2, v1) = 4; f(v2, v1) = 1;
cf(v2, v1)= 4 – 1= 3; cf (v1, v2) = 10 – (-1) = 11;

c(v3, v2) = 9; c(v2, v3) = 0; f(v3, v2) = 4;
cf(v3, v2) = 9 – 4 = 5; cf (v2, v3) = 0 – (-4) = 4;

с пропускными
способностями Cf.
Пусть имеется сеть G = (V,

Е) и два потока f1 и f2 на ней.
Рассмотрим их сумму (функцию из V X V в R):
(f1 + f2)(u, v) = f1(u, v) + f2(u, v) (1)
Лемма 2
Пусть G = (V, Е) — сеть с истоком s и стоком t, а f — поток в ней.
Пусть Gf — остаточная сеть сети G, порождённая потоком f.
Пусть f' — поток в Gf. Тогда сумма f + f ', определенная как в (1),
является потоком в сети G величины | f + f '| = | f | + | f '|.

потоком.
1) Проверим условие, связанное с ограниченной пропускной
способностью. Заметим, что

f '(u,v) ≤ сf (u,v) для всех и, v  V,
Поэтому
(f + f ')(и, v) = f(u, v) + f '(u, v) ≤ f(u, v) + (c(u, v)-f(u, v)) = c(u, v).
2) Кососимметричность. Для всех и, v  V выполнено
(f + f’)(u, v) = f(u,v) + f'(u,v) = -f(v,u) - f'(v,u) = - (f(v,u) + f’(v,u)) =
- (f + f’)(u, v)
3) Закон сохранения потока. Для всех и  V \ {s, t} выполнено:
(f + f ')(u,V) = f(u,V) + f '(u,V) = f(u,V) + f '(u, V) = 0 + 0 = 0.

Наконец, найдём величину суммарного потока:
| f + f '| = (f + f')(s,V) = f (s,V) + f '(s,V) = |f | + |f '|.

Назовём дополняющим путём простой путь из истока s в сток

t в остаточной сети Gf.
Из определения остаточной сети вытекает, что по всем ребрам (и, v) дополняющего пути можно переслать ещё сколько-то вещества, не превысив пропускную способность ребра.

Величину наибольшего потока, который можно переслать по дополняющему пути р, назовём остаточной пропускной способностью пути р:
cf = min { cf(u,v): (u,v)  p }.

Е) и
р — дополняющий путь в Gf.
Определим функцию

fp : V X V —> R:
Cf (p), если (и, v)  р
fp(u,v) = –Cf (p), если (v,u)  p (1)
0, в остальных случаях.
Тогда fp — поток в сети Gf и |fp| = cf (p) > 0.

Если добавить поток fp к потоку f, то получится поток
в сети G с большим значением.

Е), а р — дополняющий путь в сети Gf, заданный

равенством (1).
Тогда функция f' = f + fp является потоком в сети G величины | f'| = | f | + |fp| > |f|.

Доказательство вытекает из лемм 2 и 3.

в) показана сеть – результат добавления потока величины 4, проходящего

вдоль пути p. На рис. г) показана остаточная сеть, порожденная потоком с рис. в).

множества V на две части S и T = V\S,

для которых sS и tТ.
Пропускной способностью разреза (S, T) называют сумму c(S, T) пропускных способностей пересекающих разрез ребер (по всем ребрам из S  T) .
Для заданного потока f величина потока через разрез (S, Т) определяется как сумма f(S, T) по пересекающим разрез ребрам.
Минимальным разрезом называют разрез наименьшей пропускной способности среди всех разрезов данной сети.

Поток через него равен
f(v1, v3) + f(v2, v3) +

f(v2, v4) = 12 + (-4) + 11 = 19,
Пропускная способность разреза равна
с(v1, v3) + с(v2, v4) = 12 + 14 = 26.
Поток через разрез, в отличие от пропускной способности разреза, может включать и отрицательные слагаемые.

S

T

t}).
Поток через него равен
f(v1, v3) + f(v2,

v3) + f(v4, v3) + f(v4, t) = 12 + (-4) + 7 + 4 = 19,
Пропускная способность разреза равна
с(v1, v3) + с(v4, v3) + с(v4, t) = 12 + 7+ 4 = 23.

T) разрез сети G. Поток f (S, T) через разрез

равен |f |.

Следствие 6
Величина любого потока f в сети G не превосходит пропускной способности любого разреза сети G.
Доказательство
|f| = f( S, T) = ∑uS ∑yT f(u,v) ≤ ∑uS ∑yT c(u,v) = c(S, T)

поток в сети G = (V, Е).
Тогда следующие утверждения

равносильны:
1. Поток f максимален (является потоком максимальной величины) в сети G.
2. Остаточная сеть Gf не содержит дополняющих путей.
Для некоторого разреза (S,T) сети G выполнено
равенство | f | = c(S, T).
В этом случае разрез является минимальным, то есть имеет минимально возможную пропускную способность.

Gf
содержит дополняющий путь р. Рассмотрим сумму f + fp, где

fp
задается равенством 1). По следствию 4 эта сумма является
потоком в G, величина которого больше |f|, что противоречит
максимальности.
(2) => (3) Пусть в сети Gf нет пути из истока s в сток t.
Рассмотрим множество S = { v  V: в Gf существует путь из s в v}.
Положим Т = V\S. Очевидно, что s  S, a t  Т, так как в Gf нет пути
из s в t. Поэтому пара (S,T) — разрез. Ни для каких и  S и v  Т
ребро (и, v) не принадлежит Ef (в противном случае вершина v
попала бы в S). Поэтому f(u, v) = с(и, v).
По лемме 5 |f | = f(S,T) = c(S,T).
(3) => (1) Для любого разреза (S,T) верно |f| ≤ c(S,T) (следствие 6).
Поэтому из равенства |f| = c(S,T) следует, что поток f максимален.

На каждом шаге мы увеличиваем значение потока. Для этого мы

находим дополняющий путь, по которому можно пропустить ещё немного вещества, и используем его для увеличения потока. Этот шаг повторяется, пока есть дополняющие пути. Полученный поток будет максимальным.

Ford-Fulkerson-Method(G, s, t) {
положить поток f равным 0;
while ( существует дополняющий путь )
дополнить f вдоль p;
return f;
}

поток f, добавляя поток величины cf (p) по пути р.

В массиве f [и, v] хранятся текущие значения потока.

Ford-Fulkerson(G,s,t)
for(для каждого ребра (u,v) ) {
f[u,v] = 0; f[v,u]= 0; }
while( в Gf существует путь р из s в t){
cf(p)← min{cf(u,v):(u,v)входит в p}
for(для каждого ребра(u,v)пути р){
f[u,v]=f[u,v]+cf(p);
f[v,u]= -f[u,v];
}
}
}

Если выбирать дополняющий путь при помощи
поиска в ширину, то алгоритм

работает полиномиальное время.
Рассмотрий случай, когда пропускные способности – целые
числа. Инициализация требует O(E). Цикл while выполняется не
более |f*| раз, где f* - максимальный поток.
Поиск дополняющего пути в остаточной сети займет время О(Е).
Поэтому время работы процедуры будет O(E |f*|).

Если использовать поиск в ширину, то путь р будет кратчайшим
из дополняющих путей (длину каждого ребра считаем равной 1)
Эта реализация метода Форда-Фалкерсона называется
алгоритмом Эдмондса-Карпа.
Время работы алгоритма Эдмондса-Карпа равно O(VE2).

4 + 7= 11

+ 8 = 19

+ 8 + 4 = 23

из s.

(V, Е) — неориентированный граф. Паросочетанием назовем множество рёбер М

 Е, не имеющих общих концов (каждая вершина v  V является концом максимум одного ребра из М).
Будем говорить, что вершина v  V входит в паросочетание М, если в М есть ребро с концом v;
в противном случае v свободна.
Максимальное паросочетание — это паросочетание М, содержащее максимально возможное число рёбер (|М| ≥ |М'| для любого паросочетания М').

два непересекающихся подмножества L и R, и любое ребро из

Е соединяет некоторую вершину из L с некоторой вершиной из R.

Например, L — женихи, R — невесты, наличие ребра (и, v) означает, что и и v согласны стать супругами. Максимальное паросочетание доставляет ЗАГСу больше всего работы.

Паросочетание из двух рёбер. (b) Максимальное паросочетание состоит из трёх

ребер.

в двудольном графе G = (V, Е) за полиномиальное от

|V| и |Е| время.
Для этого рассмотрим сеть G' = (V', E'), построенную следующим образом: добавяляются две новые вершины: исток (s) и сток (t): V' = V U {s,t}.
Е'= {(s,u):u  L} U {(и, v): uL, vR, (и, v)E} U {(v,t): v R}
(L и R обозначаются доли графа, ребра направленные).
Будем считать, что пропускная способность каждого ребра равна единице.

, если все значения f(u,v) — целые.
Лемма 8
Пусть G =

(V, Е) — двудольный граф с долями L и R, и G' = (V, Е') — соответствующая сеть. Пусть М — паросочетание в G.
Тогда существует целочисленный поток в G' со значением |f| = |М|. Обратно, если f — целочисленный поток в G’, то в G' найдется паросочетание из |f| элементов.
Теорема 9 о целочисленном потоке
Если пропускные способности всех рёбер — целые числа, то максимальный поток, найденный алгоритмом Форда-Фалкерсона, будет целочисленным.
Следствие 10 Число рёбер в максимальном паросочетания М в двудольном графе G равно значению максимального потока в сети G'.

любого ребра равна единице; поток по выделенным рёбрам равен единице,

по остальным — нулю. Выделенные рёбра, соединяющие вершины из L с вершинами из R, соответствуют максимальному паросочетанию в двудольном графе.

нам достаточно применить метод Форда-Фалкерсона и найти максимальный поток в

соотвествующей сети G’.
Оценка времени работы такого алгоритма.
Никакое паросочетание в двудольном графе не может содержать более min(L,R) = О (V) рёбер, поэтому значение максимального потока в G' равно O(V).
Следовательно, время работы алгоритма Форда-Фалкерсона равно O(VE).

шаге, а действуем локально в окрестности одной вершины. Кроме того,

не требуем, выполнения закона сохранения потока в процессе работы алгоритма.
Определим предпоток как функцию f : V X V —> R, которая кососимметрична, удовлетворяет ограничениям, связанным с пропускными способностями, а также ослабленному закону сохранения: f(V, и) ≥ 0 для всех вершин и V\{s}.
Таким образом, в каждой вершине и (кроме истока) есть некоторый неотрицательный избыток e(u) = f(V,u).
Вершину, отличную от s, с положительным избытком назовём переполненной.

сливается. Важную роль играет целочисленный параметр — высота вершины.
Мы

будем воображать, что в процессе работы алгоритма вершина может подниматься вверх. Высота вершины определяет, куда мы стараемся направить избыток жидкости.
Высота истока всегда равна |V|, а стока — нулю. Все остальные вершины изначально находятся на высоте 0, и со временем поднимаются.
Для начала мы отправляем из истока вниз столько жидкости, сколько нам позволяют пропускные способности выходящих из истока труб (это количество равно пропускной способности разреза (s, V\s )).
Возникающий в соседних с истоком вершинах избыток жидкости сначала просто выливается, но затем будет направлен дальше.

обнаружить, что в ней есть избыток жидкости, но все трубы,

по которым ещё можно отправить жидкость из и куда-то (в ненасыщенные трубы) ведут в вершины той же или большей высоты. В этом случае мы можем выполнить операцию, называемую «подъёмом» вершины и.
После этого вершина и становится на единицу выше самого низкого из тех её соседей, в которого ведёт ненасыщенная труба, т.е., мы поднимаем и ровно настолько, чтобы появилась ненасыщенная труба, ведущая вниз.
В конце концов мы добьёмся того, что в сток приходит максимально возможное количество жидкости. При этом предпоток может ещё не быть потоком (избыток жидкости сливается). Продолжая подъём вершин, которые могут стать выше истока, мы постепенно отправим избыток обратно в исток, что означает сокращение потока жидкости от истока, — и превратим предпоток в поток, который окажется максимальным.

s и стоком t, а f — предпоток в G.

Функция h : V —> N называется высотной функцией для предпотока f, если:
h(s) = |V|, h(t) = 0, h(u) ≤ h(v) + 1
для любого ребра (и, v)Ej.
Лемма 11
Пусть f — предпоток в сети G = (V, Е) и h — высотная функция. Тогда если для вершин и, v  V, выполнено h(u) > h(v) + 1, то остаточная сеть не содержит ребра (и, v) («по круто идущим вниз трубам идёт максимально возможный поток».)

> 0;
ребро (и, v) не насыщено: сf (и, v)

> 0;
h(u) = h(v) + 1.

Push(u,v) {
df (u,v) = min(e(u), cf (u,v);
f[u,v] = f[u,v]+ df (u,v);
f[v, u] = - f[u,v]
e[u] = e[u] – df (u,v);
e[v] = e[v] + df (u,v);
}

дополнительный поток лишь по рёбрам, идущим вниз с
единичной разницей высот.

Проталкивание называется насыщающим, если в результате
ребро (u,v) становится насыщенным, то есть если cf (u,v)
обращается в нуль (ребро исчезает из остаточной сети);
в противном случае проталкивание считают ненасыщающим.

Если есть сосед, который на единицу ниже, то можно выполнить
проталкивание, но нельзя выполнить подъём.
Если все соседи не ниже, то проталкивание выполнить нельзя,
а подъём — можно, после чего возможно проталкивание.

e(u) > 0;
2) для любого ребра (u,v)  Ef выполнено:h(u)

≤ h(v).
Lift (и) поднимает переполненную вершину и на максимальную
высоту, которая допустима по определению высотной функции:
высота вершины превосходит высоту соседа в остаточной сети
не более чем на 1.
Lift(u) {
h[u] = 1 + min{ h[v]: (u,v)  Ef };
}
Заметим, если вершина и переполнена, то в Ef найдётся по крайней
мере одно ребро, выходящее из и:
так как f[V, и] = е[и] > 0, поэтому существует по крайней мере одна
такая вершина v, для которой f(v, и) > 0.
 cf (u, v) = c(u, v) - f[u, v] = c(u, v) + f[v, u] > 0, что означает, что (и, v)  Ef.}

если и=s
fp(u,v) =

–C (v,u), если и=s
0, в остальных случаях.
Initialize(G, s) {
for (для каждой вершины u  V) {
h[u] = 0; e[u] = 0;
}
for (для каждого ребра (u,v)  E) {
f[u,v] = 0; f[v,u] = 0; h[s] = |V|;
}
for (для каждой вершины u  Adj [s]) {
f[s,u] = c(s,u); f[u,s] = -c(s,u); e[u] = c(s,u);
}
}

становится равным пропускной способности этого ребра. По остальным рёбрам поток

равен 0.
В каждой смежной с истоком вершине v появляется избыток e[v] = c(s, v ).
h – высотная функция, так как рёбра (и, v), для которых
h[u] > h[v] + 1, выходят только из истока, но они насыщены и их нет в остаточной сети.

Generic-Preflow-Push {
Initialize(G,s);
while (возможны операции подъема или проталкивания)
выполнить одну из этих операций;
}

(V,E). Пусть h — высотная функция для f и вершина

и переполнена. Тогда в и возможно либо проталкивание, либо подъём.
Доказательство
Поскольку h — высотная функция, то h(u) ≤ h(y) +1 для любого остаточного ребра (u,v). Если в и невозможно проталкивание, то для всех остаточных рёбер (и, v) выполнено неравенство
h(u) < h(v) + 1, из чего следует, что h(u) ≤ h(v), и в вершине и возможен подъём.

Корректность метода. 1) Если алгоритм остановится, то предпоток f в этот момент будет максимальным потоком. 2) Алгоритм действительно остановится.
Лемма 13 ри исполнении программы Generic-Preflow-Push высота h[u] любой вершины и  V может только возрастать.
Лемма 14 Во время выполнения программы Generic-Preflow-Push функция h остаётся высотной функцией.
Лемма 15 Пусть G = (V, Е) — сеть с истоком s и стоком t. Пусть f— предпоток в G, a h — высотная для f. Тогда в остаточной сети Gf не существует пути из истока в сток.

Е) с истоком s и стоком t останавливается, то получающийся

предпоток f, будет максимальным потоком для G.
Пояснение. В момент остановки переполненных вершин в сети нет. Значит, в этот момент предпоток является потоком. Функция h будет высотной функцией, и потому в остаточной сети Gf нет пути из s в t. По теореме о максимальном потоке и минимальном разрезе поток f максимален.
Лемма 16 Пусть G = (V, Е) — сеть с истоком s и стоком t, а f — предпоток в G. Тогда для любой переполненной вершины и найдется простой путь из и в s в остаточной сети Gf.
Лемма 17 При исполнении программы Generic-Preflow-Push высота любой вершины v  V не превосходит 2|V|− 1.

превосходит 2|V|2.

Лемма 18 При исполнении программы Generic-Preflow-Push количество насыщающих проталкиваний

не превосходит 2|V||E|.

Теорема
Общее число операций подъёма и проталкивания при исполнении программы Generic-Preflow-Push на сети
G = (V, Е) равно O(V2E).

n строк и n столбцов. Обозначим через (i, j) вершину

на пересечении i-го столбца и j-ой строки. Все вершины такой решётки, не считая граничных имеют четырёх соседей.
Требуется выяснить, существуют ли т попарно непересекающихся (не имеющих общих вершин) путей от данных т ≤ n2 начальных точек решётки (x1,y1), (х2,y2), … , (хт,yт) к т различным граничным точкам.

дубль. Все инцидентные ребра каждой внутренней вершины сделайте входящими. Добавьте

выходящую дугу из каждой внутренней вершины в вершину-дубль. Все инцидентные ребра каждой внутренней вершины сделайте выходящими из вершины-дубля.
Покажите, что задача о максимальном потоке в такой сети сводится к обычной задаче о максимальном потоке для построенной таким образом сети.

Е) назовается множество путей Р с таким свойством: каждая вершина

из V принадлежит ровно одному пути из Р. Пути могут начинаться и заканчиваться где угодно, и иметь любую длину, в том числе нулевую. Покрытие наименьшим возможным числом путей называется минимальным покрытием путями.

Решение
Построим граф G' = (V’, Е’), где
V’ = {х0, х1, ... , хn} U {у0, y1, …, уn},
E' = {(x0, xi): xi  V} U {(yi, y0): yi  V} U {(xi, yj}: (i, j)  Е}
Решим для этого графа задачу о максимальном потоке.

долей, сток – с правой.