Алгоритм проталкивания предпотока решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда-Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время . Некоторые усовершенствования ещё ускоряют алгоритм: правило выбора вершин «поднять в начало» - до , выбор высшей активной вершины - до , реализация с использованием структуры данных Сеанора (Seanor) и Тарьяна - до . Впервые был опубликован в 1986 году Гольдбергом (Andrew V. Goldberg) и Тарьяном..
Описание алгоритма
Определения и обозначения
В данной статье мы называем потомком вершины u любую вершину v такую, что остаточная сеть содержит ребро (u, v).
Мы обозначаем множествa вершин и рёбер сети через и , а их количествa через V и E.
Алгоритм использует предпоток (preflow) — функцию со следующими свойствами для любых вершин и :
Ограничение пропускной способности. Поток не может превысить пропускную способность: Антисимметричность. Поток из в должен быть противоположным потоку из в : Неотрицательность избыточного потока: для всех , кроме источника и стока.
Первые два свойства совпадают с аналогичными свойствами для потока, третье является ослаблением свойства сохранения потока. Содержащаяся в этом свойстве сумма называется избыточным потоком (excess) и обозначается . Согласно этому свойству, избыточный поток неотрицателен для всех вершин, кроме источника и стока.
Мы называем вершину переполненной, если она не является источником или стоком, а избыточный поток в эту вершину строго положителен. Легко убедиться, что предпоток является потоком тогда и только тогда, когда нет переполненных вершин.
Переменные
Алгоритм хранит следующие данные: предпоток f избыточный поток для каждой вершины приписываемое каждой вершине неотрицательное целое число, называемое высотой. Высота вершины u обозначается .
Инициализация
Изначально предпоток равен пропускной способности для всех рёбер, выходящих из источника, и противоположен для обратных пар вершин:
Для остальных пар вершин предпоток равен нулю.
Начальная высота равна V для источника и 0 для всех остальных вершин.
Операции
Алгоритм применяет две операции: проталкивание (push) и подъём (relabel).
Проталкивание Проталкивание из вершины u к вершине v возможно при выполнении следующих условий: вершина u переполнена остаточная сеть содержит ребро (u, v) (иначе говоря, v - потомок u) v ниже u:
Проталкивание заключается в том, что поток увеличивается на величину
На столько же увеличивается избыточный поток .
Обратный поток и избыточный поток на столько же уменьшаются.
Проталкивание называется насыщающим, если . После насыщающего проталкивания становится равным , в результате чего ребро (u, v) исключается из остаточной сети. При ненасыщающем проталкивании , следовательно, оно делает вершину u непереполненной.
Подъём Подъём вершины u возможен при выполнении следующих условий: вершина u переполнена ни один потомок u не ниже u
Подъём заключается в том, что из всех потомков u выбирается вершина v с минимальной высотой, после чего высота вершины u становится равной .
Алгоритм
Инициализировать предпоток, избыточные потоки и высоты Пока возможно проталкивание или подъём, выполнить любую возможную операцию.
Свойства алгоритма
Доказательство максимальности потока
Докажем, что если алгоритм когда-то закончит работу, в этот момент предпоток будет максимальным потоком. Попутно докажем другие леммы, полезные для дальнейшего.
Лемма 1. Подъём любой вершины увеличивает её высоту. Доказательство. Перед подъёмом вершина не выше самого низкого из её потомков. После подъёма она выше его. Высота потомка не изменилась. Следовательно, увеличилась высота поднимаемой вершины.
Лемма 2. Высота любой вершины никогда не уменьшается. Доказательство. Проталкивание не меняет высоты вершин. Подъём увеличивает высоту поднимаемой вершины и не меняет высоты других вершин.
Лемма 3. Высоты источника и стока всегда остаются равными V и 0 соответственно. Доказательство. Источник и сток по определению не могут быть переполненными, следовательно, никогда не подвергаются подъёму. Ни подъём других вершин, ни проталкивание не влияет на высоту источника или стока. Следовательно, их высоты всегда остаются такими, как в момент инициализации, что и требовалось доказать.
Лемма 4. f всегда удовлетворяет свойствам предпотока. Доказательство. Доказываем индукцией по количеству выполненных операций. Нам надо доказать, что после инициализации f удовлетворяет свойствам предпотока, а также что если f удовлетворяло свойствам предпотока до операции проталкивания или подъёма, оно будет им удовлетворять и после неё. Инициализация. Доказывается тривиальной проверкой свойств предпотока. Проталкивание. Тоже доказывается тривиальной проверкой свойств предпотока. Подъём. Вообще не влияет на потоки.
Лемма 5 (свойство высоты). Для любого ребра остаточной сети (u, v) выполняется неравенство
Доказательство. Доказываем индукцией по количеству выполненных операций аналогично предыдущей лемме. Инициализация. После инициализации высота источника V, любой другой вершины 0. Значит, неравенство может нарушаться только если , . Но таких рёбер в остаточной сети нет. В самом деле, если граф содержит ребро (s, v), то , и остаточная пропускная способность ребра равна нулю. Если граф такого ребра не содержит, то и , и опять же остаточная пропускная способность ребра равна нулю. Проталкивание. Не влияет на высоты вершин, но может создать в остаточной сети ребро (v, u) и/или исключит из неё ребро (u, v). Создание ребра (v, u). Проталкивание возможно только если , откуда следует . Значит, для вновь созданного ребра условие выполняется. Исключение ребра (u, v). Отменяет одно из условий свойства высоты, следовательно, не прекращает его выполнение. Подъём. Рассмотрим неравенство для любой пары вершин. До подъёма оно выполняется. Если u — не поднимаемая вершина, то подъём не меняет высоту и не уменьшает , значит, неравенство продолжит выполняться и после подъёма. Если u — поднимаемая вершина, то пусть w — самый низкий из его потомков. Тогда после подъёма , что и требовалось доказать.
Лемма 6. Если в остаточной сети вершина w достижима из вершины u, то . Доказательство. Рассмотрим кратчайший путь из u к w. Он не содержит циклов, следовательно, его длина не больше . Но по свойству высоты, на каждом ребре этого пути высота уменьшается не более чем на 1. Следовательно, на всём пути она уменьшается не более чем на , что и требовалось доказать.
Лемма 7. В остаточной сети сток никогда не достижим из источника. Доказательство. Пускай это не так. Тогда по предыдущей лемме . Но по лемме 3, . Противоречие.
Лемма 8. Если алгоритм когда-то завершит работу, в этот момент предпоток будет потоком. Доказательство. Имея переполненную вершину, мы всегда можем совершить или проталкивание (если вершина выше хотя бы одного потомка), или подъём (в противном случае). Поскольку алгоритм завершает работу только когда никакие операции невозможны, в этот момент переполненных вершин нет, откуда и следует утверждение леммы.
Теорема. Если алгоритм когда-то завершит работу, в этот момент предпоток будет максимальным потоком. Доказательство. По лемме 8, предпоток станет потоком. По лемме 7, в остаточной сети сток будет не достижим из источника, иными словами, не будет увеличивающего пути. Следовательно, поток будет максимальным.Доказательство того, что последнее утверждение следует из предпоследнего см. в статье «Транспортная сеть».
Максимальное количество операций проталкивания и подъёма
В этом разделе мы не только докажем, что алгоритм завершит работу за конечное время, но и дадим верхнюю оценку максимального количества операций проталкивания и подъёма.
Лемма 1. Избыточный поток в сток () никогда не уменьшается. Доказательство. Проталкивание из u в v уменьшает избыточный поток только в u, а подъём вообще не влияет на избыточные потоки. Следовательно, единственный способ уменьшить - совершить проталкивание из стока в другую вершину. Но проталкивание возможно только из переполненных вершин, а сток не может быть переполнен по определению. Значит, уменьшить невозможно.
Лемма 2. Избыточный поток в сток () всегда неотрицателен. Доказательство. Сразу после инициализации он равен , следовательно, неотрицателен. В дальнейшем он не уменьшается, следовательно, остаётся неотрицательным.
Лемма 3. В остаточной сети источник всегда достижим из любой переполненной вершины. Доказательство. Пусть источник s недостижим из некоторой вершины u. Докажем, что u не переполнена. Пусть U, U' - множества вершин, соответственно достижимых и недостижимых из u в остаточной сети. По предположению, . Рассмотрим любую пару вершин , . Ребра (v,w) в остаточной сети нет, иначе бы из u можно было достичь v, а затем по этому ребру w, что противоречит . С другой стороны, если , то остаточная пропускная способность положительна, следовательно, такое ребро должно быть. Значит, , откуда . Теперь просуммируем избыточные потоки во все вершины U:
Первая из двух сумм в правой части равна нулю, потому что для каждой релевантной пары вершин (v,w) в ней есть два слагаемых f(v,w) и f(w,v), сумма которых равна нулю. Вторая же неположительна, поскольку неположительны все её слагаемые. Значит,
С другой стороны, каждое слагаемое в сумме неотрицательно: если v - не источник и не сток, то по третьему свойству предпотоков источника в сумме нет, потому что по предыдущей лемме Из того, что сумма неотрицательных слагаемых неположительна, следует, что все её слагаемые равны нулю. В частности, , то есть u не переполнена, что и требовалось доказать.
Лемма 4. Высота любой вершины всегда меньше 2V. Доказательство. Рассмотрим некую вершину u. Единственный способ изменить высоту вершины - подъём этой вершины. Следовательно, если вершина u никогда не поднималась, её высота осталась такой же, как была после инициализации, то есть 0 или V, и лемма доказана. В противном случае её высота осталась той же, какой стала в результате последнего подъёма. Перед последним подъёмом u была переполнена, значит, в остаточной сети из неё был достижим исток s. После подъёма путь из u в s в остаточной сети сохранился, потому что подъём не влияет на остаточную сеть. Значит, по лемме 6 из предыдущего раздела, , откуда , что и требовалось доказать.
Теорема. За всё время работы алгоритма подъёмов может быть не более . Доказательство. Подъём вершины увеличивает её высоту не менее чем на 1. Начальная высота каждой вершины не меньше 0, конечная, по предыдущей лемме, не больше 2V-1. Уменьшиться высота вершины не может. Значит, каждая вершина может выдержать не более 2V-1 подъёмов. Всего можно поднимать не более V-2 вершин (все, кроме s и t). Отсюда следует утверждение теоремы.
Теорема . За всё время работы алгоритма насыщающих проталкиваний может быть не более . Доказательство. Рассмотрим два последовательных насыщающих проталкивания из u к v. Первое из них исключает ребро (u, v) из остаточной сети, к моменту выполнения второго это ребро вновь появляется. Значит, между этими двумя проталкиваниями выполняется проталкивание из v к u, что является единственным способом восстановить ребро. При первом насыщающем проталкивании , при проталкивании из v к u, наоборот, . Учитывая, что уменьшиться высоты не могут, получаем, что высота увеличилась по крайней мере на 2. Поскольку это происходит между каждыми двумя последовательными насыщающими проталкиваниями из u к v, а высота любой вершины не может увеличиться более чем на 2V-1 (от 0 до 2V-1), количество проталкиваний из u к v не превышает V. Всего имеется 2E пар вершин, подходящих для проталкивания (все рёбра и им обратные). Значит, всего насыщающих проталкиваний не может быть больше, чем 2VE.