Редактирование: Циклическое пространство графа

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
Пусть <tex> m = |E(G)| </tex>, <tex> n = |V(G)| </tex>, <tex> k </tex> {{---}} количество компонент связности <tex> G </tex>.
 
Пусть <tex> m = |E(G)| </tex>, <tex> n = |V(G)| </tex>, <tex> k </tex> {{---}} количество компонент связности <tex> G </tex>.
  
<tex> B^t </tex> {{---}} линейное пространство, элементами которого являются <tex> t </tex>-мерные двоичные вектора и их сложение определено, как сложение по модулю <tex> 2 </tex>.  
+
<tex> B^t </tex> {{---}} линейное пространство, элементами которого являются <tex> t </tex>{{---}}мерные двоичные вектора и их сложение определено, как сложение по модулю <tex> 2 </tex>.  
  
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Циклическое пространство графа''' (англ. ''cyclic graph space'') {{---}} <tex>  C = \operatorname {Ker}(I) </tex>, где <tex> I : B^m \rightarrow B^n </tex> {{---}} линейный оператор, сопоставленный матрице инцидентности <tex> A </tex> графа <tex> G </tex>.
+
'''Циклическое пространство графа''' {{---}} <tex>  C = \operatorname {Ker}(I) </tex>, где <tex> I : B^m \rightarrow B^n </tex> {{---}} линейный оператор, сопоставленный матрице инцидентности <tex> A </tex> графа <tex> G </tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Обобщенный цикл графа <tex> G </tex>''' (англ. ''generalized graph cycle'') {{---}} элемент линейного пространства <tex>C </tex>
+
'''Обобщенный цикл графа G''' {{---}} элемент линейного пространства <tex>C </tex>
 
}}
 
}}
  
  
 
