В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 12
Текст из файла (страница 12)
Уитни) — место теории матроидов в математике и, тем более, в математичоском образовании первоначально не было осознано. Теперь»ке, когда открыва<отся все новые и новые классы матрондов, объед<п<яющая роль идеи матроида, позволяющая с возрастающим успехом применять к решению комбинаторных проблем методы алгебры, становится все более ясной. Для пас матроиды интересны, прежде всего, по двум причинам. Первая — их связь с теорией графов. <1»акти- чески.
имопно с<н»тветствие между некоторыми теоретикографовымн и алгеораичоскими понятиями привело к созданию теории матроидов. Вторая причина состоит в том, что задачи <штимизации па матроидпых структурах решаются с помощью простого, так называемого «жадного» алгоритма, который является обобщением алгоритма Краскала для пахождопия остовного дерева минимального веса в связном взвешенном графе (Х 15). «Жадптай» алгоритм изучается в этой главе. ь»6.
Азбука теории матрондов Известно несколько эквивалентных друг другу определений матронда. Эти определешп< различаются том, что учитьн<а<от различные свойства независимости. Начнем с определения, основанного па свойствах максимальных независимых мпожоств — оаз. Ъ|ат1<оиао»< М называется пара (Г, Я), где Š— конечное пепустое множество, а Я (или Я(ЛХ) ) — пепустое множество его подмножеств (называемых базами), удовлетворяющее следующим двум условиям (аксиоз<ь» баз).
В.1. Никакая из баз не содержится в другой базе. В.2. Если В1 и Вэ — базы, то для любого элемента Ь ~ В~ существует такой элемент с ~ Вм что (В1~Ь) 0 с— также база. Элементы множества Е называются элементами матроида М. х1исло !Е! называется порядком матроида М.
Понятие матроида является естественным обобщением понятия линейной независимости. А именно, если Е— коночная система векторов некоторого линейного пространства, содержащая ненулевой вектор, то в Е существует максимальная линейно независимая подсистема— база системы Е. Напомним, что все базы системы Е удовлетворяют аксиомам баз В.1 и В.2. Следовательно, всякая такая система вместе с ее базами является матроидом. Этот матроид называется векторным. Очевидно, что в обозначениях аксиомы В.2 либо Ь~Вз и тогда можно взять с = Ь, либо с ~и Ве~Вь иное противо- речило бы аксиоме В.1. Поэтому совокупность аксиом В.1 и В.2 равносильна совокупности аксиом В.1 и В'.2.
Если Вп Вэ ~ Я и Ь ~В|~Вю то в Вэ'~В~ существует такой элемент с, что (В~Я) 0 с ~ Я. У т в е р ж д е н и е 16.1. Все базы матроида равно- лющны. (> Пусть В1 и Вэ — базы, !В|! ~ !Вэ! и В~ = (Ьп Ьн... ..., Ь,). Согласно аксиоме В.2 в базе Вэ существует такой элемент сь что В =(В~'~Ь|) 0 с1 = (сь Ьэ, ..., Ь„) ~и Я, Далее, существует такой элемент сз ж Вн что В =(В ~Ь2) 0 сэ = (сь с2, Ьэ, ..., Ьр) Я. Итерируя этот процесс, получим базу В = (сь см ..., с,), являющуюся подмножеством в Вэ и потому совпадаю- щую с Ве в силу В.1. Следовательно, !Вэ! = р, ч( Мощность базы матроида М назовем его рангом и обозначим через р(ЛХ). Любое подмножество базы матроида называется не- зависимым. В частности, пустое множество независимо.
Совокупность всех независимых подмножеств элементов матроида М обозначим через э(М) (или просто э). Ни- же множество э(М) называется наборолс независимых множеств матроида М. Очевидно, что Я(М) совпадает с множеством элемен- тов из У(М), максимальных относительно включения, так что множества Я(М) и т (Лч) определяют друг друга.
5 в А, емеличеч и др. 65 Теорема 16.2. Набор т (М) независимых множеств матроида удовлетворяет следующим двум условиям (ак- сиомы независимости). 1Л. Если Х~и5'(М), У'= Х, то Уя7(М). 1.2. Если Х, У~иУ(М) и !Х! < )И, то в У~Х сущест- вует такой элемент у, что Х 0 у ее,л (М).
С Справедливость условия 1.1 очевидна; рассмотрим условие 1.2. Пусть Х, У~У(М) и )Х! < !У!. Пусть, да- лее, В~ ~и Я(М), У вЂ” Вь Среди баз, содержащих Х, вы- берем такую базу Вп чтобы пересечение В~ 6 Вг содержа- ло наиболыпее число элементов. Докаягем, что Вг~Х вЂ” Вь Действительно, если бы существовал элемент б ~ Вг~Х, оФВь то по аксиоме В.2 в базе В~ нашелся бы такой элемент з, что С = (Вг~й) 0 г ~ Я(М) . Но тогда !С 6 В~ ! > > !ВгйВ~!, что певозмоягно. Следовательно, Вг~Х и У содержатся в Вь причем )Вг~Х!+ )И =р(М) — !Х!+ + )И > р(М) = !В~!. Тем самым существует у ~и(Вг~Х) 6 и У. Поскольку Х 0 у — Вг, то элемент у — искомый.
! Очевидяо, что аксиома 1.2 эквивалентна следующей аксиоме. 1'.2. Если Х, У~н,т(М) и !Х! < !И, то в У сущест- вует такое подмножество 2, что Х !! 2 я,2'(М), !ХЬ 2! = = )И. Следующая теорема показывает, что в основу опре- деления матроида можно положить не базы, а независи- мые множества. Т е о р е м а 16Л. Пусть Š— конечное непустое множе- ство, У вЂ” непустая совокупность его подмножеств, удов- летворяющая аксиомам независимости 1.1 и 1.2, Я вЂ” мно- жество всех элементов иг .У, максимальных относительно включения. Тогда Я удовлетворяет аксиомам баз ВЛ и В.2.
!> Очевидно, что Я есть множество всех элементов из :э максимальной мощности. Пусть теперь Вь Вг ~н Я, е~ гиВь Тогда В~~в~ ~У, !В~~е~! = )Вг! — 1. Следователь- но, существует такой элемент ег ~н Вг, что (В~~в~) !! ее=Вен,т, !Вг! = )Вг), Из последнего равенства вытекает, что Вз~и Я. Тем са- мым доказано, что выполняется условие В.2. Справедли- вость условия В.1 очевидна. 0 Предыдущая теорема дает основание для нового опре- деления матроида.
Матроидом назовем пару (Е, .т ), где р — множество, а у — непустая совокупность его под- множеств (называемых независимыми), удовлетворяю- 66 щих аксиомам независимости 1А и 1.2. Множество У назовем набором независимых мььозсеств матронда. Максимальные относительно включения независимые подмножества назовем теперь базами матроида. Аксиомы баз при этом действительно будут выполнятьсн. В этом смысле приведенные два определения матропда эквивалентны. Определим ранговуьо фуьькциьо (функцию ранга) матроида ЛХ, ставящую в соответствие каждому подмножеству А ':-'Е число, равное максимальной из мощностей входящих в А независимых подмножеств и называемое рангом множества А: р(А)=шах((Х!: Х вЂ” А, ХьнУ(М)).
Очевидно, что р(Е) совпадает с определенным выше рангом р(М). Очевидно также, что подмножество А азЕ независимо тогда и только тогда, когда р(А) = !А!. Т е о р е м а 16А. Ранговая функция матроида удовлетворяет следующим трем условиям (аксиомьь ранга): р.1. О ~ р(А)( !А! для каждого А — Е; р.2. р(А) < р(В), если А жВ:-Е; р.З. р(А 0 В)+ р(А П В) ~ р(А)+ р(В) для любььх А, В ж Е.
С 11ервые два условия очевидны, рассмотрим третье. Нусть А, В':-Е, а Х вЂ” наибольпьсе по числу элементов независимое подмножество в А П В. Согласно условиьо 1'.2 в А 0 В существует наибольшее по числу элементов независимое подмножество 1', содержащее Х. Нредставим 1' в виде У= ХО т'0 И', где $'':-А~В, И'ы В~А. Независимое подмножество Х !! Г содержится в А, поэтому р(А) > 3Х 0 )т!. Аналогично р(В) > )Х О И'!. Следовательно, р(А)+ р(В) > )Х О Р! + |Х 0 Ит!.
Поскольку Х П И = = Х П И'= О, то далее имеем р(А)+ р(В)> !Х! +(!Х! + + !И!+ 3И !). Но )Х! =р(А ПВ), !Х! + !Г3+ !И !— = ! 1'! = р (А 0 В) . Итак, р(А)+ р(В)>р(А 0В)+р(А П В). ь Нодмножество А из Е называется гависимььм, если опо пе являетсн независимым. Минимальное относительно включепил зависимое множество называется циклом. Очевидно, что подмножество множества Е независимо тогда и только тогда, когда оно не содержит циклов.
Мпоькество циклов матроида М обозначим через У(ЛХ) (или просто $'). Т е о р е м а 16.5. Если М вЂ” льатроид, то множество %'(М) удовлетворяет следующим двум условиям (аксиомы циклов). СА. Ни один иг циклов не содержится в другом цикле.
С.2. Если С«и Сг — несовпадающие ««иклы и еж С«П й Сг, то множество (С1 0 Сг)хе также содержит иикл. Выполнимость условия С.1 очевидна, рассмотрим условие С.2. Пусть Р =(С«0 Сг)~е. Достаточно доказать, что множество Р зависимо. Прибегнем к помощи ранговой функции; в ее терминах нужно доказать неравенство р(Р)< «Р!. Но Р— С1 0 Сг, н потому р(Р)~р(С1 0 Сг). Согласно аксиоме р.З р(С, 0 С ) ~ р(С )+р(С )-р(С, й С ). Очевидно, что р(С;)= !С;! — 1 для цикла С;.
Так как множество С«й Сг независимо, то р(С«й Сг)= !С~ П Сг!. Итак, р(Р) ~ р(С«0 Сг) < !С~! — 1+ !Сг! — 1 — )С«П Сг! = = !С«0 Сг! — 2 и !Р! = !С1 0 Сг! — 1, а значит, р(Р)( !Р!. 0 Заметим, что совокупность аксиом р.1 — р.З (как и С.1, С.2) можно использовать для еще одного определения матронда. Следствие 16.6. Если М=(Е, У) — матроид с набором независимых множеств У, Х~нУ, у~Е, то мнолгество Х 0 у содержит не более одного ««пкла.
«> Пусть, напротив, в Х 0 у есть два несовпадающих цикла С, и Сг. Элемент у содержится в каждом из них, н, согласно предыдущей теореме, существует третий цикл С в множестве Р =(С10 Сг) ~у. Следовательно, Р— зависимое множество. Но Р'= Х н потому независимо. Полученное противоречие доказывает нужное утверждение. е« Очевидно, что из предыдущего следствия вытекает Следствие 16.7. Для любой базы В латроида и любого его элемента е, не входящего в эту базу, множество В 0 е содержит ровно одшв иикл.
и 17. Двойственный матроид Пусть М =(Е, Я) — матроид с множеством баз Я. Для произвольного Х'= Е положим Х =Е'~Х. Если В~нЯ, то множество В назовем кобазой матронда М. Пусть Яв = = (В: В ~ Я) — множество всех кобаз. Теорема 17.1. Множество Я* удовлетворяет аксиомам баз В.1 и В'.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
