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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
Строка 15: Строка 15:
 
}}
 
}}
  
Определим пространство <tex> T </tex>, как пространство, элементами которого являются наборы ребер, из которых можно составить несколько простых реберно непересекающихся циклов. 
 
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пространство <tex> C </tex> изоморфно <tex> T </tex>.
+
Пространство <tex> C </tex> изоморфно <tex> T </tex> , где <tex> T </tex>{{---}} пространство, элементами которого являются наборы ребер, из которых можно составить несколько простых реберно непересекающихся циклов.
 
|proof=
 
|proof=
 
Рассмотрим <tex> x \in  C </tex>.  
 
Рассмотрим <tex> x \in  C </tex>.  
Строка 27: Строка 26:
 
В силу определения обобщенного цикла: <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0(mod~2) </tex>.
 
В силу определения обобщенного цикла: <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0(mod~2) </tex>.
  
Значит, <tex> G </tex> можно декомпозировать  на несколько реберно непересекающихся простых циклов. Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.  
+
Покажем по индукции, что <tex> G </tex> можно декомпозировать  на несколько реберно непересекающихся простых циклов. Ведем индукцию по числу ребер.
 +
База индукции <tex> |E_1(G)|=0 </tex> очевидно выполняется.   
 +
Рассмотри <tex> G_1 </tex>. <tex>  \forall v  : v \in V_1 ~ deg(v) \equiv 0(mod~2) \Rightarrow |E_1(G)| > |V(G)| - 1 \Rightarrow  </tex> существует цикл, добавим его в декомпозицию, удалим ребра принадлежащие ему. В силу того что четность степеней вершин не изменилась то по предположению индукции декомпозируем оставшийся граф.
  
Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл (в соответствующие места поставить <tex> 1 </tex>, во все остальные <tex> 0 </tex>).
+
Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.
 +
 
 +
Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл поставив в соответствующие места <tex> x </tex> поставить <tex> 1 </tex>, во все остальные <tex> 0 </tex>.В силу линейности оператора <tex> I </tex>  и того что если  <tex>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=0 </tex>
 
}}
 
}}
  

Версия 08:19, 9 декабря 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] C [/math] изоморфно [math] T [/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] |E_1(G)|=0 [/math] очевидно выполняется. Рассмотри [math] G_1 [/math]. [math] \forall v : v \in V_1 ~ deg(v) \equiv 0(mod~2) \Rightarrow |E_1(G)| \gt |V(G)| - 1 \Rightarrow [/math] существует цикл, добавим его в декомпозицию, удалим ребра принадлежащие ему. В силу того что четность степеней вершин не изменилась то по предположению индукции декомпозируем оставшийся граф.

Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.

Если рассмотреть набор реберно непересекающихся простых циклов и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл поставив в соответствующие места [math] x [/math] поставить [math] 1 [/math], во все остальные [math] 0 [/math].В силу линейности оператора [math] I [/math] и того что если [math]I( [/math] простой цикл [math] )=0 [/math], получаем что [math] Ix=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.