Дискретная математика (998286), страница 40
Текст из файла (страница 40)
Построим множество вершин Я следующим образом: Я: =(и Е Ъ ! Л (з, и) Е С' У(и;, иг+г) Е (з, и).Е С' (ичиг»г) е Е =» г(иииг+г) < С(иниг+г) бс (иг+г,и,) Е Е =» Диг+г,и;) > 0), то есть вдоль пути (з, и) дуги в направлении путя не насыщены, а дуги против направления пути имеют положительный поток. Такая 'цепь (з,и) называется аугиентальной.
Имеем з е Я по построению. Следовательно, Я ф кз. Положим Т: =(~ '1 Я. Покажем, что 1 Е Т. Действительно, пусть | Е Я. Тогда существует аугментальная цепь (з,г), обозначим ее В. Но тогда можно найти число б: (с(е) — У(е) > О, если е ориентировано вдоль В, »ея ' (у(е) > О, если е ориентировано против В.
В этом случае можно увеличить величину потока на б,изменив поток для всех дуг аргументальной цепи: ( Г'(е) + б„если е ориентировано вдоль В, г(е): = '(г'(е) — б, если е ориентировано против В, При этом условия потока выполняются: О < б(е) < С(е), д(ч(о) = О. Таким образом, поток у увеличен на величину б, что противоречит максималь- ности потока б". Имеем 1 Е Т и Т ф а. Следовательно, Я и Т определяют разрез Р = Р+ 0 Р .
В этом разрезе все. дуги е+ насыщены (у(е+) = С(е+)), а все дуги е не нагружены ®е ) = 0), иначе Я можно было бы расширить. Имеем: шЯ = Р(Р+) — Р(Р ) = С(Р+), таким образом, Р+ — искомый разрез. П 8.5.4. Алгоритм нахождения максимального потока Следующий алгоритм определяет максимальный поток в сети, заданной матрицей пропускных способностей дуг. Этот алгоритм использует ту же идею доказательства теоремы Форда и Фалкерсона, а нмеггно, задавшись начальным приближением потока, определяется множество вершин Я, которые соединены аугментзльными цепями с источником з. Если оказывается, что Г Е Я, то это означает, что поток не максимальный и его можно увеличить на величину б.
Для определения аугментальных цепей и одновременного подсчета величины б в алгоритме использована вспомогательная структура данных: Р: аггау (1..р) оГ гесогд з: епшп (-, +) (»знак», то есть направление дуги ) и: 1..р ( предшествующая вершина в зугмептальиой цепи ) б: геа! ( величина возможного увеличения потока ) епд гесоп$ 2г4 Глава 8.
Связность Алгоритм 8.1. Нахождение максимального потока Вход: сеть С(г', Е) с источником в и стоком С, заданная матрица пропускных способностей С: аппу [1,р, 1..р] ог геа1. Выход: матрица максимального потока Р; атау [1..р, 1..р] рг геа!. Сот и, е е Ъ' Йо Р[и, е]: = 0( вначале поток нулевой ) епд гог М; ( итерация увеличения потока ) 1оген в'Йо 8[е]:=О;Ж[е] . "=О;Р[е]: =(,,) ( инициализация ) епд гог Я[в]: =1;Р[в]: =(+,в,со)( так как в ~ Я ) гереаС а: = 0( признак расширения Я ) гог е е Св с]о й'8[о] = 1бвФ[е] = 0 йеп Уогие Г(е) бо Сг Я[и] = Обв Р[е, и] < С[с, и] йеп Я[и]: = 1; Р[и]: =(+, е, ппп(Р[и].б, С[в, и] — Р[о, и]) ); а: = 1 еаза Сг епп гог гог и и Г '(е) до )г Я[и] = Обв Р[и,е] > 0 СЬев ]]:=; [.]:=(-... ( []б,Р] .]И .= епа й епс) (ог Ф[е]:=1 епа й епб гог 11 Я[С! йеп х:=С; б:=Р[С].б веЬйе х ф в сСо 1г" Р]х].в =+ йеп Р[Р[х].
и, х] . "= Р[Р[х]. и, х] + б е)ве Р[х, Р[х].п]: = Р]х, Р[х].п] — б еп4 Ьв х: = Р]х].п епд веЬйе яого М епб Ст нпгй а = 0 ОБОСНОВАНИЕ В качестве первого приближения берется нулевой поток, который по определению является допустимым. В основном цикле, помеченном меткой М, делается понытка увеличить поток. Для этого в цикле гереаС расширяется, пока это возможно, множество Я верший достижимых из вершины в по аугментальным 225 8.5. Потоки в сетях цепям. При этом, если в множество Я попадает вершина й то поток вдоль найденной аугментальной цепи (в,с) немедленно увеличивается на величину б, и начинается новая итерация с целью увеличить поток.
Процесс расширения множества Я в цикле гереа1 заканчивается, потому что множество вершин конечно, а отмеченные в массиве Ф вершины повторно не рассматриваются. Если процесс расширения множества 5 заканчивается и при этом вершина с не попадает в множество Я, то по теореме Форда и Фалкерсона найденный поток г' является максимальным и работа алгоритма завершается. П ЗАМЕЧАНИЕ Приведенный алгоритм не является самым эффективным, Более подробное изложение известных методов можно найти, например, в (14) или в [1Ц. 8.5.5. Связь между теоремой Менгера и теоремой Форда и Фалкерсона Теорема Менгера является фундаментальным результатом, который проявляется в различных формах (см., например, задачи 8А,1, 8А.2, 8А.З).
Теорема Форда и Фалкерсона также может быть получена из теоремы Менгера. Далее приведена схема неконструктивного доказательства теоремы Форда и Фалкерсона на основе теоремы Менгера. Сначала нужно получить вариант теоремы Менгера в ориентированной реберной форме; наибольшее число (в,1)-путей, непересекающихся по дугам, равно наименьшему числу дуг в (в,с)-разрезе. Это теорема Форда и Фалкерсона в том случае, когда э'е ц Е С(е) = 1. Действительно, пусть Я— множество дуг из максимального набора непересекающихся (в,1)-путей. Назначим г(е): = 1, если е е сг, и г(е): = О, если е к сг.
это поток, так как дивергенция в любой вершине равна О и поток через дугу не превосходит пропускной способности. Величина этого потока равна й < а+(в), где й — число дуг, выходящих из в, которые начинают пути из ф Этот поток максимальный. Действительно, если положить Де): = а > О для е К сГ, то 1. если дуга е входит в вершину, входящую в пути из ф или выходит из такой вершины, то нарушается условие потока (дивергенция — а или +а, соответственно); 2. если вновь назначенные дуги с ненулевыми потоками образуют новый (в, 1)- путь„то это противоречит выбору ф.
Пусть теперь пропускные способности суть натуральные числа. Тогда можно провести аналогичные рассуждения для мультиграфов, считая, что вместо одной дуги с пропускной способностью и имеется и дуг с пропускной способностью 1. Если пропускные способности — рациональные числа, то их можно привести к общему знаменателю и свести задачу к предыдущему случаю. Для вещественных пропускных способностей заключение теоремы можно получить путем перехода к пределу в условиях предыдущего случая. Глава 8.
Связность ОТСТУПЛЕНИЕ Приведенное в разделе 8.5.3 доказательство теоремы Форда н Фалкерсона конструктивно, нз него не только следует заключение о величине максимального потока, но н извлекается способ нахождения максимального потока. 8.6. Связность в орграфах Связность является одним из немногих понятий, которые не распространяются непосредственно с графов на другие родственные объекты и требуют отдельного определения и рассмотрения, 8.6.1.
Сильная, односторонняя и слабая связность В неориентированном графе две вершины либо связаны (если существует соединяющая их цепь), либо не связаны. В ориентированном графе отношение связанности вершин несимметрично, а потому определение связности отличается. Пусть С((т, Е) — ' орграф, ог и сз — его вершины. Говорят, что две вершины ст и сз сильно связаны в орграфе С, если существует путь (ориентированная цепь) из ст в оз и из иа в от. Говорят, что две вершины от и оз односторонне связаны в орграфе С, если существует путь либо из о, в огь либо из оз в о,.
Говорят, что две вершины от и ьа слабо связаны в орграфе С, если они связаны в графе С', полученном из О отменой ориентации ребер. Если все вершины в орграфе сильно (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабо) связным. Сильная связность влечет одностороннюю связность, которая влечет слабую связность. Обратное неверно. Пример На рис. 8.6 показаны диаграммы сильно, односторонне и слабо связных орграфов. Рнс. 8.8. Сильная (слева), односторонняя (в центре) и слабая (спрааа) связность 8.6.2. Компоненты сильной связности Компоненты сильной связности (КСС) орграфа С вЂ” зто его максимальные сильно связные подграфы. В.б. Связность в орграфах Каждая вершина орграфа принадлежит только одной КСС.
Если вершина не связана с другими, то считаем, что она сама образует КСС. Конденсацией С орграфа С (или графом Герца, или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой КСС орграфа С. Пример На рис. 8.7 показаны диаграммы орграфа и его конденсации. Рис. 8Л.
Оргаф (слева) и его фактор-граф (справа) 8.6.3. Выделение компонент сильной связности Следующий алгоритм, основанный на методе поиска в глубину, находит все компоненты сильной связности орграфа. Алгоритм 8.2. Выделение компонент сильной связности Вход: орграф С[У, Я), заданный списками смежности Г[е). Выход: список С компонент сильной связности, каждый элемент которого есть список вершин, входящих в компоненту сильной связности. С:=О гог ю н У г(о М[п]: =[и) 1 М[е] список вершин, входящих в ту же КСС, что и и ) е[п]: = О 1 все вершины не рассмотрены ) епг( Еог ъЫ1е У ф Э г(о зе!ест е н У 1 взять е нз У ) Т +- е 1 положить е в стек ) е[п]: = 1 1 отметить е ) КСС 1 вызов процедуры КСС ) епг( иЫ1е Основная работа выполняется рекурсивной процедурой без параметров КСС, которая использует стек Т для хранения просматриваемых вершин. Процедура КСС выделяет все КСС, достижимые из вершины, выбранной в основном алгоритме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
