T-Code (in a graph): различия между версиями

'''<math>\,t</math>-Code (in a graph)''' — [[t-Код (в графе)|<math>\,t</math>-код (в графе)]].  

A set <math>C \subseteq V(G)</math> is a '''<math>\,t</math>-code''' in <math>\,G</math> if <math>d(u,v) \geq 2t+1</math> for any two distinct [[vertex|vertices]] <math>\,u,v \in C</math>; <math>\,t</math>-codes are known as ''[[2-Packing of a graph|<math>\,2t</math>-packings]]''. In addition, <math>\,C</math> is called a '''[[t-Perfect code|<math>\,t</math>-perfect code]]''' if for any <math>u \in V(G)</math> there is exactly one <math>v \in C</math> such that

<math>d(u,v) \leq t</math>; 1-perfect codes are also called '''[[efficient dominating set|efficient dominating sets]]'''.

A set <math>C \subseteq V(G)</math> is a 1-perfect code if and only if the ''[[closed neighbourhood|closed neighbourhoods]]'' of its elements form a partition of <math>\,V(G)</math>.

 

 

* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.