K-Cover of a (hyper)graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''<math>k</math>-Cover of a (hyper)graph''' — ''[[k-покрытие (вершинное) графа (гиперграфа)|<math>k</math>-покрытие (вершинное) графа (гиперграфа)]].''  
'''<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

Текущая версия от 13:06, 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.
Источник — http://pco.iis.nsk.su/wega/index.php?title=K-Cover_of_a_(hyper)graph&oldid=12278