Теорема Форда — Фалкерсона
Теорема Форда — Фалкерсона — теорема о максимальном потоке в графе, тесно связанная с теоремой Менгера. Звучит так: величина максимального потока в графе путей равна величине пропускной способности его минимального разреза. Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин «грузов», перевозимых по всем возможным путям из вершины t в s. Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести «груза» больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей рёбер данного сечения. Утверждение доказано. Отсюда следует, что любой поток меньше или равен величине минимального сечения, а значит и максимальный поток меньше или равен величине минимального сечения. На этой теореме основан алгоритм Форда — Фалкерсона поиска максимального потока в графе, он же является доказательством необходимости данной теоремы, то есть оно является конструктивным. Другое доказательство (через усиление)Усилим теорему Форда — Фалкерсона следующим образом. Будем доказывать для сети G ( V , E ) {displaystyle G(V,E)} с потоком f равносильность сразу трёх следующих фактов: 1° Поток f максимальный 2° Пропускная способность минимального разреза равна величине потока f 3° В графе G {displaystyle G} нет дополняющего пути
3° → 2°. Очевидно, что величина потока f не превышает пропускной способности минимального разреза ( S , T ) {displaystyle (S,T)} . Пусть c ( S , T ) > f {displaystyle c(S,T)>f} . Тогда рассмотрим разрез, где во множестве S {displaystyle S} будут все вершины, кроме t {displaystyle t} . Тогда его пропускная способность не меньше пропускной способности минимального разреза, что, в свою очередь, больше величины потока f. Значит, существует направление ( u , t ) {displaystyle (u,t)} из S {displaystyle S} в T {displaystyle T} , что f ( u , t ) < c ( u , t ) {displaystyle f(u,t)<c(u,t)} . Теперь возьмём все такие u {displaystyle u} и перенесём их в T {displaystyle T} . Рассмотрев получившийся разрез, заметим, что его пропускная способность тоже больше величины потока. Снова увеличиваем множество T {displaystyle T} и делаем так до тех пор, пока в множестве S {displaystyle S} не останется только вершина s {displaystyle s} . Она же будет первой вершиной в пути, который мы создаём. Теперь смотрим какую пару мы выбрали прошлым ходом. Пусть это пара ( s , u ) {displaystyle (s,u)} . Тогда к пути добавляем вершину u {displaystyle u} . Далее смотрим в паре с какой вершиной была на первом месте вершина u {displaystyle u} . Пусть это ( u , v ) {displaystyle (u,v)} . Тогда далее к пути добавляем вершину v {displaystyle v} . Делаем так до тех пор, пока не дойдём до вершины t {displaystyle t} . Однако по построению этот путь является остаточным, что противоречит предположению. 2° → 1°. Как уже говорилось, очевидно, что величина любого потока не превышает пропускной способности минимального разреза, а величина нашего потока f {displaystyle f} равна. Тогда величина потока f {displaystyle f} не меньше величины любого другого потока в нашей сети, то есть поток f {displaystyle f} максимальный. Это доказательство хорошо тем, что не использует сложный алгоритм нахождения максимального потока в произвольной транспортной сети. ПримерСправа дана сеть с 6 вершинами V = { s , o , p , q , r , t } {displaystyle V={s,o,p,q,r,t}} , и суммарный поток от истока s {displaystyle s} к стоку t {displaystyle t} равен 5. Этот поток является максимальным для данной сети. В данной сети возможны 2 минимальных разреза: |
