Фундаментальные циклы графа — различия между версиями
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | Рассмотрим каркас T графа G. <tex>e_1,...,e_{s}</tex> — все ребра графа G которые не входят в каркас T. При добавлении <math>e_{i}</math> образуется простой цикл <tex>C_{i}</tex>. Семейство циклов <tex>C_1 ... C_{s}</tex> называется '''фундаментальными циклами графа G относительно каркаса T''' | + | Рассмотрим каркас <tex>T</tex> графа <tex>G</tex>. <tex>e_1,...,e_{s}</tex> — все ребра графа <tex>G</tex> которые не входят в каркас <tex>T</tex>. При добавлении <math>e_{i}</math> образуется простой цикл <tex>C_{i}</tex>. Семейство циклов <tex>C_1 ... C_{s}</tex> называется '''фундаментальными циклами графа <tex>G</tex> относительно каркаса <tex>T</tex>''' |
}} | }} | ||
== Свойства == | == Свойства == | ||
{{Теорема | {{Теорема | ||
|statement = | |statement = | ||
| − | Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа. | + | Множество всех фундаментальных циклов относительно любого каркаса <tex>T</tex> графа <tex>G</tex> образует базис циклического пространства этого графа. |
|proof = | |proof = | ||
| − | Рассмотрим каркас T графа G и фундаментальные циклы <tex> C_1 ... C_{s} </tex> относительно каркаса T. В каждом из <tex> С_{i} </tex> есть ребро <tex>e_{i}</tex> которое принадлежит ровно одному из <tex> C_1 ... C_{s} </tex>. Поэтому сумма различных фундаментальных циклов относительно каркаса Т не является пустым графом, из чего следует, что <tex> C_1 ... C_{s} </tex> линейно независимы. | + | Рассмотрим каркас <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>Т</tex> не является пустым графом, из чего следует, что <tex> C_1 ... C_{s} </tex> линейно независимы. |
| − | Докажем, что любой цикл из циклического пространства графа G является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, <tex> e_1 ... e_{k} </tex> ребра принадлежащие Z и не принадлежащие T. Рассмотрим граф <tex> F = Z \oplus C_1 \oplus ... \oplus C_{k} </tex>. Каждое из ребер <tex> e_{t} , t = 1,..,k </tex> встречается ровно в двух слагаемых — Z и <tex>C_{k}</tex>. Значит F содержит только ребра из T. Так как <tex> C_1 ... C_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин Z тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин F четны. Если F непустой граф то в F есть цикл, значит цикл есть и в T. Значит F пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </tex>. | + | Докажем, что любой цикл из циклического пространства графа <tex>G</tex> является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, <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 ... C_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин <tex>Z</tex> тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин <tex>F</tex> четны. Если <tex>F</tex> непустой граф то в <tex>F</tex> есть цикл, значит цикл есть и в <tex>T</tex>. Значит <tex>F</tex> пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </tex>. |
}} | }} | ||
== Литература == | == Литература == | ||
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.55. — ISBN 978-5-397-00622-4. | Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.55. — ISBN 978-5-397-00622-4. | ||
Версия 21:16, 27 октября 2010
Определение
| Определение: |
| Рассмотрим каркас графа . — все ребра графа которые не входят в каркас . При добавлении образуется простой цикл . Семейство циклов называется фундаментальными циклами графа относительно каркаса |
Свойства
| Теорема: |
Множество всех фундаментальных циклов относительно любого каркаса графа образует базис циклического пространства этого графа. |
| Доказательство: |
|
Рассмотрим каркас графа и фундаментальные циклы относительно каркаса . В каждом из есть ребро которое принадлежит ровно одному из . Поэтому сумма различных фундаментальных циклов относительно каркаса не является пустым графом, из чего следует, что линейно независимы. Докажем, что любой цикл из циклического пространства графа является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, ребра принадлежащие и не принадлежащие . Рассмотрим граф . Каждое из ребер встречается ровно в двух слагаемых — и . Значит содержит только ребра из . Так как простые циклы, то степени всех их вершин четны, степени вершин тоже четны по лемме, значит степени всех вершин четны. Если непустой граф то в есть цикл, значит цикл есть и в . Значит пустой граф, откуда следует что . |
Литература
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.55. — ISBN 978-5-397-00622-4.
