Изменения

<tex> B^k </tex> {{---}} линейное пространство , элементами которого являются <tex> k </tex>{{---}}мерные двоичные вектора и их сложение определено , как сложение по модулю <tex> 2 </tex>.

Рассмотрим граф <tex> G_1(V_1,E_1) </tex> , где <tex> E_1 </tex> {{---}} множество ребер, таких что на соответствующих местах вектора <tex> x </tex> стоят единицединицы, а <tex> V_1 = V(G) </tex> .

В силу определения обобщенного цикла : <tex> \forall v : v \in V_1 ~ deg(v) \equiv 0(mod~2) </tex>.

Значит , <tex> G </tex> можно декомпозировать на несколько реберно непересекающихся простых циклов. Отсюда следует , что каждому обобщенному циклу соответствуют ребра , которые образуют набор реберно непересекающихся простых циклов.

Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра , принадлежащие этим циклам , то им можно сопоставить обобщенный цикл(в соответствующие места поставить <tex> 1 </tex> , во все остальные <tex> 0 </tex>).

Отсюда следует , что <tex> C </tex> изоморфно пространству <tex> T </tex>, элементами которого являются множества ребер , из которых можно составить несколько реберно непересекающихся простых циклов.

<tex> dim(C)=dim(Ker(i))=m-Rang(A) </tex> , где <tex> Rang(A) = </tex> максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть цикл в <tex> G </tex> , то набор столбцов соответствующий ребрам в этом цикле ЛЗ. Отсюда следует, что если любому множеству ребер , содержащих цикл , в соответствие сопоставить набор столбцов из <tex> A </tex> то он будет ЛЗ. Если же множество ребер не содержит цикл , то набор ЛНЗ(если бы он был ЛЗ, тогда бы существовал <tex> x \in C </tex> , который соответствует некоторому подмножеству данного набора ребер, значит из набора ребер можно выделить цикл, противоречие). Максимальное число ребер , которые мы можем выделить из G и которые не содержат цикл <tex>= n - k </tex>(в каждой компоненте связности выделим цикл).