Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 57
Текст из файла (страница 57)
Маигроиды 297 этому зр(Е')= ([и, и! Е Е: о и и лежат в одной и той же компоненте графа 6'=-(г', Е')). Пример 12.8. Пусть Š— конечное множество и П вЂ” разбиение множества Е, т. е. семейство непересекающихся подмножеств множества Е, покрывающих Е; П вЂ” -(Е„Е„..., Е,). Будем называть подмножество ! из Е независимым (l Е 7) в том и только в том случае, если никакие два элемента из 1 не лежат в одном и том же множестве разбиения 11, т.
е. !! П Е;( -=-1, 7 = 1, 2, ..., р. Тогда система Мп =.(Е, Л) является матроидом, называемым матроидолс ризбиения. Чтобы показать, что Мп — матроид, достаточно показать, что для него имеется хорошо определенная функции ранга. Пусть з(А)=(1(р: Е7!) А ~ И). Читатель может легко проверить, что г(А) =, 'з'(А)~ является требуемой функцией ранга, поскольку для данного А можно построить максимальное по включению независимое подмножество в А, выбирая по одному элементу множества А из каждого Ем с которым А пересекается. Например, если Е =-,'е,, ..., е,) и П= ((е,), (е„е,), (е„е,), (е„, е„е,)), то ранг множества А=-(е,, е„е,, е„е,) в Мп равен 3; максимальным по включению независимым подмножеством в А является 7=(е,, е„е,). Оболочка множества А определяется формулой зр (А) =- 0 !елл> Ер Циклом в Мп является любое множество, состоящее из двух элементов одного и того же Е~., так (е,, е,) и (е„, е,) — циклы.
Чтобы получить другой пример матроида разбиения, вернемся к системе подмножеств, обсуждавшейся в примере 12А. Согласно нашему определению, множество В дуг орграфа О, представленного на рис. ! 2.11, независимо, если никакие две дуги из В не имеют общего конца. Зто эквивалентно разбиению дуг орграфа 0 в соответствии с тем, какая вершина является их концом. Для нашего примера это разбиение имеет вид П=-(((о,, и,), (о„о,), (и,, и,)), ((пз "г) (пг ое) ).
((иг па) ), ((вм и,) ), ((пг, и,) )). Следовательно, эта система является матроидом разбиения Мп, называемым митроидом разбиения по концам дуг для орграфа 0'), и тот факт, что жадный алгоритм решил эту задачу, был вполне естественным. Д Пример 12.9. В митричном матроиде Мл=(Е, У) множество Š— это множество столбцов некоторой (п х !ЕГ)-матрицы А, а 5— множество линейно независимых подмножеств множества Е.
Элементы матрицы А могут быть элементами любого поля К. Система подмножеств М„является матроидом, так как для нее выполняется свойство 3 теоремы !2.5. Зто следует из хорошо известного факта линейной алгебры: г) Маасроид разбиения яо началам дуг для 0 определяется англогинно. Гл, 12. Овтовныв дврввьл и мовгроиды 298 все максимальные линейно независимые подмножества множества векторов Е' имеют одинаковую мощность.
12.5 Пересечение двух матроидое Вернемся еще раз к задаче о паросочетании в двудольном графе. Пример !2. !О. Рассмогрим двудольный граф В=-(!г, (/, Е), представленный на рис...12!4, и множество ыгь" паросочетаний в В. ЯВЛяЕтСя ЛИ Пара 1Е, овь) МатрандОМУ Если бы (Е, Ф) была матроидом, то для нахождения паросочетания в лвудольном графе 1 нас был бы алгоритм намного более простой, чем построенный в предыдущих главах. Сущность матроидной струкгь туры состоит в том, что любое максиггС~-гг мальнвв по включвнигв независимое множество является также миксимальньгм г пв числу элемвнвгав.
Задача нахождения О в максимальных по включению независим г мых подмножеств тривиальна: доста- 44 ~очно добавлять элементы до тех пор, пока это возможно. К сожалению, (Е, гг4 ь' г мь) не матроид. Это легко доказывается ог тем, что паросочетание, представленное на рис. !2.14, макси,вольно пв включеинс. г2, гв. нию, но не ыаксггмально по числу олеменпгвв.
1см нс менее огь обладает довольно хорошей сгруктурой: оно являегся ггег вгсчгнггвгг двух магроидов, Другими словами, можно найти два магрогггга;р1.-(Е, у) и Лг=(Е, К), такие, что аФ=в П з!,'. Оба магронда Л4 и Л' являются матроидами разбиения. Матроид М определяется разбиением П, подразделением элементов множества Е на подмножесгва в соответствии с тем, какой вершине из (г они инцидегпны, 11агример, для графа, представленного на рис. 12.!4, Пг,=-. ((в„вь, в„), (вю вв), (в,), (в„е,), (в,)). Аналогично, матроид ргзбггеьния Лг соогвегсгвует разбиению Пи=-((в„е,), (е„, в„ еь), (е„с,гг, (в„вьЦ. Петр)дно понять, что подмножество 7 из Е яв- гг г Эта мощность в линейной алгебре называется рангом подматрипы А', определяемой множеством Е'.
С) Матричные матроиды образуют более широкий класс, чем графические магроиды н матроиды разбиения. Можно показать, что любой графический матроид или матроид разбиения представим матричным матроидом, если подобрать соответствующую матрицу А над некоторым полем К (задача 12). Однако это верно не для всех матроидов (задача 13); поэтому теория матроидов является суигеспгввнным обобщением линейной алгебры. /2.д. Пересечение двух матроидов Рис.
12.15 ляется паросочетанием тогда и только тогда, когда оно независимо в М (т. е. никакие два ребра из / не имеют общей вершины в и') и в Л' (т. е. никакие два ребра из / не имеют общей вершинь1 в (/). Следовательно, в»=а ПМ Таким образом, задачу о паросочетании в двудольном графе можно рассматривать как задачу нахождения максимального подмножества в Е, независимого в двух ма« роидах. 11 Пример 12.11. Орграф 0=(г'. А) можно использовать для пред.
ставления управлений в группе людей. При этом каждый человек изображается вершиной, и дуга (а, и) означает, что а «оказывает влияние» на и. Обычно такая ситуация оказывается хаотичной (см. рис, 12.15). На одного человека могу«оказывать влияние несколько человек, и эти влияния могут быть противоре- о, о» чивыми (как в вершине а„уп.
равляемой вершинами а„о„а,). Кроме того, в такой структуре возможны циклы (например, ори- »1 ентированный цикл (во а„ а„ а„ »5 о« и,)) или закаричивания (подобно дуге(го а,), которая закорачивает путь (о„а«, а,)). В такой ов струк1уре может не быть явного лпд«ра. — вершины, в которую не входит ни одна дуга. Иногда требуется организовать такую группу людей в ордерева.
Ордерево — это орграф (1', В), В: — А, без циклов и закорачиваний; граф 6=($', Е„), получаемый при игнорировании ориентации дуг из В, является деревом. Кроме «ого, в каждую вершинув кроме лидера — должна входить ровно одна дуга Например, жирные линии на рис. 12.15 образуют ордерево. Задача состоит в том, чтобы по данному орграфу 0.=($', А) определить, существует лн в А подмножество В, образующее ордерево. Эту задачу можно также сформулировать как задачу нахождения максимального множества, независимого одновременно в двух матроидах. Один из этих матроидов — это графический матроид орграфа /), получаемый при игнорировании ориентации.
Второй— это матроид разбиения по концам дуг для орграфа О. Должно быть очевидным, что любой лес, составленный из ордсревьев, будет лежать в пересечении этих матроидов. Поэтому А содержит некоторое ордерево В в том и только в том случае, если максимальное множество, независимоевэтих двух матроидах, имеетмощность 1$'~ — 1. Д Пример 12.12. Даны два графа 6 и 6', ребрам которых сопоставлены имена из одного и того же множесгва Е.
Такая ситуация представлена на рис. 12.!6. Ищется наибольшее подмно»,ество множества Е, ациклическое как в 6, так и в 6.'. Очевидно, ч1о это опять Гя. 12. Осаавные деревья и маяроиды задача нахождения множества наибольшей мощности, независимого в двух матроидах, а именно в графических матроидах Ми и Мп, Д В этом параграфе мы пос1роим алгоритм для нахождения по двум произвольным данным матроидам М=!Е, Ю) и 11/=!Е, К) наибольшего множества в Ю/)К Поскольку задача о паросочетанин е, ев ея ез (, > Рис. 12.16.
В днудОЛЬНОМ ГрафЕ яВЛНетСН ЧаС1ИЫМ СЛуЧаЕМ ЗадаЧИ О ЛЕрЕСЕЧании мпитроидов, полезно вначале вспомнить методы, развитые в ч 10.2 для решения этой задачи Задача о наросочетании в двудольном графе решается с помощью многократных увеличений, при которых используются увеличивающие пути для нахождения все больших паросочетанпй — в нашей новой нерминологии множеств, независимых одновременно в двух матроидах М=!Е, а) и Л(=!Е, зс) из примера !2.!О Например, 5=!еы е„ем е„е,1 — увеличивающий путь относительно паросочетания (, представленного на рис. !2.!4. В свете формулировки нашей задачи с использованием матроидов можно по-иовому представя~ ь, как 5 действует на (, увеличивая его в результате до (®5. Вначале / превращается в (+е,, затем в /+е,— е„ /+е,— е,+е,„ (+ е,— е,+е,— е,; наконеп, в (Я5=-/+е,— е,-1-ея — е,-! е, Первый элеь:ент е, пути 5 выходит из свободной вершины множества Г; поэтому (+е, независимо в М Однако (+е, не является независимым в Л' — в противном случае наше увеличение было бы уже закончено.
Образуется цикл мавроида Л/, а именно (р„е,). Далее, 5 еразрывае~» этоз цикл, удаляя е„что приводи~ к /+е,— ее Новое множество независимо как в М, так и в Л', однако имеет ту же мощность, что и исходное множество ( Поэтому мы опять пытаемся найти ребро !в данном случае ев), добавление которого не нарушает независимости в М, но, возможно, порождает цикл в Л', и затем разрываем этот цикл (удаляя е4).
При этом мы надеемся, что в конце концов придем к ребру, при добавлении которого сохраняется независимость как !2.5. Пере««чение деде иатроидое в М, так и и Л', в результате чего ! увеличивается. Эго происходит иа следующем шаге, поэтому е„— последнее ребро в 5. Аналогичным образом можио определить увеличивающие последовательности для произвольных матроидов М и Л', что иллюстрируется в следующем примере. Пример 12.13.
Пусть требуется увеличить составленный из ордеревьев лес l, предсзавлеиный иа рис. 12.17(а), до единого ордерева. Здесь М вЂ” матроид разбиения по концам дуг указанного орграфа ц д! — графический матроид, получаемый при игнорировании ориентации. Увеличивающей последовательностью отиоситель- (б) Рис.
!2.!7. но ( будет последовазельиость Ь'=(е„еь е„е„е,). Здесь I+е, независимо в М, ио зависимо в 7т', !ак как образуегся цикл (е„е„ е„е„). Заметим, что !еперь мы можем выбирать, какой из элементов е„е, или е, удализь, чтобы разорвать этот цикл. Так как все циклы в матроиде разбиения состоят из двух элементов, то в задаче о паросочетаиии в двудольном графе никогда ие бывает такого выбора. Этот факт говори! о том, что четные шаги при поиске увеличивающих путей в задаче о пересечении произвольных матроидов не будут тривиальными, как это было в случае двудольного паросочетаиия, и наш вспомогательный граф ие буде! перескакивать через четные уровни.
Выберем е, в качестве следующего элемента последовательности 5. При добавлении е, к I+е« вЂ” е, только в Лl образуется цикл (е„е„е,). Разорвем этот цикл, удаляя (е,). Теперь к 7+е,— ее+ + ее — е, можно добавитье„при этом не образуется циклов ни в М, ии в Д!, и поэтому 5 — увеличивающая последовательность. Получаемое в результате ордерево приведено на рис. 12,17(б). Пусть 5=(еь е,, ..., е ) — последова!ельиость элементов из Е. Через 5!! (!(1) обозначим пгследовательиость (еь е;„, ..., е!). Оболочку множества А«=Е отиосительио матроида М (соответствеиио й!) будем обозначать через зрм(А) (соответствеино зрк(А)). Аналогично, ранг множества А будет обозначаться ез!(А) или гм(А) в зависимости от рассматриваемого матроида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
