Называется матрицей достижимости

__

Части гиперграфа.

H’ = ‹ V’, E’ ›

Def. Подмножество вершин (V’Í V) c инцидентными им подмножествами ребер (Е’ Í Е) называется подгиперграфом гиперграфа.

Часть гиперграфа, в котором удалены какие-либо ребра, называется частью гиперграфа. Если удалены вершины и инцидентные им ребра, то говорят о подгиперграфе.

Def. Подгиперграф, описываемый такой последовательностью вершин и ребер Р_e = ‹ V_i, e_i, V₂, e₂, …, e_e, V_e+1 ›, что

а) все вершины, кроме возможных крайних, различны.

б) е₁, е₂, …, е_n – различные ребра.

в) V_i, V_i+1Î R_i, для " iÎ 1,l – называют цепью длины l.

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

Связность гиперграфа.

Гиперграф называется связным, если существует цепь между двумя любыми вершинами гиперграфа. В случае связного гиперграфа говорят, что гиперграф образует однокомпонентную связность и записывают так:

k(h) = 1 (k(k(h)) = 1)

Гиперграф называется несвязным, если он не однокомпонентный, т.е.если k(h)› 1; k(k(h))› 1).

Замечание: Матрицу гиперграфа такую М: U´ U® {0,1}, что m ={

Независимые и зависимые множества гиперграфа.

Def. Множество вершин (JÍ B(H)) гиперграфа называется независимым, если никакие две вершины из этого множества несмежные.

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