Циклическое пространство графа — различия между версиями
Строка 37: | Строка 37: | ||
|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>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 </tex> и того, что <tex>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=0 </tex> | В силу линейности оператора <tex> I </tex> и того, что <tex>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=0 </tex> |
Версия 21:10, 26 декабря 2014
Содержание
Циклическое пространство графа
Пусть
, , — количество компонент связности .— линейное пространство, элементами которого являются -мерные двоичные вектора и их сложение определено, как сложение по модулю .
Определение: |
Циклическое пространство графа (англ. cyclic graph space) — | , где — линейный оператор, сопоставленный матрице инцидентности графа .
Определение: |
Обобщенный цикл графа | (англ. generalized graph cycle) — элемент линейного пространства
Лемма: | |||||
изоморфно , где — пространство, элементами которого являются наборы | |||||
Доказательство: | |||||
Рассмотрим .Рассмотрим граф , где — множество ребер, таких, что на соответствующих местах вектора стоят единицы, а .В силу определения обобщенного цикла: .Покажем по индукции, что можно декомпозировать на несколько реберно непересекающихся простых циклов. Ведем индукцию по числу ребер. База индукции очевидно выполняется. Рассмотрим . существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов. Если рассмотреть набор реберно непересекающихся простых циклов некоторого графа и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл, поставив в соответствующие места , во все остальные .
| |||||
Размерность линейного пространства обобщенных циклов
Теорема: | |||||
Доказательство: | |||||
, где — максимальное количество ЛНЗ столбцов . Если рассмотреть простой цикл в , то сумма столбцов соответствующих этим ребрам равна , т. к. значение оператора на соответствующем обобщенном цикле в точности равно сумме этих столбцов. Значит, эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из , то он будет ЛЗ
Максимальное число ребер, которые мы можем выделить из G и которые не содержат цикл равно Итого: (в каждой компоненте связности выделим остовное дерево). | |||||
Применение
Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа.
См. также
Источники информации
- Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4
- Карпов В.Д. Теория графов - с.281