Циклическое пространство графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
Пусть <tex> m </tex> - количество ребер графа <tex> G </tex>.
+
Пусть <tex> m = |E(G)| </tex>, <tex> n = |V(G)| </tex>.
 
 
Пусть <tex> n </tex> - количество вершин графа <tex> G </tex>.
 
  
 
<tex> B^k </tex> {{---}} линейное пространство элементами которого являются <tex> k </tex>{{---}}мерные двоичные вектора и их сложение определено как сложение по модулю <tex> 2 </tex>.  
 
<tex> B^k </tex> {{---}} линейное пространство элементами которого являются <tex> k </tex>{{---}}мерные двоичные вектора и их сложение определено как сложение по модулю <tex> 2 </tex>.  
Строка 18: Строка 16:
 
'''Обобщенный цикл графа G''' - элемент линейного пространства <tex> C </tex>
 
'''Обобщенный цикл графа G''' - элемент линейного пространства <tex> C </tex>
 
}}
 
}}
 +
 +
Рассмотрим <tex> x \in  C </tex>.
 +
 +
Рассмотрим граф <tex> G_1(V_1,E_1) </tex> где <tex>  E_1 </tex> {{---}} множество ребер, таких что на соответствующих местах вектора <tex> x </tex> стоят единиц, а <tex> V_1 </tex> {{---}} <tex> V(G) </tex> .
 +
 +
В силу определения обобщенного цикла <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0(mod~2) </tex>.
 +
 +
Значит <tex> G </tex> можно декомпозировать  на несколько реберно непересекающихся простых циклов. Отсюда следует что каждому обобщенному циклу соответствуют ребра которые образуют набор реберно непересекающихся простых циклов.
 +
 +
Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра принадлежащие этим циклам то им можно сопоставить обобщенный цикл(в соответствующие места поставить <tex> 1 </tex> , во все остальные <tex> 0 </tex>).
 +
 +
Отсюда следует что <tex> C </tex> изоморфно пространству <tex> Т </tex>, элементами которого являются множества ребер из которых можно составить несколько реберно непересекающихся простых циклов.
 +
 +
=== Размерность линейного пространства обобщенных циклов ===
 +
 
== Литература ==
 
== Литература ==
 
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.
 
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.

Версия 04:50, 2 ноября 2011

Определение

Пусть [math] m = |E(G)| [/math], [math] n = |V(G)| [/math].

[math] B^k [/math] — линейное пространство элементами которого являются [math] k [/math]—мерные двоичные вектора и их сложение определено как сложение по модулю [math] 2 [/math].

Рассмотрим матрицу инцидентности [math] G [/math].

Сопоставим ей линейный оператор [math] I : R^m \rightarrow R^n [/math]

Определение:
Циклическое пространство графа[math] C = Ker(I) [/math]


Определение:
Обобщенный цикл графа G - элемент линейного пространства [math] C [/math]


Рассмотрим [math] x \in C [/math].

Рассмотрим граф [math] G_1(V_1,E_1) [/math] где [math] E_1 [/math] — множество ребер, таких что на соответствующих местах вектора [math] x [/math] стоят единиц, а [math] V_1 [/math][math] V(G) [/math] .

В силу определения обобщенного цикла [math] \forall v : v \in V_1 ~ deg(v) \equiv 0(mod~2) [/math].

Значит [math] G [/math] можно декомпозировать на несколько реберно непересекающихся простых циклов. Отсюда следует что каждому обобщенному циклу соответствуют ребра которые образуют набор реберно непересекающихся простых циклов.

Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра принадлежащие этим циклам то им можно сопоставить обобщенный цикл(в соответствующие места поставить [math] 1 [/math] , во все остальные [math] 0 [/math]).

Отсюда следует что [math] C [/math] изоморфно пространству [math] Т [/math], элементами которого являются множества ребер из которых можно составить несколько реберно непересекающихся простых циклов.

Размерность линейного пространства обобщенных циклов

Литература

Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.