Изменения

Рассмотрим остов {{Определение|definition='''Фундаментальный цикл графа <tex>TG</tex> графа относительно остова <tex>GT</tex>''' (''англ. <tex>e_1,\ldots,e_fundamental cycle'') {{s---}</tex> — все ребра графа } простой цикл <tex>GC</tex>, которые не входят в остов полученный путем добавления к [[Остовные деревья: определения, лемма о безопасном ребре|остову]] <tex>T</tex>. При добавлении ребра <mathtex>e_{i}e_1e_2 \notin T.</math> образуется простой цикл <tex>C_{i}</tex>}[[Файл:Fundomential.png|380px|центр|thumb|Пример фундаментального цикла в графе. Семейство циклов <texfont color=#ED1C24>C_1 \ldots C_{s}Красным</texfont> называется '''фундаментальными циклами графа выделен фундаментальный цикл, полученный добавлением ребра <tex>G</tex> относительно остова <tex>T(3, 4)</tex>'''.]]

Множество всех фундаментальных циклов относительно любого остова <tex>T</tex> графа <tex>G</tex> образует базис [[Циклическое пространство графа|циклического пространства ]] этого графа.

Докажем, что любой цикл из циклического пространства графа <tex>G</tex> является суммой фундаментальных циклов. Пусть <tex>Z</tex> — цикл циклического пространства графа <tex>G</tex>, <tex> e_1 \ldots e_{k} </tex> ребра принадлежащие <tex>Z</tex> и не принадлежащие <tex>T</tex>. Рассмотрим граф <tex> F = Z \oplus C_1 \oplus \ldots \oplus C_{k} </tex>. Каждое из ребер <tex> e_{t} , t = 1,\ldots ,k </tex> встречается ровно в двух слагаемых — <tex>Z</tex> и <tex>C_{k}</tex>. Значит <tex>F</tex> содержит только ребра из <tex>T</tex>. Так как <tex> C_1 \ldots C_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин <tex>Z</tex> тоже четны по [[Циклическое пространство графа#lemma1|лемме]], значит степени всех вершин <tex>F</tex> четны. Если <tex>F</tex> непустой граф, то в <tex>F</tex> есть цикл, значит цикл есть и в <tex>T</tex>. Значит <tex>F</tex> пустой граф, откуда следует что <tex>Z = C_1 \oplus \ldots \oplus C_{k} </tex>.