|
|
| Строка 10: |
Строка 10: |
| | |proof = | | |proof = |
| | | | |
| − | Рассмотрим каркас <tex>T</tex> графа <tex>G</tex> и фундаментальные циклы <tex> C_1 ... C_s </tex> относительно каркаса <tex>T</tex>. В каждом из <tex> С_i </tex> есть ребро <tex>e_i</tex>, которое принадлежит ровно одному из <tex> C_1 ... C_{s} </tex>. Поэтому сумма различных фундаментальных циклов относительно каркаса <tex>T</tex> не является пустым графом, из чего следует, что <tex> C_1 ... C_s </tex> линейно независимы. | + | Рассмотрим каркас <tex>T</tex> графа <tex>G</tex> и фундаментальные циклы <tex> C_1 ... C_s </tex> относительно каркаса <tex>T</tex>. В каждом цикле есть ребро <tex>e_i</tex>, которое принадлежит ровно одному из <tex> C_1 ... C_{s} </tex>. Поэтому сумма различных фундаментальных циклов относительно каркаса <tex>T</tex> не является пустым графом, из чего следует, что <tex> C_1 ... C_s </tex> линейно независимы. |
| | | | |
| | | | |
Версия 07:33, 17 января 2011
Определение
| Определение: |
| Рассмотрим каркас [math]T[/math] графа [math]G[/math]. [math]e_1,...,e_{s}[/math] — все ребра графа [math]G[/math] которые не входят в каркас [math]T[/math]. При добавлении [math]e_{i}[/math] образуется простой цикл [math]C_{i}[/math]. Семейство циклов [math]C_1 ... C_{s}[/math] называется фундаментальными циклами графа [math]G[/math] относительно каркаса [math]T[/math] |
Свойства
| Теорема: |
Множество всех фундаментальных циклов относительно любого каркаса [math]T[/math] графа [math]G[/math] образует базис циклического пространства этого графа. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим каркас [math]T[/math] графа [math]G[/math] и фундаментальные циклы [math] C_1 ... C_s [/math] относительно каркаса [math]T[/math]. В каждом цикле есть ребро [math]e_i[/math], которое принадлежит ровно одному из [math] C_1 ... C_{s} [/math]. Поэтому сумма различных фундаментальных циклов относительно каркаса [math]T[/math] не является пустым графом, из чего следует, что [math] C_1 ... C_s [/math] линейно независимы.
Докажем, что любой цикл из циклического пространства графа [math]G[/math] является суммой фундаментальных циклов. Пусть [math]Z[/math] — цикл циклического пространства графа G, [math] e_1 ... e_{k} [/math] ребра принадлежащие [math]Z[/math] и не принадлежащие [math]T[/math]. Рассмотрим граф [math] F = Z \oplus C_1 \oplus ... \oplus C_{k} [/math]. Каждое из ребер [math] e_{t} , t = 1,..,k [/math] встречается ровно в двух слагаемых — [math]Z[/math] и [math]C_{k}[/math]. Значит [math]F[/math] содержит только ребра из [math]T[/math]. Так как [math] C_1 ... C_{k} [/math] простые циклы, то степени всех их вершин четны, степени вершин [math]Z[/math] тоже четны по лемме, значит степени всех вершин [math]F[/math] четны. Если [math]F[/math] непустой граф то в [math]F[/math] есть цикл, значит цикл есть и в [math]T[/math]. Значит [math]F[/math] пустой граф, откуда следует что [math]Z = C_1 \oplus ... \oplus C_{k} [/math]. |
| [math]\triangleleft[/math] |
Литература
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.55. — ISBN 978-5-397-00622-4.
