4633
правки
K-Cover of a (hyper)graph: различия между версиями
Материал из WikiGrapp
нет описания правки
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. | |||
