Connected component of a hypergraph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Connected component of a hypergraph''' --- связная компонента гиперграфа. Let <math>{\mathcal E} = (V, \{E_{1}, \ldots, E_{m}\})</mat…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Connected component of a hypergraph''' | '''Connected component of a hypergraph''' — ''[[связная компонента гиперграфа]].'' | ||
гиперграфа. | |||
Let <math> | Let <math>\mathcal {E} = (V, \{E_{1}, \ldots, E_{m}\})</math> be a [[hypergraph]]. A sequence <math>(E_{1}, \ldots, E_{k})</math> of distinct hyperedges is a '''[[path]]''' of length <math>\,k</math> if for all <math>\,i, \; 1 \leq i < m, \; E_{i} \cap E_{i+1} \neq \emptyset</math>. Two [[vertex|vertices]] <math>\,x \in E_{1}, \; y \in E_{k}</math> are connected (by the path <math>(E_{1}, \ldots, E_{k})</math>), and <math>\,E_{1}</math> and <math>\,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. | ||
sequence <math>(E_{1}, \ldots, E_{k})</math> of distinct hyperedges is a '''path''' of length <math>k</math> if for all <math>i, \; 1 \leq i < m, \; E_{i} \cap | |||
E_{i+1} \neq \emptyset</math>. Two vertices <math>x \in E_{1}, \; y \in E_{k}</math> | ==Литература== | ||
are connected (by the path <math>(E_{1}, \ldots, E_{k})</math>), and <math>E_{1}</math> | |||
and <math>E_{k}</math> are also connected. A set of hyperedges is ''' connected''' if | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
every pair of hyperedges in the set is connected. A '''connected component of a hypergraph''' is a | |||
maximal connected set of hyperedges. | |||
Текущая версия от 13:44, 24 ноября 2014
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.