Подпространство четных подграфов

Пусть G есть (p,q) – граф и LGq есть линейное пространство всех подграфов графа G.

Теорема: Множество Lчет всех четных подграфов графа G образует подпространство линейного пространства LGq всех подграфов графа G.

Доказательство:
Покажем, что множество Lчет замкнуто относительно линейных операций сложения и умножения на константу. Пусть H1 и H2 – четные подграфа графа G и v произвольная вершина в G. S(v), S1(v), S2(v), S12(v) есть степени вершины v в графах H1+H2, H1, H2, H1 ∩H2,- соответственно. Пусть a, a1, a2, a12 – есть характеристические вектора этих подграфов.

E1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13
a1 1 0 1 0 1 0 1 0 1 0 1 0 0
a2 1 0 0 0 0 0 1 0 0 0 0 1 1

a1+a2=(0,0,1,0,1,0,0,0,1,0,1,1,1,…)

Степени S1(v)=6, S2(v)=4, S12(v)=2.
Степень вершины v в графе H1+H2 складывается из числа ребер в вершине v графа H1 плюс число ребер в вершине v графа H2 минус удвоенное число ребер в вершине v графа H1∩H2, т.е. S(v) = S1(v) + S2(v) – 2S12(v). Получается, что степень любой вершины v в графе H1+H2 есть число четное ⇒ сумма H1+H2 – есть четный граф.

Если H есть четный подграф графа G, то 0*H и 1*H есть четные подграфы графа G. Итак множество Lчет замкнуто относительно линейных операций сложения и умножения на константу. Все 8 аксиом пространства выполняются для Lчет, ибо они выполняются для соответствующих векторов из E2q. Поэтому множество Lчет есть подпространство линейного пространства LGq.

Замечание:
всякий простой цикл в графе G есть четный подграф графа G.

Определение: Матрица множества простых циклов графа G есть матрица, строки которой есть характеристические вектора простых циклов этого множества.

Утверждение: Пусть C1, C2,…,Ck есть циклы в графе G, попарно не пересекающиеся по ребрам, тогда:
1) Объединение C1∪C2∪…∪Ck = C1+C2+…+Ck
2) Циклы C1, C2,…,Ck – линейно независимы.

Доказательство (1): т.к. циклы C1, C2,…,Ck не имеют попарно общих ребер, то матрица их характеристических векторов aC1, aC2,…,aCk в каждом столбце имеет не более одной единицы. Поэтому при сложении строк матрицы, т.е при поразрядном сложении векторов по mod 2 каждая единица (каждое ребро) не пропадает, тогда сложение характеристических векторов (сложение циклов) совпадает с объединением соответствующих циклов по общим вершинам.

Доказательство (2): каждая строка матрицы характеристических векторов линейно независима от других строк матрицы. Т.к. если строка aci в разряде j имеет единицу, то в разряде j остальные строки матрицы имеют 0, и 1 в разряде j вектора aCj не может быть получена никакой линейной комбинацией нулей на месте j остальных векторов ⇒ все строки в матрице, а ⇒ и все циклы C1, C2,…,Ck, линейно независимы.

Лемма: множество всех простых циклов графа G составляет порождающую систему подпространства Lчет всех четных подпространств графа G.

Доказательство: Пусть H есть произвольный четный подграф графа G. По теореме Эйлера граф H представим, как объединение некоторых простых циклов C1, C2,…,Ck из H с попарно не пересекающимися множествами ребер. По утверждению H = C1 + C2+…+Ck. Всякий цикл в H есть цикл в G, поэтому граф H есть линейная комбинация множества простых циклов в G, причем в этой линейной комбинации коэффициент 1 имеют C1, C2,…,Ck а остальные простые циклы имеют коэффициенты 0.

Теорема: подпространство Lчет четных подграфов линейного пространства LGq всех подграфов связного (p,q)-графа G имеют размерность dim(Lчет)=q-p+1.

Доказательство: Пусть G=(V,E) есть связный (p,q) граф. Пусть подграф — дерево T=(V,ET) – есть некоторый каркас графа G, число ν хорд в G равно q-p+1. Каждый простой цикл четен. Каждая хорда e=(u,v) вместе с единственной простой цепью [u,v] в дереве T образует простой цикл. Вектора таких циклов для различных хорд образуют линейно независимую систему ∑, ибо каждый цикл содержит ребро (свою хорду), не принадлежащую ни одному из остальных циклов системы ∑. Мощность |∑|= ν = q – p+1, с другой стороны каждый четный подграф H графа G линейно выражается через циклы системы ∑. В самом деле, пускай e1, e2,…,er есть все хорды в графе H. Прибавим к четному подграфу H графа G те же циклы С1, С2,…,Сr из ∑, которые содержат хорды е1, е2,…,еr из H. Тогда суммарный четный граф H’ = H + С1 + С2+…+ Сr не содержит ни одной хорды, т.е. H’ есть подграф каркаса T. Всякое дерево имеет висячую вершину с нечетной степенью 1. Но граф Н’ четен, как сумма четных графов, следовательно граф Н’ пуст, т.е. не имеет ребер, т.е. в линейном пространстве LGq элемент H’ есть 0, тогда H’ = H + С12+…+Сr=0⇒ H=-(С12+…+Сr) ⇒ H = (С1 + С2+…+Сr), т.к. –1=1 (mod 2). Итак, всякий четный подграф H графа G линейно выражается через циклы системы ∑. Получили, что ∑ есть линейно независимая система циклов в G. Причем, любой четный подграф в G линейно выражается через циклы ∑ ⇒ ∑ — есть базис пространства Lчет четного подграфа графа G, поэтому мощность |∑|=q-p+1 и dim(Lчет) = q – p+1.


Оставить комментарий





Статистика

Рейтинг@Mail.ru