Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 177
Текст из файла (страница 177)
Как мы знаем, процедура П1эснлкое вызывается 0(Ъ'з) раз, следовательно, общее время, затраченное на ненасышаюшие проталкивания, 0(1, 3) Таким образом, время выполнения процедуры Кеелвеь-То-гконт составляет О(Ъ'з + Ъ'Е), что эквивалентно 0(Ъ'з). Упражнения 26.5.1 Проиллюстрируйте, используя в качестве образца рис. 26.10, выполнение процедуры йеьлвее-То-гпонт для транспортной сети, представленной на рис. 26.1,(а). Предполагается, что начальный порядок следования вершин в списке Т вЂ” (171, ог, сз, и4), а списки соседей имеют следуюший вид: Е1.
Гь7 = (а, 1'г ОЗ), Ег )Ъ7 = (а а1 'аэ а4) аз 'ь7 = (11Ы аг~ а41ь) и4 117 = (ог, оз 1) . 26.5.2 * Необходимо реализовать алгоритм проталкивания предпотока, в котором поддерживается порядок обслуживания переполненных вершин "первым вошел, первым вышел". Данный алгоритм разгружает первую вершину в очереди и удаляет ее оттуда, а все вершины, которые перед этой разгрузкой не были переполнены, но по- чпч9 зэжои 'июон9оэопэ ачнмэЛподп згмэьги едцэд и гчнипкЬа эпз 'изээ иом -ез а емозоп озончкевгиэмеьг кинэпэпэдпо еьепее озь 'эзимгемоц июон9оэопэ цонмэЛподп гминэьинедзо чзкдоазэпаопЛ нэжкоп 'ЛнипкЬа огЛнневве огЛпжем а цншкпоха 'козон цгчнчиэзижокоп игчндеии э 'э'з 'июон9оэопэ гнчнмэйюдп ззм -эии 'ед9эд и мем онаед 'гчнишдэв иодоюм а 'чзээ огЛнздопэнедг иидюнээед 'в .зээии эн — (9) '11.9Г эид ен емюшэд е 'Вохгча звени (е) "ц 9~ эид ен емзлпэд 'дэгчидпвН гчпинедз ивмьоз игчньиисед ш егзч9 -огк м мэьоз хгчаоздезэ си 'ниппЬа хиш9о хизпгмэии эн 'иэзЛп ш ик зэЛезэапЛэ 'чз.икэвэдпо гч9озь 'гчоз а кэзэеьшпмеа (шэщозд эдвэвэ) арохгчэ о ваарт ("'6' х) ' .
'(егг'ех) '(гй'гх) мэьоз хгчаоздезэ еи > ш оневее эмзэшэд а чзэЛц и = г' ипи г = е 'и = г 'г = г хгчдоюм ккп '(г')) имьоз ио9оэ хигпопапшывэдп 'нишдэа хгчньинедз иэинэьошмэи ее 'епээоэ эджюь оп онаод юэии имзэгпэд ен -ипкЬа магга (Е 'з) мвм 'эп9позэ рг-С и эмодю ц-г а кэогйпкпохен 'ЛнипкЬв ниь -енео9О '[('9р'эид ен онеевмоп мем 'нишдэв аоп9позэ и и модзэ и аи иигпкоюоэ 'федз игчннеаодизнэидоэн ио9оэ зэкквез.эвэдп и х и гчодэгчеед (ргзЗ) внвзэтад эромгчв О вьврвЕ Г91 ИЬВЕГВР. (.эмизмедп ен емоюпвэдп кинеаимпеюдп епоюгч иипвеиавэд ичнаизмэффе чзиь -Лкоп зэкпоаеоп емзЛжэгчодп емизэидаС) гчюэгчв иэипмнЛф кэыкнак г( зЛ9идзв иоеед9о нимез цгчннэьйгоп озь 'эзимгвмод .(г + ~л~ 'г( а)хвгп = у а кеаипаен -еюЛ 'з( < ц гг цодоым кпп '(е) — Л э а ЛнипкЬа огЛпжвм юкпаон9о (эгзягзпэЧ дец) вмшбиэнвди вмввзэвдве 'юЛвзээшЛэ у эинэьена эомез инэд емоюи анод -озэ ен эеэдеед егончнвиинивг в кэзмпохвн з( < г(.а э гчнипкЬв ээа озь 'эзижвмоц з( = г( а иодоюм Л 'цомез .эм 'иоюэгчв цоннеп э гчнишдэа ценно ин ын озодогом ккп '1 — ~Л~ > з( > г) оиэиь эоаэп эодоюмэн .иЛазээпзЛэ емоюппэдп кинеаим -иеюдп егчзидозке кинэнкошчв ээээпаШ в эмьоз цодоюмэн а озь 'иижопоппэдгг э" лРС '( Л)О да -кошча но гч9озь 'мез чзмаоеикеэд онжогч емоюппэдп кинеанмкеюдп позэвг 'ениш -«Ьа кеннэнвопэгЬп вшпэгчаивн кэгэвздэапоп епзээв эмг дзеед ииээ оз.ь 'эзнжемоц гЗзчОмд-О1-ЧвпечвЦ гчдЛПэнодп кинэнкопгча инэиэда Лмнэно ен зэкиваоп озе мея '~ + Ч'н = г("и ккпэньгча охэодп 'г('и юкгшон90 1янучвя едЛпэподп икээ эмгеп 'чзеюцед юпЛ9 гчзидозпв цжннэгп9о9о оз.ь 'эзижемоц ГК'9С ( Л)О кинда ее моюп цгчнчкеииэмви юкпэиьгча кедоюм 'вгчмидоше озон -нвп шипееивеэд чзиодюоп онжои озь 'эзпжвмод 'кэзэепкЬаес за.идаше 'цоюЛп кэзиаонвзэ чпжЬьо евзом ипэдэьо пэном а кэзгмешэргоп 'игчзчаомвз ипею ээн экэ ллофглГг о ввоввГ гвр влвлаогггГ Г,Г лвооь ООУ 801 Глава 26.
Задача о максимальном ломаке (б) (а) Рие. 26.11. Решетки дла задачи о выходе. Стартовые точки — черные, прочие вершины решетки— белые. (а) Решетка е выходом, предетавленным заштрихованными пузами. (6) Решетка без выхода. сведена к стандартной задаче о максимальном потоке для транспортной сети сопоставимого размера. б. Разработайте эффективный алгоритм решения задачи о выходе и проанализи- руйте время его выполнения. а6.2. Зодича о минимольном нокрытии яутями Покрытие нутями (рабз сочег) ориентированного графа С = (К Е) — это множество Р не имеющих обших вершин путей, таких, что каждая вершина из множества У принадлежит ровно одному пути из Р. Пути могут начинаться и заканчиваться где угодно, а также иметь произвольную длину, включая О.
Минимяльным нокрьннием нуяпзми (пппшппп ра()з сонет) )рафа С называется покрытие, содержащее наименьшее возможное количество путей. зь Предложите эффективный алгоритм поиска минимального покрытия путями ориентированного ациклического графа С = (Ъ; Е). (Указаниег предположив, что У = (1, 2,..., и), постройте граф С' = (У', Е'), где 1" =(хо хз, х )(-)(э)о йз й ) Е' = ((хо, х ): з б У) 0 ((у(, уо): з й Ъ ) 0 ((х(, уу); (з, з) Е Е) и примените алгоритм поиска максимального потока.) б.
Будет ли ваш алгоритм работать для ориентированного графа, содержащего циклы? Объясните свой ответ. 26.3. Алгоритмическое конеулвтирование Профессор решил открыть компанию, проводящую консультации по разным алгоритмам. Он разделил алгоритмы на и важных областей (грубо соотвегствуюших различным частям этой книги), представленных множеством А (Аз, Аз,..., А„). Для каждой подобласти Аь он может нанять эксперта по данной тЕМатИКЕ За СЬ ДОЛЛаРОВ.
У КОМПаНИИ ИМЕЕТСЯ МНОжЕСтВО ? = (з),,У2,..., .1,„) ПО- тЕНцнаПЬНЫХ ЗадаЧ. Дпя ВЫПОЛНЕНИЯ ЗадаЧИ зз КОМПаНИя дОЛжма НаНятЬ ЗКСПЕртОВ га эьк эзга ВО2 Часть КЕ Алгоритмы дли работы с графами для подмножества В; ь А подобластей. Каждый эксперт может одновременно работать над несколькими задачами. Если компания решает взяться за задачу Уь она должна нанять экспертов во всех подобластях в Вн и получит за выполнение задачи оплату в р; долларов. Профессору необходимо определить, для каких подобластей следует нанять экспертов и за какие задачи взяться, чтобы максимизировать чистую прибыль, равную плате за выполненные задачи минус оплата труда нанятых экспертов.
Рассмотрим следующую транспортную сеть С. Она содержит исток а, вершины Аы Аз,..., А„, вершины .Ум,Уз,...,,У и сток 1. Транспортная сеть содержит ребра (а, Аи) ()с = 1,2..., и) с пропускной способностью с(а, Аь) = сы и для 1 = 1, 2,..., т транспортная сеть содержит ребра (Уг,1) с пропускной способностью с(,7„1) = рь Если Аи е В; ()с = 1, 2,..., и и 1 = 1, 2,..., т), то С содержит ребро (Аы.У;) с пропускной способностью с(Аы У,) = оо. а.
Покажите, что если,У; Е Т для разреза (Б, Т) с конечной пропускной способностью транспортной сети С, то Аи Е Т для каждого Аи Е Вь б. Покажите, как определить максимальную чистую прибыль из пропускной способности минимального разреза транспортной сети С и заданных значений р,. в.
Разработайте эффективный алгоритм определения того, за какие зацачи следует взяться и каких экспертов нанять. Найдите время работы своего алгоритма как функцию от т, и и г = 2 ',", ~В;~. 2б.б. Обновление максимального нотока Пусть С = (1г, Е) представляет собой транспортную сеть с истоком а и стоком г и целочисленными пропускными способностями. Предположим, что известен максимальный поток в С. а. Предположим, что пропускная способность некоторого одного ребра (и, с) е Е увеличена на 1.
Предложите алгоритм обновления максимального потока с временем выполнения О(1г + Е). б. Предположим, что пропускная способность некоторого одного ребра (и, с) е Е уменьшена на 1. Предложите алгоритм обновления максимального потока с временем выполнения 0(Ъ' + Е). 36,5. Масштабирование Пусть С = (Ъ; Е) представляет собой транспортную сеть с истоком а и стоком 1 и целочисленными пропускными способностями с(и, в) каждого ребра (и, о) е Е. Пусть С = шах< „)ее с(и, п). гь Докажите, что минимальный разрез С имеет пропускную способность не более С )Е(.
ЮЗ глава гд Задача о максимальном ломаке б. Для заданного числа К покажите, как за время 0(Е) можно найти увеличивающий путь с пропускной способностью не менее К, если таковой путь существует. Для вычисления максимального потока в С можно использовать следующую мо- дификацию процедуры Гоко-ГОькпкзом-Мптноп. МАх-Г1Азтч'-Вт-ЗсА1.11ччл(С, в, 1) 1 С = шах1и „)а к с(п, с) 2 Инициализировать поток З значением О К 2116 с) 4 тгййеК>1 5 зтЬ~!е существует увеличивающий путь р с пропускной способностью не менее К 6 Увеличить поток 7" вдоль р 7 К=К/2 8 гетпгп 7" в. Докажите, что МАХ-Гьоъ'-Вт-Зсмлип возвращает максимальный поток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
