На главную   ::   Содержание



Потоки в сетях. Теорема Форда--Фалкерсона о максимальном потоке в сети

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

Теперь сформулируем задачу более строго.

Пусть задан ориентированный граф $ G=(V,E)$ с двумя выделенными вершинами, $ s\in V$ -- источником и $ t\in V$ -- стоком. Пусть каждому ребру $ (u,v)\in E$ поставлено в соответствие число $ c(u,v)\geqslant0$, называемое пропускной способностью ребра. В случае, когда $ (u,v)\notin E$ , полагаем $ c(u,v)=0$. Будем считать, что граф связен и любая вершина $ v\in V$ лежит на каком-либо пути $ s\rightsquigarrow v \rightsquigarrow t $ (из истока в сток). То есть, нет «бесполезных» вершин. Такой граф будем называть сетью.

Потоком в сети $ G$ назовем функцию $ f: V\times V\rightarrow \mathbb{R}$ , обладающую следующими тремя свойствами:

  1. Ограничение, связанное с пропускной способностью:

    $\displaystyle f(u,v)\leqslant c(u,v)\quad\forall  u,v \in V
$

  2. Кососимметричность:

    $\displaystyle f(u,v)=-f(v,u)\quad\forall  u,v \in V
$

  3. Сохранение потока:

    $\displaystyle \sum_{v\in V}f(u,v)=0\quad\forall u\in V\setminus \{s,t\}
$

Величина $ f(u,v)$ показывает, сколько вещества движется из вершины $ u$ в вершину $ v$. Если эта величина отрицательна, то вещество движется в обратную сторону.

Величина потока -- это число, определяемое как сумма

$\displaystyle \vert f\vert=f(s, V)=\sum_{v\in V}f(s,v).$

Задача поиска максимального потока: для заданной сети $ G$ найти поток максимальной величины.

ОСТАТОчНЫЕ СЕТИ
$\textstyle \parbox{1.5em}{{ }\hspace{1.5em}{ }}$ Пусть $ G=(V,E)$ -- сеть с истоком $ s$ и стоком $ t$. Пусть $ f$-- поток в этой сети.

Определение 1.   Для любой пары вершин $ u$ и $ v$ остаточной пропускной способностью из $ u$ в $ v$, называется величина

$\displaystyle c_f(u,v)=c(u,v)-f(u,v)
$

Эта величина определяет, сколько еще потока можно направить из $ u$ в $ v$. Остаточная пропускная способность может превосходить $ c(u,v)$, если в данный момент $ f(u,v)<0$ -- в этом случае можем отменить встречный поток и направить еще $ c(u,v)$ вещества, не превышая пропускной способности ребра $ (u,v)$.

Определение 2.   Сеть $ G=(V,E_f)$, где

$\displaystyle E_f=\bigl\{ (u,v)\in V \times V:\;c_f(u,v)>0 \bigr\},
$

называется остаточной сетью сети $ G$, порожденной потоком $ f$.

Следующая лемма поясняет, что потоки можно складывать, причем величина их тоже складывается. Поток, найденный по остаточной сети также складывается с потоком по исходной сети.

Лемма 1.   Пусть $ G=(V,E)$ -- сеть с истоком $ s$ и стоком $ t$, а $ f$ -- поток в ней. Пусть $ G_f$ -- остаточная сеть сети $ G$, порожеденная потоком $ f$. Пусть $ f'$ -- поток в $ G_f$, Тогда сумма $ f+f'$, определяемая, как

