137
правок
Изменения
м
→Бинарный матроид
{{Определение
|definition=
'''Бинарный матроид(binary matroid)''' - — матроид, представимый над полем целых чисел по модулю 2.
}}
Например, графовый матроид является бинарным.
Составим матрицу инцидентности <tex>A = (a_{ij})</tex> для графа <tex>G = \langle V, E \rangle</tex>. Строки этой матрицы соответствуют вершинам графа, а столбцы {---} — ребрам.
* Если <tex>j</tex>-ое ребро есть петля, инцидентная <tex>i</tex>-ой вершине, то <tex>a_{ij} = 0</tex>.
* Если <tex>i</tex>-ая вершина инцидентна <tex>j</tex>-ому ребру, то <tex>a_{ij} = 1</tex>
<tex>\Rightarrow</tex> Если некоторые столбцы матрицы <tex>A</tex> линейно-зависимы, то среди них можно выделить столбцы с нулевой суммой. Есть два варианта:
1) Cреди выбранных столбцов есть нулевой, значит тогда в соответствующем множестве ребер есть петля, то есть цикл.
2) У нас есть столбец <tex>S</tex>, который является суммой остальных столбцов. Этому столбцу соответствует ребро <tex>uv</tex>. Начнем с вершины <tex>u</tex> переходить по другим ребрам из <tex>R \setminus uv</tex> (по каждому ребру проходим только один раз), в итоге мы придем в вершину <tex>v</tex>, так для остальных вершин у нас обязательно будет четное число выходящих из них ребер, потому что иначе на позиции этой вершины в столбце <tex>S</tex> была бы единица (а единицы у нас только на позициях u и v). То есть Таким образом мы показали, что существует два пути между вершинами 7<tex>u</tex> и <tex>v</tex> (тот который мы построили и путь по ребру <tex>uv</tex>), значит в выбранном множестве ребер есть цикл.
<tex>\Leftarrow</tex> Пусть некоторое множество ребер содержит цикл. Если среди них есть петля, то соответствующий ей столбец будет нулевым (по построению матрицы инцидентности), он и обеспечивает линейную-зависимость всего набора векторов.
