Рис. 27.10 27.12 Задача о выходе. Начальные точки чёрные, остальные - белые, (а) Выход есть (выделены пути, его обеспечивающие). (Ь) Выхода нет.

Задачи

27-1 Задача о выходе

Имеется, граф вершины которого образуют решётку из га строк и га столбцов (рис. 27.12). Обозначим черезвершину на пере-

сечении г-го столбца и j-ой строки. Все вершины такой решётки (га X га grid), не считая граничных [г = 1, г = га, j = 1 или j = га) имеют четырёх соседей. В задаче о выходе (escape problem) требуется выяснить, существуют ли т попарно непересекающихся (не имеющих общих вершин) путей от данных т га2 начальных точек решётки (х\, у\), (х2, у2),..., (хт, ут) к т различным граничным точкам. Например, для задачи о выходе рис. 27.12(a) ответ положителен, а для рис. 27.12 (Ь) - отрицателен.

(a)Рассмотрим сеть, в которой пропускные способности имеют не только рёбра, но и вершины. Это означает, что поток, входящий в данную вершину, не может превосходить некоторого числа (пропускной способности вершины). Покажите, что задача о максимальном потоке в такой сети сводится к обычной задаче о максимальном потоке для сети несколько большего размера.

(b)Укажите алгоритм, решающий задачу о выходе. Чему равно время его работы?

27-2 Минимальное покрытие путями

Покрытием путями (path cover) ориентированного графа G = (V, Е) назовём множество путей Р с таким свойством: каждая вершина из V принадлежит ровно одному пути из Р. Пути могут начинаться и заканчиваться где угодно, и иметь любую длину, в том числе нулевую. Покрытие наименьшим возможным числом путей назовём минимальным покрытием путями (minimum path cover).

(a)Постройте эффективный алгоритм, находящий минимальное покрытие путями графа G = (V,E). (Указание. Пусть V = {1, 2,..., га}. Построим граф G = (V, Е), где

V = {х0, xi,..., хп} U {у0, у!,..., уп},

Е= {{x0,xl)\iev}\j{{yl,y0)\i е V}u{(Xl,yj}\(i,j) е Е},

и решим для этого графа задачу о максимальном потоке.)

(b)Правильно ли работает этот алгоритм, если у графа есть циклы? Ответ объясните.

27-3 Эксперименты в космосе

Институт космических исследований планирует серию Е = {Е\, Е2, , Ет} экспериментов в космосе. За результат эксперимента Е{ спонсоры выплачивают рг- долларов. Для этих экспериментов требуются приборы из множества / = {1\, 12, , 1п}] Для проведения эксперимента Ej необходимо множество Rj С / прибо-

ров. Стоимость доставки прибора 1к составляет ск долларов. Требуется выяснить, какие эксперименты следует проводить, чтобы прибыль (доход от экспериментов минус стоимость доставки нужных приборов) была максимальной.

Для решения этой задачи рассмотрим сеть G с истоком s, стоком t, вершинами 1\, 12, , 1п и Е\, Е2, , Ет. Сеть имеет также рёбра (s, 1) пропускной способности Ck (для всех к = 1,2,... , га); (Ej, t) пропускной способности pj] (для всех j = 1, 2,... , то); (Ik, Ej) бесконечной пропускной способности, если 1к £ Ej (для к = 1, 2,... , га и j = 1,2,... ,то).

(a)Рассмотрим разрез (S, Т) с конечной пропускной способностью для построенной сети. Пусть Ej £ Т. Покажите, что 1к £ Т для всех Ik £ Rj.

(b)Как, зная все pj и пропускную способность минимального разреза сети G, найти максимальную прибыль от экспериментов?

(c)Постройте алгоритм, определяющий, какие эксперименты следует проводить [для получения наибольшей прибыли] и какие для этого нужны приборы. Оцените время его работы как функ-

27-4 Максимальный поток в изменённой сети

Предположим, нам известен максимальный поток в сети G = (V,E), в которой все пропускные способности рёбер - целые числа.

(a)Пусть пропускная способность некоторого ребра (и,v) £ Е увеличилась на единицу. Приведите алгоритм, находящий максимальный поток (для изменённой сети) за время 0(V + Е).

(b)Пусть пропускная способность некоторого ребра (и,v) £ Е уменьшилась на единицу. Приведите алгоритм, находящий максимальный поток (для изменённой сети) за время 0(V + Е).

27-5 Масштабирование

Рассмотрим сеть G = (V, Е) с истоком s и стоком t. Пусть пропускная способность с(и, v) любого ребра (и, v) £ Е - целое число. Положим С = max с(и, v).

(a)Докажите, что пропускная способность минимального разреза сети G не превосходит С£.

(b)Докажите, что при любом заданном К можно за время 0(E) найти дополняющий путь с пропускной способностью не меньше К или установить, что такого пути нет.

Алгоритм Max-Flow-By-Scaling вычисляет максимальный поток в сети G с помощью масштабирования. Это одна из реализаций метода Форда-Фалкерсона.

\textsc{Max-Flow-By-Scaling}($G,s,t$)

1$C\leftarrow\max\limits {(u,v)\in E}{c(u,v)}$

2сделать поток $f$ нулевым

m

цию от то, га и г = 2 \Rj

3 = 1

(u,v)eE

3$K\leftarrow 2~{\lfloor\log C\rfloor>$

4while $K\ge 1$

5do while существует дополняющий путь $p$ пропускной способности не менз

6do дополнить $f$ вдоль $р$

7$K\leftarrow К/2$

8return $f$

(c)Докажите, что программа Max-Flow-By-Scaling вычисляет максимальный поток.

(d)Докажите, что в момент проверки условия цикла в строке 4 пропускная способность минимального разреза остаточной сети не превосходит 2К\Е\.

(e)Докажите, что цикл в строках 5-6 выполняется О(Е) раз для любого значения К.

(f)Докажите, что время работы алгоритма Max-Flow-By-Scaling равно О(Е2 log С).

27-6

Двусторонние границы

Рассмотрим сеть G = (V,E). Предположим, что ограничения на поток в этой сети двусторонние. Именно, для потока / и для каждого ребра (и, v) мы требуем, чтобы b(u, v) f(u, v) с(и, v), где с и Ь - заданные функции на рёбрах. (Возможно, что эти ограничения противоречивы - тогда потока не существует.)

(a)Пусть / - поток в сети G. Докажите, что / c(S,T) - b(T,S) для любого разреза (S,T).

(b)Пусть в сети G максимальный поток существует. Докажите, что его значение равно минимальной (по всем разрезам (S,T)) разности c(S, Т) - b(T, S).

Рассмотрим сеть G = (V, Е) с двусторонними границами с истоком s и стоком t. Обозначим верхнюю и нижнюю границы cub соответственно. Построим обычную сеть G = (V, Е) с верхней границей (пропускной способностью) с, истоком s и стоком t, положив

V = V U {s,t}

Е = Е U {(s, v)\v £ V} U {(и, t)\u £ V} U {(s, t), (t, s)}.

Для рёбер (u,v) G E положим c(u,v) = c(u,v) - b(u,v); для всех вершин и G V положим c(s,u) = b(V,u), а также c(u,t) = b(u,V). Кроме того, положим c(s,t) = c(t,s) = оо.

(c)Докажите, что поток в сети G существует тогда и только тогда, когда для максимального потока в сети G все рёбра, входящие в t, насыщены.

(d)Постройте алгоритм, который выясняет, существует ли поток в данной сети с двусторонними границами, и если да, то находит этот поток. Оцените время работы этого алгоритма.

Замечания