В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 13
Текст из файла (страница 13)
«' Справедливость условия В.1 очевидна, рассмотрим условно В'.2. Пусть В1 и Вг — две кобазы, х~вВ1~Вг. 11уткпо доказать сущсствовапис в Вг~В~ такого элемента у, что А =(В~~х) 0 у ~и Я*. (1)' Так как хФВь то согласно следствию 16.7 множество В~ Б х содержит цикл С. Поскольку цикл пе может содержаться в базе, то существует у ~ С' П Вх Так как х я е Вг, то у Ф х. Следовательно, у ~н Вь Итак, у ~ Вг~Вь Теперь докажем, что верно (1), С этой целью рассмотрим мнонсество А =(В~ 0 х)~у. В силу следствия 16.7 С является единственным циклом, содержащимся в В~ 0 х.
Поэтому А нс содержит циклов и, следовательно, является независимым множеством. Далее 1А! = !В~ 1, так что А — база и потому А — кобаза. З Из предыдущей теоромы вытекает, что нара (Е, Яв) является матроидом с множеством баз Я*. Этот матроид называется двойственным к матроиду М и обозначается через М*. Очевидно, что М** =М. Зависимое (независимое) множество элементов матроида Мв называется козависимым (конеэависимым) в М. Цикл матроида М* называется коуиклом матроида М. Ранговая функция матроида М* называется коранговой функг1ией матроида М п обозначается через р*. Очевидно, что р*(М)= ~Е~ — р(М). Поскольку кобазы, коциклы и т.
д. являются базами, циклами и т. д. двойственного матроида, то для любого утверждения о циклах, базах и т. д. матроида существует аналогичное двойственное утверждение о двойственных обьектах — коциклах, кобазах и т. д. Если одно из этих утверждений верно для всех матроидов, то верно и двойственное утверждение. Очевидпо, что в терминах кобаз можно следующим образом определить зависимые множества. У т в е р ж д с п и с 17.2. Произвольное подмножество элементов матроида является зависимым тогда и только тогда, когда оно имеет непустое пересечение с каждой кобазой.
Теорема 17.3. Непустое подмножество Х элементов матроида является циклом тогда и только тогда, когда оно удовлетворяет следующим двум условиям: 1) ~ХП С~ чь1 для каждого коцикла С; 2) Х вЂ” минимальное относительно включения непустое подмножество, удовлетворяющее условию 1). Доказательство этой теоремы основано на следующих двух леммах.
69 Л е м ма 17.4. Для любого ненустого независимого подмлохсества Х элементов матроида существует такой кочикл С, что ~Х й С~ = 1. >> Множество Х содержится в некоторой базе В. Пусть х~и Х. В силу следствия 16.7 множество В 0 х содержит некоторый поцпкл С. Очевидно, что С й В= (х) = =сйх. а Лом ма 17.5. Для всякого уикли Х и любого ко>(икла С матроида вер>ю соотношение ~Х й С! ть 1. с Пусть, напротив, Х й С = (х).
Согласно утверждению 17.2 коцикл С вЂ” минимальное подмножество в Е, имеющее пепустое пересечение с каждой базой. Следовательно, С вЂ” максимальное подмножество в Е, не содер>кащее баз, и потому С 0 х содержит некоторую базу В. Мпожоство Х~х независимо и салери>итси в С 0 х. Из аксиомы 1.2 теперь получаем, что существует база Р, удовлетворяющая условию Х~х — РыСОх. Но С пе содержит баз, поэтому х~Р, Х вЂ” Р. Последнее противоречит аксиоме П1. а (> Доказательство теоремы 173. Необходимость. Пусть Х вЂ” цикл. Тогда па основании леммы 17.5 ~х й С) чь 1 для каждого коцикла С. Любое подмножество из Х независимо и, в силу леммы 17.4, не удовлетворяет условию 1). Д о с т а т о ч н о с т ь.
Пусть Х вЂ” непустое подмножество элементов матроида, удовлетворяющее условиям 1) н 2). Согласно лемме 17.4 множество Х зависимо. Все его собственные подмножества не удовлетворяют условию () п независимы в силу леммы 17.5. а 4 18. Примеры матроидов рассмотрим некоторые примеры матроидов., 1. Пара (Е, (К)), где Š— конечное непустое множество, является матроидом, единственной базой которого служит само множество Е. Этот матроид называется свободным (или дискретным).
Циклов свободный матроид не имеет, всякое подмножество Х ы К независимо, р(х) =-' ~х~'. Двойственный к свободному — тривиальный матроид (Е, (З)), единственной базой которого является пустое множество. Очевидно, что к> служит единственным независимым множеством тривиального матроида; его циклы — все одпозлементпые подмножества множества Е; р(Х) = 0 для любого Х вЂ” К. 70 2. Пусть Š— линейное пространство над произвольным полем г*, Š— Š— конечное пепустое подмножество, У вЂ” множество, элементами которого служат все линейно независимые над Г системы векторов из Е и пустое множество. Тогда пара (Е, У) является матроидом с набором независимых множеств У (этот факт вытекает из известной в линейной алгебре теоремы Штейница о замене). Такой матроид называется векторным матроидом, порожденным множеством векторов Е.
Базами этого матропда служат все базы множества Е. Нели же в Е нет баз, т. е. если Е = (О), то единственной базой векторного матроида является пустое множество, т. е. он тривиален. Ранг векторного матроида равен рангу множества Е, т. е. размерности подпространства, пороягдонного множеством Е. В частности, ваяв в качестве Е множество векторов, являющихся столбцами (строками) какой-либо матрицы Л, получим матричный матроид, или матроид столбцов (строк) матрицы Л.
Ранг этого матроида равен рангу матрицы Л. В качестве иллюстрации рассмотрим матроид М столбцов матрицы Обозначив (-й столбец этой матрицы через е~ (1=1, 4), получим Е = (еь еп ез, е4), р(М) = гапй Л = 3. Перебирая все максимальные линейно независимые системы столбцов матрицы Л, обпаруязим, что матроид М имеет ровно 3 базы: В~ = (е1, ем ез), Вз = (еь ез, е4), Вз = (ен ез, ез). Зависимых множеств 2: Е и (ез, ез, е4), причем последнее мпожоство служит единственным циклом матроида М. Кобазы: В1 = (е4), Вз = (ез), Вз=(ез). Козависимые множества: (е|) и каждое подмножество в Е, содержащее более одного элемента.
Коциклы: (е~), (ез, ез), (ен е4), (ез е4) ° 3. Пусть С вЂ” произвольный граф. Определим матроид М(С) =(Е, Я) па мпоя ество Е =ЕС, объявив базамп множества ребер всех остовов графа С, т. е. Я= (ЕН: Н вЂ” остов С). Из утверждения 13.8 вытекает, что аксиомы баз в этой ситуации действительно выполняются. Поскольку каждый подграф графа С, являющийся лесом, содержится в некотором остове (утверягдепие 13.7), то независимыии множествами в М(С) служат множества 71 ребер подграфов в 6, являющихся лесамп, н только они.
Циклы матронда М(С) — это множества ребер простых циклов графа 6. Если п(6), т(6), Й(6) — числа вершин, ребер и компонент графа С соответственно, то р(М(С) ) = п(С) — й(6) = т*(6), р*(М(6) ) = т(6) — р(М(6) ) = т(С), т. е. ранг и коранг матропда М(6) равны, соответственно, коциклическому рангу н циклическому рангу графа 6. Если  — множество всех ребер какого-либо остова графа 6, то мшнкество ЕС'ьВ называется коостовом. Подмножество П ~ ЕС называется разделшощим множестволь графа 6, если число компонент графа С вЂ” П больше, чем число компонент С.
Минимальное относительно включения разделяющее множество называется разрезом. Кобазами в М(С) служат коостовы графа С. Из утверждения 17.2 непосредственно вытекает, что коза висимые мноькества в е, ег М(6) — это разделяющие мноя ества графа С, а коциклы — это е е 3 разрезы. Поэтому между свойстРььс. 18Л вами простых циклов и разрезов графа существует большая аналогия. Эта аналогия и явилась одной из причин возникновения понятия «матропд». Матроиды М(6) и М~(6) называются матроидом ь(нилов (циклическим матроььдоль) и ллатроидоль разрезов (коуиклическььм матроидолс) графа С соответственно. 1'ассмотрьгзь, например, циклический матроид М(6) графа С, изображенного на рис.
18.1. Для этого матроида Е = (еь ег, ез, е«). Он имеет ровно три базы: В~ = (еп ег, е«), Вг = (еь е,, е«), В, = (ез, ез, е«). Единственным его циклом служит множество (еь ег, ез). Кобазы: В~ = (ез), Вг = (ег), Вз = (е1); коциклы: (еь ег), (еь ез), (ез, ез), (е«). Очевидно, что для любого дерева Т циклический матропд М(Т) свободен, а М*(Т) тривиален. Вернемся к произвольным графам. Применяя установленные выше утверяньеььия о свойствах баз, независимых множеств н циклов матропда к матроидам М(6) и Мв(6), получим следуьощие утверждения о графах. Каждое из них неслоя но доказать непосредственно, одпако здесь вскрывается их общая сущность. Утььерждение 18.1, Пусть Е и Н вЂ” аь)нклические подграуььь грауьа 6 и (ЕЕ(( ~Е~~.
Тогда существует та- ьое подмножество Х ЕХХ, что граф Г' =Е+ Х также является ациклиыеским и !ЕХг'~ = ~ЕН~. Утвернгд ение 18.2. Если Р1 и Рг — несовпадающие разрезы в графе С, имеющие общее ребро е, то множество ребер (Р1 0 Рг) ~е является разделя|ощим. Утверждение 183, Для любого непустого оциклического подграфа Е графа 6 существует разрез в С, имеющий с Е ровно одно общее ребро. Утверждение 18.4.
Число общих ребер любого простого цикла и. любого разреза графа отлично от 1. 3 а м е ч а н и е. Очевидно, что в формулировках утверждений 18.1 — 18.4 может фигурировать произвольный псевдограф, а не только простой граф. в 19. Изоморфизм матроидов Пусть М~ =(Еь Я~) и Мг=(Ем Яг) — два матроида с множествами баз Я~ и Яг, ц: Е~ — Ег — биекция.
Для Х':-Е1 полон1им ц(Х) = (ф(х): х ~и Х). Если для любого Х':-Е1 имеем ц(Х)ы Яг тогда и только тогда, когда Хю ~ Яп то биекция ц называется изоморфизмом матроида ЛХ~ на матроид Мг. В этой ситуации будем писать ц: М,-М,. Для изоморфизма гр существует обратная бнекция причем очевидно, что для любого !' — Ег имеем ц '(!')~в Я~ тогда и только тогда, когда у ~Яг. Следовательно, если (1) — изоморфизм матроидов, то и Мг — М~ — также изоморфизм. Если существует изоморфизм (1), то будем называть матроиды ЛХ, и Мг изоморфнылш, и писать М| — = ЛХз. Утверждение 19.1. Если цк М1 — Мг — изоморфизм матроидов, то: 1) ц(Х) — независимое множество матроида Мг тогда и только тогда, когда Х является независимым множеством матроида М~,' 2) ц(Х) — цикл матроида ЛХг тогда и только тогда, когда Х является циклом матроида М~,' 3) ц(Х) — кобаза матроида Мг тогда и. только тогда, когда Х является кобазой матроида М~', 4) гр(Х) — коцикл матроида Мг тогда и только тогда, когда Х является коциклом в Мь 1) 1!усть Х вЂ” независимое множество матроида Мь Тогда Х содержится в некоторой базе В ~к Яь Множество 73 ьр'(Х) содержится в базе ьр(В)иЯ«и потому независимо в матронде Мв Поскольку множество ~р(Х) отображается на Х обратным нзоморфнзмом ьр ', то из независимости мнояьества ьр(Х) в свою очередь следует независимость множества Х 2) Пусть Х вЂ” цикл матропда ЛХь т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
