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

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

Доказательство:
Покажем, что множество L_чет замкнуто относительно линейных операций сложения и умножения на константу. Пусть H₁ и H₂ – четные подграфа графа G и v произвольная вершина в G. S(v), S₁(v), S₂(v), S₁₂(v) есть степени вершины v в графах H₁+H₂, H₁, H₂, H₁ ∩H₂,- соответственно. Пусть a, a¹, a², a¹² – есть характеристические вектора этих подграфов.

a¹+a²=(0,0,1,0,1,0,0,0,1,0,1,1,1,…)

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

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

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

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

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

Доказательство (1): т.к. циклы C₁, C₂,…,C_k не имеют попарно общих ребер, то матрица их характеристических векторов a_C1, a_C2,…,a_Ck в каждом столбце имеет не более одной единицы. Поэтому при сложении строк матрицы, т.е при поразрядном сложении векторов по mod 2 каждая единица (каждое ребро) не пропадает, тогда сложение характеристических векторов (сложение циклов) совпадает с объединением соответствующих циклов по общим вершинам.

Доказательство (2): каждая строка матрицы характеристических векторов линейно независима от других строк матрицы. Т.к. если строка a_ci в разряде j имеет единицу, то в разряде j остальные строки матрицы имеют 0, и 1 в разряде j вектора a_Cj не может быть получена никакой линейной комбинацией нулей на месте j остальных векторов ⇒ все строки в матрице, а ⇒ и все циклы C₁, C₂,…,C_k, линейно независимы.

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

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

Теорема: подпространство L_чет четных подграфов линейного пространства L_G^q всех подграфов связного (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 линейно выражается через циклы системы ∑. В самом деле, пускай e₁, e₂,…,e_r есть все хорды в графе H. Прибавим к четному подграфу H графа G те же циклы С₁, С₂,…,С_r из ∑, которые содержат хорды е₁, е₂,…,е_r из H. Тогда суммарный четный граф H’ = H + С₁ + С₂+…+ С_r не содержит ни одной хорды, т.е. H’ есть подграф каркаса T. Всякое дерево имеет висячую вершину с нечетной степенью 1. Но граф Н’ четен, как сумма четных графов, следовательно граф Н’ пуст, т.е. не имеет ребер, т.е. в линейном пространстве L_G^q элемент H’ есть 0, тогда H’ = H + С₁+С₂+…+С_r=0⇒ H=-(С₁+С₂+…+С_r) ⇒ H = (С₁ + С₂+…+С_r), т.к. –1=1 (mod 2). Итак, всякий четный подграф H графа G линейно выражается через циклы системы ∑. Получили, что ∑ есть линейно независимая система циклов в G. Причем, любой четный подграф в G линейно выражается через циклы ∑ ⇒ ∑ — есть базис пространства L_чет четного подграфа графа G, поэтому мощность |∑|=q-p+1 и dim(L_чет) = q – p+1.

Комментарии запрещены.