Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 47
Текст из файла (страница 47)
пропускные способности узлов формулируется следующим образом: ГЛ. >2. ПОТОКИ В НЕПРЕРЫВНОЙ СРЕДЕ максимизировать Р при условиях — э, если ?=з, ~хп — ~„х>ь= О, если ?Фг, ~, Р, если у =2. х».р0, 0<х><-.ш; для всех ? „хм =хн ?? азовем разрезом, разделяюи?им >«'«и Л> «в сети с и ропускиыми способностями узлов, множество узлов, удаление которых превращает исходную сеть в несвязную сеть, состоящую из двух. или более частей, где узлы Л', и Л>> попадают в разные части; при этом никакое собственное подмножество рассматриваемого множества узлов не должно обладать.
указанным свойством. Два узла назовем соседними, если в сети имеется дуга, их соединяющая. Хотя в общем случае удаление такого разреза может разбить сеть более, чем на две части, все же разрез будет обозначаться (Х, Х). Здесь Х обоаначает множество узлов в той части сети, которая содерн«ит Л",. Нетрудно видеть, что разрез (Х, Х) состоит из всех узлов множества Х, являющихся соседними с узлами нз Х.
Разрез, обладающий минимальной суммой пропускных способностей узлов, называется мивимальиым разрезом. В сети с пропускными способностями узлов справедлива теорема о максимальном потоке и минимальном разрезе, аналогичная соответствующей теореме из гл. 8. Действительно, сеть с пропускными способностями узлов простым приемом может быть превращена в сеть с пропускными способностями дуг (Форд и Фалкерсон [67]). Но, поскольку при этом резко возрастает число дуг '), будем рассматривать непосредственно сеть с пропускными способностями узлов. Теоэема о макси»«лльпо»> потоке и миннмлльном Разрезе (в сети с пропускными способностями узлов).
Максимальная '] Каждый узел Л'; разбивается на две части, «левую» н «вравую», в добавляется орнонтированвал дуга, ведущая нз левой части Л>> в ого правую часть. Все орнентвроваээыс дуги в исходной сети, входившие в уэсл Л>,, в новой сотв заменяются на дуги, зходял>ис в его левую часть; все ориентированные дуги в исходной сети, выходцев>ис вз узла Л>>, в новой сети заменяются эа дуги, выходящие из его правой части.
Каждая неорнентировавная дуга А» заменяется на дзе ориевтврозввэых, одна нз которых ведет ич левой части Л«в нраву>о часть Л'Л а другая — нз левой частнд> в правую часть Л'ь Таким образом, если з исходной сети было и узлов я л> неорневтированных дуг, то з новой сети добавляется л+ л> дуг.— Прим. л«р««.
»2.2. сгти с пРОпускными спОсОБнОстями узлов 259 величина потока из источника А», в сток А»» равна пропускной способности минимального разреза, разделяющего А», и А»». Докззхткльство. Предположим, что все пропускные способности ш» узлов целочнслепны, н пусть рм — произвольнь»й поток, не обязательно максимальный.
Если величина этого потока равна пропускной способности некоторого разреза, то теорема доказана (ясно, что величина любого потока из А»„в А»» не превышает пропускной способности разреза, разделяющего А», н А»»). В противном случае найдем цепь, с помощью которой можно увеличить поток. Для этого определим подмножество узлов Х, такое, что поток мо>кет быть послан в любой узел, принадлежащий Х.
Обозначим и»ы -= ш»п (и»;, и»2). Используя текущий поток р„, определим рекуррептно множество Х по следующим правилам. О. Ж.бХ. 1. Если А»» ЕХ, х»»<и»»» и хз<шп то А»;сХ. 2. Если А»» Е Х и х;» ) О, то А» Е Х. 3. Если А»»ЕХ, х»»<и»ы, хз=и»»э хзз>0, то А»чЕХ. При таком определении Х возможны 2 случая.
Случаи 1. Узел А»» попадает в множество Х..НО»»а»ком, чт»з поток может быть тогда уволичен. Так как А», с Х, то должна существовать цепь нз»ч, в А»», для дуг которой выполняются условия правил 1 — 3. Очевидно, что если выполня»отся условия правил 1 — 2, то поток вдоль такой цени может быть увеличен. Если же выполняются условия правила 3, то положим е .= »П»Б (»в»»в — хси хз»), а затем добавим е к потоку х;; и вычтем з из хер Это эквивалентпо увеличению потока в узел А»ю причем поток через увел А»» остается равным пропускной способности ир Так как величины и»» целочнсленны, то и е будет целым числом. А так как максимальный поток ограничен сверху, то поток нз А»е в А»» может возрастать на з конечное число раз, и, следовательно, случай 1 мо»кет встретиться только' конечное число раз. Случай 2.
Узел»У» попадает в Х. Пока»коз», что построенный поток равен пропускной способности некоторого разреза. Назовем соседние с Х узлы у-узламн, или узлами нз у. Утеер кдается следующее. 1'. Не существует дугового потока иа у-узла в узел, принадлежащий Х. 2'. Все у-узлы насыщены (т. е. х» — — и»»). 3 . Не существует дугового потока из Х вЂ” у в у. 4'. Не существует дугового потока из одного у-узза в другой у-узел. ГЛ.
12. ПОТОКИ В НЕПРЕРЫВНОЙ СРЕДЕ 270 Докажем зги утвернсдепия (см. рис. 12.2). 1'. Не существует дугового потока хя ) О, такого, что !!'! с Х, 11'! с у, так как в противном случае узел !!'! попадал бы в Х по правилу 2. 2'. Пусть узел Л'! принадлежит Х, а у-узел Дг! является соседним с ннм. Иа доказанного выше предложения 1' следует, что х» ~ )О. Если бы х» ( и», то по правилу 1 !!'1с Х.
Поэтому х,1 — — и!» =- ВИВ (и!1, и!;). Если и!» =- и1;, то х» = и,. Значит, х1 = 1Р,, т. е. Узел !!'; ПасыЩен. Если ь2» — — п2!г то х» — — — и!!. Р и с. 12.2. Следовательно, х; = и!1, т. е. узел 11!! насыщен. Очевидно, что насыщенный узел !!'1 не может попасть в Х по правилу 1. Далее, насыщенный узел 1111 не может попасть в Х по правилу 2. Действительно, тогда существовал бы дуговой поток х;р, где Хр с Х.
Но тогда сумма х» -1- х;Р превышала бы п2„что невозможно. Итак, насыщенный узел !!'! может попасть в Х только по правилу 3. Тогда должен существовать дуговой поток хгч в некоторый насыщенный узел Д1ю Так как х» .— — и1„то этим насыщенным узлом может быть толысо 1!'1. Таким обрааом, все у-узлы являются насыщенными. 3* — 4=. Пусть 11'! — произвольный у-узел. Предположим, что существует узел 2уь~Х с хьз)О.
Так как д1,~у, то найдется соседний с пнм увел Ж1 ~Х. Поскольку У1,!(Х, а узел 11!! насы- '1 щеппый, то (в силу правила 3) х1, =- и!1;; отсюда, учитывая 1! — ! 1! хд ) О, получаем и!1; = ю! . Следовательно, 11'! — насыщенный узел. 1- 11! = 11. 11 Но узел,211 по правилам 1 и 2 (см. доказательство п. 2) пс мог 11 12,2. СЕТИ С ПРОПУСКНЫМИ СПОСОБНОСТЯМИ УЗЛОВ 271 попасть в Х.
Значит он лопал в Х по правилу 3 через систему узлов 1У1 — ~гтз — гг'1, где 11гг ~Х и отличен от 1У1 (так как оп ! ранее 1У1 попал в Х). Повторяя те же самые рассуждения для '1 узла гУ1, убеждаемсн, что оп попал в сеть через систему узлов гуг — «)У1 -1У1, где 1У1 попал в Х ранее 1111, и т.
д. Получаем 12 г 12 'г' последоватольность узлов )уг,, )уг, ..., )у1, ..., каждый нз которых попал в гшожество Х через следугощий, и все они различны. Бесконечность этой последовательности противоречит конечности исходной сети. Поэтому предположение о существовании узла гг'„СХ с х1,2)0 неверно, и утвержденна 3' — 4' доказаны. Таким образом, величина потока из гг'г в гг11 равна ~, хп= К1ЕХ к1Ег = ~ нг1. Так как у-узлы — зто все соседние узльг для узлов из Х, КТЕТ то множество у является разрезом.
° Можно разработать метод 'расстановки пометок, аналогичный методу, приведенному в гл. 8 н основанный на рассмотренных трех рекуррентных правилах. Однако правило 3 требует, чтобы просматривались не только все узлы дгю соседние с каждым узлом, но такнге н все сосеДние ДлЯ кажДого Узла гг'ю Это Резко Увеличивает объем вычислений. Рассмотрим процедуру расстановки пометок, которая основана только на правилах 1 и 2. Все узлы разбиваются на пять типов: 1. Поыеченные узлы (П-узлы). Узел гг'1 называется помеченным, если по рекурронтным правилам 1 илн 2 он попадает в множество Х.
2. Помеченные и просмотренные узлы (ПП-узлы). Узел гг'1 называется помеченным и просмотренным, если он является П-узлом и просмотрены все узлы, с пим соседние. 3. Отброшенные узлы (О-узлы). Узел г111 называется отброшенным, если он насыщен, т. о. хг — — игн 4. Отброшенные и просмотренные узлы (ОП-узлы). Узел называется отбро1пенпым и просмотренным, если он является О-узлом, все соседние с ним О-узлы гт ь просмотрены и прн этом не оказалось нн одного дугового потока Хгз) О.
5. Непомеченные узлы (Н-узлы). Узел гг'; называется непомеченным, если он не принадлежит ни к одному нз четырех перечисленных выше типов. Процедура расстановки пометок осуществляется следующим образом. ГЛ. 12. ПОТОКИ В НЕПРЕРЫВНОЙ СРЕДЕ 272 Сначала помечают узлы, которые можно включить в Х только по праннлам 1 нли 2. После этого производятся действия, аналогичные тем, которые осуществлялись па шаге 1 в $8.2. При этом помеченные узлы получают пометку П, а отброшенные узлы получают пометку О. Если сток оказался помеченным (в этом случае говорят, что произошел прорыв), то поток увеличивают (как па шаге 2 в $8.2), затем стирают все пометки и вновь переходят к шагу 1. Если сток оказался непомеченным (произошел ненрорын), то просматриваются по очереди один за другим все О-узлы.
Если для фиксированного О-узла Уг не существует дугового потока хь; ) О, где»»гь является О-узлом, то узел 1»'1 является отброшенным и просмотренным; оп получает пометку ОП. Если же такой О-узел 1«'а найдется, то О-узел )»') становится помеченным и получает пометку П. После этого просматривают все соседние с»»г„О-узлы н Н-узлы, ищутся среди ннх новые П-узлы и О-узлы. Если все узлы имеют пометки ОП, ПП или Н, то процедура расстановки пометок прекращается. Если при этом»»г« Е Х, то максимальный поток построен. В описанной процедуре расстановки пометок некоторый узел Л'; сначала может быть помечен как О-узел (если х; — — шг), затем он может стать ОП-узлом (если не существует О-узла Уь, такого, что хь; ) 0). ПРеДполоасим, что хгь ) 0 ДЛЯ всех О-Узлов ггь. В дальнейшем О-узел Уа может стать П-узлом и, кроме .того, рассматриваемый узел Уг также может стать П-узлом, если х;а ) О.
Таким образом, самая длинная последовательность пометок, приписываемых некоторому узлу»»гт, может быть следующей: Н вЂ” » О -». ОП -ь П -ь ПП. Следовательно, при осущестнлении описанной итерации расстановки пометок каждый узел просматривается вместе со своими соседями самое большее дважды '). 12.3. Потоки в непрерывной среде Рассмотрим известную задачу варкацнонпого исчисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
