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

Матроид называется бинарным, если он представим над , полем целых чисел по mod 2.

Очевидно, что циклический матроид М (G) и матроид разрезов графа G бинарные. Нами уже доказана теорема 4.6, в которой каждый цикл М (G) выражается в виде суммы по mod 2 некоторых базисных циклов графа G. Подобный результат справедлив и для разрезающих множеств графа G. Это свойство циклов и разрезающих множеств (коциклов) сохраняется и для случая бинарных матроидов. Однако в общем случае произвольных матроидов оно не выполняется. Пусть, например, , а М в качестве циклов имеет все подмножества из трех элементов S. Тогда сумма по mod 2

циклов {1, 2, 3} и {1, 2, 4} даст {3, 4}, являющееся независимым множеством матроида М.

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

Пусть М — матроид на множестве S. Пусть — база — соответствующая кобаза М. Напомним, что где — базисный цикл . Аналогично , где — базисный коцикл . Как и в случае неориентированных графов (гл. 6), определим базисную коцикломатическую матрицу и базисную цикломатическую матрицу матроида М по отношению к базе В. Очевидно, что матрицы будут иметь вид

Заметим, что — -матрицы.

Допустим, что матроид М — бинарный. Тогда он имеет стандартное представление на вида

    (10.10)

Пусть базисный цикл Тогда сумма по mod 2 столбцов матрицы (10.10), соответствующих элементам равна нулю. Поскольку сумма по mod 2 векторов аналогична кольцевой сумме соответствующих множеств, легко видеть, что

Другими словами,

    (10.11)

Таким образом, матрица является стандартным представлением над и по отношению к базе В.

Исходя из стандартного представления для двойственного матроида М, можно аналогично показать, что является стандартным представлением над матроида М.

Поскольку матроид имеет по отношению к данной базе единственное стандартное представление, из следствия 10.24.1 вытекает

    (10.12)

Таким образом, мы доказали следующую теорему:

Теорема 10.25. Пусть М — бинарный матроид на множестве S.

1. Базисная цикломатическая матрица М по отношению к произвольной базе является стандартным представлением этого матроида.

2. Базисная коцикломатическая матрица матроида М по отношению к произвольной базе является стандартным представлением матроида М.

Из формулы (10.12) мы получаем также следующий интересный результат.

Теорема 10.26. Пусть М — бинарный матроид. Пусть — базисные коцикломатическая и цикломатическая матрицы матроида М по отношению к общей базе. Тогда

    (10.13)

Пусть С — цикл матроида М; мы можем связать с ним -вектор-строку, каждый элемент которого соответствует элементу матроида М, а элемент вектора равен 1, если соответствующий элемент множества S входит в цикл С. Например, строки — это векторы, соответствующие базисным циклам. Матрица, содержащая все циклические векторы матроида М, называется цикломатической матрицей матроида М и обозначается D (М). Аналогичным образом определяется коцикломатическая матрица D (М) матроида М.

Допустим, что — вектор, соответствующий циклу С бинарного матроида М. Так как стандартное представление матроида М, сумма по mod 2 столбцов соответствующих элементам С, равна 0. Другими словами,

    (10.14)

Аналогично если — коциклический вектор, то

    (10.15)

Заметим, что мы считали расстановку столбцов соответствующей одному порядку элементов.

Теорема 10.27. Пусть М — бинарный матроид на S. Пусть В — база, цикл матроида . Если будет обозначать базисный цикл элемента по отношению к В, то

Доказательство основано на выражениях (10.12) и (10.14). См. теорему 6.7. Для доказательства обратной теоремы мы нуждаемся в следующем утверждении:

Теорема 10.28. Пусть М — матроид. Пусть для любых базы В и цикла С матроида М имеем , где

— базисный цикл по отношению к В, Тогда сумма по двух любых различных циклов матроида М содержит цикл этого матроида.

Доказательство. Допустим, что не содержит цикла. Пусть

Тогда — независимое множество в матроиде М. Поэтому существует база Но тогда

Следовательно, по предположению теоремы что противоречит условию

Теорема 10.29. Пусть М — матроид. Пусть для любых базы В и цикла С матроида М имеем , где а — базисный цикл X; по отношению к В. Тогда М — бинарный матроид.

Доказательство. Пусть — произвольная база матроида Базисная цикломатическая матрица матроида М по отношению к В имеет вид

Для доказательства теоремы покажем, что матрица

    (10.16)

является стандартным представлением матроида М над GF (2).

Пусть С — цикл матроида М. Если то по условиям теоремы Из определения А следует, что сумма по mod 2 столбцов матрицы в формуле (10.16), соответствующих членам цикла С, равна 0. Таким образом, эти столбцы линейно зависимы над GF (2).

Допустим, что — цикл матроида АГ, порожденного на S линейной зависимостью соответствующих вектор-столбцов матрицы (10.16). Тогда По теореме 10.28 W содержит цикл С матроида М. Но С не может быть собственным подмножеством цикла W, так как это противоречило бы тому, что W — цикл матроида М. Таким образом, Следовательно, матрица (10.16) есть представление матроида М над GF (2). Другие характеризации бинарного матроида даны в следующей теореме. Теорема 10.30. Пусть М — матроид. Следующие утверждения эквавалентны:

1. Для любых цикла С и коцикла С матроида четно.

2. Сумма по mod 2 произвольного набора различных циклов матроида М есть объединение непересекакяцихся циклов того же матроида.

3. Если для любых базы В и цикла С матроида М имеем — базисный цикл - по отношению к базе В, то

4. М — бинарный матроид.

Доказательство.

Пусть -различные циклы матроида М, а Не нарушая общности, допустим, что А не содержит петель.

Поскольку для любого коцикла — четно то легко видеть, что — также четно. Допустим, что А — независимое множество. Тогда приходим к противоречию, поскольку по лемме 10.3 существует коцикл, имеющий точно один элемент из А. Таким образом, А — зависимое множество и содержит цикл С.

Если теорема доказана. Допустим противное: пусть Заметим, что для любого коцикла С имеем, что четно. Поэтому мы можем повторить рассуждения для A Поскольку конечно и этот процесс в конце концов закончится, приводя в результате к набору непересекающихся циклов, объединение которых равно А.

. См. доказательство теоремы 4.6.

. Аналогично теореме 10.29.

. По теореме 10,27 всякий цикл С можно выразить через базисные циклы . По формуле (10.15) имеем, что — четно для всех . Поэтому легко видеть, что — четно.

Очевидно, что заменой циклов на коциклы в теореме 10.30 достигается альтернативная характеризация в терминах коциклов.