Пусть G=(V,E) есть (p,q) – граф с множеством V=(v₁, v₂,…, v_p) вершин и E=(e₁,e₂, …,e_q) – ребер. Пусть H⊆G – есть остовный подграф графа G с тем же множеством V вершин.

Подграфу H поставим в соответствие характеристический вектор.
a_Н ={a₁, a₂, …, a_n}, где i=1,2,…q и a_i равен:
— 1, если ребро e_i ∈ H
— 0, если ребро e_i ∈ H

Между множеством L_G^q всех основных подграфов графа G и множеством всех наборов из E₂^q можно установить взаимнооднозначное соответствие, при котором вектору a=(a₁, a₂, …, a_q) соответствует подграф H_a=(V, E_a) в котором ребро e_i ∈ E_a ⇔ a_i=1. На множестве всех подграфов графа G определим сложение и умножение на const из E₂^q = {0,1} следующим образом. Пусть H, H₁, H₂ есть подграфы графа G и а_Н, а_Н1, a_Н2 есть соответствующие характеристические вектора. Пусть λ ∈ E₂, тогда:
Подграф H₁+H₂ соответствует вектору a_Н1+a_Н2.
Подграф λ*H соответствует вектору λ*a_Н.
Подграф 0*H соответствует вектору 0*a_Н.

Потому содержит только вершины из G, но ни одного ребра. Подграф 1*H совпадает с H, ибо его характеристический вектор 1**a_Н = *a_Н.

Линейное пространство наборов E₂^q изоморфно системе подграфов L_G^q, потому система LGq есть линейное пространство. Размерность обоих пространств равна q, числу ребер в G.

Им соответствуют вектора

a_H1+ a_H2 = (1,1,0,0,0,1,0) – ему соответствует подграф H₁+H₂

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