§ 21. Бинарные матроиды

Рассмотрим более детально матроиды, представимые над полем из двух элементов,— бинарные матроиды.

Бинарным является, например, матроид М = (Е, β) с множеством элементов E = {1, 2, 3, 4}, множество β баз которого составляют все трехэлементные подмноже­ства в Е, содержащие 1. В самом деле, положив φ(1) = (1, 1, 0, 0), φ(2) = (0, 1, 1, 0), φ (3) = (0,0,1,1), φ(4) = (0, 1, 0, 1), получим представление матроида М над полем из двух элементов 0 и 1.

Пусть F = {0, 1} = Z₂ — поле классов целых чисел по модулю 2, М — матроид с множеством элементов Е, т — порядок матроида М, т. е. число элементов в Е, 2^E — булеан множества Е (совокупность всех подмножеств мно­жества Е). Превратим этот булеан в линейное простран­ство над Z2, определив подходящим образом сложение подмножеств и их умножение на 0 и 1. Именно, для X, Y  2^Е положим X+Y = (XY)\(X∩Y) —сумма мно­жеств по модулю 2 (симметрическая разность), 1 • X = X, 0 • X = Ø. Прямая проверка подтверждает, что в 2^E внесена структура линейного пространства над Z2, нуле­вым вектором которого служит Ø.

Пусть L — подмножество пространства 2^Е, состоящее из пустого множества, всех циклов матроида М и объеди­нений попарно непересекающихся циклов. Фиксируем какую-либо базу В матроида М. Согласно следствию 16.7 для любого е  в множестве В е существует ровно один цикл. Обозначим этот цикл через Сe.

Теорема 21.1. Если исходный матроид М является бинарным, то L — подпространство пространства 2^E раз­мерности ρ *(M), базис которого составляют все циклы из множества

где В — произвольная база матроида М.

> Пусть nXm-матрица А является представлением матроида М над Z2. Для произвольного непустого под­множества X множества Е обозначим через S(X) сумму (по модулю 2) всех столбцов матрицы А, соответствую­щих элементам из X.

Заметим, что непустое подмножество ХЕ является элементом множества L тогда и только тогда, когда S(X) = 0. Действительно, пусть вначале X — цикл. Тогда система столбцов, соответствующих элементам из Х_г ли­нейно зависима над Z2, и потому для какого-либо под­множества Y в X S(Y) = 0. Но всякая часть рассматри­ваемой системы столбцов линейно независима, следова­тельно, Y = X. Итак, S{X) = 0 для цикла X. Очевидно, что то же верно, если X — объединение попарно непере­секающихся циклов.

Обратно, пусть ХЕ и S(X) = 0. Тогда система столб­цов матрицы А, соответствующих элементам подмноже­ства X, линейно зависима над Z2 и, следовательно, X — зависимое множество. Поэтому оно содержит цикл Х1. Если Y = X\ X1= Ø, то S(У) = 0, поскольку S(X) =S(Х1) = 0 и S{X) = S(X1) + S{Y). Следовательно, Y со­держит цикл Х2. Через несколько подобных шагов мы разобьем множество X на непересекающиеся циклы.

Пусть X и Y — произвольные элементы множества L, Z = X∩Y, X' = X\Z, Y' = Y\Z. Тогда X+Y = X'Y', X' ∩Y' = Ø, S(X+Y) = S(X') + S(Y'). Ho S(X) = O = S(X') + S(Z), поэтому S(X') = S(Z). Аналогично S(Y') = S(Z). Следовательно, S(X+ Y) = S(Z) +S(Z) = 0.

Тем самым доказано, что L — подпространство про­странства 2^E.

Теперь докажем, что (1)—базис пространства L. Если бы система векторов (1) была линейно зависимой над Z2, то сумма каких-либо из них была бы равна ну­левому вектору пространства 2^Е, т. е. пустому множеству. Но если е1, е2, ..., ek — попарно различные элементы из , то

Следовательно, система (1) линейно независима.

Остается доказать, что произвольный элемент X про­странства L является суммой по модулю 2 каких-либо циклов из (1). Это очевидно для Х = Ø. Пусть xL и Х≠Ø. Согласно утверждению 17.2 Х ∩= Ø. Если X ∩ = { е1, е2, ..., ek}, то

В самом деле, это равенство равносильно равенству

Левую_ часть последнего обозначим через D. Так как Cei ∩ = {ei} и eiX, то D∩B = Ø. Следовательно, D — независимое множество. С другой стороны, DL, а каждый элемент пространства L, отличный от пустого множества, является зависимым множеством. Итак, D = Ø, т. е. верно равенство (2). <

Заметим, что условие бинарности в формулировке теоремы 2.1 существенно. Пусть, например, М = (Е, β) — матроид с множеством элементов Е = {1, 2, 3, 4}, базами которого служат все двухэлементные подмножества мно­жества Е. Тогда {1, 2, 3} и {1, 2, 4} — циклы, а {1, 2, 3} + {1, 2, 4} = {3, 4} — база. Следовательно, множество L не является в этом случае подпространством.

Возвратимся к бинарным матроидам. Пространство L называется пространством циклов матроида М, а его ба­зис (1)— базисом циклов этого матроида (относительно базы В).

Так как двойственный матроид М* также является бинарным (теорема 20.3), то верна теорема, двойствен­ная предыдущей, и возникают понятия пространства ко­циклов и базиса коциклов. Именно, пусть L* — подмно­жество булеана 2^Е, элементами которого служат все ко­циклы матроида М, объединения попарно непересекаю­щихся коциклов и пустое множество. Фиксируем в М базу В. Тогда для любого элемента еВ множество В е содержит ровно один коцикл Сe*. В этих обозначе­ниях верно

Следствие 21.2. Множество L* является подпро­странством пространства 2^Е размерности ρ(М). Множест­во коциклов

где В — фиксированная база матроида M, служит бази­сом этого пространства.

Базисы циклов (1) и коциклов (3) легко определя­ются друг через друга. Верна следующая

Теорема 21.3. Пусть f  В, {Сe1, Сe2, ..., Cek] — множество всех циклов из базиса (1), содержащих f, Xf = {f, е1, е2, ..., ek}. Тогда Xf = Сf*.

> Согласно следствию 16.7 множество f содержит ровно один коцикл. Очевидно, что Xf  f. Поэтому достаточно доказать, что Xf является коциклом. По тео­реме 17.3 множество Xf — коцикл, если выполняются сле­дующие условия:

1. |Xf ∩ С| ≠ 1 для каждого цикла С;

2. Xf — минимальное непустое множество, удовлетво­ряющее условию 1).

