4625
правок
(k,d)-Coloring: различия между версиями
Материал из WikiGrapp
нет описания правки
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. | |||
