333
правки
Изменения
Нет описания правки
Рассмотрим граф <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> |E_1(G)|=0 </tex> очевидно выполняется.
Рассмотрим <tex> G_1 </tex>. <tex> \forall v : v \in V_1 ~ deg(v) \equiv 0(\mod~2) \Rightarrow |E_1(G)| > |V(G)| - 1 \Rightarrow </tex> существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.
Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.
