Def.Число ребер гиперграфа, инцидентных данной вершине называют степенью вершины

В этом случае записывают

deg V_i = k

2. Число вершин гиперграфа, инцидентных ребру, называют степенью ребра.

deg e_j = |e_j| = m

deg e₁ = 1; deg e₃ = 3; deg e₇ = 0

3.Гиперграф, степень любого ребра которого равна h, называют регулярным (h – однородным, h – унифор.)

" e_i deg e_i = h

Замечание. Говорят, что регулярный гиперграф представляет h – арное отношение.

R Í Vⁿ

Двуоднородный гиперграф с кратными ребрами называют мультиграфом.

4.Двуоднородный гиперграф без кратных ребер называется простым графом (очевидно именно такой граф есть графическое представление бинарного отношения на множестве вершин).

5.h – арное отношение (h – регулярный гиперграф) часто задают с помощью мографа (модельный граф)

Пример.

Н = ‹V, E ›

V = {V₁,V₂,V₃,V₄}; R = { ‹ V₁,V₂,V₃›, ‹V₁,V₃,V₄›, ‹V₂,V₃,V₄› }

Г_V1 ={V₂,V₃} Г_V2 ={ V₃,V₄} Г_V4= {V₂,V₃}

Очевидно, что все h-однородные гиперграфы без кратных ребер являются антицепями (антицепь – это гиперграф, никакое из ребер которого не является подмножеством другого).

Дата добавления: 2014-01-06