Заметим, что расстояния ограничены сверху значением V (кратчайший путь не проходит дважды через одну вершину), так что общее число таких чередований есть 0(V), как мы и обещали.

Подсчитаем теперь общее время работы алгоритма Эдмондса-Карпа. Каждая итерация требует времени О(Е), их будет 0(VE), поэтому всего будет 0(VE2).

В разделе 27.4 мы расскажем о другом подходе к поиску максимального потока, который позволяет сделать это за 0(V2E). Его усовершенствование позволяет ещё уменьшить время работы, получив оценку 0(V3) (раздел 27.5).

Упражнения

27.2-1

Найдите поток через разрез ({s, v2, V4}, {v\, v3, t}) на рис. 27.1 b). Чему равна пропускная способность этого разреза? 27.2-2

Проследите за выполнением лгоритма Эдмондса-Карпа для сети рис. 27.1 (а). 27.2-3

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

27.2-4

Докажите, что для любых вершин и и v, любого потока / и пропускной способности с выполнено Cf(u, v)-\-cj(v, и) = с(и, v)-\-c(v, и). 27.2-5

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

27.2-6

Рассмотрим сеть с несколькими истоками и стоками, в которой каждый исток s4- производит ровно рг- единиц потока, а каждый сток tj потребляет ровно qj единиц, т.е. f(si, V) = pi и f(V, tj) = qj. При этом 2~}гРг = 2~}j Qj- Как узнать, возможен ли поток с такими ограничениями, сведя эту задачу к задаче о максимальном потоке?

27.2-7

Докажите лемму 27.3. 27.2-8

Покажите, что при поиске максимального потока в сети G = (V, Е) достаточно сделать \Е\ шагов, если только правильно выбрать дополняющие пути на каждом шаге. (Указание. Считая, что максимальный поток известен, покажите, как следует выбирать пути.)

27.2-9

Назовём запасом связности (edge connectivity) неориентирован-

ного графа минимальное число рёбер, которое необходимо удалить, чтобы сделать граф несвязным. Например, связность дерева равна единице, а связность цикла равна 2.

Как узнать связность графа с помощью программы поиска максимального потока? Её следует применять не более чем к \V\ сетям, каждая из которых содержит 0(V) вершин и О(Е) рёбер.

27.2-10

Предположим, что для каждого ребра (и, v) сети обратное ему ребро (v, и) также входит в сеть Покажите, что алгоритм Эдмондса-Карпа требует не более \V\ \Е\/4 итераций. (Указание: для каждого ребра (и, v) проследите, как меняются S(s,u) и S(v,t) между теми моментами, когда ребро (и, v) критическое.)

27.3. Максимальное паросочетание в двудольном графе

Некоторые комбинаторные задачи (например, задача о сети с несколькими истоками и стоками из раздела 27.1) сводятся к разобранной нами задаче о максимальном потоке. Другой пример такого рода - задача о максимальном паросочетании в двудольном графе (см. раздел 5.4). В этом разделе покажем, как с помощью метода Форда-Фалкерсона можно решить эту задачу для графа G = (V, Е) за время 0(VE).

Задача о максимальном паросочетании

Пусть G = (V, Е) - неориентированный граф. Паросочетанием (matching) назовем множество рёбер М С Е, не имеющих общих концов (каждая вершина v £ V является концом максимум одного ребра из М). Будем говорить, что вершина v £ V входит в паросочетание М (is matched), если в М есть ребро с концом v; в противном случае v свободна (is unmatched). Максимальное паросочетание (maximum matching) - это паросочетание М, содержащее максимально возможное число рёбер (\М\ М для любого паросочетания М). Пример паросочетания приведён на рис. 27.8.

В этом разделе мы будем рассматривать паросочетания лишь в двудольных графах. Мы предполагаем, что множество V разбито на два непересекающихся подмножества L и R, и любое ребро из Е соединяет некоторую вершину из L с некоторой вершиной из R.

Для задачи о максимальном паросочетании в двудольном графе есть несколько метафор. Вот наиболее известная: L - женихи, R - невесты, наличие ребра (и, v) означает, что и и v согласны стать супругами. Максимальное паросочетание доставляет ЗАГСу

Рис. 27.8 27.8 Двудольный граф. Множество вершин разбито на две части L и R. (а) Паросочетание из двух рёбер. (Ь) Максимальное паросочетание состоит из трёх элементов.

Рис. 27.9 27.9 Сеть, соответствующая двудольному графу, (а) Двудольный граф рис. 27.8. Выделенные рёбра образуют максимальное паросочетание. (Ь) Соответствующая сеть G и максимальный поток в ней. Пропускная способность любого ребра равна единице; поток по выделенным рёбрам равен единице, по остальным - нулю. Выделенные рёбра, соединяющие вершины из L с вершинами из R, соответствуют максимальному паросочетанию в двудольном графе.

больше всего работы.

Поиск максимального паросочетания в двудольном графе Мы будем использовать метод Форда-Фалкерсона для поиска максимального паросочетания в двудольном графе G = (V, Е) за полиномиальное от \V\ и \Е\ время. Для этого рассмотрим сеть G = (V,E), соответствующую двудольному графу G (рис. 27.9). Эта сеть строится так: добавяляются две новые вершины, которые будут истоком (s) и стоком (t): V = V U {s,t}. Множество (направленных) рёбер сети G таково:

Е ={(s,u)\u £ L} U

U {(и, v)\u е L, v е R, (и, v) £ Е} и

{{v,t)\veR}.

(напомним, что через L и R обозначаются доли графа). Будем считать, что пропускная способность каждого ребра равна единице.

Следующая лемма устанавливает соответствие между потоками в G и паросочетаниями в G - но прежде дадим ещё одно определение.

Поток / в сети G = (V, Е) называется целочисленным (integer-valued), если все значения f(u,v) - целые. Лемма 27.10

Пусть G = (V, Е) - двудольный граф с долями L и R, и G = (V, Е) - соответствующая сеть. Пусть М - паросочетание в G. Тогда существует целочисленный поток в G со значением / = \М\. Обратно, если / - целочисленный поток в G, то в G найдется паросочетание из / элементов.

Доказательство

Сначала докажем, что паросочетание порождает поток, задав поток / следующим образом. Если (и, v) £ М, то f(s, и) = f(u, v) = f(v,t) = 1 и f(u,s) = f(v,u) = f(t,v) = -1. Для всех остальных рёбер (и, v) £ Е положим f(u, v) = 0. Неформально говоря, каждое ребро (и, v) £ М соответствует единичному потоку по пути s -> и -> v -> t. Никакие два таких пути не содержат общих вершин (кроме истока и стока) или рёбер.

Чтобы проверить, что / является потоком, достаточно заметить, что / представим в виде суммы потоков по этим путям. Поток через разрез (LL){s}, RL){t}) равен \М\, поэтому по лемме 27.5 значение потока / равно \М\.