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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = Рассмотрим каркас T графа G.<math>e_1,...,e_{s}</math> — все ребра графа G которые…»)
 
 
(не показаны 32 промежуточные версии 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition =
+
|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'''
+
'''Фундаментальный цикл графа <tex>G</tex> относительно остова <tex>T</tex>''' (''англ. fundamental cycle'') {{---}} простой цикл <tex>C</tex>, полученный путем добавления к [[Остовные деревья: определения, лемма о безопасном ребре|остову]] <tex>T</tex> ребра <tex>e_1e_2 \notin T.</tex>}}
}}
+
[[Файл:Fundomential.png|380px|центр|thumb|Пример фундаментального цикла в графе. <font color=#ED1C24>Красным</font> выделен фундаментальный цикл, полученный добавлением ребра <tex>(3, 4)</tex>]]
 +
 
 
{{Теорема
 
{{Теорема
 
|statement =
 
|statement =
Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа.
+
Множество всех фундаментальных циклов относительно любого остова <tex>T</tex> графа <tex>G</tex> образует базис [[Циклическое пространство графа|циклического пространства]] этого графа.
 
|proof =
 
|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>.
+
Рассмотрим остов <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</tex>, <tex> e_1 \ldots e_{k} </tex> ребра принадлежащие <tex>Z</tex> и не принадлежащие <tex>T</tex>. Рассмотрим граф <tex> F = Z \oplus C_1 \oplus \ldots \oplus C_{k} </tex>. Каждое из ребер <tex> e_{t} , t = 1,\ldots ,k </tex> встречается ровно в двух слагаемых — <tex>Z</tex> и <tex>C_{k}</tex>. Значит <tex>F</tex> содержит только ребра из <tex>T</tex>. Так как <tex> C_1 \ldots C_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин <tex>Z</tex> тоже четны по [[Циклическое пространство графа#lemma1|лемме]], значит степени всех вершин <tex>F</tex> четны. Если <tex>F</tex> непустой граф, то в <tex>F</tex> есть цикл, значит цикл есть и в <tex>T</tex>. Значит <tex>F</tex> пустой граф, откуда следует что <tex>Z = C_1 \oplus \ldots \oplus C_{k} </tex>.
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Остовные деревья: определения, лемма о безопасном ребре|Остовные деревья]]
 +
* [[Циклическое пространство графа|Циклическое пространство графа]]
 +
 +
==Источники информации==
 +
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Текущая версия на 22:33, 20 октября 2016

Определение:
Фундаментальный цикл графа [math]G[/math] относительно остова [math]T[/math] (англ. fundamental cycle) — простой цикл [math]C[/math], полученный путем добавления к остову [math]T[/math] ребра [math]e_1e_2 \notin T.[/math]
Пример фундаментального цикла в графе. Красным выделен фундаментальный цикл, полученный добавлением ребра [math](3, 4)[/math]
Теорема:
Множество всех фундаментальных циклов относительно любого остова [math]T[/math] графа [math]G[/math] образует базис циклического пространства этого графа.
Доказательство:
[math]\triangleright[/math]

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

Докажем, что любой цикл из циклического пространства графа [math]G[/math] является суммой фундаментальных циклов. Пусть [math]Z[/math] — цикл циклического пространства графа [math]G[/math], [math] e_1 \ldots e_{k} [/math] ребра принадлежащие [math]Z[/math] и не принадлежащие [math]T[/math]. Рассмотрим граф [math] F = Z \oplus C_1 \oplus \ldots \oplus C_{k} [/math]. Каждое из ребер [math] e_{t} , t = 1,\ldots ,k [/math] встречается ровно в двух слагаемых — [math]Z[/math] и [math]C_{k}[/math]. Значит [math]F[/math] содержит только ребра из [math]T[/math]. Так как [math] C_1 \ldots 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 \ldots \oplus C_{k} [/math].
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6