Описание гкс гиперграфами

Коммутационную схему можно также упрощенно описать с помощью гиперграфов.

Гиперграф — обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.

С математической точки зрения, гиперграф представляет собой пару H = (E,V), где E - непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а V - семейство непустых (необязательно различных) подмножеств множества E, называемых рёбрами гиперграфа.

Гиперграфы применяются, в частности, при моделировании электрических схем.

Пример гиперграфа приведен на рис. 2.4.

E=e₁,e₂,e₃,e₄,e₅,e₆,e₇

V=v₁,v₂,v₃,v₄=e₁,e₂,e₃,e₂,e₃,e₃,e₅,e₆,e₄

Граф H = (E,V) называется гиперграфом, если он состоит из множества вершин Е={е₁,е₂,…,е_n} и множества рёбер V={v_1,v_2,…,v_m}. Причём каждое ребро v_iV представляет собой некоторое подмножество множества вершин, т.е. v_iE, v_iпусто,

В гиперграфе H=(E,V) две вершины считаются смежными, если существует ребро V, содержащее эти вершины. Два ребра смежные, если их пересечение – непустое множество.

Для графа H=(E,V), приведенного на рис. 2.5,

E=7, V= 4.

Е={e₁,e₂,e₃,e₄,e₅,e₆,e₇}

V₁={e₁,e₂,e₃,e₄}, V₂={e₂,e₃,e₆,e₇}, V₃={e₄,e₅}, V₄={e₅,e₇}.

Здесь, например, вершины e₁ и e₂ смежные, т.к. они связаны с ребромV₁. v₁,v₂ – смежные рёбра, т.к. их пересечение даёт множество {e₂, e₃}.

Гиперграф может быть описан матрицей инцидентности I(H)=║a_ij║_nxm, строки которой соответствуют вершинам графа, а столбцы – его ребрам.

aij	1, если ei є Vj , 0 в противном случае.

Для гиперграфа с рис. 2.5 матрица инцидентности имеет вид:

I(H)=		V1	V2	V3	V4
	e1	1	0	0	0		V1 = {e1, e2, e3, e4} V2 = {e2, e3, e6, e7} V3 = {e4, e5} V4 = {e5, e7}
	e2	1	1	0	0
	e3	1	1	0	0
	e4	1	0	1	0
	e5	0	0	1	1
	e6	0	1	0	0
	e7	0	1	0	1

Представим теперь коммутационную схему в виде гиперграфа. В такой модели каждому ребру гиперграфа H взаимно - однозначно соответствует определённая цепь. Каждое ребро гиперграфа представляется в виде замкнутой кривой, охватывающей инцидентные ребру вершины. Если ребро инцидентно только двум вершинам, то их обычно соединяют отрезком. Тогда для схемы (рис. 2.2) гиперграф имеет вид (рис. 2.6):

E=e₁,e₂,e₃,e₄,e₅,e₆,e₇

V=v₁,v₂,v₃,v₄,v₅,v₆

V₁={e₀,e₁}; V₂={e₀,e₁,e₃}; V₃={e₁,e₂,e₃};

V₄={e₂,e₃,e₄}; V₅={e₀,e₂}; V₆={e₀,e₄}

V=e₀,e₁, e₀,e₁,e₃, e₁,e₂,e₃,  e₂,e₃ e₄, e₀,e₂,e₀,e₄