В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 17
Текст из файла (страница 17)
Теоремы Холла — частный случай теоремы Радо. Дей- ствительно, если М вЂ” свободный матроид, то ранг любого подмножества Х вЂ” Е равен ~Х~. С Доказательство теоремы Радо. Необхо- димость условия теоремы очевидна; если существует не- зависимая трансверсаль семейства Я, то ее пересечение с объединением любых й подмножеств Я1 содержит й-эле- ментное независимое подмнон1ество. Следовательно, ранг этого объединения не менее й.
Д о с т а т о ч н о с т ь. Вначале докажем, что при вы- полнении условий теоремы ни одно из множеств Я, не может содержать более одного такого элемента, удаление которого нарушает условие теоремы. Пусть, напротив, множество Я1 содержит два таких элемента х и у. Это значит, что существуют такие множества индексов А и Вв(2,...,т),что р ( () Я1 () (Я1 '~ х)) ( ) А ), р(() Ег() (д, р))<~В!, Не В где р — ранговая функция матроида М. Положив () Я1()(Я,' х)=С, () Я1()(Я; у)=В, 1ЕА 1ЕВ имеем )А1+!В! ~ р(С) + р(Н) Э- р(С 0 Н)+ р(С 9 Н) (см.
аксиому Р.З). Но С()В= О Е1, СПВ и Е1. 1ЕАЦВ~,1 1ЕА1В Поэтому )А(+ ) В)>р( () Я1) + р( () 511. Н то же время по условию теоремы р( 0 В1)~~(АП В!+(, НЕАОВ01 р ( 0 Я1) Э:! А П В ) 1ЕАЦВ 89 Итак, !Л!+ !В! > !Л !У В!+ 1+ !Л П В! = !Л!+ !В!+ 1. Последков протпворечио доказывает нужное утверждение. Пусть теперь какое-либо из подмнонсеств Яс содернсит более одного элемента. Тогда из Я; можно удалить некоторый элемент, пе нарушив справедливости условия теоремы. Итерируя этот процесс, придем к ситуации, в которой !Яс! =1 (с=1, т) и выполняются условия теоремы. По тогда все Яс попарно различны и нх объединение и есть нужная трапсвсрсаль.
ч! Понятие трапсверсали можно обобщить следующим образом. Пусть Š— конечное пепустое множество, Я = =(Яп Яп ..., Я ) — семейство его пепустых подмножеств, (усс, йг, ..., в„,) — последовательность целых половсительных чисел. Семейство Р=(Рп Рг, ..., Р ) подмножеств из Г назовем (йс, усг, ..., й.,)-трапвверсалыо семейства я, если 1) Р,шд„!=1, т; 2) )Р,!=усе 1=1, щ; 3) Р, П Р, = И прп с Ф у. Очевидно, что введенная выше трансверсаль является (1, ..., 1) -трапсверсалью. Поэтому задача о свадьбах (о существовании трапсверсали) естественным образом обобщается теперь в виде задачи о гарвлсах.
Решение этой задачи, т. е. условия существования (усс, усм..., ус )- трапсверсали, легко получить непосредственно из теоремы Холла. Заменим семейство Я другим семейством (йс! ~сг ' ~ дсй ~гс ~22~ ' ' ' ~ '~гас дплс~ дтг ° ° ° ° " тьщ), где Я„= Я, (с = 1, т, у = 1, йо у =-1, т). Очевидно, что семейство Я имеет (усс, ую ..., й„,)-трапсверсаль тогда и только тогда, когда существует трансверсаль семейства Я'.
Таким образом, верно Следствие 22.1. Длл сущвстссоваспсл (йс, усп..., й )- трапсверсали семейства Я =(Яь Яю ..., Я ) необходимо и достаточно, чтобы длл любого 1': — (1, 2, ..., т) выполнялось неравенство ~ () д,)~~' Лс сес С Йс т Аналогично пз теоремы Радо тсоссспо получить критерий существования независимой (йс, йю ..., !с,„)-трапсверсали. 90 Из теоремы Радо вытекает также следующий критерий существования независимой частичной трансверсалв фиксированной мощности. Сле яства е 22 2.
В ооогссачвниях теоремы Радо свлсейство 5' имеет незавнск.кусо частичную трансверсаль лсошности ! - т тогда и только тогда, когда для каждого й = 1, т ранг объедссквнкя люб!ах Ус подлтожвств Я, кв зсвньксе, че.к у+1 — т. !)усть Р— такое ьпсожоство, что !Р! =и — 1 и Р й Е = О. 11остроим новый матр,!ид М' на мноясестве Е 0 Р, объявив его базами все подмпои остов ВОР, где  — база матропда М (очевидно, что аксиомы баз действительно выполпясотся), и рассмотрим семейство Т = ( Т!, Тг, ..., Т ), Т = 5', 0 Р, с = 1, т.
Очевидно, что исходное семейство Е имеет независимую частичную трапсверсаль мощности 1 тогда и только тогда, когда семейство Т имеет трапсверсалгч независимую относительно матропда М. Согласно предыдущему следствию, для существования такой трапсверсали необходимо и достаточно, чтобы объединение любых й подмножеств Т, содержало независимое относительно матропда М подмножество мощности й, Но последнее условие равносильно условию следствия. <1 11!ив в качестве М свободный матроид, получим Следствие 22.3.
Семейство подмножеств Я имеет частичнусо трасссверсаль мощности 1~ т тогда и только тогда, ковда для каждого 7с =1, т объединение любых й нодлсссожеств Яс имеет мощность ке лсеньисе, чем Й+1 — т. 11ропзвольпое семейство Я=(Яс, Ям ..., Я ) пепустых подмножеств множества Е определяет на Е структуру матроида, независимыми мпоясествами которого являются частичные трапсверсали етого семейства и пустое множество. Об атом свидетельствует следующая Теорема 22.4 (Дж. Эдмонде, Д.
Фалкерсоп, 1965г.). Множество 5', элементами которого служат всв частичные трансверсали семейства подмножеств Я и пустое мноэсество, удовлетворяет аксиомам независимости 1.1 и 1.2. 1> В доказательстве луясдаетсл только справедливость условия 1.2. 11ропзвольпусо частичную трансверсаль Х= = (хс, хг, ..., х„) семейства Е, продставляющую подсемейство (Яс, Я;,,..., Ь'сд), т. е. такую, что хр~ Яс„, запп- 1' шем в виде ((хс, с!), (хг, !2), ..., (хм сч)1. (2) 91 Пусть ((Ун 11) (У21!2) ~ (Уь и)) (3) — еще одна частичная трансверсаль и 1) й. Нужно доказать существование среди ун ую ..., у, такого у, что Х~у Х Если в (3) есть такая пара (у, /), что у не совпадает пи с одним из х в (2), а !' — пи с одним из й то, очевидно, что ХМУРА,у.
Пусть теперь в (3) нет такой пары. Но так как 1) Й, то сУЩествУет индекс ~', пУсть это 1ь отличный от всех индексов 1 в (2). При этом у1 совпадает с каким-либо из х, например, у~ = хь Теперь можно написать ((хь!!), (хз, зз), ..., (хм |А))~ т. е. трапсверсаль Х представляет и подсемейство (Я;~, Я;,, ...,Я;„), при этом х~ = уь Среди индексов уз, ..., й существует индекс, отличный от каждого 1з, ..., 1м пусть зто будет уз. Тогда уз совпадает с каким-либо из хз,...,х„ например, уз = хз, Теперь имеем ((хн у~), (хз, 1з), (хз, зз), ..., (х„з',)), х1=ун хз= уз.
Итерируя этот процесс, получим х; = у; (1 = 1, й) (с точностью до перенумерации элементов у;) . Следовательно, Х=(у„у,, ..., д), Х~у„, -=Х Итак, (Е, й) — матроид с набором независимых множеств т. Этот матроид называется матроидом триневерсалей семейства Я. Матроид, изоморфный матроиду транс- версалей какого-либо семейства подмножеств, называется трвнсверсальным.
В вая ном частном случае, когда исходное семейство Я явллетсл разбиением множества Е, т. е. () Яз = Е, и подмножества Я, попарно не пересекаются, матроид трапсверсалей семейства Я называется матроидом разбиения Я. Очевидно, что подмножество Х вЂ” Е независимо отпосительяо матроида разбиения Я тогда и только тогда, когда ~ Х П 5, ~ ( 1 (1 = 1, яз) . 5 23. Жадный алгоритм рассмотрим следующую аадачу дискретной оптимизации. Пусть Š— пепустое конечное множество, ин Е— Нт — функция, ставящая в соответствие каждому эле- 92 менту е этого мпо1кества пеотрнцател1шое действительное число ш(е) — вес элемента е. Для Х жЕ вес ш(Х) определим как сумму весов всех элементов множества Х: и:(Х) = ~ ш(х).
хмх Пусть, далее, — некоторый набор подмножеств мпожества Е, т. е. ': — 2е. Задача состоит в выборе в подмножества максимального веса. Оказывается, что в случае, когда является набором независимых множеств матроида, эта оптимизационная задача решается с помощью следующего простого алгоритма.
Жадный (градиентный) а л гор и т м. 1-й шаг. Находим такой элемент е1еяЕ, что и1(е1) = шах ш(е). (евя й-й шаг (й ~ 2). Находим такой элемент ехай Е, что ш (еь) = шах ш (е). (ег ..еЬ,~~Я, ЕЛЕ1, 1=1, Ь вЂ” 1 Если такого элемента нет, то конец. Примером жадного алгоритма служит алгоритм Краскала нахождения остова максимального веса во взвешеняом графе (см.
9 15). Очевидно, что выходом жадного алгоритма всегда является элемент множества , максимальный относительно включения. Однако он может оказаться не максимального веса. Чтобы убедиться в этом, рассмотрим пример: Е= (1, 2, 3), = И1), (1, 2), (2, 3)), ш(1) = 3, ш(2)= 2, ш(3)=4. Наш алгоритм найдет множество (1, 2), хотя множество (2, 3) имеет оольший вес. Возникает вопрос: когда же можно гарантировать получение подмножества максимального веса, решая задачу с помощью жадного алгоритма? На этот вопрос отвечает следующая Теорема 23.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
