Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями — различия между версиями
Nikitaevg (обсуждение | вклад) м (→Теоремы: Опечатка в доказательстве) |
|||
Строка 65: | Строка 65: | ||
|statement=Число итераций [[Схема алгоритма Диница|алгоритма Диница]] в сети <tex>N</tex> (<tex>s</tex> — исток, <tex>t</tex> — сток) с целочисленными пропускными способностями — <tex>O(\sqrt{P})</tex>. | |statement=Число итераций [[Схема алгоритма Диница|алгоритма Диница]] в сети <tex>N</tex> (<tex>s</tex> — исток, <tex>t</tex> — сток) с целочисленными пропускными способностями — <tex>O(\sqrt{P})</tex>. | ||
|proof= | |proof= | ||
− | Пусть <tex>F</tex> - максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на 1. Если <tex>F > \sqrt{P}</tex>, рассмотрим последнюю фазу, на момент начала выполнения которой поток в сети был меньше, чем <tex>F - \sqrt{P}</tex>. После этого потребуется не больше <tex>\sqrt{P}</tex> фаз, чтобы найти максимальный поток. На предыдущей фазе поток (<tex>f</tex>) в <tex>N</tex> был не больше <tex>F-\sqrt{P}</tex>, таким образом <tex>F-|f| \ | + | Пусть <tex>F</tex> - максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на 1. Если <tex>F > \sqrt{P}</tex>, рассмотрим последнюю фазу, на момент начала выполнения которой поток в сети был меньше, чем <tex>F - \sqrt{P}</tex>. После этого потребуется не больше <tex>\sqrt{P}</tex> фаз, чтобы найти максимальный поток. На предыдущей фазе поток (<tex>f</tex>) в <tex>N</tex> был не больше <tex>F-\sqrt{P}</tex>, таким образом <tex>F-|f| \geqslant \sqrt{P}</tex>. |
<tex>N(f)</tex> - сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex>, и получить оценку длины <tex>l</tex> слоистой сети: | <tex>N(f)</tex> - сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex>, и получить оценку длины <tex>l</tex> слоистой сети: |
Версия 13:39, 25 декабря 2016
Определения
Определение: |
Пусть сеть с целочисленными пропускными способностями.
Обозначим и , как максимальная пропускная способность ребра и максимальный поток соответственно.. . - потенциал вершины . Тогда общий потенциал выражается формулой: .Остаточную сеть обозначим . Обозначим длину слоистой сети - как длину кратчайшего пути в . | -
Теоремы
Лемма (1): |
Пусть - расстояние между и в сети с текущим потоком, равным 0, и максимальным потоком, равным .
Тогда |
Доказательство: |
Пусть сохранения потока, если обозначить как любой допустимый поток, то единиц потока должно проходить через . Но суммарное количество потока, которое может проходить через любую вершину не превосходит ее потенциала. Отсюда, если обозначить как общий потенциал вершин из , то мы имеем: - расстояние между и , а - набор вершин, удаленных от на . - разъединяющее множество узлов: при его удалении исчезают все пути из в . Следуя закону
для любого допустимого потока . В частности, , таким образом получаем:и лемма доказана. |
Лемма (2): |
Пусть - сеть, а - допустимый поток в этой сети. Тогда общий потенциал в остаточной сети равен общему потенциалу . |
Доказательство: |
Пусть - функция пропускных способностей в , а - потенциал, множество входящих ребер и множество выходящих ребер вершины из .Достаточно доказать, что . Ребру из соответствуют ребро из с пропускной способностью , и ребро из с пропускной способностью . Аналогично, ребру из соответствуют ребра из с пропускной способностью и с пропускной способностью . Используя закон сохранения потока, нетрудно проверить, что
и что и требовалось доказать. |
Теорема (Первая теорема Карзанова): |
Число итераций алгоритма Диница в сети ( — исток, — сток) с целочисленными пропускными способностями — . |
Доказательство: |
Пусть - максимальный поток в сети . Теорема верна для , так как после каждой фазы поток увеличивается хотя бы на 1. Если , рассмотрим последнюю фазу, на момент начала выполнения которой поток в сети был меньше, чем . После этого потребуется не больше фаз, чтобы найти максимальный поток. На предыдущей фазе поток ( ) в был не больше , таким образом .- сеть с максимальным потоком и потенциалом (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между и в , и получить оценку длины слоистой сети: Так как каждая фаза увеличивает длину слоистой сети минимум на один, то осуществляется не больше фаз. Таким образом происходит не более фаз. |
Лемма (3): |
Пусть в сети параллельных ребер. - поток в , а - максимальный поток в . Тогда расстояние между и в таково: . нет |
Доказательство: |
Обозначим Таким образом как набор вершин на расстоянии от . Множества и определяют разрез . Пропускная способность этого разреза не больше , так как все ребра между и также являются ребрами между и и не более чем двумя параллельными ребрами, исходящими из какой-то вершины в остаточной сети. По теореме о максимальном потоке/минимальном разрезе, . ограничен наименьшим из . Но эта величина максимальна, когда для , таким образом . Выражая , получаем нужное. |
Теорема (Вторая теорема Карзанова): |
Число итераций алгоритма Диница с целочисленными пропускными способностями - . |
Доказательство: |
Если , то теорема очевидна. Положим, что , и рассотрим последнюю фазу, в которой поток не превышает . В этот момент осталось не более фаз, и - сеть с максимальным потоком . Мы можем применить Лемму(2), чтобы оценить длину слоистой сети, и, соответственно, количество выполненных фаз:
Таким образом, прошло . фаз, и фаз осталось. Теорема доказана. |