Аноним

Vertex path cover: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Vertex path cover''' --- вершинное путевое покрытие. Let <math>{\mathcal P} = \{P_{1}, \ldots, P_{k}\}</math> be a set of paths in a dig…»)
 
Нет описания правки
 
Строка 3: Строка 3:
Let <math>{\mathcal P} = \{P_{1}, \ldots, P_{k}\}</math> be a set of paths in a digraph
Let <math>{\mathcal P} = \{P_{1}, \ldots, P_{k}\}</math> be a set of paths in a digraph
<math>D</math>. <math>{\mathcal P}</math> is a ''' vertex path cover''' of <math>D</math> iff <math>\{V(P_{1}), \ldots,
<math>D</math>. <math>{\mathcal P}</math> is a ''' vertex path cover''' of <math>D</math> iff <math>\{V(P_{1}), \ldots,
V(P_{k})\}</math> is a partition of <math>V(D)</math>.
V(P_{k})\}</math> is a partition of <math>V(D)\,</math>.


<math>pn_{v}(D) = \min\{|{\mathcal P}|: {\mathcal P}\mbox{ is a vertex path cover
<math>\textstyle pn_{v}(D) = \min\{|{\mathcal P}|: {\mathcal P}</math> is a vertex path cover
of }D\}</math>
of <math>D\}\,</math>
is the ''' vertex path number''' of <math>D</math>.


is the ''' vertex path number''' of <math>D</math>.
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.