В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 53
Текст из файла (страница 53)
золя: !) для любой дугн «спХ величина 9(х), называемая рюталам ло дуге х, удовлетворяет условию 9~9(х) л-с(х)! 2) для любаЯ промежуточной вершнпы и выполняется равенство р(в, о! — ~] Е(о, в) а, вшрг г(о) вмп(о! т. е. сумма потоков по дугам, заходящим в е, равна сумме потоков па дугам, нсхадящпм нз и. Пример 4.63.
На ркс. 4.46,6 показан допустимый паюк в транспортной сегв, апнсанной в примере 4.52. Прв наждой дуге указана величина потока по ней. Очевидно, что выполняются асе условия, перечисленные в определеннк допустямого потока (про. верьте выполненне второго условия для промежуточных вершнь ит, ол). Утллрллщн о 4.55.Длл лисою Лвчнтлжлю лапка е л гр глортнов секи О ллволввггл ров нтоо (4 551 овп(о ) вп (о ! По снрллтлеоию аонтстлного штока е ннслн 'Я ]~ р(в, о! — ~ р(», в)] О.
1459! омррт(о о ) вмО-'(о! ввп(о! Заметны, что для каждой дугн х (иь и)свХ, где ильи . величина 9(х) входнт а левую часть равенства (4.59) лишь олин раз я прн атом со знаком плюс. Аналогично для каждой Луги х (и, и )свХ, где ичьил велнчнна 9(х) входят в левую часть равенства (4.59) лишь один раз н пря этом со знаком мннрс.
С дРУгой стаРоны, дла каждой дУгн х (пь ил)снХ, где нь пттн ш)лт(иь и„), еелнчнна Е(х) входнт в левую часть равенства (459) один раз со знаком плюс (прн и иь го п,щВ-'(и)) н одни раз со знаком мнаус (прн и = иь ы лтс Р(и)), что в сумме дает нулевой вклад в левую часть равенства (4.59), учн- 550 тывнн сказанное, занлючаем, что нз равенства (4.50) следует кправазлппаагь равенства (4.58). Лпн ноа ломка а в тр нлортнса тс П нвммвст швн ннв р. р зив сумме штоков но всем ду вн, эв ппшнн в с, н.п, о о вп с сс .(в саву уппрмэснпв К!), — всвнчннв, рввнвв сунйс псовом па з вп аутвн. з хонямн» ш с т. в.
а( с ] ~ Ч(, «]. сшл-'(с ) смр(с,] Пусть а — лопустнмый патон в транспортной сети Р. Дуга хщХ называется наоми(пнной, еслн поток по ней равен ее пропускной способности, т. с. еслн р (х) = с (х). Поток а называется полнил, если любой путь в О нз а! в о содержит, по крайней мере, олпу насыщенную лугу. Поток р называется максимальным, если его велнчнна р прилипает максимальное заачслне по сравнению с лругнмн допустпмыми попжамм в транспортной сета О. Очевндпо, что максимальный поток а обязательно является полпым (так как в противном случае в О существует некоторая простая цепь т] нз ш в о, не содержащая насышыгных дуг, а слсдопательиа, можно уеелвчнть на единицу потокн по всем дугам пз я н тем самым увеличить на единицу р, что протнноречнт условию мащималикктн потока).
Обратное же, жюбше соэоря. нессрво. Как будет наказано ниже (см. прнмер 4.57), существуют полные патаки, не янляющнссн максимальными. Тем пе ме«ее полный поток можне рассматривать как пыюторое приближение к мщсснмвльному потоку. В связи с этим аяншем алга. ритм псптраепня полного потока в транспортной сегн О.
Алгорвтм 4ЛЯ: Шаг 1. Полагаем Ухщд а(х) =0 (т. е начинаем с нулевого потока). Кроме тога, налагаем Р' О. Шпг 2. Удаляем вз орграфа О' все дуги, япляющнесн насызценнымн прн потоке р а транспортной сегк О. Полученный оутра снова обозначаем черю О'. В аг 8. Ищем в О' простую цепь т] пз о, в о . Если такой цепи нет, то а — «сапный полный поток з транспортной сетн Р. В про гншклс случае переходим к шагу 4. Шаг 4.
увеличиваем поток р(х) ао «аждай дуге .с кз т] ва одинаковую вели жну а)0 такую, что, по крайней мере, одна дуга вз т! оказывается насыщенной, а потоки по остальным дугам пз и не превышагот нх пропускных способностей. Прп этом величина потока р также увелнчнвается ва а, а сам поток р в транспортной сети О остается допустимым (поскольку в каждую промежутчную веРшину, содержащуюся в т], дополнительно пошло а единиц потока н нз нее вышло также а елнннц потока). После етого переходим к шагу 2.
Обоснование алгоритма 4.10 несложно (провсднте его само. сто ятсльно). !6 Зв! Пример 4.64. Построим полный ноток в транспортной сети О, изображенной па рис. 4.47, а (в скобках указаны пропускные способности дуг). Воспользуемся алгоритмом 4.10. Полагаем Р' О, УхшХ «2(х) = О, т. е. начинаем с нулевого потока (см. на рис 4.47,б язображы«ие орграфа Р с указанием величин потока «р по дугам). При нулевом потоке отсутствуют насыщенные дуги. Выделим в 0' простую цепь п«о,о,о«о«н увеличим потони по дугам из и, на три (до насыщения дуги (оз, о«) ).
В результате получим поток в = 4««, содержащий одну насыщенную о о 6«г (~~ й?«' ?(ц 47~ ') " В К фт Я' «г т! 3! и! л! Рис. 4.4? дугу (см, на рис 4.47, з изображепне орграфа 0 с указанием величин потока р, по дугам). Пометим ес знаком К (аналогично будем помечать все другие насыщенные дуги) и удалим из орграфа О', Оставшийся орграф снова обозначаем через О' (см. изображение О' на рнс 4.47,г). Выделим в О' простую цепь ц, о,озозо,о«н увеличим потоки по дугам яз П«ма два (до насыщения луг (оь оз).
(оь о«)). В результате получим потоке« = =«йв содержащий три насыщенные дуги (см. иа рнс. 4.4?,д и*о. бражеиие орграфа О с указанием величин потока 2«т по лугам). Удалим вновь полученные насыщенные дуги из 0'. Оставшийся орграф снова обозначим через О' (см, его изображение на ряс. 4.47,е). Выделим в О' пРостУю цепь «1« = о,озо,о, и Увеличим потоки по ДУгам из «1« на два (До вагышенна ДУги (о«, о«)). В результате получим поток «р рз, содержащий четыре насыщенные дуги (см. на риц 44?,ж изображение орграфа Р с уиа. заннем величин потока «рз по дугам). Удалим вновь полученную насыщенную дугу нз О'. Оставшийся орграф снова обозначим через Р' (см.
его изображение на рнс. 4.47,з). Вылепим в 0' простую цепь ц, о«о,о,о«и увеличим потоки по дугам из ц« на два (до насыщения дуги (о„о,) ). В результате получим поток «р = ф«, содержащий пять насып«еиных дуг (см. иа рис. 4,47,п 262 изображение орграфа О с указанием величин потока ре по дугам). Удалим вновь полученную насыщенную дугу из 0'. Оставшийся орграф снова обозначим через О' (см. его ыображенне на рис. 447,к). Заметим, что н 0' не сущесшует пути иэ о, в вп а слеловательно, в трамспортной сепг О с потопом Пс не су.
пгествует пути из щ н ое. который не содержал бы насыщенных луг, т. е. поток Пе являетсн полным. Вечнчииа Ч, полученного полного потока равна 9. Как будет поиазано ниже (см. пример 4.57), этот поток не является макскмалвным. 4.5.2. Орграф приращений (4.5)! 4.5.3: Разрез. Пропускная способнщть разреза Пус Ю - трав «ертнея еть д. е яюбсгс нне с сн» у, 4' т егн, ч н е Щрн нем ), Гюегеюн мгн П ствеонсньэе ннем~ст е верине )" НМ» ЕЕ Ы ННОВ С Ю ЛУГ Х(У) ЦИ, ) МХ)ЕМ Ун жуть т.. Ннежестее, вювмеюмее в себя ме Лтш, нсяеэямне не еермнн, ве рнн анемв- 2ЭЗ Введем лля заданной транспортной сети О и допустимого потока ср в этой сети срграф приращений 1(0, ср), имеющий те же аершиггы, что н сеть О.
Каждой дуге х = (о, м) сжХ транспортной сети 0 в орграфе приращений 1(О, р) сшжветствуют две дугин х и х' (ю, о) — дуга, противоположная по напрвзленюо дуге. х. Припишем дугам х (о, ю)щХ, х' = (ю, и) орграфа приращений 1(О, ч) длину 1г П ) (О, если р(х) щ с(х); (4.бб) (со, если р(х) = с(х); П .) /О, если п(х))О; (со, если п(х)-О, т. е. орураф 1(0, и) является нагруженным. При этом очевиано, что длина любого пути нэ ос в и в орграфе 1(О, ср) равна либо О, чнбо со. Пусть с) — некоторая простаи цепь в орграфе 1(0, р).
Булем говореть, что цепь т) прохолит через дугу х - (о, ю) щХ, если. либо к, либо х' (еу, о) солержктсн в 4). При этом, если х содержится в н, то го- н зорим, что направление ц и х совпакают, а еслв х' содержится в Н, то говорам, что направления П и х пропгво- в г с ф положим. Пример 4.55. Орграф приращений с) ЦО, рс) для транспортной сети 0 и потока ре (см.
пример 4.54) изображен Рве. 443 на рнс. 4АЗ. шнэ Уь н вэгслшяне гсэшнэм, эрнээлэ вэш» Уь Число «Х(УН = Е-() э а Х( 1',) .п*эмевегеэ пэоэуа чае гэсгабчсг ью эсэра х(у,) Р ээ з е минимальное ээсэускнов сосгобэасгьп нээмээегсэ мини ээ н Пример 4.бб. Для транспортной сетн О (см.
прнмер 4Д2) н множества вершин Уг - (оь оэ, иэ) раврвэ сети О опгоснтельно (г, представляет собой множество дуг Х(Уг) = ((оь о*), (оь оэ), (оь ог)). Ею пропускная сгюсобность составляет с(Х(У,)) = б+ +6+2 13. Утвержденна 4.57 Для любого допустшэою потока р в транспортной сети Р и любого мчожесша УгсУ, где а а Уг, о„а Уь выиолпяегсл неравенство р ш с(Х(Уг)), т. е. величина любого допустимого потока в сети О (в том числе и максимального) не превышает пропускной способности любого раэрсэв сети О (в том числе н минимального). С уатэм того, чю эге есвшннн е Уь эв н клвчеэнвм э, ээлявгсэ :лро евупмэмнв, э О(э„) = О, нмгем В(, э.) = ~ Г(в. э.)+ ар-'(э ) вап-'( ) + й~ [Ч у(в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
