Изменения
Новая страница: «{{Определение |definition = Рассмотрим каркас T графа G.<math>e_1,...,e_{s}</math> — все ребра графа G которые…»
{{Определение
|definition =
Рассмотрим каркас T графа G.<math>e_1,...,e_{s}</math> — все ребра графа G которые не входят в каркас T. При добавлении <math>e_{i}</math> образуется простой цикл <math>C_{i}</math>. Семейство циклов <math>C_1 ... C_{s}</math> называется '''фундаментальными циклами графа G относительно каркаса T'''
}}
{{Теорема
|statement =
Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа.
|proof =
Рассмотрим каркас T графа G и фундаментальные циклы <math> C_1 ... C_{s} </math> относительно каркаса T. В каждом из <math> С_{i} </math> есть ребро <math>e_{i}</math> которое принадлежит ровно одному из <math> C_1 ... C_{s} </math>. Поэтому раздичных фундаментальных циклов относительно каркаса Т не является пустым графом, из чего следует, что <math> C_1 ... C_{s} </math> линейно независимы.
Докажем, что любой цикл из циклического пространства графа G является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, <math> e_1 ... e_{k} </math> ребра принадлежащие Z и не принадлежащие T. Рассмотрим граф <math> F = Z \oplus C_1 \oplus ... \oplus C_{k} </math>. Каждое из ребер <math> e_{t} , t = 1,..,k </math> встречается ровно в двух слагаемых — Z и <math>C_{k}</math>. Значит F содержит только ребра из T. Так как <math> С_1 ... С_{k} </math> простые циклы, то степени всех их вершин четны, степени вершин Z тоже четны по лемме, значит степени всех вершин F четны. Если F непустой граф то в F есть цикл, значит цикл есть и в T. Значит F пустой граф, откуда следует что <math>Z = C_1 \oplus ... \oplus C_{k} </math>.
}}
|definition =
Рассмотрим каркас T графа G.<math>e_1,...,e_{s}</math> — все ребра графа G которые не входят в каркас T. При добавлении <math>e_{i}</math> образуется простой цикл <math>C_{i}</math>. Семейство циклов <math>C_1 ... C_{s}</math> называется '''фундаментальными циклами графа G относительно каркаса T'''
}}
{{Теорема
|statement =
Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа.
|proof =
Рассмотрим каркас T графа G и фундаментальные циклы <math> C_1 ... C_{s} </math> относительно каркаса T. В каждом из <math> С_{i} </math> есть ребро <math>e_{i}</math> которое принадлежит ровно одному из <math> C_1 ... C_{s} </math>. Поэтому раздичных фундаментальных циклов относительно каркаса Т не является пустым графом, из чего следует, что <math> C_1 ... C_{s} </math> линейно независимы.
Докажем, что любой цикл из циклического пространства графа G является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, <math> e_1 ... e_{k} </math> ребра принадлежащие Z и не принадлежащие T. Рассмотрим граф <math> F = Z \oplus C_1 \oplus ... \oplus C_{k} </math>. Каждое из ребер <math> e_{t} , t = 1,..,k </math> встречается ровно в двух слагаемых — Z и <math>C_{k}</math>. Значит F содержит только ребра из T. Так как <math> С_1 ... С_{k} </math> простые циклы, то степени всех их вершин четны, степени вершин Z тоже четны по лемме, значит степени всех вершин F четны. Если F непустой граф то в F есть цикл, значит цикл есть и в T. Значит F пустой граф, откуда следует что <math>Z = C_1 \oplus ... \oplus C_{k} </math>.
}}
