Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 103
Текст из файла (страница 103)
Предположим, что Сд = (17, А) и Сн = (17, В) — леса графа С и что ~В~ > ~А~, те. А и  — ациклические множества ребер, и в множестве В содержится больше ребер, чем в множестве А. Мы утверждаем, что лес Е = (17р, Ер) содержит ровно ~)гр( — ~Ер~ деревьев. Чтобы понять, почему это так, предположим, что Е состоит из 1 деревьев, где 1-е 473 !лала Сб.
Жаднме алгорилсмм дерево содержит и, вершин и е, ребер. Тогда мы имеем (Ер(=~ е, с=с с (ос — 1) (согласно теореме Б.2) откуда вытекает, что С = 1с7р( — ~Ер1 Таким образом, лес С л содержит ))7! — )А! деревьев, а лес Сл содержит ٠— )В! деревьев. Поскольку в лесу Сл меньше деревьев, чем в лесу Сл, в Сл должно содержаться некоторое дерево Т, вершины которого принадлежат двум различным деревьям леса Сл.
Более того, так как дерево Т вЂ” связное, оно должно содержать такое ребро (и, и), что вершины и и и принадлежат разным деревьям леса Сл. Поскольку ребро (и, и) соединяет вершины двух разных деревьев леса Сд, его можно добавить в лес Сл, не образовав при этом цикла. Таким образом, структура Мел удовлетворяет свойству обмена, что и завершает доказательство того, что Мэ является матроидом.
Для заданного матроида М = (Я,Х) назовем элемент х сХ А расширением (ехСепзсоп) множества А Е Х, если его можно добавить в А без нарушения независимости, т.е. х является расширением множества А, если А с.! (х) е Х. В качестве примера рассмотрим графовый матроид Мо. Если А — независимое множество ребер, то ребро е является расширением множества А тогда и только тогда, когда оно не принадлежит этому множеству и его добавление в А не приводит к образованию цикла.
Если А — независимое подмножество в матроиде М, то, если у него нет расширений, говорят, что А — максимальное множество. Таким образом, множество А является максимальным, если оно не содержится ни в одном большем независимом подмножестве матроида М. Сформулированное ниже свойство часто оказывается весьма полезным. Теорема 1б.б Все максимальные независимые подмножества матроида имеют один и тот же размер. Доказательство. Докажем теорему методом от противного. Предположим, что А — максимальное независимое подмножество матроида М и что существует другое максимальное независимое подмножество В матроида М, размер которого превышает размер подмножества А.
Тогда из свойства обмена следует, что множество А расширяемо до большего независимого множества А с ! (х) за счет 474 Часть гк Усовершенствованные .иетоды разработки и анализа некоторого элемента х е  — А, что противоречит предположению о максималь- ности множества А. В качестве иллюстрации применения этой теоремы рассмотрим графовый матроид Мс: связного неориентированного графа С.
Каждое максимальное независимое подмножество Мсз должно представлять собой свободное дерево, содержащее ровно ~ Ц вЂ” 1 ребер, которые соединяют все вершины графа С. Такое дерево называется оетовньзм дерекам (зрапшпя 1гее) графа С.
Говорят, что матроид М = (Я, Х) взвешенный (зие(ййзед), если с ним связана весовая функция ю, назначающая каждому элементу х Е Я строго положительный вес ю(х). Весовая функция ю обобщается на подмножества Я путем суммирования ю(А) = ~ ~ю(х) есА для любого подмножества А к- Я. Например, если обозначить вес ребра е графового матроида Мс: через ю(е), то ю(А) представляет собой суммарный вес всех ребер, принадлежащих множеству А.
Жадные алгоритмы на взвешенном матропде Многие задачи, для которых жадный подход позволяет получить оптимальное решение, можно сформулировать в терминах поиска независимого подмножества с максимальным весом во взвешенном матроиде. То есть задан взвешенный матроид М = (Б, х), и нужно найти независимое множество А Е 1, для которого величина ю(А) будет максимальной.
Назовем такое максимальное независимое подмножество с максимально возможным весом оптимальнмм подмножеством матроида. Поскольку вес ю(х) любого элемента х е Я положителен, оптимальное подмножество всегда является максимальным независимым подмножеством, что всегда помогает сделать множество А большйм, насколько это возможно. Например, в задаче о минимальиом осшокном дереве (пип1шшп-зрапшпя-пее ргоЫеш) задаются связный неориентированный граф С = (17, Е) и функция длин ю, такая, что ю(е) — (положительная) длина ребра е. (Термин "длина" используется здесь для обозначения исходного веса, соответствующего ребру графа; термин "вес*' сохранен для обозначения весов в соответствукицем матроиде.) Необходимо найти подмножество ребер, которые соединяют все вершины и имеют минимальную общую длину. Чтобы представить эту проблему в виде задачи поиска оптимального подмножества матроида, рассмотрим взвешенный матроид Мс с весовой функцией ю', где ю (е) = юо — ю(е), а величина юо превышает максимальную длину любого ребра.
В таком взвешенном матроиде любой вес является положительным, а оптимальное подмножество представляет собой остовное дерево в исходном графе, имеющее минимальную общую длину. Точнее говоря, каждое максимальное независимое подмножество А соответствует остовному дереву с ~(7~ — 1 ребрами, и поскольку для любого максимального независимого 475 Глава 74 Жадыые алгаггыаывы подмножества А справедливо соотношение ла'(А) = ~~~ и'(е) еЕА = ~(иго — иг(е)) еЕА = (1й'~ — 1)гюо — ~ лл(е) еЕА = (~Ц вЂ” 1)иго — ю(А), независимое подмножество, которое максимизнрует величину ю'(А), должно минимизировать величину ла(А). Таким образом, любой алгоритм, позволяющий найти оптимальное подмножество А произвольного матроида, позволяет также решить задачу о минимальном остовном дереве.
В главе 23 приводится алгоритм решения задачи о минимальном остовном дереве, а здесь описывается жадный алгоритм, который работает для произвольного взвешенного матроида. В качестве входных данных в этом алгоритме выступают взвешенный матроид М = (Б, 2) и связанная с ним весовая функция ла.
Алгоритм возвращает оптимальное подмножество А. В рассматриваемом псевдокоде компоненты матроида М обозначены как М. Я и М. Х, а весовая функция— как и. Алгоритм является жадным, поскольку все элементы х е Я рассматриваются в нем в порядке монотонного убывания веса, причем элемент тут же добавляется в множество А, если множество А 15 (х) является независимым. ОКЕЕЮ л'(М, и>) 1 А=И 2 Отсортировать М.Я в невозрастающем порядке весов ш 3 аког Каждый х е М.Я в невозрастающем порядке весов ю(х) 4 1ТА15(х) Е М Т 5 А = А0(х) 6 ге4вгп А В строке 4 для каждого элемента х проверяется, останется ли А после его добавления независимым множеством. Если останется, в строке 5 выполняется добавление х в А. В противном случае х отвергается.
Поскольку пустое множество является независимым и поскольку каждая итерация цикла Ьг поддерживает независимость А, подмножество А всегда независимо по индукции. Следовательно, процедура Одеепу всегда возвращает независимое подмножество А. Вскоре мы увидим, что А является подмножеством с максимальным возможным весом, так что А представляет собой оптимальное подмножество.
Время работы процедуры Одеепу легко проанализировать. Обозначим через п величину ~Я~. Фаза сортировки длится в течение времени 0(п 1к и). Строка 4 выполняется ровно и раз, по одному разу для каждого элемента множества Я. При каждом выполнении строки 4 требуется проверить, является ли независимым множество А О (х). Если каждая подобная проверка длится в течение времени 0(5(п)), общее время работы алгоритма составляет 0(п 1к и + пДп)).
476 Часть 7К Усовершенствованные методы разработки и она|ива Теперь докажем, что процедура бкеепу возвращает оптимальное подмножество. Лемма 16. 7 (Матроиды обладают свойством жадного выбора) Предположим, что М = (Я,Х) — взвешенный матроид с весовой функцией ес и что множество Я отсортировано в невозрастающем порядке весов. Пусть х— первый элемент множества Я, такой, что множество (х) независимо (если такой х существует). Если элемент х существует, то существует и оптимальное подмножество А множества Я, содержащее элемент х. Доказательство. Если такого элемента х не существует, то единственным независимым подмножеством является пустое множество и доказательство закончено.
В противном случае предположим, что  — произвольное непустое оптимальное подмножество. Предположим также, что х ф В; в противном случае считаем, что А = В дает оптимальное подмножество Я, которое содержит х. Ни один из элементов множества В не имеет вес, больший, чем ю(х). Чтобы увидеть, почему это так, заметим, что из у Е В следует, что множество (у) независимо, поскольку В е Х, а семейство Х наследственное. Таким образом, благодаря выбору элемента х обеспечивается выполнение неравенства вс(х) > ю(у) для любого элемента у е В. Построим множество А, как описано ниже.
Начнем с А = (х). В соответствии с выбором элемента х множество А — независимое. С помощью свойства обмена будем многократно осуществлять поиск нового элемента множества В, который можно добавить в множество А, пока не будет достигнуто равенство ~А~ = ~В(; при этом множество А останется независимым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
