Фундаментальные циклы графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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'''
+
  Рассмотрим каркас 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'''
 
}}
 
}}
 
== Свойства ==
 
== Свойства ==
Строка 9: Строка 9:
 
Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа.
 
Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа.
 
|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> линейно независимы.
+
Рассмотрим каркас 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> линейно независимы.
 
Докажем, что любой цикл из циклического пространства графа 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> С_1 ... С_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин Z тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин F четны. Если F непустой граф то в F есть цикл, значит цикл есть и в T. Значит F пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </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> С_1 ... С_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин Z тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин F четны. Если F непустой граф то в F есть цикл, значит цикл есть и в T. Значит F пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </tex>.
 
}}
 
}}

Версия 23:46, 13 октября 2010

Определение

Определение:
Рассмотрим каркас 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

Свойства

Теорема:
Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа.
Доказательство:
[math]\triangleright[/math]

Рассмотрим каркас 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].
[math]\triangleleft[/math]