Connected component of a hypergraph

Материал из WikiGrapp
Версия от 13:44, 24 ноября 2014; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Connected component of a hypergraphсвязная компонента гиперграфа.

Let [math]\displaystyle{ \mathcal {E} = (V, \{E_{1}, \ldots, E_{m}\}) }[/math] be a hypergraph. A sequence [math]\displaystyle{ (E_{1}, \ldots, E_{k}) }[/math] of distinct hyperedges is a path of length [math]\displaystyle{ \,k }[/math] if for all [math]\displaystyle{ \,i, \; 1 \leq i \lt m, \; E_{i} \cap E_{i+1} \neq \emptyset }[/math]. Two vertices [math]\displaystyle{ \,x \in E_{1}, \; y \in E_{k} }[/math] are connected (by the path [math]\displaystyle{ (E_{1}, \ldots, E_{k}) }[/math]), and [math]\displaystyle{ \,E_{1} }[/math] and [math]\displaystyle{ \,E_{k} }[/math] are also connected. A set of hyperedges is connected if every pair of hyperedges in the set is connected. A connected component of a hypergraph is a maximal connected set of hyperedges.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.