Изменения

Перейти к: навигация, поиск

Циклическое пространство графа

1330 байт добавлено, 00:36, 10 октября 2010
Эквивалентность определений
Определения 1 и 2 эквивалентны.
|proof =
* <math>1 \rightarrow 2</math>
Рассмотрим множество <math>\Zeta</math> реберно непересекающихся циклов. 1-цепь <math>\sigma</math> состоящая из всех ребер из <math>\Zeta</math>
имеет границу 0, так как для любого ребра <math>e_{i} = (u_{i}, v_{i})\in \Zeta \ u_{i}, v_{i}</math> встречаются в <math>\delta\sigma </math> четное число раз.
* <math>2 \rightarrow 1</math>
Рассмотрим 1-цепь <math>\sigma</math>. Из того, что граница <math>\sigma</math> равна 0 следует, что для любого <math>e = (u, v) \in \sigma </math> u и v встречаются в <math>\delta \sigma </math> четное число раз. Значит <math>\sigma</math> можно разбить на дизъюнктные подмножества <math>E_1,..., E_{i},</math> такие, что путь состоящий из <math>u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}</math>, где <math>e_{k} =(u_{k}, v_{k}) \in E_{i}</math> является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.
}}
}}
== Свойства ==
{{Теорема
Анонимный участник

Навигация