{{Лемма
 
{{Лемма
|id = lemma1
 
 
|statement=
 
|statement=
Пространство <tex> C </tex> изоморфно <tex> T </tex>, где <tex> T </tex>{{---}} пространство, элементами которого являются наборы [[Основные_определения_теории_графов#def_graph_edge_1 | ребер]], из которых можно составить несколько простых реберно непересекающихся [[Основные_определения_теории_графов#def_graph_cycle_1 | циклов]].
+
Пространство <tex> C </tex> изоморфно <tex> T </tex>, где <tex> T </tex>{{---}} пространство, элементами которого являются наборы ребер, из которых можно составить несколько простых реберно непересекающихся циклов.
 
|proof=
 
|proof=
 
Рассмотрим <tex> x \in  C </tex>.  
 
Рассмотрим <tex> x \in  C </tex>.  
Строка 25: Строка 24:
 
Рассмотрим граф <tex> G_1(V_1,E_1) </tex>, где <tex>  E_1 </tex> {{---}} множество ребер, таких, что на соответствующих местах вектора <tex> x </tex> стоят единицы, а <tex> V_1 = V(G) </tex> .
 
Рассмотрим граф <tex> G_1(V_1,E_1) </tex>, где <tex>  E_1 </tex> {{---}} множество ребер, таких, что на соответствующих местах вектора <tex> x </tex> стоят единицы, а <tex> V_1 = V(G) </tex> .
  
В силу определения обобщенного цикла: <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> |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> 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>G</tex> и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл, поставив <tex> 1 </tex> в соответствующие места <tex> x </tex>, во все остальные <tex> 0 </tex>.  
+
Если рассмотреть набор реберно непересекающихся простых циклов некоторого графа <tex>G</tex> и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл, поставив в соответствующие места <tex> x </tex> <tex> 1 </tex>, во все остальные <tex> 0 </tex>.  
  
 
{{Утверждение
 
{{Утверждение
 
|statement = Если <tex>\textbf{C}</tex> {{---}} обобщенный цикл, соответствующий простому циклу <tex>C'</tex> графа <tex>G</tex>, то <tex>I(\textbf{C}) = 0</tex>
 
|statement = Если <tex>\textbf{C}</tex> {{---}} обобщенный цикл, соответствующий простому циклу <tex>C'</tex> графа <tex>G</tex>, то <tex>I(\textbf{C}) = 0</tex>
 
|proof=Пусть <tex>\textbf{C}</tex> {{---}} обобщенный цикл из условия, а <tex>C'</tex> {{---}} соответствующий ему простой цикл.  
 
|proof=Пусть <tex>\textbf{C}</tex> {{---}} обобщенный цикл из условия, а <tex>C'</tex> {{---}} соответствующий ему простой цикл.  
Тогда <tex>I(\textbf{C}) = \bigoplus\limits_{e \in C'}c(e)</tex>, где <tex>c(e)</tex>{{---}} столбец в [[Матрица_инцидентности_графа | матрице инцидентности графа]] <tex>G</tex>, соответствующий ребру <tex>e</tex>. Так как каждая вершина в <tex>C'</tex> имеет степень <tex> 2 </tex>, то для любого <tex>i \in \overline{0, |VG| - 1}</tex> верно <tex>|\{e \in C': c(e)_i = 1\}| = 2</tex>, а значит <tex>I(\textbf{C})_i = 1 \oplus 1 = 0</tex>. Таким образом <tex>I(\textbf{C}) = 0</tex>. }}
+
Тогда <tex>I(\textbf{C}) = \bigoplus\limits_{e \in C'}c(e)</tex>, где <tex>c(e)</tex>{{---}} столбец в матрице инцидентности графа <tex>G</tex>, соответствующий ребру <tex>e</tex>. Так как каждая вершина в <tex>C'</tex> имеет степень 2, то для любого <tex>i \in \overline{0, |VG| - 1}</tex> верно <tex>|\{e \in C': c(e)_i = 1\}| = 2</tex>, а значит <tex>I(\textbf{C})_i = 1 \oplus 1 = 0</tex>. Таким образом <tex>I(\textbf{C}) = 0</tex>. }}
  
 
В силу линейности оператора <tex> I </tex>  и того, что <tex>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=0 </tex>
 
В силу линейности оператора <tex> I </tex>  и того, что <tex>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=0 </tex>
Строка 48: Строка 47:
 
<tex> \operatorname {dim}(C) = m - n + k </tex>
 
<tex> \operatorname {dim}(C) = m - n + k </tex>
 
|proof=
 
|proof=
<tex> \operatorname {dim}(C)=\operatorname {dim}(\operatorname {Ker}(I))=m-\operatorname {Rang}(A) </tex>, где <tex> \operatorname {Rang}(A) </tex> {{---}} максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть простой цикл <tex>C</tex> в <tex> G </tex>, то сумма столбцов соответствующих этим ребрам равна <tex>0</tex>, т. к. значение оператора <tex>I</tex> на  соответствующем обобщенном цикле в точности равно сумме этих столбцов. Значит, эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex>, то он будет ЛЗ
+
<tex> \operatorname {dim}(C)=\operatorname {dim}(\operatorname {Ker}(i))=m-\operatorname {Rang}(A) </tex>, где <tex> \operatorname {Rang}(A) {{---}} </tex> максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть простой цикл <tex>C</tex> в <tex> G </tex>, то сумма столбцов соответствующих этим ребрам равна <tex>0</tex>, т. к. значение оператора <tex>I</tex> на  соответствующем обобщенном цикле в точности равно сумме этих столбцов. Значит, эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex>, то он будет ЛЗ
  
 
{{Утверждение
 
{{Утверждение
Строка 59: Строка 58:
 
}}
 
}}
  
== Применение ==
+
== Литература ==
Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf  Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>.
+
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.
 
 
== См. также ==
 
*[[Линейный_оператор|Линейный оператор]]
 
 
 
*[[Ядро_и_образ_линейного_оператора|Ядро и образ линейного оператора]]
 
 
 
== Примечания ==
 
<references/>
 
 
 
== Источники информации ==
 
*Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4
 
 
 
*Карпов В.Д. Теория графов - с.281
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)