$\displaystyle (f+f')(u,v)=f(u,v)+f'(u,v)\quad \forall u,v\in V,
$

является потоком в сети $ G$, величины $ \vert f+f'\vert=\vert f\vert+\vert f'\vert$.

ДОПОЛНяЮЩИЕ ПУТИ
$\textstyle \parbox{1.5em}{{ }\hspace{1.5em}{ }}$ Пусть $ f$ -- поток в сети $ G$.

Определение 3.   Дополняющим путем называется простой путь из истока $ s$ в сток $ t$ в остаточной сети $ G_f$.

Ясно, что по каждому ребру дополняющего пути можно переслать еще сколько-то вещества. Обозначим такой путь через $ p$.

Определение 4.   Остаточной пропускной способностью пути $ p$ называется величина

$\displaystyle c_f(p)=\min\bigl\{ c_f(u,v):\;(u,v)\in p \bigr\}.
$

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

Лемма 2.   Пусть $ f$ -- поток в сети $ G$ и $ p$ -- дополняющий путь в $ G_f$. Определим функцию $ f_p: V \times V\rightarrow \mathbb{R}$ так:

$\displaystyle f_p(u,v)=
\begin{cases}
c_f(p),&\text{ если $(u,v)\in p$ };\\...
...{ если $(v,u)\in p$ };\\
0,&\text{ в остальных случаях}.\\
\end{cases}
$

Тогда $ f_p$ -- поток в сети $ G_f$, причем $ \vert f_p\vert=c_f(p)>0$.

Очевидно, что если добавить поток $ f_p$ к потоку $ f$ (говорят, увеличить покок $ f$ вдоль пути $ p$), то получится поток с большим значением. Результат этого добавления формулируется в следующей лемме.

Следствие 1.   Пусть выполнены условия леммы 2., тогда функция $ f'=f+f_p$ является потоком в сети $ G$, величины $ \vert f'\vert=\vert f\vert+\vert f_p\vert>\vert f\vert$.

РАЗРЕЗЫ В СЕТяХ
$\textstyle \parbox{1.5em}{{ }\hspace{1.5em}{ }}$

Определение 5.   Разрезом в сети $ G=(V,E)$ называется разбиение множества $ V$ на две части $ S$ и $ T=V\setminus S$, для которых $ s\in S$ и $ t\in T$.

Определение 6.   Пропускной способностью разреза $ (S,T)$ называют сумму $ c(S,T)$ пропускных способностей пересекающих разрез ребер:

$\displaystyle c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)
$

Определение 7.   Для заданного потока $ f$ величина потока через разрез $ (S,T)$ есть сумма $ f(S,T)$ по пересекающим разрез ребрам:

$\displaystyle f(S,T)=\sum_{u\in S}\sum_{v\in T} f(u,v)
$

Определение 8.   Минимальным разрезом называется разрез наименьшей пропускной способности (среди всевозможных разрезов данной сети).

Следующая лемма утверждает важное свойство разрезов. Оказывается, что величины потока через все разрезы одинаковы (и равны величине потока).

Лемма 3.   Пусть $ f$ -- поток в сети $ G$, а $ (S,T)$ -- разрез сети $ G$. Тогда поток $ f(S,T)$ через разрез $ (S,T)$ равен $ \vert f\vert$.

Следствие 2.   Величина любого потока $ f$ в сети $ G$ не превосходит пропускной способности любого разреза сети $ G$.

Теорема 1. (Форда--Фалкерсона о макс. потоке и мин. разрезе)   Пусть $ f$ -- поток в сети $ G=(V,E)$. Тогда следующие утверждения равносильны:
  1. Поток $ f$ максимален (по величине) в сети $ G$.
  2. Остаточная сеть $ G_f$ не содержит дополняющих путей.
  3. Для некоторого разреза $ (S,T)$ сети $ G$ выполнено равенство $ \vert f\vert=c(S,T)$.

Доказательство. $ (1)\Rightarrow(2)$. Пусть $ f$ -- максимален, однако $ G_f$ содержит дополняющий путь $ p$. Рассмотрим сумму $ f+f_p$, по следствию 1. это поток в $ G$, причем его величина больше, чем $ \vert f\vert$, что противоречит максимальности $ f$.

$ (2)\Rightarrow(3)$. Пусть в сети $ G_f$ нет пути из истока в сток. Рассмотрим

$\displaystyle S=\bigl\{ v\in V:\;$   в $G_f$ существует путь из $s$ в $v$$\displaystyle \bigr\}.
$

Положим $ T=V\setminus S$. Очевидно, что $ s\in S$, а $ t\in T$. Поэтому пара $ (S,T)$ -- разрез. Ни для каких $ u\in S$ и $ v\in
T$ ребро $ (u,v)$ не пренадлежит $ E_f$ (иначе $ v$ попала бы в $ S$). Поэтому $ f(u,v)=c(u,v)$. По лемме 3. $ \vert f\vert=f(S,T)=c(S,T)$.

$ (3)\Rightarrow(1)$. Из неравенства $ \vert f\vert\leqslant c(S,T)$ (следствие 2.) и равенства $ \vert f\vert=c(S,T)$ (по условию) следует, что поток $ f$ максимален.

$ \blacksquare$



На главную   ::   Содержание