T-Code (in a graph): различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>t</math>-Code (in a graph)''' --- <math>t</math>-код (в графе). A set <math>C \subseteq V(G)</math> is a '''<math>t</math>-code''' in <math>G</ma…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>t</math>-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 | 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 | ||
2t+1</math> for any two distinct vertices <math>u,v \in C</math>; <math>t</math>-codes are known | <math>d(u,v) \leq t</math>; 1-perfect codes are also called '''[[efficient dominating set|efficient dominating sets]]'''. | ||
as ''<math>2t</math>-packings''. In addition, <math>C</math> is called a '''<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 sets'''. | |||
A set <math>C \subseteq V(G)</math> is a 1-perfect code if and only if the | 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>. | ||
''closed | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 19:25, 12 ноября 2013
[math]\displaystyle{ \,t }[/math]-Code (in a graph) — [math]\displaystyle{ \,t }[/math]-код (в графе).
A set [math]\displaystyle{ C \subseteq V(G) }[/math] is a [math]\displaystyle{ \,t }[/math]-code in [math]\displaystyle{ \,G }[/math] if [math]\displaystyle{ d(u,v) \geq 2t+1 }[/math] for any two distinct vertices [math]\displaystyle{ \,u,v \in C }[/math]; [math]\displaystyle{ \,t }[/math]-codes are known as [math]\displaystyle{ \,2t }[/math]-packings. In addition, [math]\displaystyle{ \,C }[/math] is called a [math]\displaystyle{ \,t }[/math]-perfect code if for any [math]\displaystyle{ u \in V(G) }[/math] there is exactly one [math]\displaystyle{ v \in C }[/math] such that [math]\displaystyle{ d(u,v) \leq t }[/math]; 1-perfect codes are also called efficient dominating sets.
A set [math]\displaystyle{ C \subseteq V(G) }[/math] is a 1-perfect code if and only if the closed neighbourhoods of its elements form a partition of [math]\displaystyle{ \,V(G) }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.