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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Размерность линейного пространства обобщенных циклов)
Строка 30: Строка 30:
  
 
=== Размерность линейного пространства обобщенных циклов ===
 
=== Размерность линейного пространства обобщенных циклов ===
 +
==Теорема о существовании простого пути в случае существования пути==
 +
{{Теорема
 +
|statement=
 +
Если между двумя [[Основные определения теории графов|вершинами графа]] существует [[Основные определения теории графов|путь]], то между ними существует простой путь.
 +
|proof=
 +
 +
=== Доказательство построением ===
 +
 +
Возьмём любой из существующих путей между нужными нам вершинами: <tex>v_0e_1v_1e_2v_2 ... e_nv_n</tex>.
 +
 +
* Алгоритм:
 +
1. Для вершины <tex>v_i</tex> найдём момент её последнего вхождения в путь {{---}} <tex>v_j</tex>.
 +
2. Удалим отрезок пути от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно.
 +
Получившаяся последовательность вершин и рёбер графа останется путём от <tex>v_0</tex> до <tex>v_n</tex>, и в нём вершина <tex>v_i</tex> будет содержаться ровно один раз.
 +
Начнём процесс с вершины <tex>v_0</tex> и будем повторять его каждый раз  для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
 +
 +
=== Альтернативное ===
 +
Выберем из всех путей между данными вершинами путь наименьшей длины.
 +
 +
Предположение:
 +
Пусть он не простой.
 +
Тогда в нём содержатся две одинаковые вершины <tex>v_i = v_j</tex>, <tex>i < j</tex>. Удалим из исходного пути отрезок от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно. Конечная последовательность также будет путём от <tex>v_0</tex> до <tex>v_n</tex> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь {{---}} простой.
 +
}}
  
 
== Литература ==
 
== Литература ==

Версия 04:52, 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] T [/math], элементами которого являются множества ребер из которых можно составить несколько реберно непересекающихся простых циклов.

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

Теорема о существовании простого пути в случае существования пути

Теорема:
Если между двумя вершинами графа существует путь, то между ними существует простой путь.
Доказательство:
[math]\triangleright[/math]

Доказательство построением

Возьмём любой из существующих путей между нужными нам вершинами: [math]v_0e_1v_1e_2v_2 ... e_nv_n[/math].

  • Алгоритм:
1. Для вершины [math]v_i[/math] найдём момент её последнего вхождения в путь — [math]v_j[/math].
2. Удалим отрезок пути от [math]e_{i+1}[/math] до [math]v_j[/math], включительно.
Получившаяся последовательность вершин и рёбер графа останется путём от [math]v_0[/math] до [math]v_n[/math], и в нём вершина [math]v_i[/math] будет содержаться ровно один раз.

Начнём процесс с вершины [math]v_0[/math] и будем повторять его каждый раз для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.

Альтернативное

Выберем из всех путей между данными вершинами путь наименьшей длины.

Предположение:

Пусть он не простой.
Тогда в нём содержатся две одинаковые вершины [math]v_i = v_j[/math], [math]i \lt j[/math]. Удалим из исходного пути отрезок от [math]e_{i+1}[/math] до [math]v_j[/math], включительно. Конечная последовательность также будет путём от [math]v_0[/math] до [math]v_n[/math] и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь — простой.
[math]\triangleleft[/math]

Литература

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