Изменения

'''Регулярный Бинарный матроид(regular binary matroid)''' - матроид, представимый над любым полемцелых чисел по модулю 2.

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