(k,d)-Coloring: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>(k,d)</math>-Coloring''' --- <math>(k,d)</math>-раскраска. Let <math>k</math> and <math>d</math> be positive integers such that <math>k \geq 2d</…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>(k,d)</math>-Coloring''' - | '''<math>\,(k,d)</math>-Coloring''' — ''[[(k,d)-Раскраска|<math>\,(k,d)</math>-раскраска]].'' | ||
Let <math>k</math> and <math>d</math> be positive integers such that <math>k \geq 2d</math>. A | Let <math>\,k</math> and <math>\,d</math> be positive integers such that <math>\,k \geq 2d</math>. A '''<math>\,(k,d)</math>-coloring''' of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G = (V,E)</math> is a mapping <math>\,c: V \rightarrow Z_{k}= \{0,1, \ldots, k-1\}</math> such that, for each [[edge]] <math>\,(u,v) \in E</math>, <math>\,|c(u)- c(v)|_{k} \geq d</math>, where <math>\,|x|_{k} = \min\{|x|,k-|x|\}</math>. This generalizes a usual notion of a ''[[k-Coloring|<math>\,k</math>-coloring]]'': an ordinary <math>\,k</math>-coloring of <math>G</math> is just a <math>\,(k,1)</math>-coloring. | ||
'''<math>(k,d)</math>-coloring''' of a graph <math>G = (V,E)</math> is a mapping <math>c: V \rightarrow Z_{k} | |||
= \{0,1, \ldots, k-1\}</math> such that, for each edge <math>(u,v) \in E</math>, <math>|c(u) | ==Литература== | ||
- c(v)|_{k} \geq d</math>, where <math>|x|_{k} = \min\{|x|,k-|x|\}</math>. This | |||
generalizes a usual notion of a ''<math>k</math>-coloring'': an ordinary <math>k</math>-coloring | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
of <math>G</math> is just a <math>(k,1)</math>-coloring. | |||
Текущая версия от 13:10, 1 октября 2014
[math]\displaystyle{ \,(k,d) }[/math]-Coloring — [math]\displaystyle{ \,(k,d) }[/math]-раскраска.
Let [math]\displaystyle{ \,k }[/math] and [math]\displaystyle{ \,d }[/math] be positive integers such that [math]\displaystyle{ \,k \geq 2d }[/math]. A [math]\displaystyle{ \,(k,d) }[/math]-coloring of a graph [math]\displaystyle{ \,G = (V,E) }[/math] is a mapping [math]\displaystyle{ \,c: V \rightarrow Z_{k}= \{0,1, \ldots, k-1\} }[/math] such that, for each edge [math]\displaystyle{ \,(u,v) \in E }[/math], [math]\displaystyle{ \,|c(u)- c(v)|_{k} \geq d }[/math], where [math]\displaystyle{ \,|x|_{k} = \min\{|x|,k-|x|\} }[/math]. This generalizes a usual notion of a [math]\displaystyle{ \,k }[/math]-coloring: an ordinary [math]\displaystyle{ \,k }[/math]-coloring of [math]\displaystyle{ G }[/math] is just a [math]\displaystyle{ \,(k,1) }[/math]-coloring.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.