Новиков Ф.А. Дискретная математика для программистов (860615), страница 52
Текст из файла (страница 52)
Имеем:div(/, s) = w(f) = F(P+) - F(P-)= F(P+) = J2 f(v, t) - - div(/, t).•Глава 8. Связность278ЛЕММА 3w { f ) ^ДОКАЗАТЕЛЬСТВОЛЕММА 4F{P).w { f ) = F{P+)-F{P~)< F{P+)^F(P).•m a x w ( f ) ^ minC(P).ДОКАЗАТЕЛЬСТВОПОпредыдущей лемме w ( f ) ^ F(P), следовательно, max w ( f ) ^^ m i n F ( P ) . По определению F(P) ^ C(P), следовательно, m i n F ( P ) ^ min C(P).Имеем: m a x w ( f ) ^ mmC(P).•(Форда-Фалкерсона 2 )Максимальный поток в сети равен минимальной пропускной способности разреза, то есть существует поток /*, такой, чтоТЕОРЕМАw { f ) = maxw(f)= nnn С(Р).Пусть / — некоторый максимальный поток. Покажем, что существует разрез Р, такой, что w(f) — С{Р). Рассмотрим граф G', полученный изсети G забыванием ориентации дуг.
Построим множество вершин S следующимобразом:ДОКАЗАТЕЛЬСТВОS =f{u ev\({ui,ui+1)3(s,u)eG'У{щ,т+1)G E ==> f(ui,ui+1)& (ui+i,ui) G E =>• f(ui+1,ui)e (s,u) e G'< С(щ,щ+1)k> 0)},то есть вдоль пути (s, и) дуги в направлении пути пе насыщены, а дуги противнаправления пути имеют положительный поток. Такая цепь (s,u) называетсяаугментальной. Имеем s е S по построению. Следовательно, S Ф 0. ПоложимT: = V \S.
Покажем, что t е Т. Действительно, пусть t е S. Тогда существуетаугментальиая цепь (s,t), обозначим её R. Но тогда можно найти число 6 > 0:. . ....| с(е) - fie) > 0,д: = т1пД(е), г д е Д ( е ) : = < „, .ееяI /(е) > 0,если е ориентировано вдоль R,_если е ориентировано против R.В этом случае можно увеличить величину потока па 6, изменив поток для всехдуг аугментальной цепи:J /(е) 4- 6, если е ориентировано вдоль R,| / ( е ) - <5, если е ориентировано против R.При этом условия потока выполняются: 0 ^ /(е) ^ С(е), div(i;) = 0.12Лестер Рендальф Форд мл. (р. 1927).Дальберт Рей Фалкерсон (1924-1976).2798.4.
Потоки в сетяхТаким образом, поток / увеличен па величину S, что противоречит максимальности потока / . Имеем t G Т и Т Ф 0 . Следовательно, S и Т определяют разрезР = Р+ U P " . В этом разрезе все дуги е+ насыщены ( / ( е + ) = с(е + )), а все дуги е~ пе нагружены (/(е~) = 0), иначе £ можно было бы расширить. Имеем:w ( f ) = F(P+)— F(P~)= С(Р+),таким о б р а з о м , Р+— и с к о м ы й разрез.•8.4.4. Алгоритм нахождения максимального потокаСледующий алгоритм определяет максимальный поток в сети, заданной матрицейпропускных способностей дуг. Этот алгоритм использует идею доказательстватеоремы Форда-Фалкерсопа, а именно, задавшись начальным приближениемпотока, определяем множество вершин S, которые соединены аугмеитальиымицепями с источником s.
Если оказывается, что t G S, то это означает, что поток немаксимальный и его можно увеличить на величину 6. Для определения аугмептальных цепей и одновременного подсчета величины 6 в алгоритме использованавспомогательная структура данных:Р : array [l..p] of records : enum ( - , + ) { «знак», то есть направление дуги }п : 1..р { предшествующая вершина в аугмепталыюй цепи }<5 : real { величина возможного увеличения потока }end recordN : array [l..p] of 0..1 { отметка узла }S : array [l..p] of 0..1 { признак принадлежности вершины множеству S}Алгоритм 8.1 Нахождение максимального потокаВход: сеть G(V,E) с источником s и стоком t, заданная матрица пропускныхспособностей С : array [l..p, l..p] of real.Выход: матрица максимального потока F : array [1 ..р, 1 ..р] of real,for u, v G V doF[u,v]: = 0 { вначале поток пулевой }end forM : { итерация увеличения потока }for v G V doS[v]: = 0; N[v]: = 0; P[v]: = ( + , nil, 0) { инициализация }end forS[s]: = 1; P[s]: = ( + , nil, oo) { так как s G S }repeata: = 0 { признак расширения S }for v € V doif S[v] = 1 к TV [и] = 0 thenfor u G Г(г») doif S[u] = 0 к F[v, u] < C[v,u] thenS[u]: = 1; P[u]: =(+, v, min(PM.<5, C[v, u] - F[v, u])); a: = 1end if280Глава 8.
Связностьend forfor и e r _ 1 ( v ) doif S[u] = 0 & F[u, v] > 0 thenS[u]: = 1; P[u] : =(-,v, min(P[i;].<5, F[u, v]));a: = 1end ifend forN[v]: = 1 { узел v отмечен }end ifend forif S[t] thenx: = t { текущий узел аугментальной цепи }S: = P[t].S { величина изменения потока }while х ф s doif P[x].s = + thenF[P[x].n, x]: = F[P[x].n, x] + <5 { увеличение потока }elseF[x, P[x].n]: = F[x, P[x].n} — <5 { увеличение потока }end ifx : = P[x].n { предыдущий узел аугментальной цепи }end whilegoto Mend ifuntil a — 0В качестве первого приближения берётся нулевой поток, которыйпо определению является допустимым.
В основном цикле, помеченном меткойМ, делается попытка увеличить поток. Для этого в цикле repeat расширяется,пока это возможно, множество S узлов, достижимых из источника s по аугментальпым цепям. При этом, если в множество S попадает сток t, то поток вдольнайденной аугментальной цепи (s,t) немедленно увеличивается на величину 6и начинается новая итерация с целью увеличить поток.
Процесс расширениямножества S в цикле repeat заканчивается, потому что множество узлов конечно, а отмеченные в массиве N узлы повторно не рассматриваются. Еслипроцесс расширения множества S заканчивается и при этом сток t не попадаетв множество 5, то по теореме Форда-Фалкерсопа найденный поток F являетсямаксимальным и работа алгоритма завершается.•ОБОСНОВАНИЕЗАМЕЧАНИЕПриведённый алгоритм не является самым эффективным. Более подробное изложениеизвестных методов можно найти, например, в [8] или в [21].8.5.
Связность в орграфах2818.4.5. Связь между теоремой Менгера и теоремойФорда-ФалкерсонаТеорема Менгера является фундаментальным результатом, который проявляетсяв различных формах (см., например, задачи 8.3.1, 8.3.2, 8.3.3). Теорема ФордаФалкерсона также может быть получена из теоремы Менгера. Далее приведенасхема доказательства теоремы Форда-Фалкерсопа на основе теоремы Менгера.Сначала нужно получить вариант теоремы Менгера в ориентированной рёберной форме: наибольшее число (s,£)-nyTeft, не пересекающихся по дугам, равнонаименьшему числу дуг в (s, £)-разрезе. Это теорема Форда-Фалкерсоиа в томслучае, когда Ve е Е (с(е) = 1).
Действительно, пусть Q — множество дуг измаксимального набора непересекающихся (s,£)-nyTeft. Назначим поток следующим образом: / ( е ) : = 1, если е е Q, и / ( е ) : = 0, если е g Q. Это поток, так какдивергенция в любом узле равна 0 и поток через дугу пе превосходит пропускной способности.
Величина этого потока равна к < d + (s), где к — числодуг, выходящих из s, которые начинают пути из Q. Этот поток максимальный.Действительно, если положить / ( е ) : = а > 0 для некоторой дуги е g Q, то:1) если дуга е входит в узел, входящий в пути из Q, или выходит из такого узла,то нарушается условие потока (дивергенция —а или + а соответственно);2) если вновь назначенные дуги с ненулевыми потоками образуют новый (s,t)~путь, то это противоречит выбору Q.Пусть теперь пропускные способности суть натуральные числа.
Тогда можно провести аналогичные рассуждения для мультиграфов, считая, что вместо однойдуги с пропускной способностью п имеется п дуг с пропускной способностью 1.Если пропускные способности — рациональные числа, то их можно привести кобщему знаменателю и свести задачу к предыдущему случаю.Для вещественных пропускных способностей заключение теоремы можно получить путем перехода к пределу в условиях предыдущего случая.ОТСТУПЛЕНИЕПриведенное в разделе 8.4.3 доказательство теоремы Форда-Фалкерсона конструктивно,из него не только следует заключение о величине максимального потока, но и извлекаетсяспособ нахождения максимального потока. Набросок доказательства в этом подразделенеконструктивен — из него нельзя извлечь алгоритм.8.5.
Связность в орграфахСвязность является одним из немногих понятий, которые пе распространяютсянепосредственно с графов па другие родственные объекты и требуют отдельногоопределения и рассмотрения в каждом случае. В данном разделе рассматриваетсясвязность в орграфах, поскольку именно это понятие чаще всего применяетсяв программировании.282Глава 8. Связность8.5.1.
Сильная, односторонняя и слабая связностьВ неориентированном графе две вершины либо связаны (если существует соединяющая их цепь), либо пе связаны. В ориентированном графе отношениесвязанности узлов несимметрично, а потому определение связности отличается.Пусть G(V, Е) — орграф, гл и v2 — его узлы. Говорят, что два узла гл и v2 сильносвязаны в орграфе G, если существует путь (ориентированная цепь) как из vi вv2, так и из v2 в гл. Говорят, что два узла гл и v2 односторонне связаны в орграфеG, если существует путь либо из гл в v2, либо из v2 в гл. Говорят, что два узлагл и v2 слабо связаны в орграфе G, если они связаны в графе G', полученномиз G забыванием ориентации дуг.
Если все вершины в орграфе сильно (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабо)связным. Сильная связность влечет одностороннюю связность, которая влечетслабую связность. Обратное, разумеется, неверно.Пример На рис. 8.7 показаны диаграммы сильно, односторонне и слабо связных орграфов.8.5.2. Компоненты сильной связностиКомпонента сильной связности (употребляется аббревиатура КСС) орграфа G —это его максимальный сильно связный подграф.Каждый узел орграфа принадлежит только одной КСС.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