Пусть С — цикл, D = C ∩ Xf. Так как (1) — базис про­странства циклов, то С однозначно представляется в ви­де суммы циклов из (1):

Если fC, to f принадлежит хотя бы одному слагаемо­му в (4), например, fCei. Тогда

Пусть fC. Тогда либо f не входит ни в одно из слагаемых (4), либо f входит по меньшей мере в два из этих слагаемых. В первом случае D = Ø. Во втором пусть, например,

Тогда {еi1, еi2}  D, |D|>1. Тем самым доказано, что выполняется условие 1).

Пусть теперь Y Xf. Если f Y, то Y содержится в кобазе и потому конезависимо. Согласно лемме 17.4 су­ществует такой цикл С, что |Y∩С| = 1. Если же fY, но, например, еi ≠ Y, то |Y∩Сei| = 1. Тем самым доказано, что Xf — коцикл. <

Ниже окажется полезным следующее

Утверждение 21.4. Если φ — изоморфизм бинарного матроида М1 на матроид М2, а (1) — базис цикла матроида М1 относительно базы В, то система

(5)

является базисом циклов матроида M2 относительно базы φ(В).

> По определению изоморфизма матроидов множество φ(В) является базой матроида M2. Для любого цикла матроида M1 множество φ(С) — цикл матроида M2. Ecли теперь е — элемент матроида M1 и еB, то φ(e) φ(В). Согласно следствию 17.7 множество S= φ(В) φ(e) содержит ровно один цикл. Этот цикл совпадает с φ(Сe), поскольку Ce  Be и, следовательно, φ(Сe) S. Итак, доказано, что (5)—базис циклов матроида M2 относительно базы φ(В). <

Теперь обратимся к графам. Графический и, следовательно, кографический матроиды бинарны, о чем свидетельствует

Теорема 21.5. Для любого непустого графа G матрица инцидентности I = I(G) является представлением, циклического матроида M(G) над Z2.

> Для произвольного подмножества ребер X обозначим через I(X) подматрицу матрицы I, составленную иp столбцов, соответствующих ребрам, входящим в X. Достаточно доказать, что rank I(X) < |X| тогда и только тогда, когда подграф G(X), порожденный множеством ребер X, содержит цикл. Но I(X) — матрица инцидентности графа G(X). При изменении нумерации вершин или ребер ранг этой матрицы, понятно, не изменится. Пусть граф G(X) содержит цикл С. Перенумеруем вершины и ребра графа G(X) так, чтобы элементы, входящие в цикл С, имели меньшие номера. Теперь матрица I(X) принимает вид

где А — матрица инцидентности графа С. В каждом столбце матрицы А ровно две единицы, поэтому сумма ее строк по модулю 2 равна нулевой строке. Следовательно, det А = 0, и столбцы матрицы А, а вместе с ними и столбцы матрицы I(X) линейно зависимы.

Пусть теперь граф G(X)—ациклический. Очевидно, что достаточно считать его деревом. Снова изменим нуме­рацию вершин и ребер графа G(X). Одной из концевых вершин дерева G(X) и инцидентному ей ребру припи­шем номер 1. Теперь обратимся к дереву G(X) — 1. Од­ной из его концевых вершин и инцидентному ей ребру припишем номер 2 и т. д. В этой нумерации матрица инцидентности примет вид

ранг ее равен числу столбцов. <

