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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о существовании простого пути в случае существования пути)
(Размерность линейного пространства обобщенных циклов)
Строка 35: Строка 35:
 
<tex> dim(C) = m - n + k </tex>
 
<tex> dim(C) = m - n + k </tex>
 
|proof=
 
|proof=
 +
<tex> dim(C)=dim(Ker(i))=m-Rang(A) </tex>
 +
<tex> Rang(A) = </tex> {{---}} максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть цикл в <tex> G </tex> то набор столбцов соответствующий ребрам в этом цикле ЛЗ. Отсюда следует, если любому множеству ребер содержащих цикл в соответствие сопоставить набор столбцов  из <tex> A </tex> то он ЛЗ. Если же множество ребер не содержит цикл то набор ЛНЗ(если бы он был ЛЗ, тогда бы существовал  <tex> x \in C </tex> который соответствует некоторому подмножеству данного набора ребер, значит из набора ребер можно выделить цикл, противоречие). Максимальное число ребер которые мы можем выделить из G и которые не содержат цикл {{---}} <tex> n - k </tex>(в каждой компоненте связности выделим цикл).
 +
Итого: dim(C)=m - n + k
 
}}
 
}}
  

Версия 05:35, 2 ноября 2011

Определение

Пусть [math] m = |E(G)| [/math], [math] n = |V(G)| [/math], [math] k [/math] — количество компонент связности [math] 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] T [/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](в каждой компоненте связности выделим цикл).

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

Литература

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