Изменения

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

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

Рассмотрим каркас остов <tex>T</tex> графа <tex>G</tex> и фундаментальные циклы <tex> C_1 ... \ldots C_s </tex> относительно каркаса остова <tex>T</tex>. В каждом цикле есть ребро <tex>e_i</tex>, которое принадлежит ровно одному из <tex> C_1 ... \ldots C_{s} </tex>. Поэтому сумма различных фундаментальных циклов относительно каркаса остова <tex>T</tex> не является пустым графом, из чего следует, что <tex> C_1 ... \ldots C_s </tex> линейно независимы.

Докажем==См. также==* [[Остовные деревья: определения, что любой цикл из циклического пространства лемма о безопасном ребре|Остовные деревья]]* [[Циклическое пространство графа <tex>G</tex> является суммой фундаментальных циклов. Пусть <tex>Z</tex> — цикл циклического пространства |Циклическое пространство графа <tex>G<]] ==Источники информации==* Харари Фрэнк '''Теория графов''' = Graph theory/tex>, <tex> e_1 Пер.с англ.. e_{k} </tex> ребра принадлежащие <tex>Z</tex> и не принадлежащие <tex>T</tex>предисл. Рассмотрим граф <tex> F = Z \oplus C_1 \oplus В.П.Козырева. \oplus C_{k} </tex>Под ред. Каждое из ребер <tex> e_{t} , t = 1,Г.П.,k </tex> встречается ровно в двух слагаемых — <tex>Z</tex> и <tex>C_{k}</tex>Гаврилова. Значит <tex>F</tex> содержит только ребра из <tex>T</tex>Изд. Так как <tex> C_1 2-е.— М.. C_{k} </tex> простые циклы: Едиториал УРСС, то степени всех их вершин четны, степени вершин <tex>Z</tex> тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин <tex>F</tex> четны2003. Если <tex>F</tex> непустой граф, то в <tex>F</tex> есть цикл, значит цикл есть и в <tex>T</tex>— 296 с. Значит <tex>F</tex> пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </tex>.}}— ISBN 5-354-00301-6

== Литература ==[[Категория: Алгоритмы и структуры данных]]Харари Ф. Теория [[Категория: Основные определения теории графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.55. — ISBN 978-5-397-00622-4.]]