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

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

Версия от 12: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.