Алгоритм проталкивания предпотока

Алгоритм проталкивания предпотока решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда-Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время $O(V^{2}E)$$O(V^{2}E)$. Некоторые усовершенствования ещё ускоряют алгоритм: правило выбора вершин «поднять в начало» - до $O(V^3)$$O(V^{3})$, выбор высшей активной вершины - до $O(V^2\sqrt{E})$$O(V^{2}{\sqrt {E}})$, реализация с использованием структуры данных Сеанора (Seanor) и Тарьяна - до $O(VE\log <!--\; \; -->(V^2/E))$$O(VE\log(V^{2}/E))$ . Впервые был опубликован в 1986 году Гольдбергом (Andrew W. Goldberg) и Тарьяном..

Описание алгоритмаПравить

Определения и обозначенияПравить

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

Мы обозначаем множествa вершин и рёбер сети через $\mathbf{V}$${\mathbf {V}}$  и $\mathbf{E}$$\mathbf {E}$ , а их количествa через V и E.

Алгоритм использует предпоток (preflow) — функцию $f:V\times <!--\; \times \; -->V\to <!--\; \to \; -->\mathbb{R}$$\ f:V\times V\rightarrow {\mathbb {R}}$  со следующими свойствами для любых вершин $u$$\ u$  и $v$$\ v$ :

1. Ограничение пропускной способности. Поток не может превысить пропускную способность: $f(u,v)\le <!--\; \le \; -->c(u,v).$$\ f(u,v)\leq c(u,v).$ 
2. Антисимметричность. Поток из $u$$\ u$  в $v$$\ v$  должен быть противоположным потоку из $v$$\ v$  в $u$$\ u$ : $f(u,v)=-<!--\; -\; -->f(v,u).$$\ f(u,v)=-f(v,u).$ 
3. Неотрицательность избыточного потока: $\underset{w\in <!--\; \in \; -->V}{\sum <!--\; \sum \; -->}f(w,u)\ge <!--\; \ge \; -->0$$\ \sum _{w\in V}f(w,u)\geq 0$  для всех $u\in <!--\; \in \; -->V$$\ u\in V$ , кроме источника и стока.

Первые два свойства совпадают с аналогичными свойствами для потока, третье является ослаблением свойства сохранения потока. Содержащаяся в этом свойстве сумма $\underset{w\in <!--\; \in \; -->V}{\sum <!--\; \sum \; -->}f(w,u)$$\ \sum _{w\in V}f(w,u)$  называется избыточным потоком (excess) и обозначается $e_u$$e_{u}$  . Согласно этому свойству, избыточный поток неотрицателен для всех вершин, кроме источника и стока.

Мы называем вершину переполненной, если она не является источником или стоком, а избыточный поток в эту вершину строго положителен. Легко убедиться, что предпоток является потоком тогда и только тогда, когда нет переполненных вершин.

ПеременныеПравить

Алгоритм хранит следующие данные:

• предпоток f
• избыточный поток $e_u$$e_{u}\$  для каждой вершины
• приписываемое каждой вершине неотрицательное целое число, называемое высотой. Высота вершины u обозначается $h_u$$h_{u}\$ .

ИнициализацияПравить

Изначально предпоток равен пропускной способности для всех рёбер, выходящих из источника, и противоположен для обратных пар вершин:

$f(s,u)=c(s,u)$$f(s,u)=c(s,u)\$ 

$f(u,s)=-<!--\; -\; -->c(s,u)$$f(u,s)=-c(s,u)\$ 

Для остальных пар вершин предпоток равен нулю.

Начальная высота равна V для источника и 0 для всех остальных вершин.

ОперацииПравить

Алгоритм применяет две операции: проталкивание (push) и подъём (relabel).

ПроталкиваниеПравить

Проталкивание из вершины u к вершине v возможно при выполнении следующих условий:

• вершина u переполнена
• остаточная сеть содержит ребро (u, v) (иначе говоря, v - потомок u)
• v ниже u: $h_u>h_v$$h_{u}>h_{v}\$ 

Проталкивание заключается в том, что поток $f(u,v)$$f(u,v)$  увеличивается на величину

$\mathrm{\delta <!--\; \delta \; -->}f(u,v)=min(e_u,c(u,v)-<!--\; -\; -->f(u,v))$$\delta f(u,v)=\min(e_{u},c(u,v)-f(u,v))\$ 

На столько же увеличивается избыточный поток $e_v$$e_{v}\$ .

