В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 15
Текст из файла (страница 15)
(6) Среди коэффициентов а; в последнем равенстве есть отличные от нуля, поскольку У >в О. Следовательно, система столбцов (5) линейно зависима. Обратно, пусть система каких-либо, например, последних т — р строк матрицы В линейно зависима. Тогда (5) — линейно зависимая систома векторов, и потому верно равенство вида (6), среди коэффициентов а> которого есть отличные от нуля. Определим столбец У формулой (4). Поскольку система векторов (2) линейно независима, то УФО, и У вЂ” решение системы (1). Итак, система (1) имеет ненулевое решение вида К Но тогда столбец Л, который получается из У в результате удаления последних т — р координат, является ненулевым решением системы (3).
Следовательно, столбцы матрицы С линейно зависимы. Доказано, что из линейной зависимости каких-либо т — р строк матрицы В вытекает линейная зависимость дополняющей системы р столбцов матрицы А. Тем самым доказана теорема. > $ 21. Бинарные матроиды Рассмотрим более детально матроиды, представимые над полем из двух элементов,— бипарныв матроиды. Бинарным является, например, матроид М=(Е, М) с множеством элементов Е = (1, 2, 3, 4), множество М баз которого составляют все трехэлементные подмножества в Е, содержащие 1. Б самом деле, положив ф(1)= (1, 1, О, 0), ф(2)=(0, 1, 1, 0), ф(3)=(0,0, 1, 1), ф(4)= =(О, 1, О, 1), получим представление матроида М над полем из двух элементов 0 и 1. Пусть Е = (О, 1) = Хз — поле классов целых чисел по модулю 2, М вЂ” матроид с множеством элементов Е, т— порядок матроида М, т. е.
число элементов в Е, 2е — булеан множества Е (совокупность всех подмножеств множества Е) . Превратим этот булеап в линейное пространство пад Хз, определив подходящим образом сложение подмножеств и их умножение па 0 и 1. Именно, для Х, Уш 2в положим Х+ У =(Х 0 У)~(Х 0 У) — сумма мнооееств ло модулю 2 (симметрнческая разность), 1 ° Х= = Х, 0 Х = И. Прямая проверка подтверждает, что в 2е внесена структура линейного пространства пад Ег, пулевым вектором которого служит 8.
Пусть Л вЂ” подмножество пространства 2е, состоящее из пустого множества, всех циклов матроида М и объединений попарно непересекающихся циклов. Фиксируем какую-либо базу В матронда М. Согласно следствию 16.1 для любого в~В в множестве В 0 е существует ровно один цикл. Обозначим этот цикл через С,. Теорема 21.1. Если исходный матроид М является бинарнылц то Л вЂ” надпространство пространства 2г размерности р*(М), базис которого составляют все циклы из множества (С,: ежВ), где  — произвольная база матроида М. > Пусть и Х гп-матрица А является представлением матроида М над Уг.
Для произвольного непустого подмножества Х множества Е обозначим через Я(Х) сумму (по модулю 2) всех столбцов матрицы А, соответствующих элементам из Х. Заметим, что непустое подмножество Х':-Е является элементом множества Л тогда и только тогда, когда Я(Х)= О. Действительно, пусть вначале Х вЂ” цикл. Тогда система столбцов, соответствующих элементам из Х, линейно зависима над Хг, и потому для какого-либо подмножества У в Х Я(У)= О. 11о всякая часть рассматриваемой системы столбцов линейно независима, следовательно, У= Х. Итак, Б(Х)= О для цикла Х. Очевидно, что то же верно, если Х вЂ” объединение попарно непересекаюгцихся циклов. Обратно, пусть Х вЂ” Е и Я(Х) = О.
Тогда система столбцов матрицы А, соответствующих элементам подмножества Х, линейно зависима пад Хг и, следовательно, Х— зависимое множество. Поэтому оно содержит цикл Хь Если У = Х~Х~ чь И, то Я(У) = О, поскольку Я(Х) = =Я(Х,)=0 н Я(Х)=Я(Х~)+Я(У). Следовательно, У содержит цикл Хь Через несколько подобных шагов мы разобьем множество Х па непересекающиеся циклы. Пусть Х к У вЂ” произвольные элементы множества Ь, /=ХП У, Х'=Х~/, У'= У17. Тогда Х+У=Х'0У', Х' д У' = О, Я(Х+ У) = Я(Х')+ Я(У'). Но Я(Х) = О = = Я(Х')+ Я(7), поэтому Я(Х') = Я(/2).
Аналогично В(У') = Я(2). Следовательно, Я(Х+ У) = Я(7)+ В(Я) = О. Тем самым доказано, что Л вЂ” надпространство пространства 2'. 80 Теперь докажем, что (1) — базис пространства Х. Если бы система векторов (1) была линейно зависимой над Хм то сумма каких-либо из них была бы равна нулевому вектору пространства 2л, т. е. пустому множеству.
Но если ес, ем ..., е, — попарно различные элементы из В, то Се + Се + .. + Сев-л(ес,е ...,е )„ Следовательно, система (1) линейно независима. Остается доказать, что произвольный элемент Х пространства Е является суммой по модулю 2 каких-либо циклов из (1). Это очевидно для Х= 8. Пусть асн Ь и Х т'- 8. Согласно утверждению 17.2 Х П В чь 8. Если ХПВ=(ес, ем ..., ее), то Х=С, +С,,+...+С,„. В самом деле, это равенство равносильно равенству Се +Се + ° ° ° +Сеь+Х=О (=И) (2) Левую часть последнего обозначим через Р. Так как С,, Д В = (ес) и е, ы Х, то Р й В = З. Следовательно, Р— независимое множество. С другой сторопы, Р ы Ь, а каждый элемент пространства Ь, отличный от пустого мнохсества, является зависимым множеством.
Итак, Р= = 8, т. е. верно равенство (2). е Заметим, что условие бинарности в формулировке теоремы 2.1 существенно. Пусть, например, М=(Е, Я)— матроид с множеством элементов Е = (1, 2, 3, 4), базами которого служат все двухэлементные подмноекества мноясества Е. Тогда (1, 2, 3) и (1, 2, 4) — циклы, а (1, 2, 3) + + (1, 2, 4) =(3, 4) — база. Следовательно, множество Ь пе является в этом случае подпространством.
Возвратимся к бинарным матропдам. Пространство Ь называется пространством в(иклов матроида М, а его базис (1) — базисом циклов этого матроида (относительно базы В). Так как двойственный матроид Ми такясе является бинарным (теорема 20.3), то верна теорема, двойственная предыдущей, и возникают понятия пространства коциклов и базиса кос(нилов, Именно, пусть Ье — подмножество булеана 2', элементами которого слулсат все коциклы матроида М, объединения попарно непересекающихся коциклов и пустое множество. Фиксируем в М базу В. Тогда для любого элемента е ~ В множество б В А, Емеличев и др. 81 Ф В 0 е содержит ровно один коцикл С,. В этих обозначениях верно С л ед с т в и е 21,2, Множество Ь* является подпространетвож пространства 2' размерности р(М).
Множество коциклов [С,: вен В), (3) где  — фиксированная база л атроида М, слулсит базисол этого пространства. Базисы циклов (1) и коциклов (3) легко определяются друг через друга. Верна следующая Теорема 21.3. Пусть /~ В, (С,, С,,, ..., С,„)— лножество всех циклов из базиса (1), содержащих Хг = (/, ен еи ..., е,). Тогда Хт = Сз. С Согласно следствию 16.7 множество В О/ содерязит ровно одни коцикл. Очевидно, что Хг — В 0/. Поэтому достаточно доказать, что Хз является коциклом. По теореме 17.3 множество Х, — коцикл, если выполняются следующие условия: 1) ~Хт й С).~1 для каждого цикла С. 2) Х, — минимальное непустое множество, удовлетворяющее условию 1).
Пусть С вЂ” цикл, Р = С й Хо Так как (1) — базис пространства циклов, то С однозначно представляется в виде суммы циклов из (1): С = Се. + ... + Се, ° (4) Если /~я С, то / принадлежит хотя бы одному слагаемому в (4), например, /енС, Тогда $ е; ~Хи (/,ез)с=Р, )Р(>1. Пусть /Ф С. Тогда либо / не входит ни в одно из слагаемых (4), либо / входит по меньшей мере в два из этих слагаемых. В первом случае Р = Ы.
Во втором пусть, например, /я Сы, /я С„. Тогда (е;, е;,) с=Р, !Р! ) 1. Тем самым доказано, что выполняется условие 1). Пусть теперь У~ Хо Если /Ф У, то У содерязится в кобазе и потому копезаэпсимо. Согласно лемме 17.4 существуот такой цикл С, что ~Уй С~ = 1. Если зке /~к У, но, например, е, Ф У, то ~ Е П С,,~ = '1. Тем самым доказано, что Хл — коцикл. 0 Нинке окажется полезным следующее У т в е р х~ д о и и е 21А. Если ~р — изолгоргризлг бинарного матроида М~ на матроид Мм а (1) — базис ииклов л~атроида М~ относительно базы В, то система ((р(С.): ешВ) (5)' является базисом циклов матроида Мг относительно базы ~р(В).
> По определению изоморфизма матроидов множество у(В) является базой матроида Мь Для любого цикла С матроида М~ множество ~р(С) — цикл матроида Мз. Если теперь е — элемент матроида М~ и е ФВ, то <р(е)Ф<р(В)'. Согласно следствию 17.7 множество Я = ~р(В) 0 <р(е) содержит ровно один цикл.
Этот цикл совпадает с ~р(С,), поскольку С, — В 0 е и, слодовательно, ~р(С,) — Я. Итак, доказано, что (5) — базис циклов матроида Мз относительно базы <р(В). < Теперь обратимся к графам. Графический и, следовательно, кографический матроиды бипарны, о чем свидетельствует Теорема 21.5. 1(ля любого непустозо графа С матрица инцидентноста 1 = 1(6) является представлениелч циклического матроида М(С) иад Хз. > Для произвольного подмножества ребер Х обозначим через 1(Х) подматрицу матрицы 1, составленную из столбцов, соответствующих ребрам, входящим в Х. Достаточно доказать, что гап1г1(Х)( ~Х! тогда и только тогда, когда подграф С(Х), порожденный мпохсеством ребер Х, содержит цикл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
