Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 42
Текст из файла (страница 42)
Лемма 9.6. В аросевой сети ЛГ расстоянии между з и ! не может прель>шать ) Г> )>~ ! ), где ( ! ! — величина максимального потока. 1' Доказательство. Пусть 'е'„)Р„..., )х> обозначают, кзк в доказательстве леммы 9.5, множества вершин, находящихся соответственно на расстоянии 1, 2,, ! от з, Докажем, что ) Ге) ) ~ Г( Весь максимальный поток )Г"! должен проходить через )>о.
Но, поскольку сеть простая, через каждую вершину множества 1',. х>, может проходить только одна единица этого потока, так как ф> либо ее степень захода, либо ее степень исхода равна 1. Следо- 44 Вательно, ))>,!: !Г(и($')= ~,()р,)= !)7(. Отсюда !(((рцГ), (1 е Гл. 9. Задача о максимальном потоке 220 Теорема 9.4.
Для простых сетей время работы алгоритма, представленного на рис 9.13, не превосходит 0()У(«!з (А1) Доказательсспво. Так же как в теореме 9.3, достаточно показать, что 5'=0(]У(0«). Опять если (Г1" (У)«~"-, то утверждение теоремы получается непосредственно. В противном случае рассмотрим этап, после которого величина потока первый раз превышает (Д вЂ” ) У(''; пусть и — величина потока в начале этого этапа.
Величина оптимального потока в Л/ (д) не меньше, чем )У10«, и, следовательно, по лемме 9.б ((~ У)' ' (заметим, что если Ж вЂ” простая сеть и г' — поток с компонентами 0 н 1, то Лг ()) также простая сеть; см. задачу 10). Поэтому до этого момента было не более ]У]«г«этапов и остается не более (У)«г«этапов. Следовательно, Я=О((У)«г«), н теорема доказана.
Г) Задачи 1. Опишите алгоритм, использующий некоторый вариант алгоритма ПОИСК для нахождения связных компонент ~ рафа О. Па завершении алгоритма вершины первой связной компоненты графз 0 должны быть помечены символом «1», второй компоненты — символом,2» и т, д. 2. Напишите вариант алгоритма ПОИСК, вьгясняющнГ«, является лн граф 0=(У, Е) лесом. Время работы вашега алгорн«мз должно быть 0(]У1), 3. ПУсть 0=(У, Е) — неко«оРый «Раф н аь и, и ~ Ь', ПУсть ПШ (и) и ПШ(ш) обозначают порядковые намерз, которые получаю| вершины и н ш при поиске в ширину из вершины а,. и пусть Л(и), д(ш) — длины кратчайших путей нз о, соответственно в и н щ Покажите, что из условия ПШ(и)~ПШ(ш) вытекает «((и) ке (ш). 4. Орграф 0=(У, А) называется сильно связным, если для лкбых е, и~ У су- ществует путь нз о в и и путь из и в о. Опишите алгоритм, который по данному орграфу 0=(У, А) определяет за время 0()А)), является ли 0 сильно связным.
5*. Приведите алгоритм со сложностью 0]А), находящий сильно связные компоненты орграфа 0=(У, А). 8. Приведите алгоритм са сложностью 0((Е)), определяющий, является лн граф 0=(У, Е) двудольг«ым. 7. Граф 0=(У, Е) называется дзусзязиым, если для любых двух ребер ег, е е Е существует цикл в графе О, содержащий как ег, так и ев. Приведите алгоритм со сложностью 0((Е1), определяющий, является ли данный граф 0=(У, Е) дву- связным. 8. Запишите поиск в глубину квк рекурсивные алгоритм (вспамните задачу 5 из гл.
8] без использования массива О. й. Пусть Л'=(з, 1, У, А, Ь) — некоторая сеть. Перед рм этапом алгоритма Форда — Фалксрсона нмее«ся некоторый поток, обозначаемый 17 1. На рм этапе находится увеличивающий путь ру в «]Г((у «), и ноток увеличивается вдоль этого пути иа бм где 67 — мнннл«ум допоянительных пропускных способностей по дугам пути рр Назовем дугу нугн рр имеющую дополнительную пропускную способ- ность 6ь )-перси»саком, а) Покажите, что если дуга (и, а) является рперешейком и 1'.перешейком для некоторых Р)1, то дуга (и, и) должна появиться в пути р; для некоторого /к.
<1(Р. Пусть теперь ру — »«ратчайшии путь нз з в 1 в сети «У(1» д на этапе 1. б] Покажите, что расстояние (т. с, длина кратчайшего пути в дг()Г)) нз з в лю- бую вершину ' с У не может убывать при переходе от одного этапа к следующему. 221 Комментарии и ссылки в) Пусть дуга (и, а) является /-перешейном и /'-перешейном для некоторых /')/, Покажите, что расстояние от з до / на этапе /' должно быть больше, чем иа этапе /.
г) Покажите, что при использовании правила выбора кратчайшего увеличивакнцего пути алгоритм Форда — Фалкерсона останавливается после 0((У! )А!) увеличений. !О. Покажите, что если А/ — простая,егь н / — поток а и с компонентами 0 н 1, го 51(/) также простая сеть 11. Покажите, что для следующих вариантов задачи о максимальном потоке существует полиномиальиый алгоритм Каждый аариаш сеодигле к исходной формулировке задачи о максималыюм потоке. а) Сеть имеет много источников н стоков б) Сеть неорнентнрованнэ в) Вершины наряду с лугамн нменп пропускные способности. г] Сеп неориентнровзнна, н вершины имеют пропускные способности. д*) Имеются как верхние, ~ак н нижние границы величины потока по каждой дуге.
!2. а) Покажите, что з-/-сяязность орграфа 0=(У, Я) (см. задачу 8 из гл. 6) можно вычислить за время О(!У! 6!А(), б) Решите задачу а) для неориентированного графа (прн том же определе. ннн з-/-связности]. 13. Связностью графа 6=(У, Е) называется минимум з-/-свяэнастей по всем парам з, /~ У а) Покажите, что для связносчи с(6) графа 6 выполняется неравенство с(6)~ ° с2!Е)/! У!.
бь) Покажите, что связность графа 6 можно найти, вычисляя не более с(6) Х Х! У! з-/-связиастей. в) Выведите из а) и б), ~то с(6) можно вычислить за время О(!У!'/з !Ез!). 14. а) Постройте сети /у=(з, ! У А, З) для бесконечного числа значений )У), на которых время работы алгорнзма, приведенного на рнс. 9.13, есть (1 (!!'!л), б) Постройте сети /у с единнчнымн пропускными способностями для беско. нечнога числа значений )У(, на которых время работы алгоритма, приведенного на рис.
9.!3, есть !!(!У! 6 !А!). й) Постройте простые сети АГ с единичными пропускными способносгями для беснонечного числа значений )У), на которых время работы алгоритма, приведенного на рнс. 9.!3, есть 0(! у(ыэ !А!) Кемментврии и ссылки Идея поиска по графу очень естественна н поэтому очень стара; см„например, ' ГВе! Вегйе С.
Тйеогу о1 Пгарйз апб пэ Арр1|са1юпз. (4ечг Уогй: Лойп эу!!еу Л! Зопз, !пс., !958. !Имеется перевод: Берж К. Теория графов и ее прнмене. ние.— Мл ИЛ, 1962,! Более интересные приложения поиска в глубину можно найти в работах (Та!! Тат!ап й. Е. Оер!й-1~гь! 5еагсй апб Глпеаг Пгарй А18ог!!йшз, Л. $! АМ Сагир., 1. Г(о.
2 (1972), !46 — 160 (Та2! Тат!ап й. Е Р!пб пй 0ош!па!огь !п 0йес!еб Пгарйз, Л. $!АМ Сотр., 3 (1974), 62 — 89. ГНТ1! Норсгой Л. Е., Тат/ап й. Е. О!чцйпй а Сггарй !п!о Тпсоппес!ес( Согпропепиь Л. 5!АМ Сошр., 2 (1973), 135 — 158. 'ГНТ2! Норсгой Л Е., Тат!ап й. Е. Е!!!с!еп! Р1аплгйу Тез()пй, Л. АС51, 21 (!974), 549 — 558. !Валави 4, 5 н 7 взяты нз !Та1!. Гл. 9. Задача о максимальном лошака Первым полиномиальным алгоритмом для нахождения максимального потока была модификация алгоритма пометок Форда и Фалкерсона, приведенная в задаче 9 и опубликованная в работе [ЕК] ЕсЬпопбз Л., Кагр $«. М.
Т1>еогеНса! !шргоеешепш !п А)йог)!Ьш)с Е!1)с!епсу 1ог Хебжог1«Г)ом РгоЬ!ешз, Л. АСМ, 19, $(о 2,1972), 248 — 264. Е. А. Диниц независимо обнаружил более быстрый алгоритм, используя идею увеличения однонременно вдоль многих путей [Ди) Диниц Е. А. Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой. — ДАН СССР, 1970, т. $94, йй 4, с. 754 †7. Несколько улучшенных алгоритмов приведено в работах: [Ка] Карзанов А. В. Нахождение максимального потока в сети методом предпо. токов.
— ДАН СССР, 1974, т. 215, йй 1, с. 49 — 52. [Че] Черкасский Б. В. Алгоритм построения максимального потока в сети с трудоемкостью 0(]$»]з]'!Е!) действий.— В сбл «Мате»«этические методы решения экономических задач». Сб. 7, 1977, Мл Наука. с. 117 — !26. [Оа] ОаИ 2. А Кеш А1йогй!тгп [ог (йе Мах)ша) Г!оь Рго)»)спц Ргос. !9!Ь 5ушр.
оп Гоцпг)алоиз о1 Согпрц1ег Зс!епсе, 1ЕЕЕ (Ос(оЬег $978), 23! — 245. [О/4] Сза)$! Х., $4аашаб А. Ме1шогй Г)о»ч ацб Пепе«а!!тед Ра[Ь Соп«ргезшоп, Ргос. 111Ь Апина! АСМ 5ушр, оп ТЬеогу о1 СошрцНпй, АСМ (Мау !979), 13 — 26. [5Ь] 58$)оасЬ У. Ап 0(п /1ойЧ) Махнпцш-Г!ом А!8ог)1Ьш, ТесЬ. Керог1 5ТАЬР С5-78-802, Сошри1ег Бс$епсе $>ер!., 51ап1ог«$ Оп)те«э)(у, 1978. Самый быстрый из известных алгоритмов для разреженных сетей принадлежит Слеатору и Тарьяну; см. (51] 8!еа1ог Т), $>. (неопубликованная диссертация, Станфордский университет, 1980).
В следующей таблице приведено время работы указанных алгоритмов. ,',«!' »! ! 1Сз! о($и)»»»$лР ! о()н)[л$!оз $! $> / о(! и$! л ! !оа ! Гр Для плотных сетей 0($$»$«) — наилучшая известная оценка. Алгоритм, приве денный на рис. 9.13,— это алгоритм из работьг [Ка] н значительно >прощенноь виде, как он представлен в рзботе [МКМ] Ма!Ьо1га )г.
М., Кшпаг М. Р., Майезй»чаг! 5. ЬЬ Ап 0($$»]») А)йо\!Ьш 1о Г«поЧпй Мах)шцш Г!оъз )п Ь)е1>чогйз, 1п1. Ргос. Ье((егз, 7, Ь/о. 6 (Ос1оЬе 19?8], 277 — 278. В том случае, когда сеть планарна, существуют более быстрые алгоритмы; см [!5] 11а! А., 58$)оасЬ '»'. Мах$шцгп Г!отч )п Р!апаг Ме!чгогйз, Л. 8!АМ Согпр., 8 $9о. 2 ($979), 135 — 150. Теоремы 9.3 и 9.4 и задачи 12 н $3 взяты из работы [ЕЦ Ечеп 5., Тат)зп К. Е. Ме(шогй Г!о>ч апб Тш(]пй Огарй СоппесНтйу, Л. 81А! Сагир., 4, Мо. 4 (1975), 507 — 518.
!О Алгоритмы для задачи о паросочетании Паросочсчпанием в графе называется множество ребер, никакие два из которых не имеют общей вершины. Задача нахождения в заданном графе паросочетания, имеющего как можно больше ребер, хорошо известна; в другом варианте даны также веса ребер и целью является нахожде1ше паросочетания, имеющего наибольшии суммарный вес.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