Обратный поток $f(v,u)$$f(v,u)\$  и избыточный поток $e_u$$e_{u}\$  на столько же уменьшаются.

Проталкивание называется насыщающим, если $\mathrm{\delta <!--\; \delta \; -->}f(u,v)=c(u,v)-<!--\; -\; -->f(u,v)$$\delta f(u,v)=c(u,v)-f(u,v)\$ . После насыщающего проталкивания $f(u,v)$$f(u,v)\$  становится равным $c(u,v)$$c(u,v)\$ , в результате чего ребро (u, v) исключается из остаточной сети. При ненасыщающем проталкивании $\mathrm{\delta <!--\; \delta \; -->}f(u,v)=e_u$$\delta f(u,v)=e_{u}\$ , следовательно, оно делает вершину u непереполненной.

ПодъёмПравить

Подъём вершины u возможен при выполнении следующих условий:

• вершина u переполнена
• ни один потомок u не ниже u

Подъём заключается в том, что из всех потомков u выбирается вершина v с минимальной высотой, после чего высота вершины u становится равной $h_v+1$$h_{v}+1$ .

АлгоритмПравить

• Инициализировать предпоток, избыточные потоки и высоты
• Пока возможно проталкивание или подъём, выполнить любую возможную операцию.

Свойства алгоритмаПравить

Доказательство максимальности потокаПравить

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

Лемма 1. Подъём любой вершины увеличивает её высоту.
Доказательство. Перед подъёмом вершина не выше самого низкого из её потомков. После подъёма она выше его. Высота потомка не изменилась. Следовательно, увеличилась высота поднимаемой вершины.

Лемма 2. Высота любой вершины никогда не уменьшается.
Доказательство. Проталкивание не меняет высоты вершин. Подъём увеличивает высоту поднимаемой вершины и не меняет высоты других вершин.

Лемма 3. Высоты источника и стока всегда остаются равными V и 0 соответственно.
Доказательство. Источник и сток по определению не могут быть переполненными, следовательно, никогда не подвергаются подъёму. Ни подъём других вершин, ни проталкивание не влияет на высоту источника или стока. Следовательно, их высоты всегда остаются такими, как в момент инициализации, что и требовалось доказать.

Лемма 4. f всегда удовлетворяет свойствам предпотока.
Доказательство. Доказываем индукцией по количеству выполненных операций. Нам надо доказать, что после инициализации f удовлетворяет свойствам предпотока, а также что если f удовлетворяло свойствам предпотока до операции проталкивания или подъёма, оно будет им удовлетворять и после неё.

• Инициализация. Доказывается тривиальной проверкой свойств предпотока.
• Проталкивание. Тоже доказывается тривиальной проверкой свойств предпотока.
• Подъём. Вообще не влияет на потоки.

Лемма 5 (свойство высоты). Для любого ребра остаточной сети (u, v) выполняется неравенство

$h_u\le <!--\; \le \; -->h_v+1$$h_{u}\leq h_{v}+1\$ 

Доказательство. Доказываем индукцией по количеству выполненных операций аналогично предыдущей лемме.

• Инициализация. После инициализации высота источника V, любой другой вершины 0. Значит, неравенство $h_u\le <!--\; \le \; -->h_v+1$$h_{u}\leq h_{v}+1$  может нарушаться только если $u=s$$u=s\$ , $v\ne <!--\; \ne \; -->s$$v\neq s\$ . Но таких рёбер в остаточной сети нет. В самом деле, если граф содержит ребро (s, v), то $f(s,v)=c(s,v)$$f(s,v)=c(s,v)$ , и остаточная пропускная способность ребра равна нулю. Если граф такого ребра не содержит, то $f(s,v)=0$$f(s,v)=0$  и $c(s,v)=0$$c(s,v)=0$ , и опять же остаточная пропускная способность ребра равна нулю.
• Проталкивание. Не влияет на высоты вершин, но может создать в остаточной сети ребро (v, u) и/или исключит из неё ребро (u, v).
  • Создание ребра (v, u). Проталкивание возможно только если $h_{v}<h_{u}\$ , откуда следует $h_v\le <!--\; \le \; -->h_u+1$$h_{v}\leq h_{u}+1\$ . Значит, для вновь созданного ребра условие выполняется.
  • Исключение ребра (u, v). Отменяет одно из условий свойства высоты, следовательно, не прекращает его выполнение.
