Фундаментальные циклы графа — различия между версиями
VVolochay (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 17 промежуточных версий 7 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
{{Определение | {{Определение | ||
| − | |definition = | + | |definition= |
| − | + | '''Фундаментальный цикл графа <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 = | ||
| − | Множество всех фундаментальных циклов относительно любого | + | Множество всех фундаментальных циклов относительно любого остова <tex>T</tex> графа <tex>G</tex> образует базис [[Циклическое пространство графа|циклического пространства]] этого графа. |
|proof = | |proof = | ||
| − | Рассмотрим | + | Рассмотрим остов <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 | + | Докажем, что любой цикл из циклического пространства графа <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 | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Основные определения теории графов]] | [[Категория: Основные определения теории графов]] | ||
Текущая версия на 19:07, 4 сентября 2022
| Определение: |
| Фундаментальный цикл графа относительно остова (англ. fundamental cycle) — простой цикл , полученный путем добавления к остову ребра |
| Теорема: |
Множество всех фундаментальных циклов относительно любого остова графа образует базис циклического пространства этого графа. |
| Доказательство: |
|
Рассмотрим остов графа и фундаментальные циклы относительно остова . В каждом цикле есть ребро , которое принадлежит ровно одному из . Поэтому сумма различных фундаментальных циклов относительно остова не является пустым графом, из чего следует, что линейно независимы. Докажем, что любой цикл из циклического пространства графа является суммой фундаментальных циклов. Пусть — цикл циклического пространства графа , ребра принадлежащие и не принадлежащие . Рассмотрим граф . Каждое из ребер встречается ровно в двух слагаемых — и . Значит содержит только ребра из . Так как простые циклы, то степени всех их вершин четны, степени вершин тоже четны по лемме, значит степени всех вершин четны. Если непустой граф, то в есть цикл, значит цикл есть и в . Значит пустой граф, откуда следует что . |
См. также
Источники информации
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
