Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 56
Текст из файла (страница 56)
В конзрпримере на рис. 12.!2 (в и г) жадный алго- !2.4. Матроиды ритм приводит к пути, представленному на рив. 12.12(г), а оптимальный путь имеет вид, представленный на рис. 12.!2(в) () Пример !2.6. В следующем примере система (Е, У) имеет несколько другой характер В ней Š— зто множество столбцов (аХ (б) (а) (т) (в) Ряс !2.12. ж(Е!)-матрицы 4 и 5 — семейсэво аинейно незивисильи множеств столбцов ма~рины 4 Для примера, приведенного на риа.
!2 13, имеем (еь е„ея, е„)Е5 в го время как (еи во е„ем)(5 и (ео е„ е,)(9 Решаез ли жадный алгоритм комбинаторную задачу оптпмп эапии, связанную алой лкнияпяпи,й системой подмножеств? Довольню уди- Рис 12.13 вительно, 'по отве~ положителен. Этот факч будеэ получен в примере 12.9 как простое следсзвие рассматриваемых дал~с в э~им пара. графе конструкций и элементарных фактов из линейной алгебры ! э Рассмотренные выше примеры указываю1 на интересный испек ь Некогорые из рассмотренных сне~ем подмиожесгв (например, сис. темы из примеров !2.2, 12 4 и !2.6), хотя сильно различаются по природе и происхождению, облалаю~ общим важным свойствим; 1.
адпый алгоритм решае~ соо~ве~сэвующие комбина~орпые задачи Гл. !е. Оеыовяые деревья и маыроиды оптимизации. В противоположность этому другие системы подмножеств не обладаютгаким хорошим свойством. С помощью контр- примеров мы показали, что комбинаторные задачи оптимизации для систем подмножеств из примеров 12.3 и 12.5 ие могут быть решены с использованием жадного алгоритма.
Это важное различие формализовано в следующем определении. Определение 12.2. Пусть М=(Е, д/ — система подмножеств. Будем называть М митроадолг, если жадный алгоритм корректно решает любую индивидуальную комбинаторную задачу оптимизации для системы М. Д Таким образом, система подмножеств (Е, У! из примера 12.2 являегся магроидом; ее называют григ/гическим матроидом, учитывая ее интерпретацию в виде системы лесов графа.
Система (А, З) из примера 12А также есть матроид; в дальнейшем мы назовем его матроидом разбиения (см. пример 12л8) Иаконец матроиды, аналогичные матроиду из примера 12.6, известны как магпричные матроиды. Исторически понягие матроида было впервые введено как обобщение этого подкласса, использующее некоторые простые аксиомы, Следующий результат показывает эквивалентность этих двух подходов. Теорема 12.5.
Пусть М -(Е, Ю) — система подмножеств. Тогди следугви(гге утверждения эквиваленпгны. ! ) М вЂ” матропд. 2) Егли („(,,ЕР, где )(ргг=Р и )( +;(=Р+1, то сУгЦе. сгпггг!еггг такой' элемент еЕ (р„— (р, что /р+е~ 7. 3) Если А — подлгножеггпво множества Е и (, (' — макеимильныг пп вклгочрнпкг подмножестеа множества А, гпв )('~=!!). Доказательство. (! ) => (2) . Предположим, что М вЂ” матронд, но 12) нс выполняется, т.
е. существуют такие два независимых подмножесгва (, (р+„что ! !р! = р, ) lрег )= р+ 1 и нн для какого еЕ( „— ( подмножество !,+е не является независимым. Рассмотрим следующие веса иг на Е: р+2, еЕ (р, аг(е)= р+1, еБ! „— /, О, .( !,гг/„„, Замегим вначале, что (р не оптимально, так как и(/р„г)) )(р.!.!)е)р(р+2).=иг(/„).
Жадный алгоритм в этом случае начнет с выбора всех элементов множества (, поскольку эти элемснты имеют максимальный вес. После этого жадный алгоритм не сможег улучшить общий вес, так как для всех остальных элеменгов е либо („+е(Л (если е ц!„,), либо иг(е)==0. Следовательно, жадный алгоритм дает неоптимальное решение (, и поэгому М не ягляетгя /2.4. Матроидм матроидом, что противоречит нашему предположению.
Таким образом, рассматриваемая имплпкация доказана (2)~(3) Предполшьим, что (2) выполняеггя, и пусть 1, 1'— два максимальных по включения~ независимых подмножества множества Ас:-Е Допустим, чго (1~(11'!. Отбрасывая (1'! — )1! — 1 элементов из 1 (напомним, что 7 замкнуто относительно включения), можно получить такое множсство 1"~1', что (1"(=!/!+1. По свойству 2 можно найти элемент . б 1" — 1, ~акой, что 1+гЕ.7. Следовательно, ( ие являечгя максимальным по включению независимым подмножелвом множесгва Л Полученное противоречие доказывает требуемую импликацию. (3)~(!) Допустим, что свойство 3 справедливо для М, и покажем, что тогда жадный алгоритм решае~ М Предположим, что это не так; т. е предположим, чго для некогорого множества весов гв(г), «Е Е, жадный алгоритм приводит к независимому множеству 1= — (е,, е,,, ..., е,), в то время как существуег множество l= (г„г„ ..., е/) ц,7, такое, что ш(11)щ(/).
Будем считать, что элементы множеств 1 и l упорядочены гак, что щ(е,))ю(е,.))....>ш(г;) и га(е,'))щ(г,'))...)ш(е,') Можно считать, что 1 — максимальное по включению независимое подмножество и Е По построению 1 максимально по включению, поэтому из свойства 3 (при Е =-Л) вы~екает, что /--1 Покажем, что для всех гп:=1, 2,, 1 вьшолняе~ся неравенсзво ш(г ))ю(г„',), что будет противоречить нашему предположению о ~ом, что щ(1))ш(/). Доказательство проведем ин. дукцией по т.
Для ш=) узверждение справедливо. Прегшоложим теперь, что га(е )(ю(е') для некоторого т=»! и га(г,))га(г,') для з=1„..., т — 1. Рассмотрим множеств А =(еЕ Е: ш(г))и(е') ). Множество (г„, е ~) является максимальным по включению независимым подмножеством в А, так как если (г„е„, е „е) Е,7 и ш(е)~ш(г„',))гв(е ), то жадный алгорим должен был бы выбрать е вместо е в качестве следующего элемента множества 1. Это противоречит свойству 3, поскольку (е,', ..., е„') — другое независимое подмножество в А большей мощности. Этим завершается индукция и все доказательство. Г) Определение 12.3. Пусть М=(Е, 7) — матроид и А~Е. Рангов г (А) множества А в М называется мощность максимальных по включешпо независимых подмножеств множества 4 Заметим, что, согласно свойству 3 из георемы 12.5, все такие подмножества в А имеют одну и гу же мощность, и, следовательно, ранг всегда определяется корректно.
Максимальные по включению независимые подмножества множества Е называются базисами. Отметим, что в силу замкиутосзи 7 относительно включения М полностью определяется семейством 73 его базисов По заданному Я семейство 7 можно восстановить следующим образом: 5= «1: 1«=/) для некоторого ВЕЗ). Г) Определение !2.4. Подмножество 0 множества Е, не входящее в Ю, называется зпвисилыл. Минимальное по включению зависи- Гл. 12. Остовные деревья и мотроиди мое подмножество С в Е называегся циклом. Оболочкой множества А называется максимальное по включению множество 5, содержащее А и удовлетворяющее условию «(5)=-«(А).
Ниже приведены два интересных свойства матроидов. Первое является обобщением предложения 1.2. Теорема 12.6. Пусть (Е д и еЕ Е. Тогда либо (л-еЕ и', либо 1+е содержит единспюенный цикл. Доказательство. Предположим, что!+е1/Э. Пусть С= (с: 1+е— — с Е 7). Утверждается, что С вЂ” цикл. Во-первых, это подмножество зависимо: в противном случае можно было бы увеличить его до базиса в! -ге (заметим, что Со=( 1 е), который должен был бы иметь мощность )l ~ и, следовательно, имел бы вид (1 е — д, но это абсурдно, так как тогда д Е С.
Во-вторых, С минимально, так как при удалении любого его элемента, скажем с, получается подмножество С вЂ” с, содержащееся в независимом подмножестве 1-~е — с. Для доказательства единственности предположим, что Р— другой цикл в (-ге и в С вЂ” Р имеется некоторый элемент с. Тогда Р является подмножеством /-)-е — с"и, следовательно, независимо, что противоречит нашему предположению. ) ) Теорема 12.7. Любое подмножество А =Е имеет единтпвенную оболочку, определяемую следуюи(им образам: эр(А)== (е: «(Л-ье)=:= =«(А) ). Доказательство. Если Я вЂ” оболочка подмножества А и еЕ Я, то «(А-ье)=«(Л).
Ибо в противном случае если «(А -,е))«(А), то «(5))«(А+е))«(А); приходим к прогиворечию. Следовательно, Е~эр(А). Остается показать, что «(эр(А)) =«(А) Нетрудно по. нять, что общий базис двух множеств является базисом их объединения. Поэтому базис множества А является базисом в зр(А), так как он является базисом в А+е для каждого е Е зр(Л).
Следствим) 1. зр(А) являетгя объединением А и всех циклов, все элементы которьсх, кроме одного, содержтпся в А. Следствие 2. Если ( Р 2, /л-е~р и с принадлежит циклу в (-1-е, то зр(/)=-зр((+е — с). Пример 12.7. Если У вЂ” множество лесов графа 6 — -(1«, Е), то /(Ло=(Е, У ) — графический матроид. Циклы в М«; — это (теоретико-графовые) циклы графа 6. Легко видеть, что ранг подмножества Е' из Е равен «(Е')=-) Ц— — с(Е'), где с(Е') — число связных компонент графа 6'=-()«, Е') Оболочка зр(Е') подмножества Е' из Š— это наибольшее подмножество, содержащее Е' и имеющее тот же ранг, что и Е'. Пп- 12.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
