Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 48
Текст из файла (страница 48)
] ] Гл. !О. Алгоритмьг для зидичи о паросочепшнип Задйчи 1. Покажите, что в двудольном графе мощность максимального паросочетання равна мощности наименьшего множества вершин, понрываюшнх зсе ребра (т. е. каждое ребро инцидентно некоторой вершине данного множества), 2. Покажите, что в двудольном графе В=(У, К Е), в котором [У)= )61=и, имеется паросочетание мощности и тогда и только тогда, когда для всех 5~У выполняется условие [(и~ (/: (о, и) ~Е для некоторой вершины и~5)!)[5(, 3. Ргберным покрытием графа 6=(У, Е) называешься такое подмножество С множества Е, что У=- () !и „! и (и, о). Предположим, что в О нет нзолировзиных вершин.
Покажите, что мощность минимального реберного покрытия С в графе О равна мощности максимального паросочетания М в О, увеличенкой на [У[ — 2)М[. Приведите аффективный алгоритм для нахождения минпмального ребернвго покрытия графа. 4'. Пусть у графа 6=(У, Е) множество вершин У равно (ом оз ..., и„). Малгрицей Татта Т(6) графа 6 назовем следующую (ихп).матрицу: ( кО, если [гг, оу[~Е и 1 > П (6)гу ~ хгу, если [оп оу)мЕ и ! < у, О в противном случае, где х; — переменные. Покажите, что в 6 имеется полное оаросочетание тогда и только тогда, когда йе1(Т (6))чьО.
5. Пусть Р— множество заданий, которые нужно выполнить на двух процессорах, и пус!ь все задании требуют одного и того же количества времени (скажем, !). Предположим, что имеется ориентированный ациклический граф Р=ф, А), такой, что если (/м в',) ~А, то задание г', должно быть выполнено раныке, чем г'х. Следующая задача называечся задачей о расписании для двух про~!гсгоров; для данного Р найти оптимальное рислисание, т.
е. такую функцию 5 ~(-» (1 2, ..., Т), что !) !(г 67-' 5(у)=!!ж2 длн всех !тТ! 2) если А, /г) Е А, то 5(У,) <5(У ); 3) Т имеет минимальное возможное значение. а] Пусть Ор=(йз, Ер], где [/ь /л) ~ Ел тогда и только тогда, котла в Р не су. шествует пути как из l, в г'х, так и нз l„в /, Предположим, что М вЂ” максимальное паросочетание в Ор. Покажите, по наименьшее достижимое Т должно удовлетворять неравенству Т)!'3г! — )М, '(вспомните задачу 3). б') Покажите, что всегда существует расписание, для которого Т= )~ ! — [М[.
Приведите аффект!!нный алгоритм нахождения оптимааьного расписания (ср с теоремой !5.5). 5. В ориентированном графе каждая дуга имеез начало и конец. Биоривнти. рованный граф (У, А) также содержит множесгво вершин и множество дуг, однако в нем дуги могут иметь либо начало и конец, либо два начала, либо два конца. Биоригнтированнал сеть 5(=(з, 1, У, А, Ь) — зго сеть, в которой (У, А] — биориентированный граф.
Кроме того, з не является концом никакой дуги и Г не яьляег. ся началом никакой дуги, Поток / в дг — зто такая функция из А в 2+, что((а)т ~Ь(а) для всех а~А и для каждой вершины и~У вЂ” (з, 1) выполняется равенство Х Г(]- Х Г(] а1 и — конец а в3 в — канало а Величина потока [ равна Х / (а) а: в — начало в Покажите, что задачу о паросочетанни в произвольном графе можно эффективно свести к задаче о максимальном потоке в биориентированной сети с единичными пропускными способностями.
(Ср. о 5 10.3). Задачи 7*. Покажите, что любую индивидуальную задачу о потоке в биориентиро. ванной сети с единичными пропускными способностями можно эффективно свести к индивидуальной задаче о паросочетании. 8. Покажите, приведя соответствующий пример, что если 6=(У, Е)— граф, М вЂ” паросочетание в 6 и Ь вЂ” цветок (цикл с 2т+1 ребрами, т из которых принадлежат М), то следующее утверждение может быть неверным: увеличивающий путь в 6 относительно М существует ~огда и только тогда, когда существует увеличиваюгций путь в 6(Ь относителыю М!Ь. Ср.
с теоремой 10.4. 9. Примените алгоритм, приведенный на рис. 10. !3, для увеличения паросочетания, показанного ниже. их "з иа и, "з ии иы ига 19. Цель этой задачи — показать, что соответств>ющпм образом реализуя процедуры ЦВЕТОК и УВЕЛИЧЕНИЕ, можно понизить время работы алга. ритма построения паросочетвпия в пронзволыюм графе, приведенного на ри .
!0.10, до 0()У!х). а) Предположим, что для кажлого ребра е текущего графа, которого не было в предыдущем текущем графе, хранится ребро пред(г) из предыдущего текущего графа, которому соответствует е. Покажите, что при использовании этого приема нажлое выполнение процедуры УВЕЛИЧЕНИЕ требует 0()УВ) времени. б*) Покажите, как реализовать процедуру ЦВЕТОК (которая теперь должна также пересчитывать массив пред) ~ак, чтобы общее время, затрачиваемое на псе вызовы этой процедуры, составляло 0(~У!х) на этап.
! 1. Задача о лиуосочетании а оуиенлгирсааннаи графе формулируется следующим образом. Для данного орграфа 0=(У, А) найти такой подграф (У, М), чтобы степень захода и степень исхода каждой вершины из У в подграфе (У, М) была равна 1. Приведите эффек~ивный алгоритм для решения задачи о паросочетании в ориентированном графе путем свеления ее к задаче о паросочетании в днудольном графе. 12.
Задича а Ьшоетпании формулируется следуюьчнм образом. Для данных двудольного графа В=-(У, 0, Е) и функции Ь: У() 0 — ь л+ выяснить, существ>ет ли такое подмножество Мс:Е, что каждая вершина и~ У() 0 инцидентна Ь ребрам из М.
а) Приведите алгоритм для задачи о Ь-сочетании со сложностью 0((У„,„„Ь(В а), б) Приведите алгоритм для задачи о Ь-сочетании со сложностью 0(~УИ). 13*. Приведите полиномиальный алгорятм для задачи о Ь-сочетании в произвольных графах, (Ухаюние пас~ройте новый граф, имеющий Ь(и) новых вершин для каждой вершины и и по две новые вершины для каждого ребра; найдите полное паросочетание в этом графе). 14.
Задача о ларасочетании с Узким метлам формулируется следующим образом. Для."энного графа 6=(у, Е) и весов ю: Š— ь ь+ найти такое полное паро- 252 Гт !О. Алгоритмы дгя задачи о ларасачегпании сочегшше 54, чтобы тах, гх ш(е) был как можно меньше. Приведите полиномнагшныи алгоритм ддя этой задачи. !5'. Приведите полиномиальный алгоритм для следующей задачи. Для данных графа 0=СИ Е), разбиения множества )г на два подмножества А н В и двух левых чисел и и Ь найти такое паросо ~етание Ы, чтобы не меньше чем а вершин из А, и не меньше чем Ь вершин нз В, были инлидентны ребрам из ЛЕ 16. Зада ш аб улаксаке контейнероз формулируется следующим образом Даны л иеглхх пшел (с,, ..., си) н дополнительно целое число  — вместилюсть контейнера.
и требуется ггайти такое разбиение данных целых чисел по контей. нершх, чтобы сумма всех полых чисел в каждоы контейнере не превышала В н число контеянсров было ггиггилга.гьггьггг Покахште, что если числа су удовлетворяют неравенству су)В(3, то задачу об упаковке контейнеров можно сфорл~улггровать как задачу о паросочстаншс Решйте затем ее наиболее простым способом. Комментарии и ссыннм Ллгоритмы для нахождения паросочетання в двудольноч графе известны довольно давно; см., например, [На) На!(М., дг. Лл Л!йог!!йгп 1ог ПВНлс1 Кергеьеп1а!(чез, Ашепсап Майн Л!ол!)г. 1у, 63 (!956), 7!6 — 7!7.
[РЕ[ (гид 1.. К,, !и![ге~хоп О. ((. Г!огчь |п (йе(хчогйь. Ргйгсе!оп, Н. бл Рг[лсе!ол ()гйч (иеьь, 1962. [Иьгеется перевод'. Форд Л. Р., Фалкерсои Д. Р. Потоки в сеих.— Мг Д!ггр, !963.) Теорсты 10.1 (об )нелл лгвзющсм пути) была независимо доказана в работах [Ве! Всгде С. Тно 1'[~согелгь ш (ггарй Тйеогу, Ргос Манона! Лсай. о1 Бе|енсе, 43 (1957), 842 — 844. [[х)х) ~' огтзл К.
7., Рабщ М. О. Ал А(йогййт 1ог а Мгп[тигп Сочег о1 а Сггарй, Ргос. Лглег1сзг! Мз()г 5ос(е!у, 10 (!959), 315 — 319 Интересно, что долгое время господствовало мнение, что эта теорема нглосргди гткенио дает эффективлыи алгоритм для построения паросочетания в недвудольном графе.
Эдмонде первым указал на сложность втой задачи и привел для нее элегантное решение [Еб) Ег!лгоггбь Л Ра(йы Тгееь апб Иошегь, Салай. Л Л(а!(г., 17 (1965), 449 — 467. г/ Ллгоритм д.ш двудодыюго случая из 9 10.3 со сложностью 0([И А[Е[) азах из работы [НК[ Норсгой Л Е., Кагр )(. М. А л Л А[йог)рлгп (ог Мах~ппнп Ма(сйшй (п В!- раг!Ке Сггар(гь, ) 5!ЛМ Сагир., 2 0973), 225 — 231. Тот факт, что эточ алгоритм является часчггым случаем алгоритма построения максималыюго потока хля простой сети, впервые был отмечен в работе (Е'П Ечел 5., Тат!ап ((, Е. Мебмог1г Р(ош апб Теь1шй Огарй Соплес!гчйу, Л.
5!АМ Сагир., 4, Ыо 4 (1975), 507 — 512. Самый быс~рыгг пз известных алгоритмов для задачи о паросочетании в недвудольном грзфе описан в работе [МЧ[ Якай 5., Уатгаш Ч. Ч. Лл О()' [И [Е[) Л)йоггршл Мг Илс~щй Ыах!лгглгг Ма1срйлй !и Сапега! Огар[гь, Ргсс, Тшел1уйнь! Липла( Бугпроьшгп ол 11к Гошгба!1олз о(Согпри!ег Бс!епсе, Еопй Веасй, Са)йоги!а; 1ЕЕЕ (1980), 17 — 27. Более ранний алгоритм, менее эффекгивиый для разреженных графов, нэлол,сн в работах [ЕК] Ечеп Б„Кзггэ О. Ап 0(ля ь) Л!дог!риги !ог Махнллт Л(г(сйлж !и гас: ь(гар)гя, Ргос 5!х1еелГн Лппиа! 5ыпр ол Еоилйа!июь о! (хнгг лггчг 5г: «.:.- Комменлгаргги и ось~ма! Вегяе!еу, Са1 Ноги (а: ! Е ЕЕ (1975), 100 — 1! 2.
[Ка) Каггч О. Ап 0(пз'з) А18ог!1Ьгп 1ог Мах)птнпт Ма(сЬ!пя гп Оепега1 ОгарЬз (неопубликованная диссертапия, ТесЬп!оп, НаПа, 1згае1, 1977). задача 3 взята из [гч)1[, задача 4 — из работы [Тп[ ТпНе 11г, Т. ЧЬе Гас1огз о! ОгарЬз, Сапаг). д.
Ма(Ь., 4 (1952), 314 — 328. Задача 5 взята из работы [ЕК!4[ Гп)и М., Качагп! Т., Х)пагпгуа К. ОР1ппа( Зеснепс)п8 о( Тгчо ЕягВча)еп( Ргосеззогз, Л. 5! АМ, 17 (1969), 784 — 789, а задача 15 — из [Ру[ РарадппННоп С. Н., Уаппа)гарЗз М. ТЬе Согпр)ехВу о[ йез(г!с1ед Зрапп!п8 Тгее РгоЬ!егпз, рр. 460 — 470 !п Ан(опга1а, Ьап8на8ез апд Ргоягаптпт!и8, сб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
