Линейное пространство подграфов данного графа

Пусть G=(V,E) есть (p,q) – граф с множеством V=(v1, v2,…, vp) вершин и E=(e1,e2, …,eq) – ребер. Пусть H⊆G – есть остовный подграф графа G с тем же множеством V вершин.

Подграфу H поставим в соответствие характеристический вектор.
aН ={a1, a2, …, an}, где i=1,2,…q и ai равен:
— 1, если ребро ei ∈ H
— 0, если ребро ei ∈ H

Между множеством LGq всех основных подграфов графа G и множеством всех наборов из E2q можно установить взаимнооднозначное соответствие, при котором вектору a=(a1, a2, …, aq) соответствует подграф Ha=(V, Ea) в котором ребро ei ∈ Ea ⇔ ai=1. На множестве всех подграфов графа G определим сложение и умножение на const из E2q = {0,1} следующим образом. Пусть H, H1, H2 есть подграфы графа G и аН, аН1, aН2 есть соответствующие характеристические вектора. Пусть λ ∈ E2, тогда:
Подграф H1+H2 соответствует вектору aН1+aН2.
Подграф λ*H соответствует вектору λ*aН.
Подграф 0*H соответствует вектору 0*aН.

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

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

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

E1 e2 e3 e4 e5 e6 e7
aH1 0 0 1 0 1 1 1
aH2 1 1 1 0 1 0 1

aH1+ aH2 = (1,1,0,0,0,1,0) – ему соответствует подграф H1+H2


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





Статистика

Рейтинг@Mail.ru