Обратимся еще раз к представлениям циклического матроида M(G) над Z₂. Пусть EG=E и φ: Е→Zⁿ2 — представление. Поскольку длина цикла в графе не менее трех, то все двухэлементные множества ребер независи­мы. В этой ситуации, как отмечалось выше, представле­ние φ индуцирует изоморфизм матроидов. Поэтому из предыдущей теоремы непосредственно вытекает

Следствие 21.6. Циклический матроид M(G) не­пустого графа G изоморфен векторному матроиду над Z2, порожденному столбцами матрицы инцидентности I(G).

К бинарному матроиду M(G) применима также тео­рема 21.1, т. е. верно

Следствие 21.7. Все циклы графа G, объединения циклов, не имеющих общих ребер, и пустое множество относительно сложения по модулю 2 и умножения на числа по формулам 1•X=X, 0•X=Ø составляют ли­нейное пространство над Z2 — пространство циклов графа G, размерность которого равна циклическому рангу v(G). Аналогичное утверждение верно для разрезов.

Базисы циклов и коциклов матроида M(G) называ­ются базисами циклов и, соответственно, разрезов гра­фа G.

Следствие 21.8. Каждый цикл графа однозначно представляется в виде суммы по модулю 2 циклов, взя­тых из какого-либо фиксированного базиса циклов. Ана­логичное утверждение верно для разрезов.

Следствие 21.9. Любой граф G содержит не более чем 2^v(G) -1 циклов.

Как правило, число циклов в графе значительно мень­ше, чем число, указанное в предыдущем следствии. Оданако приведенная оценка точна в том смысле, что суще­ствуют графы, число циклов в которых равно 2^v(G) -1. Таковы, например, все леса и граф, изображенный на рис. 21.1.

Следствие 21.10. Любой граф имеет не более чем 2^v(G) -1 разрезов.

Следствие 21.11. Пусть G — граф, Н — его остов, f  ЕH, [Се1, Се2, ..., Cek] — множество всех циклов, входящих в базис циклов относительно Н и содержащих f, Сf* ₌ {f, e1, e2 ..., ek}. Тогда {Сf*: f  ЕH} — базис разре­зов графа G относительно остова Н.

Рассмотрим примеры.

1. Пусть G — граф, изображенный на рис. 21.2. Множество ребер {1, 2, 6, 8} порождает в G остов. Базис циклов относительно этого остова: С3 = G(2, 3, 8), С4 = G(1, 2, 4), C5 = G(1, 5, 6), C₇ = G(2, 1, 6, 7), С₉ = G(6, 1, 2, 8, 9). Каждый другой цикл однозначно разлагается в сумму каких-либо из этих пяти. Например, G(3, 5, 9) = С3 + С5 + С9. Множество {С1*, С2*, С6*, С8*}, где C1* ={1,4, 5, 7, 9}, С2* = {2, 3, 4, 7, 9}, С6* = {6, 5, 7, 9}, C8* = {8, 3, 9}, является базисом разрезов графа G.

2. Найдем базис циклов графа G, заданного своей матрицей инцидентности I. Пусть

Этот граф изображен на рис. 21.3, однако при отыскании базиса циклов рисунок использоваться не будет.

В силу следствия 21.6 базы системы столбцов этой матрицы соответствуют ребрам остовов, а минимальные линейно зависимые системы столбцов — простым циклам.

Используем два следующих утверждения из линей­ной алгебры:

1) Пусть А' — матрица, полученная из матрицы А в результате элементарных преобразований строк. Если ка­кой-либо столбец матрицы А линейно выражается через другие ее столбцы, то точно такое же соотношение (с теми же коэффициен­тами и номерами столбцов) верно и для столбцов матрицы А'.

2) Всякую невырожденную матри­цу с помощью элементарных преобра­зований строк можно превратить в еди­ничную.

Превратим базисную подматрицу матрицы I (т. е. подматрицу макси­мального порядка с отличным от нуля определителем) в единичную, после че­го совсем просто будет найти в графе G остов и базис циклов. Прибавляя (по модулю 2) поочередно ко второй строке первую, к третьей — вторую, к пятой — третью и четвертую, получим

Итак, rank I = 4, первые четыре столбца составляют базу системы столбцов. Соответствующие им ребра e1, e2, e3, е4 порождают в графе G остов.

Далее к первой строке прибавляем третью и четвертую, ко второй — третью, к третьей — четвертую:

Линейные соотношения между столбцами последней мат­рицы те же, что и между столбцами исходной матрицы I. Если Ak (k = 1,…,6) — столбцы матрицы I, то A5 = А2 + А4, А6 = A1 + A3 + A4, столбцы А2, А4, А5 линейно зависимы над Z2, причем это — единственная минимальная линей­но зависимая система столбцов, содержащаяся в {А1, А2, A3, A4, А5}. Аналогично {А1, А3, А4, А5} — единственная минимальная линейно зависимая система столбцов, со­держащаяся в {А1, А2, A3, A4, А6}. Ребра графа G, соответствующие столбцам матрицы I, входящим в эти мини­мальные линейно зависимые системы, образуют в G про­стые циклы, составляющие базис системы циклов:

(см. рис. 21.3).