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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
Строка 15: Строка 15:
  
 
Определим пространство <tex> T </tex>, как пространство элементами которого являются наборы ребер из которых можно составить несколько простих реберно непересекающихся циклов.   
 
Определим пространство <tex> T </tex>, как пространство элементами которого являются наборы ребер из которых можно составить несколько простих реберно непересекающихся циклов.   
 +
 
{{Лемма
 
{{Лемма
|statement=<tex>T </tex> изоморфно <tex> С </tex>
+
|statement=
 +
Пространство <tex> C </tex> изоморфно <tex> T </tex>.
 
|proof=
 
|proof=
 
Рассмотрим <tex> x \in  C </tex>.  
 
Рассмотрим <tex> x \in  C </tex>.  
Строка 27: Строка 29:
  
 
Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл (в соответствующие места поставить <tex> 1 </tex>, во все остальные <tex> 0 </tex>).
 
Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл (в соответствующие места поставить <tex> 1 </tex>, во все остальные <tex> 0 </tex>).
 
Отсюда следует, что <tex> C </tex> изоморфно пространству <tex> T </tex>, элементами которого являются множества ребер, из которых можно составить несколько реберно непересекающихся простых циклов.
 
 
}}
 
}}
 
 
== Размерность линейного пространства обобщенных циклов ==
 
== Размерность линейного пространства обобщенных циклов ==
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=

Версия 03:36, 19 ноября 2011

Определение

Пусть [math] m = |E(G)| [/math], [math] n = |V(G)| [/math], [math] k [/math] — количество компонент связности [math] G [/math].

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


Определение:
Циклическое пространство графа[math] C = Ker(I) [/math], где [math] I : B^m \rightarrow B^n [/math] - линейный оператор соопоставленый матрице инциндентности [math] A [/math] графа [math] G [/math].


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


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

Лемма:
Пространство [math] C [/math] изоморфно [math] T [/math].
Доказательство:
[math]\triangleright[/math]

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

Рассмотрим граф [math] G_1(V_1,E_1) [/math], где [math] E_1 [/math] — множество ребер, таких что на соответствующих местах вектора [math] x [/math] стоят единицы, а [math] V_1 = 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]\triangleleft[/math]

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

Теорема:
[math] dim(C) = m - n + k [/math]
Доказательство:
[math]\triangleright[/math]

[math] dim(C)=dim(Ker(i))=m-Rang(A) [/math], где [math] Rang(A) = [/math] максимальное количество ЛНЗ столбцов [math] A [/math]. Если рассмотреть цикл в [math] G [/math], то набор столбцов соответствующий ребрам в этом цикле ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из [math] A [/math] то он будет ЛЗ. Если же множество ребер не содержит цикл, то набор ЛНЗ (если бы он был ЛЗ, тогда бы существовал [math] x \in C [/math], который соответствует некоторому подмножеству данного набора ребер, значит из набора ребер можно выделить цикл, противоречие). Максимальное число ребер, которые мы можем выделить из G и которые не содержат цикл [math]= n - k [/math] (в каждой компоненте связности выделим цикл).

Итого: [math] dim(C)=m - n + k [/math]
[math]\triangleleft[/math]

Литература(формулировки другие)

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