лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

8.5.4. Алгоритм нахождения максимального потока

Следующий алгоритм определяет максимальный поток в сети, заданной матрицей пропускных способностей дуг. Этот алгоритм использует ту же идею доказательства теоремы Форда и Фалкерсона, а именно, задавшись начальным приближением потока, определяется множество вершин S, которые соединены аугмен-тальными цепями с источником s. Если оказывается, что t e S, то это означает, что поток не максимальный и его можно увеличить на величину 8. Для определения аугментальных цепей и одновременного подсчета величины 8 в алгоритме использована вспомогательная структура данных:

Р • array [l..p] of record

s : enum (—,+) { «знак», то есть направление дуги }

п : 1..р { предшествующая вершина в аугментальной цепи }

S : real { величина возможного увеличения потока } end record

Алгоритм 8.1. Нахождение максимального потока

Вход: сеть G(V, Е) с источником s и стоком t, заданная матрица пропускных способностей С : array [l..p, l..p] of real.

Выход: матрица максимального потока F : array [l..p, l..p] of real, for u, v € V do

p[_Uj _v]: = 0{ вначале поток нулевой } end for

M : { итерация увеличения потока } for v е V do

S{v] : = Q;N[v}: = 0;P[v] :=(,,) { инициализация } end for

S[s]: = 1; P[s]: =(+, s, oo){ так как s € S } repeat

a: = 0{ признак расширения 5 } for и е У do

if SM = l&N[v] =0then for u e I» do

if S[u] = 0&F[v,u} < C[v,u] then

S[u]: = 1; P[u]: =(+, v, mm(P[v}.5, C[v, u] - F[v, u])); a : = 1 end if end for forueT-¹^) do

if 5[и] =OkF[u,v] >0then

S[u]: = 1; P[u]: =(-,v, mm(P[v].S, F[u, v})); a: = 1 end if end for N[v]: = 1 end if end for if S[t] then

x:'=i;5:*=P[ti.S while x ^ s do if P[x].s=* + then

F[P[x}'.n,x]: = F[P[x].n, x}+6 else

F[x,P[x].n}: = F[x,P(x].n}-5 end if x: = P[x].n end while goto M end if until a = 0

обоснование

В качестве первого приближения берется нулевой поток, который по опре, нию является допустимым. В основном цикле, помеченном меткой М, дел ся попытка увеличить поток. Для этого в цикле repeat расширяется, пока э возможно, множество S вершин, достижимых из вершины s по аугментальнь цепям. При этом, если в множество 5 попадает вершина t, то поток вдоль най денной аугментальной цепи (s,t) немедленно увеличивается на величину 6, и начинается новая итерация с целью увеличить поток. Процесс расширения мно жества S в цикле repeat заканчивается, потому что множество вершин конечно, а отмеченные в массиве N вершины повторно не рассматриваются. Если про цесс расширения множества S заканчивается и при этом вершина t не попадает в множество S, то по теореме Форда и Фалкерсона найденный поток F является максимальным и работа алгоритма завершается. П

ЗАМЕЧАНИЕ

Приведенный алгоритм не является самым эффективным. Более подробное изложение известных методов можно найти, например, в [14J или в [11].

Связь между теоремой Менгера и теоремой Форда и Фалкерсона

Теорема Менгера является фундаментальным результатом, который проявляется в различных формах (см., например, задачи 8.4.1, 8.4.2, 8.4.3). Теорема Форда и Фалкерсона также может быть получена из теоремы Менгера. Далее приведена схема неконструктивного доказательства теоремы Форда и Фалкерсона на основе теоремы Менгера. Сначала нужно получить вариант теоремы Менгера в ориентированной реберной форме: наибольшее число (s,t)-путей, непересекающихся по дугам, равно наименьшему числу дуг в (s, £)-разрезе. Это теорема Форда и Фалкерсона в том случае, когда Ve е Е С(е) = 1. Действительно, пусть Q -множество дуг из максимального набора непересекающихся (s,t)-путей. Назначим f(e): = 1, если е е Q, и f(e): = 0, если е £ Q. Это поток, так как дивергенция в любой вершине равна 0 и поток через дугу не превосходит пропускной способности. Величина этого потока равна k ^ d⁺(s), где k — число дуг, выходящих из s, которые начинают пути из Q. Этот поток максимальный. Действительно, если положить f(e]: = о > 0 для е & Q, то

1. если дуга е входит в вершину, входящую в пути из Q, или выходит из такой вершины, то нарушается условие потока (дивергенция -а или +а, соответ ственно);

2. если вновь назначенные дуги с ненулевыми потоками образуют новый (s,t)- путь, то это противоречит выбору Q.

Пусть теперь пропускные способности суть натуральные числа. Тогда можно провести аналогичные рассуждения для мультиграфов, считая, что вместо одной ду-и с пропускной способностью п имеется п дуг с пропускной способностью 1. Если пропускные способности — рациональные числа, то их можно привести к общему знаменателю и свести задачу к предыдущему случаю.

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

ОТСТУПЛЕНИЕ -

Приведенное в разделе 8.5.3 доказательство теоремы Форда и Фалкерсона конструктивно, из него не только следует заключение о величине максимального потока, но и извлекается способ нахождения максимального потока.

Связность в орграфах

Связность является одним из немногих понятий, которые не распространяются непосредственно с графов на другие родственные объекты и требуют отдельного определения и рассмотрения.

Сильная, односторонняя и слабая связность

В неориентированном графе две вершины либо связаны (если существует соединяющая их цепь), либо не связаны. В ориентированном графе отношение связанности вершин несимметрично, а потому определение связности отличается.

Пусть G(V, Е} — орграф, vi и v₂ — его вершины. Говорят, что две вершины v\ и V2 сильно связаны в орграфе G, если существует путь (ориентированная цепь) из v\ в г>₂ и из V2 в vi. Говорят, что две вершины v\ и v₂ односторонне связаны в орграфе G, если существует путь либо из v_: в v₂, либо из v₂ в v\. Говорят, что две вершины v\ и v₂ слабо связаны в орграфе G, если они связаны в графе G', полученном из G отменой ориентации ребер. Если все вершины в орграфе сильно (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабо) связным. Сильная связность влечет одностороннюю связность, которая влечет слабую связность. Обратное неверно.

Пример на рис. 8.6. показаны диаграммы сильно, одностороннее и слабо связанных орграфов.

рис. 8.6.Сильная (слева), односторонняя (в центре) и слабая (справа) связность

. Компоненты сильной связности

Компоненты сильной связности (КСС) орграфа G — это его максимальные сильно связные подграфы.

Каждая вершина орграфа принадлежит только одной КСС. Если вершина не связана с другими, то считаем, что она сама образует КСС. Конденсацией G* орграфа G (или графом Герца, или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой КСС орграфа G.

Пример

На рис. 8.7 показаны диаграммы орграфа и его конденсации.

Рис. 8.7. Оргаф (слева) и его фактор-граф (справа)

Содержание