Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 58
Текст из файла (страница 58)
Определение 12.5. Последовательность Я=-(е„е„..., е„) называется чередующейся относительно множества 7 Е й П К, если выполняются следующие условия. Гм 12. Оетовные деревья и моогроиды 302 Чер !. !+е, Е 2 и е,(1. Чер2. Для любого четного г, 2(1(т, справедливо ег ц ! и вРм(!Г+)5ы)г эРыг1). Черд. Для любого нечетного 1, 3<1<т, справедливо еф н врм (!О+5ге)=- Рог(! !в,) Кроме того, если гп иечетно и !Я5 Е рь', то 5 называется увеличивающей последовательностью. П Лемма 12.2.
Пусгь 5 — чередуюгцаяся последовательность. Тогда !) !(95гг Е81.' для четных г; 2) !С+)5п Е з для нечетных г Доказапгельство. !. Так как в,(! для нечетных г', то !Я5„: ь! для четных г'. Так как зр,(!+5„)=зР,(!), то ! и !Я5п имеют одинаковый ранг в йг, Так как ! независимо, т. е. имеет полный ранг в !гг, то !Я5п также независимо. 2, Случай нечетного 1 рассматривается совершенно аналогично. (З Таким образом, чередующиеся последовательности относительно независимого множества ! — это такие последовательности элементов из Е, чго стоящие в них на нечегных нес~ах элементы порождают циклы в У, разрываемые затем следующими элементами.
На. шей целью является поиск чередующихся последовательностей с использованием знакомого нам метода всггомогагельного орграфа для некоторого подходящим образом определяемого вспомогагельного орграфа, множесгво вершин которого совпадает с Е К сожалению, это невозможно, если опираться только на понятие чередующейся последовательности Эго связано с тем, что вспомогательный орграф, получаемый непосредственно из определения чередующихся последователшнютей, является дггнамическияг, т.
е. его нельзя зафиксировать заранее. Множество вариаггтов для продолжения построения чередующейся последовательности на каждом шаге может существенно зависеть ог выбора на предыдущих шагах. На рис. !2.!8 это проиллюстрировано на примере пересечения двух графических матроидов для графов Сг и !1. Здесь гИ вЂ” матроид, соответствующий О, и !гг — магронд, соответствующий Н.
Текущее независимое мно. жесгво имеег вид (о,, е,', е„ев)=1, Чередующиеся последовательности (е„е„ев! и !е„е„ев! имеют один и тот же последний элемент е„но совершенно различные продолжения. Первую можно продолжигь ребрами е,' и ео в то время как вторую можно продолжить ребрами е, и е, Никакой фиксированный вспомогательный граф не может отразить варианты, возможные в обоих случаях. Такая динамическая природа задачи о путях является иногда симптомом невозможносги простого решения задачи. (См.следующий параграф и гл. 15, где обсуждается задача о гамияьтоновом пути.) К счастью, в случае задачи о пересечении матроидов достаточно несколько ограничить определение чередующейся последовательности, /2.8.
//»реве»евсее двух натрвссдвв 303 чтобы получился подходящий статический вспомогательный орграф. Пусть дано / Е й П зь" и 1+е,(й. Через С; будем обозначать единственный М-цикл в 1+ес. Если 1+е,(зс, то через Рс будем обозначать соответствующий й/-цикл. "г 'е еь е5 Рис. 12лв. Определение 12.6. Последовательность 5 — -)е„е.„..., е ) .назы- ваесся правильной относительно / ц з () зс, если выполняются следующие условия. Пр1. /+е, Е Э и е,(1.
Пр2. Для любого четного г, 2<с'и т, справедливо есЕ/ и ее ЕРс,. КРоме того, е;АР», длЯ любого четного /г < г. ПрЗ. Для всех нечетных г, 3 = г < т, справедливо ее (/1 и е,, Е Сс. К роме того, е„, ~ С, для любого нечетного й < г. Кроме того, если т нечетко и /Я-,'5Е%;, то 5 называется правильной уве.ггсчссваюгцей сгоследовательностью. Лемма 12.3. Правильные последовательносспи являсотся чередуюгцилгися. Доказательство. Из Пр!, очевидно, следуег Чер( (см.
определение 12.6). Покажем, что из 1'!рЗ следует ЧерЗ. Представим /Я5сс для нечетного г в виде 1+е, +(е,— е,) + +... +(е; — ес,). Каждому заключенному в скобки слагаемому (е, — е/ ,) соответствует добавление некоторого элемента к 1 (+/ 5, / „ при котором образуется М-цикл (а именно цикл С„ так как е„,гс С/ для нечетных й < /), и удаление некоторого элемента из этого цикла, Однако по следствию 2 из теоремы 12.7 это не изменяет оболочки множества. Следовательно, ври (l Я 5ы) = = — врм (/+ е,).
Чтобы показать, что из Пр2 следует Чер2, представим /Д+5гс для четного г в виде 1+(ес,— е;)+(ес в — ес,)+... +(е,— е,). Гл. !2. Оетоеные деревья и ыатроиды Снова каждая скобка (е,— е,) содержит добавление некоторого элемента е,, к !Я~Я/~, о при котором образуется цикл О Цикл О, образуется именно при добавлении к !ЯЯ,, е элемента е „поскольку е» ~ О, для четных /г > !. Затем удаляется элемент е! из О,, Зееги операции сохраняют оболочку множества относйтельно матроида )(/ (см.
следствие 2 из теоремы 12,7), и поэтому эры(!ЯЕ„.)г эры(/). () Правильные последовательности образуют собственное подмно. жество в множестве чередующихся последовательностей. Читатель может проверить, что последовательность 5=-(ео е», е„е,, е,! из примера 12.13 является чередующейся, но не является правильной. Это следует из того, что е, Е О, в нарушение свойства Г!р2. Имеются две причины для определения этого ограниченного класса чередующихся последовательностей: !) их можно находить с помощью поиска в «статическом» вспомогательном орграфе; 2) при их использовании сохраняется гарантия, что будет достигнута оптимальность.
Например, существует правильная увеличивающая последовательность относительно леса из ордеревьев, представленного на рис. 12.17(а). Это последова»ельность Я'=-!е„е„е,). Множеством вершин нашего вспомогательного орграфа (Е, А) будет множество Е.
Каждый элемент е; ŠŠ— / будет кандидатом на нечетные позиции в правильной чередующейся последовательности 5. Если /+е;(Л, то находим С, и добавляем к А дугу (еп е,) для каждого е!Е С; — е, в соответствии со свойством !1рЗ. Если ! , 'е; Е 5, то е, может использоваться в качестве первого элемента в 5. В качестве последнего элемента последовательности Я может использоваться любой элемент из Š— !, такой, что !+е, Еус'; эти элементы будут нашими целями, и достижение любого из них будет указывать иа то, что найден правильный увеличивающий путь. Если же /+е, (Х, то, согласно свойству Пр2, добавляем к А дугу (еп е/) для каждого ее из О,— ео Пример 12.14. Построим вспомогательный орграф (Е, А) для леса !, состоящего из ордеревьев, представленного на рис.
12,17(а), Для этого просмотрим по очереди все элементы из Š— !. Начнем с е,. Так как /+е, Е Р, где 5 — матроид разбиения по концам дуг, то е, может быть начальным элементом последовательности Я. Кроме того, /-)-е,~уг', где уь' — графический матроид. Так как О, ==-,'е„е,, е,, е„', то добавляем к А дуги (е„е»), (е,, е,) и (е„е,). Для е„имеем !-'е,~3. Так как С»=-(е„е,), добавляем к А дугу (е„е,); так как !+е,(з(' и О»=(е„е„е,), то к А добавляются дуги (е„е,) и (е», е„).
Для е, замечаем, что /+е„Е 5, поэтому е„может быть начальным элементом последовательности Я Так как !+е,~К и О, -=(е„, е„е„), то к А добавляются дуги (е„, е,) и (е», е„). Аналогично, ! А-е, ( д и С. =- = (е„е,), а также /+е„( 5 и С,„= (е„, е„). 1(оэтому к А до- !2.д. Переееленлле двух латроидов бавляются дуги (е„е,) и (е„е,„). Наконец, У+е„!+е„цК, поэтому оба элемента е, и е„являются целевыми. Описанный вспомогательный орграф представлен на рис. 12.19. Заметим, ел е1 еэ е5 Рис. !2.!9. что орграф (Е, А) является двудольным, так как любая дуга идет из ! в Š— ! или обратно.
!, Оказываегся, что недостаточно найти какой-нибудь путь из 5 в Т во вспомогательном орграфе. Некоторые такие пути могут не ел ел еб ( ) ев ~С~~ е, Я (б) Рис. $2.20. соответствовать увеличивающим последовательностям. Это проиллюстрировано на рис. 12.20, где рассматривается еще одна задача об ордереве. Множество 1, которое нужно увеличить, выделено на рис. 12.20(а) жирными линиями.
Соответствующий вспомогательный орграф представлен на рис. !2.20(б). Заметим, однако, что путь 5=-1е„е„е„е,, е,! во вспомогательном орграфе не является увели. чивающим путем. При этом множество )+)5=-(еп ем ев, е,) не образует леса из ордсревьев — оно не является независимым в графическом матроиде. Причина состоит в том, что в рассматриваемом пути 306 Гл. 12. Оегоовные деревья и .яотроиды имеется падпуть, а именно 5'=!е„е„г,!.
Это означает, что для 5 нарушается свойсзво Пр2 — поскольку е, Е О, — т. е. эта последовательность ие являезся правильиой. Следовательно, чы должны использсвать поиск в ширину для нахождения во вспомогательном орграфе кратчайисих путейс из 5 в Т. Оказывается, что такие пути всегда будут праеильиыми и, следовательно, увеличивающими. Полиосзью описанный алгоризм приведен иа рис.
12.21. Чтобы показать коррекз кость этого алгоритма, необходимо виачале проделать некоторую прсдварительиую работу. Пусть Е, и Е„ таковы, что Е,() Е,=Е. Назовем рангом этой пары множеств (для фиксированных матроидов М и йс) число г(Е„ Е,)=-гм(Е,)+ + гн(Е,) Пусть / — произвольное множество из д П Ж. Лемма 12.4. гГЕо Е,)'=я(l!. Дпказателесписа. Г!усть усГ У П Е, и /ь=д П Е,. Так как у, и у, — независимые подмножества соотвессовеиио в Е, и Е„то г(Е„Е,) =глс (Е )+гк (Ес)) !.1, !+! Iс!) )у! С Пусть масроиды сИ и !ь' задаются алгоритмами о!о и и!д, и пусть С(!Е!) — верхняя оценка сложности этих алгоритмов при работе с задачами размера !Е !. Теорема 12.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