• Подъём. Рассмотрим неравенство $h_u\le <!--\; \le \; -->h_v+1$$h_{u}\leq h_{v}+1\$  для любой пары вершин. До подъёма оно выполняется. Если u — не поднимаемая вершина, то подъём не меняет высоту $h_u$$h_{u}\$  и не уменьшает $h_v$$h_{v}\$ , значит, неравенство продолжит выполняться и после подъёма. Если u — поднимаемая вершина, то пусть w — самый низкий из его потомков. Тогда после подъёма $h_u=h_w+1\le <!--\; \le \; -->h_v+1$$h_{u}=h_{w}+1\leq h_{v}+1\$ , что и требовалось доказать.

Лемма 6. Если в остаточной сети вершина w достижима из вершины u, то $h_{u}-h_{w}<V\$ .
Доказательство. Рассмотрим кратчайший путь из u к w. Он не содержит циклов, следовательно, его длина не больше $V-<!--\; -\; -->1$$V-1$ . Но по свойству высоты, на каждом ребре этого пути высота уменьшается не более чем на 1. Следовательно, на всём пути она уменьшается не более чем на $V-<!--\; -\; -->1$$V-1$ , что и требовалось доказать.

Лемма 7. В остаточной сети сток никогда не достижим из источника.
Доказательство. Пускай это не так. Тогда по предыдущей лемме $h_{s}-h_{t}<V\$ . Но по лемме 3, $h_s-<!--\; -\; -->h_t=V-<!--\; -\; -->0=V$$h_{s}-h_{t}=V-0=V\$ . Противоречие.

Лемма 8. Если алгоритм когда-то завершит работу, в этот момент предпоток будет потоком.
Доказательство. Имея переполненную вершину, мы всегда можем совершить или проталкивание (если вершина выше хотя бы одного потомка), или подъём (в противном случае). Поскольку алгоритм завершает работу только когда никакие операции невозможны, в этот момент переполненных вершин нет, откуда и следует утверждение леммы.

Теорема. Если алгоритм когда-то завершит работу, в этот момент предпоток будет максимальным потоком.
Доказательство. По лемме 8, предпоток станет потоком. По лемме 7, в остаточной сети сток будет не достижим из источника, иными словами, не будет увеличивающего пути. Следовательно, поток будет максимальным.

Максимальное количество операций проталкивания и подъёмаПравить

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

Лемма 1. Избыточный поток в сток ($e_t$$e_{t}$ ) никогда не уменьшается.
Доказательство. Проталкивание из u в v уменьшает избыточный поток только в u, а подъём вообще не влияет на избыточные потоки. Следовательно, единственный способ уменьшить $e_t$$e_{t}$  - совершить проталкивание из стока в другую вершину. Но проталкивание возможно только из переполненных вершин, а сток не может быть переполнен по определению. Значит, уменьшить $e_t$$e_{t}$  невозможно.

Лемма 2. Избыточный поток в сток ($e_t$$e_{t}$ ) всегда неотрицателен.
Доказательство. Сразу после инициализации он равен $c(s,t)$$c(s,t)$ , следовательно, неотрицателен. В дальнейшем он не уменьшается, следовательно, остаётся неотрицательным.

Лемма 3. В остаточной сети источник всегда достижим из любой переполненной вершины.
Доказательство. Пусть источник s недостижим из некоторой вершины u. Докажем, что u не переполнена. Пусть U, U' - множества вершин, соответственно достижимых и недостижимых из u в остаточной сети. По предположению, $s\notin <!--\; \notin \; -->U$$s\notin U$ . Рассмотрим любую пару вершин $v\in <!--\; \in \; -->U$$v\in U$ , $w\in <!--\; \in \; -->U^{\prime }$$w\in U'$ . Ребра (v,w) в остаточной сети нет, иначе бы из u можно было достичь v, а затем по этому ребру w, что противоречит $w\in <!--\; \in \; -->U^{\prime }$$w\in U'$ . С другой стороны, если $f(v,w)<0\$ , то остаточная пропускная способность $c(v,w)-<!--\; -\; -->f(v,w)$$c(v,w)-f(v,w)\$  положительна, следовательно, такое ребро должно быть. Значит, $f(v,w)\ge <!--\; \ge \; -->0$$f(v,w)\geq 0\$ , откуда $f(w,v)\le <!--\; \le \; -->0$$f(w,v)\leq 0\$ . Теперь просуммируем избыточные потоки во все вершины U:

