137
правок
Изменения
м
→Бинарный матроид
Необходимо доказать, что если мы возьмем множество ребер <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). Таким образом мы показали, что существует два пути между вершинами 7<tex>u</tex> и <tex>v</tex> (тот который мы построили и путь по ребру <tex>uv</tex>), значит в выбранном множестве ребер есть цикл.
<tex>\Leftarrow</tex> Пусть некоторое множество на множестве ребер содержит есть цикл, докажем линейную-зависимость соответствующих столбцов. Если среди них данного множества ребер есть петля, то соответствующий ей столбец будет нулевым (по построению матрицы инцидентности), он и обеспечивает линейную-зависимость всего набора векторов.Если цикла петли нет, то рассмотрим столбцы, отвечающие ребрам простого цикла. Любая строка матрицы <tex>A</tex> содержит в этих столбцах ровно 2 единицы. Поэтому сумма по модулю 2 указанных столбцов равна нулевому столбцу, что означает линейную зависимость исходного множества столбцов.
==Матроид с выкинутым элементом==
