K-Cover of a (hyper)graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Cover of a (hyper)graph''' --- <math>k</math>-покрытие (вершинное) графа (гиперграфа). This is a collection of po…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Cover of a (hyper)graph''' - | '''<math>k</math>-Cover of a (hyper)graph''' — ''[[k-покрытие (вершинное) графа (гиперграфа)|<math>k</math>-покрытие (вершинное) графа (гиперграфа)]].'' | ||
(гиперграфа). | |||
This is a collection of points such that each edge contains at least <math>k</math> of | This is a collection of points such that each [[edge]] contains at least <math>\,k</math> of | ||
them. 1-cover is simply a vertex (point) cover. A <math>k</math>-cover can also be | them. <math>\,1</math>-cover is simply a [[vertex cover, vertex covering|vertex (point) cover]]. A <math>\,k</math>-cover can also be | ||
regarded as a mapping <math>t: \; V(G) \rightarrow \{0, 1, \ldots\}</math> such | regarded as a mapping <math>t: \; V(G) \rightarrow \{0, 1, \ldots\}</math> such | ||
that <math>\sum_{x \in E} t(x) \geq k</math> for each edge <math>E</math>. | that <math>\sum_{x \in E} t(x) \geq k</math> for each edge <math>\,E</math>. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Версия от 05:38, 10 марта 2017
[math]\displaystyle{ k }[/math]-Cover of a (hyper)graph — [math]\displaystyle{ k }[/math]-покрытие (вершинное) графа (гиперграфа).
This is a collection of points such that each edge contains at least [math]\displaystyle{ \,k }[/math] of them. [math]\displaystyle{ \,1 }[/math]-cover is simply a vertex (point) cover. A [math]\displaystyle{ \,k }[/math]-cover can also be regarded as a mapping [math]\displaystyle{ t: \; V(G) \rightarrow \{0, 1, \ldots\} }[/math] such that [math]\displaystyle{ \sum_{x \in E} t(x) \geq k }[/math] for each edge [math]\displaystyle{ \,E }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.