$\underset{v\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}{e}_v=\underset{v\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}\underset{w\in <!--\; \in \; -->V}{\sum <!--\; \sum \; -->}f(w,v)=\underset{v\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}\underset{w\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}f(w,v)+\underset{v\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}\underset{w\in <!--\; \in \; -->U^{\prime }}{\sum <!--\; \sum \; -->}f(w,v)$$\sum _{v\in U}e_{v}=\sum _{v\in U}\sum _{w\in V}f(w,v)=\sum _{v\in U}\sum _{w\in U}f(w,v)+\sum _{v\in U}\sum _{w\in U'}f(w,v)$ 

Первая из двух сумм в правой части равна нулю, потому что для каждой релевантной пары вершин (v,w) в ней есть два слагаемых f(v,w) и f(w,v), сумма которых равна нулю. Вторая же неположительна, поскольку неположительны все её слагаемые. Значит,

$\underset{v\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}{e}_v\le <!--\; \le \; -->0$$\sum _{v\in U}e_{v}\leq 0$ 

С другой стороны, каждое слагаемое в сумме $\underset{v\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}{e}_v$$\sum _{v\in U}e_{v}$  неотрицательно:

• если v - не источник и не сток, то $e_v\ge <!--\; \ge \; -->0$$e_{v}\geq 0$  по третьему свойству предпотоков
• источника в сумме нет, потому что $s\notin <!--\; \notin \; -->U$$s\notin U$ 
• $e_t\ge <!--\; \ge \; -->0$$e_{t}\geq 0$  по предыдущей лемме

Из того, что сумма неотрицательных слагаемых неположительна, следует, что все её слагаемые равны нулю. В частности, $e_u=0$$e_{u}=0\$ , то есть u не переполнена, что и требовалось доказать.

Лемма 4. Высота любой вершины всегда меньше 2V.
Доказательство. Рассмотрим некую вершину u. Единственный способ изменить высоту вершины - подъём этой вершины. Следовательно, если вершина u никогда не поднималась, её высота осталась такой же, как была после инициализации, то есть 0 или V, и лемма доказана. В противном случае её высота осталась той же, какой стала в результате последнего подъёма. Перед последним подъёмом u была переполнена, значит, в остаточной сети из неё был достижим исток s. После подъёма путь из u в s в остаточной сети сохранился, потому что подъём не влияет на остаточную сеть. Значит, по лемме 6 из предыдущего раздела, $h_{u}-h_{s}<V$ , откуда $h_{u}<2V$ , что и требовалось доказать.

Теорема. За всё время работы алгоритма подъёмов может быть не более $(2V-<!--\; -\; -->1)(V-<!--\; -\; -->2)$$(2V-1)(V-2)$ .
Доказательство. Подъём вершины увеличивает её высоту не менее чем на 1. Начальная высота каждой вершины не меньше 0, конечная, по предыдущей лемме, не больше 2V-1. Уменьшиться высота вершины не может. Значит, каждая вершина может выдержать не более 2V-1 подъёмов. Всего можно поднимать не более V-2 вершин (все, кроме s и t). Отсюда следует утверждение теоремы.

Теорема . За всё время работы алгоритма насыщающих проталкиваний может быть не более $2VE$$2VE$ .
Доказательство. Рассмотрим два последовательных насыщающих проталкивания из u к v. Первое из них исключает ребро (u, v) из остаточной сети, к моменту выполнения второго это ребро вновь появляется. Значит, между этими двумя проталкиваниями выполняется проталкивание из v к u, что является единственным способом восстановить ребро. При первом насыщающем проталкивании $h_u>h_v$$h_{u}>h_{v}$ , при проталкивании из v к u, наоборот, $h_{u}<h_{v}$ . Учитывая, что уменьшиться высоты не могут, получаем, что высота $h_v$$h_{v}$  увеличилась по крайней мере на 2. Поскольку это происходит между каждыми двумя последовательными насыщающими проталкиваниями из u к v, а высота любой вершины не может увеличиться более чем на 2V-1 (от 0 до 2V-1), количество проталкиваний из u к v не превышает V. Всего имеется 2E пар вершин, подходящих для проталкивания (все рёбра и им обратные). Значит, всего насыщающих проталкиваний не может быть больше, чем 2VE.

Наконец, чтобы найти верхнюю границу для числа ненасыщающих проталкиваний, используем в качестве потенциальной функции сумму высот всех переполненных вершин. Обозначим эту сумму через Φ. Ненасыщающее проталкивание из u в v не меняет высот, но превращает u из переполненной в непереполненную и может превратить v из непереполненной в переполненную; на статус остальных вершин оно не влияет. Следовательно, Φ уменьшается как минимум на $h_u-<!--\; -\; -->h_v$$h_{u}-h_{v}$ . Проталкивание возможно только если $h_u>h_v$$h_{u}>h_{v}$ , следовательно, ненасыщающее проталкивание уменьшает Φ как минимум на 1. Изначально Φ=0, но никогда Φ не может стать отрицательным. Значит, алгоритм может совершить лишь столько ненасыщающих проталкиваний, на сколько другие операции повысят Φ. Подъём повышает Φ не более чем на 2V-1, a насыщающее проталкивание - также не более чем на 2V-1. Значит, общее количество таких проталкиваний не более $(2V-<!--\; -\; -->1{)}^2(V-<!--\; -\; -->2)+2VE(2V-<!--\; -\; -->1)$$(2V-1)^{2}(V-2)+2VE(2V-1)$ , или $O(V^2(V+E))$$O(V^{2}(V+E))$ .

Поскольку изолированные вершины (не инцидентные ни одному ребру исходной сети) никак не влияют на операции проталкивания или подъёма, для оценки числа операций мы можем мысленно исключить их, после чего $V\le <!--\; \le \; -->2E$$V\leq 2E$ . Следовательно, количество ненасыщающих проталкиваний $O(V^{2}E)$$O(V^{2}E)$ . Добавив сюда не более $2VE$$2VE$  насыщающих проталкиваний, мы получим, что общее количество проталкиваний также $O(V^{2}E)$$O(V^{2}E)$ .

РеализацияПравить

Храним множество переполненных вершин, а для каждой вершины — два множества потомков: с не меньшей высотой и с меньшей высотой. Все эти множества храним просто в виде массивов (в терминах C++ - векторов) элементов.

• Определение нужного действия:
  • если пусто множество переполненных вершин, останавливаемся
  • копируем его последний элемент в u
  • если y u нет потомков меньшей высоты, вызываем подъём u
  • иначе копируем последний из таких потомков в v и вызываем проталкивание от u к v
• Проталкивание из u в v
  • меняем f(u, v), f(v, u), e(u), e(v), предварительно сохранив их старые значения
  • при необходимости исключаем u из множества переполненных вершин
  • при необходимости добавляем v к этому множеству
  • при необходимости исключаем v из множества потомков u
  • при необходимости добавляем u к множеству потомков v с не меньшей высотой
• Подъём вершины u
  • просматриваем высоты всех потомков и находим минимальную из них
  • меняем высоту вершины u
  • просматриваем всех потомков с не меньшей высотой, и некоторых переносим в множество потомков с меньшей высотой
  • просматриваем всех соседей вершины u (списки соседей должны быть подготовлены при инициализации), и при необходимости переносим u в множество потомков с не меньшей высотой.

Определение нужного действия и проталкивания выполняются за константное время (заметим, что в проталкивании исключается всегда последний элемент множества). Следовательно, все определения нужного действия и проталкивания требуют $O(V^{2}E)$$O(V^{2}E)\$  операций.

Для нахождения времени подъёма заметим, что перенос вершины u в множество потомков с не меньшей высотой требует её исключения из множества потомков с меньшей высотой. Поскольку множества потомков хранятся как вектора, а исключение элемента вектора требует количества операций, пропорционального его длине, такой перенос может требовать $O(V)$$O(V)\$  операций. Значит, выполнение переносов для всех соседей требует $O(d_{u}V)$$O(d_{u}V)\$  операций, где $d_u$$d_{u}\$  — степень вершины u. Остальные действия, выполняемые в ходе подъёма, требуют меньшего количества операций, значит, подъём требует $O(d_{u}V)$$O(d_{u}V)\$  операций. Одна вершина может выдержать $2V-<!--\; -\; -->1$$2V-1\$  подъёмов, следовательно, все её подъёмы требуют $O(d_u{V}^2)$$O(d_{u}V^{2})\$  операций, а все подъёмы всех вершин — $O(\underset{u}{\sum <!--\; \sum \; -->}{d}_u{V}^2)=O(V^{2}E)$$O(\sum _{u}d_{u}V^{2})=O(V^{2}E)\$  операций.

Следовательно, реализация алгоритма занимает $O(V^{2}E)$$O(V^{2}E)\$  операций.

Алгоритм «поднять в начало»Править

Алгоритм «поднять в начало» (relabel to front) представляет собой более эффективную, чем описано выше, реализацию алгоритма проталкивания предпотока. Время работы составляет $O(V^3)$$O(V^{3})$ .

Допустимые рёбраПравить

Алгоритм использует понятие допустимых рёбер. Ребро (u, v) называется допустимым (admissable), если выполнены два условия:

1. $f(u,v)<c(u,v)\$ , или, что то же самое, ребро (u, v) присутствует в остаточной сети.
2. $h_u=h_v+1$$h_{u}=h_{v}+1\$ 

Заметим, что с учётом свойства высоты, эти условия совпадают с последними двумя условиями применимости к рёбрам операции проталкивания. Следовательно,

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

Кроме того, допустимость подъёма, с учётом свойства высоты, может быть сформулирована следующим образом

Подъём допустим тогда и только тогда, когда поднимаемая вершина переполнена и из неё не исходит допустимых рёбер

Кроме того, можно доказать ещё два свойства допустимых рёбер.

Свойство 1. Проталкивание не создаёт новых допустимых рёбер.
Доказательство. Пускай некоторое проталкивание сделало ребро (u, v) допустимым. Допустимость ребра (u, v) полностью определяется 4 параметрами: высотами вершин u и v, потоком по ребру и его пропускной способностью. На высоты вершин и пропускные способности рёбер никакое проталкивание не влияет. Значит, оно повлияло на поток f(u, v). Это могло сделать лишь проталкивание по ребру (u, v) или (v, u). Но проталкивание по ребру (u, v) требует, чтобы оно уже было допустимо до проталкивания, что противоречит предположению. Проталкивание же по ребру (v, u) требует в частности, чтобы u было ниже v. Поскольку проталкивание не влияет на высоты, u будет ниже v и после проталкивания, что нарушает второе условие допустимости.

Свойство 2. После подъёма вершины v, все рёбра, входящие в v, будут недопустимыми.
Доказательство. Рассмотрим любое такое ребро (u, v) и докажем, что после подъёма оно будет недопустимым.

• Если до подъёма ребро присутствовало в остаточной сети, то по свойству высоты выполнялось $h_u\le <!--\; \le \; -->h_v+1$$h_{u}\leq h_{v}+1$ . Подъём увеличивает высоту вершины v, следовательно, после него $h_{u}<h_{v}+1$ , что нарушает второе свойство допустимости.
• Если до подъёма ребро отсутствовало в остаточной сети, оно будет отсутствовать в ней и после подъёма, потому что подъём не влияет на потоки. Значит, первое условие допустимости будет нарушено.

Хранящиеся значенияПравить

Кроме предпотока и высот, алгоритм хранит следующее:

• Для каждой вершины v - список её соседей $N[v]$$N[v]$ . Список содержит каждую вершину w такую, что сеть содержит ребро (v,w) или ребро (w,v). Порядок произвольный. Списки соседей строятся один раз в начале работы алгоритма и далее не меняются.
• Для каждой вершины v - указатель $current[v]$$current[v]$  на один из элементов списка соседей (в терминах C++ - итератор). В начале указывает на первый элемент списка.
• Список L всех вершин, кроме источника и стока. В начале содержит вершины в произвольном порядке. В дальнейшем вершины могут перемещаться, но не исключаться и не добавляться к списку.
• Указатель it на один из элементов списка L (в терминах C++ - итератор). В начале указывает на первый элемент списка.

РазрядкаПравить

В этом разделе мы опишем функцию, которую называется разрядка (discharge) вершины. Разрядка применяется только к переполненным вершинам.

ОписаниеПравить

Разрядка вершины u выполняется следующим образом:

Шаг 1. Пока вершина u переполнена, выполнять шаги 2-4.

Шаг 2. Если current вышел за конец списка, поднять вершину u и вернуть current в начало списка.

Шаг 3. Иначе, если допустимо проталкивание от u к current[u], выполнить его.

Шаг 4. Иначе продвинуть current на 1 элемент вперёд.

СвойстваПравить

Лемма 1. После каждой итерации цикла, если функция не остановилась, вершина u будет переполненной.
Доказательство. Следует из проверки на шаге 1.

Лемма 2. После каждой итерации цикла, ребро (u, current[u]) недопустимо, не существует, либо функция остановится. Здесь current - значение указателя к началу итерации.
Доказательство. Если было выполнено условие на шаге 2, ребро не существует. Иначе, если не было выполнено условие на шаге 3, ребро было не допустимо; поскольку проталкивание не создаёт новых допустимых рёбер, оно и осталось недопустимым. Наконец, если было выполнено проталкивание на шаге 3, оно было или насыщающим, или ненасыщающим. В первом случае ребро (u, v) исчезло из остаточной сети, значит, для него нарушилось первое условие допустимости. Во втором случае вершина стала не переполненной, после чего функция остановилась на шаге 1.

Лемма 3. Когда выполняется условие шага 2, ни одно ребро, исходящее из u, не допустимо.
Доказательство. Рассмотрим любое такое ребро (u, v). Если вершина v не смежна с вершиной u, ребро отсутствует в остаточной сети, следовательно, нарушается первое условие допустимости. В противном случае вершина была рассмотрена на шаге 3. Рассмотрим последний раз, когда это произошло. Сразу после этого ребро (u, v), по предыдущей лемме, стало недопустимым. В дальнейшем в функции не могло проводиться никаких операций, кроме проталкивания по другим рёбрам, исходящим из u. Такие проталкивания не могли, по первому свойству допустимости, вновь сделать ребро (u, v) допустимым.

Свойство 1. Проталкивания и подъёмы выполняются только тогда, когда они допустимы.
Доказательство. Допустимость каждого проталкивания проверяется явно. Допустимость подъёма гарантируется тем, что на шаге 2 вершина u будет переполненной по лемме 1, а также тем, что из неё не исходит допустимых рёбер по лемме 3.

Свойство 2. После завершения работы функции, вершина u не переполнена.
Доказательство. Функция может остановиться только на шаге 1. Остановка происходит только если вершина u не переполнена.

Описание алгоритмаПравить

Помимо предпотока и высот, алгоритм "поднять в начало" хранит список вершин L и указатель на один из его элементов (в терминах C++ - итератор) it.

• Инициализация:
  • Инициализировать потоки и высоты, как в алгоритме проталкивания предпотока.
  • Если никаких вершин, кроме источника и стока, нет, остановиться; задача решена.
  • Построить списки соседей всех вершин и установить итераторы на начала списков.
  • Записать в L список всех вершин, кроме источника и стока, в произвольном порядке.
  • it указывает на начало списка.
• Пока it указывает на какую-то вершину списка:
  • Выполнить разрядку вершины, на которую указывает it.
  • Если вершина в ходе разрядки изменила высоту, переставить в начало списка её и итератор it (так что он по-прежнему будет указывать на неё).
  • Продвинуть итератор it на одну позицию вперёд.

СвойстваПравить

Топологической сортировкой орграфа (V,E) называется список некоторых его вершин, отсортированный так, что для любого ребра $(u,v)\in <!--\; \in \; -->E$$(u,v)\in E$ , u в списке находится раньше, чем v.

Лемма 1. После каждой итерации внешнего цикла, список L является топологической сортировкой графа допустимых рёбер (ТСГДР).
Доказательство. Индукция по количеству итераций внешнего цикла.
База. После инициализации высота источника равна V, всех остальных вершин 0. При этом $V\ge <!--\; \ge \; -->2$$V\geq 2$ , потому что есть хотя бы 2 вершины — источник и сток. Следовательно, для любой пары вершин второе условие допустимости нарушено, и допустимых рёбер нет вообще. Значит, любой список вершин является ТСГДР.
Шаг. Пускай мы просмотрели вершину v.

• Если она не была поднята, порядок вершин не изменился. До её просмотра список был ТСГДР. В ходе просмотра производились только операции проталкивания, которые не создают новых допустимых рёбер. Значит, список остался ТСГДР.
• Если она была поднята, то она была перемещена в начало списка. Докажем, что все допустимые рёбра удовлетворяют условию топологической сортировки.
  • Исходящие из v: должны удовлетворять условию топологической сортировки в любом случае, поскольку v находится в начале списка.
  • Входящие в v: таких нет. В самом деле, по свойству высоты перед последним подъёмом для любого ребра $(u,v)$$(u,v)$  остаточной сети выполнялось $h_u\le <!--\; \le \; -->h_v+1$$h_{u}\leq h_{v}+1$ . Подъём увеличил $h_v$$h_{v}$ , следовательно, после него уже выполнялось $h_{u}<h_{v}+1$ , что нарушает второе свойство допустимости. Значит, для любой вершины u, ребро $(u,v)$$(u,v)$  сразу после подъёма или не входило в остаточную сеть, или нарушало второе свойство допустимости. В обоих случаях оно было недопустимым. С тех пор не выполнялось никаких операций, кроме, может быть, проталкиваний. Как мы доказали, проталкивания не создают новых допустимых рёбер.
  • Не инцидентные v: в ходе итерации не менялась ни их допустимость, ни относительный порядок вершин, отличных от v. Следовательно, все эти рёбра продолжат удовлетворять условию топологической сортировки.

Лемма 2. После каждой итерации внешнего цикла, просмотренная вершина и все вершины, находящиеся левее её в списке, не переполнены.
Доказательство. Индукция по количеству итераций внешнего цикла.
База. После первой итерации просмотренная вершина не переполнена по свойству разрядки, а вершин левее её нет.
Шаг. Пускай мы просмотрели вершину v. Сама она не переполнена по свойству разрядки. Если она поднята и, следовательно, перемещена в начало списка, то вершин левее её нет, и теорема доказана. В противном случае на данной итерации выполнялись только операции проталкивания от вершины v к вершинам, в которые из v ведут допустимые рёбра. Поскольку операция проталкивания не создаёт новых допустимых рёбер, все эти рёбра были допустимыми и до начала итерации. Следовательно, по предыдущей лемме, все вершины, к которым выполнялось проталкивание, находились правее v в списке. Следовательно, вершины левее v в списке не могли стать переполненными на данной итерации. Но по предположению индукции, они не были переполненными и ранее. Теорема доказана.

Лемма 3. После завершения алгоритма, ни одна вершина не переполнена.
Доказательство. Чтобы завершить алгоритм, мы должны просмотреть последнюю вершину в списке L. По предыдущей лемме, после этого ни одна вершина списка L не переполнена. Но список L содержит все вершины, кроме источника и стока, а источник и сток не могут быть переполненными по определению.

Свойство. Алгоритм «поднять в начало» (АПН) является частным случаем алгоритма проталкивания предпотока (АПП).
Доказательство. Инициализация высот и предпотока в АПН совпадает с таковой у АПП. Изменения высот и предпотока в АПН происходит только путём вызова разрядки, которая, в свою очередь, выполняет лишь легитимные операции проталкивания и подъёма. Наконец, по завершению АПН ни одна вершина не переполнена, следовательно, операции проталкивания или подъёма невозможны.

Время работыПравить

Оценим количество раз, которое выполняются разные действия, и общее их время работы.

РазрядкиПравить

При каждой разрядке без подъёма it смещается на одну позицию вправо. Список L содержит V-2 вершин, следовательно, больше V-2 подряд разрядок без подъёма невозможно выполнить. Количество подъёмов $O(V^2)$$O(V^{2})$ , следовательно, количество разрядок $O(V^3)$$O(V^{3})$ .

Сам по себе вызов разрядки и сопутствующие расходы (продвижение итератора, возвращение по циклу) занимают константное время. Следовательно, общее время на все такие действия $O(V^3)$$O(V^{3})$ .

ПодъёмыПравить

Рассмотрим произвольную вершину u. Пусть $d_u$$d_{u}$  - её степень. Вершина может быть поднята не более 2V-1 раз, причём затраты времени на каждый подъём $O(d_u)$$O(d_{u})$ . Следовательно, затраты времени на подъём всех вершин составляют $O\left((2V-<!--\; -\; -->1)\underset{u}{\sum <!--\; \sum \; -->}{d}_u\right)$$O\left((2V-1)\sum _{u}d_{u}\right)$ , или $O(VE)$$O(VE)$ .

ПроталкиванияПравить

Насыщающих проталкиваний, как мы доказали ранее, не больше O(VE).

Ненасыщающее проталкивание делает вершину непереполненной, после чего разрядка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов разрядки, то есть $O(V^3)$$O(V^{3})$ .

Время работы одного проталкивания константное. Значит, общее время работы проталкиваний $O(V^3)$$O(V^{3})$ .

Сдвиги итератора currentПравить

Рассмотрим произвольную вершину u. Пусть $d_u$$d_{u}$  - её степень. Через каждые $d_u$$d_{u}$  сдвигов current[u] происходит подъём вершины. Всего подъёмов не более 2V-1. Следовательно, количество сдвигов итератора для всех вершин составляет $O\left((2V-<!--\; -\; -->1)\underset{u}{\sum <!--\; \sum \; -->}{d}_u\right)$$O\left((2V-1)\sum _{u}d_{u}\right)$ , или $O(VE)$$O(VE)$ .

Время каждого сдвига константное.

Суммарное времяПравить

Суммируя предыдущие разделы, получаем, что время работы алгоритма составляет $O(V^3+VE)$$O(V^{3}+VE)$ , или $O(V^3)$$O(V^{3})$ .

ЛитератураПравить

• Томас Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1., глава 26