В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 18
Текст из файла (страница 18)
Если . — набор независимых множеств матроида М =(Е, ), элементам которого приписаны неотрицателы1ые веса, то жадный алгоритм находит в множество максимального веса. Очевидно, что жадный алгоритм строит базу; пусть это база Вг=(е1, ег, ..., е,), ш(е1)) ш(ег)~...) ш(е,). 93 Остается покааать, что вес базы Во максимален. Пусть это нс так. Среди всех баз максимального веса выберем такую базу В, которая имеет наибольшее число общих элементов с Вг.
Так как ВчеВе и !В! = !Вз), то Во~В чь Ф В. Выберем в Во~В элемент е; с минимальным номером й Множество В !! е, содержит цикл С. Так как база матроида циклов не содерягит, то существует е ~ С ~ Во. Пусть В' =(В~е) !! ее Множество В' пе содеряьпт циклов, поскольку С вЂ” единственный цикл в В 0 е~ (следствие 16.7). Кроме того, !В'! = !В!.
Следовательно, В' является базой. Далее имеем В ЙВо =(ВПВо)0 е„!В й Вг! > !ВПВо!. Поэтому и (В')( ш(В), (1) иное противоречило бы выбору базы В. С другой стороны, ш(В ) = ш(В) — ш(е)+ ш(е,), поэтому из (1) вытекает, что ш(е)) ш(е,). Но последнее неравенство неверно, поскольку на 1-м шаге алгоритм выбрал еь а не е. Полученное противоречие доказывает теорему. 0 Из приведенного выше доказательства вытекает, что жадный алгоритм поясно трактовать как следующуьо процедуру получения базы максимального веса в матроиде: выбираем элементы матропда в порядке невозрастания весов, отвергая лишь те элементы, добавление которых наругнает условие независимости получаемых множеств.
Аналогично работает жадный алгоритм и для получения базы минимального веса, только при этом элементы матропда выбираются в порядке неубывання весов. Заметим, что приведенное здесь доказательство предыдущей теоремы буквально то же, что и доказательство теоремы 15.1, обосновывающей алгоритм Краскала. Оказывается, верна теорема, в некотором смысле обратная предыдущей.
Теорема 23.2. Пусть Р— набор подмножеств ко~ьечиого множества В, обладающий тем свойством, что если Хяр, У с Х, то Уяр. Тогда, если Г не является набором независимых лтожеств матроида, то применение к Г жадного алгоритма гге гара~ьтирует получения подмножества максималы*ого веса. С' Пусть для набора Р не выполняется аксиома 1.2, т. е, в Г есть такие Х = (хп хг, ..., хь+~), У = (уп уг, ° ° ° ..., у„), что не существует х~шХ~уь для которого У 0 х;~ иР. Покажем, что в атом случае можно так подобрать 94 веса, что жадный алгоритм построит множество не максимального веса.
Пусть ю(у>)=1 ((=1, й), ю(х>)=8, если х>~нХ>У, где О < г < 1, и> (е) = О, если е я Е>>(Х О У) . Тогда жадный алгоритм построит сперва мнонгество У. Так как отсутствует такой элемент хь что У 0 х; >и г", то далее алгоритм выберет элементы из Е'>(ХО У) и закончит работу, получив в результате множество Хе, вес которого равен весу множества У. Пусть !ХО У) = р.
Тогда ю(Х)=р — (й+1 — р)й Поэтому, учитывая, что ю (Хе)= й, можно выбрать О < ( < 1 таким, чтобы было ю (Хе) < ю (Х) . Тем самым жадный алгоритм не находит в р множества максимального веса. 0 5 24. Объединение и пересечение матроидов Пусть ЛХ> и Мг — два матроида на множестве элементов Е с наборами независимых множеств > и . г соответственно. Положим , = (ХО У: Хгн. >, Уги%). Как показывает прямая проверка, множество удовлетворяет аксиомам независимости. Следовательно, (Е, )— матровд, для которого служит набором независимых моожесте.
Этот матроид называется объединением митроидов М> и Мг и обозначается через ЛХ> Н Мг. Очевидно, что операция объединения матроидов ассоциативна, и можно говорить об объединении нескольких матроидов. Теорема 24.1. Пусть (ЛХ>.' ( = 1, й) — семейство матроидов, определеннь>х на одном и том же множестве Е, с роиговыми функциями р, соответственно, й) 1, М— объединение всех этих матроидов. Тогда ранговая функция р матроида М определяется для любого подмножества Х вЂ” Е равенс~вом р (Х) = п>(п (р, (А) -(- р, (А) + ... + р„(А) + ! Х'~Л ф. (1) лах г Рассмотрим отдельно два случая.
1. р(Х)=!Х). В этом случае р(Л) =!Л! для лз>бого подмножества А '= Х. Очевидно, что р (А) < р> (А)+рг(А)+... + р,'(А)', поэтому р,(А)+р,(А)+...+р„(А)+ )Х~А! >р(А)+ !Х~А)- = )А!+ !Х~А! = )Х! =р(Х). Прн А = О получаем р1(А)+ рт(А)+... + р,(А)+ !Х~А ! = !Х! = р(Х). Равенство (1) доказано. 2. р(Х) ( !Х!. Воспользуемся индукцией по я.
Вначале пусть й = 2. По определению р(Х) = )В!, где  — максимальное независимое подмножество в Х. Очевидно, что В = (В й А) 0 (В П (Х~А ) ) для любого А — Х. Так как !В ПА! ~р(А)(р1(А)+рт(А), )В П (Х~А) ! ~ )Х~А 1, то для любого А ': — Х р(Х)= !В! = !В ПА!+ !ВП(Х~А) ! ( ~ р1(А)+ рт(А)+ )Х~А!. (2) Теперь получим нижнюю оценку для р(Х). Пусть Мз — копия матроида Мм определенная на множестве Е', имеющем пустое пересечение с Е. Более точно: Е = = (е„е„..., е„), Е' = (е„е„..., ев), Е О Е' = 8, множество (е~, ..., е~ ~ независимо относительно матрон- 1' да ЛХ, тогда и только тогда, когда (е;, ..., е; ! независимо относительно Мь Очевидно, что можно определить матроид на множестве Е 0 Е', объявив его независимыми множествами объединения Х 0 У, где Х ез Е независимо относительно матроида Мь У': — Е' — относительно М,.
Обозначим этот матроид и его ранговую функци1о через М, Ц Лт, и р соответственно. Пусть теперь Х вЂ” произвольное подмножество множества Е. Положив Я; = (еп е;), Я =(К: е, ~ Х), получим семейство Я подмножеств множества Е 0 Е'. Согласно следствию 22.2 для любого ~ ~ !Х! частичная трансверсаль мощности Г семейства Я, независимая относительно матроида ЛУ, !.! М„существует тогда и только тогда, когда для любых г подмножеств Е; выполняется условие р'(Я; () ... !) Я,))г+С вЂ” /Х!, г=1,)Х!. (3) Объединение множеств, заключенное в скобки, предста- 96 вим в виде А 0 А', где А — Е, А' ж Е'. Ясно, что р'(А 0 А') = р~(А)+ рт(А)', 1Х! — г = 1Х~А1, поэтому условие (3) можно переписать так: р~ (А)+ рз(А) > г — 1Х~А1. (4) С другой стороны, легко понять, что следующие два утверждения равносильны: т) существует частичная трансверсаль мощности ~ се- мейства подмножеств о', независимая относительно мат- роида М, () М,; 2) р(Х)) ~.
В самом деле, пусть Т вЂ” такая трапсверсаль и пусть, для определенности, Р Т= !е„..., ею ер~.м ..., с~1, е;~ Е, е; е- =Е'. (5) Тогда (ез, ..., ег) ~ Р(ЛХ,), (е ь, ..., е~) е— : У (М,), (е ь ..., е,) ~н.Т(Ме) и, следовательно, (еп ..., ею е,+ь ..., е,) ~п У(М~ У Мз), (6) т. е. выполняется условие (2). Обратно, если выполняются условия (2) и (6), причем (еп ..., ег) ~иР(М,), (е,.ь ..., е,) жУ(Мз), то множество Т, определяемое условиями (5), является частичной трансверсалью мощности 1 семейства подмножеств 8, независимой относительно матроида Мт () М,. Равносильность утверждений 1) и 2) доказана. Из предыдущего вытекает, что р(Х) ) ~ тогда п только тогда, когда для любого подмножества А множества Х верно неравенство (4).
Следовательно, при ~=р(Х)+1 в Х существует такое подмножество Ао, которое не удовлетворяет неравенству (4), т. е. р~ (Ао)+ рз(Ае) ( р(Х)+ 1 — 1Х~Ао!, откуда (7) р(Х) ~ р~ (Ао)+ рт(Ао)+ 1Х~Ао1. Из (7) и (2) вытекает р (Х) = р~ (Ао) + рз(Ао) + 1Х~Ао1. 97 7 в. м вмевичев и аю Последнее равенство в сочетании с неравенством (2) лриводит к формуле р(Х) = шгп(р,(А) + рг(А) +1Х' А1). лгхх Для й = 2 теорема доказана. Пусть теперь й ) 2 и теорема нерпа для обьедпнепня менее чем й матрондов.
Если р — ранговая функция объединения ЛХ~ 0 Мг Б... 0 М„ц то в силу доказанного выше н индуктивного предположепия имеем о(Х) = ~пш (р'(В) + р, (В) + 1ХчВ1) =- ос х = пни (пни (р, (А) + ... + рь-г (Л) + 1 В ', А 1) + вьх ~лпв + р,(В) +1х,в1). Поскольку Л вЂ” В и 1В~Л1+1Х~В1=1Х'Л1, то рассматрпваемьш минимум достигается лишь при Л =В, и потому получаем р(Х) = пнп (о, (Л) -1- ... -1- рк(А) + 1Х" А1).
З л.х Ниже через (Е, р) обозначается матроид с множеством элементов Е и рапговой функцией р. Следствие 242. Матроид (1.", р) имеет 1 попарно пепересекаюигихся баз тогда и только тогда, когда для любого Л сеЕ верно неравенство Ур (А) + 1А1 ~ Ер (Е) . С Пусть (ЛХ вЂ” объедпнезше 1 экземпляров матроида М, р' — рапговая функция этого объединения. Очевидно, что р'(РЛХ) - Ур(М) и ЛХ имеет 1 попарно пепересекаюшихся баз только прп условии р'(УЛХ)=)р(М). Теперь нужное утверждение непосредственно вытекает из предыдугцой теоремы. 0 С л е д от в и о 24.3.
Для представи кости мноисества Е в виде объединения не более чем 1 независимых подмножеств матроида ЛХ=(Е, р) необходимо и достаточно, чтобы любое подмножество Л ': — Е удовлетворяло условию 1Л1 - (р(А). (9) с' Множоство Е представимо в виде указанного объединения только тогда, когда р'(РМ) = 1Е1. Согласно теореме 24Л последнее равносильно неравенству 1Е1 ~ ~1р(Л)+1А1, в свою очередь равносильному неравенству (9).
0 98 Применим два предыдущих следствия к циклическому матроиду М(6) непустого графа 6. В рассматриваемой ситуации независимыми множествами матроида служат множества ребер ациклических подграфов. Объединим каждый такой подграф со всеми не входящими в пего воршинами С и будем считать подграф остовным. Для любого остовного подграфа П верно равенство р(М(Н) ) =— = п(6) — 1с(Н). Если Н вЂ” остовный подграф с множеством ребер Л, то неравенства (8) и (9) превращасотся в неравенства тп(С) — т(Н))1(й(Н) — й(6)) (10) и, соответственно, пс(Н) ~ 1(п(С) — 1с(Н) ) . (11) Поэтому верны следующие два утверлсдения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
