K-Cover of a (hyper)graph

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

[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.