4624
правки
Backbone coloring: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Backbone coloring''' --- хребтовая раскраска. Consider a graph <math>G = (V,E)</math> with a spanning tree <math>T = (V,E_{T})</math> (backbon…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Backbone coloring''' | '''Backbone coloring''' — ''[[хребтовая раскраска]].'' | ||
Consider a graph <math>G = (V,E)</math> with a spanning tree <math>T = (V,E_{T})</math> | Consider a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G = (V,E)</math> with a [[spanning tree]] <math>\,T = (V,E_{T})</math> | ||
(backbone). A vertex coloring <math>f: V \rightarrow \{1,2, \ldots \}</math> is | ([[backbone]]). A [[vertex coloring]] <math>f: V \rightarrow \{1,2, \ldots \}</math> is | ||
proper, if <math>|f(u) - f(v)| \geq 1</math> holds for all edges <math>(u,v) \in E</math>. A | proper, if <math>|f(u) - f(v)| \geq 1</math> holds for all [[edge|edges]] <math>(u,v) \in E</math>. A | ||
vertex coloring is a '''backbone coloring''' for <math>(G,T)</math>, if it is | [[vertex]] coloring is a '''backbone coloring''' for <math>\,(G,T)</math>, if it is | ||
proper and, additionally, <math>|f(u) - f(v)| \geq 2</math> holds for all edges | proper and, additionally, <math>|f(u) - f(v)| \geq 2</math> holds for all edges | ||
<math>(u,v) \in E_{T}</math> in the spanning tree <math>T</math>. | <math>(u,v) \in E_{T}</math> in the spanning [[tree]] <math>\,T</math>. | ||
The '''backbone coloring number''' <math>BBC(G,T)</math> of <math>(G,T)</math> is the | The '''backbone coloring number''' <math>\,BBC(G,T)</math> of <math>\,(G,T)</math> is the | ||
smal-lest integer <math>\ell</math> for which a backbone coloring <math>f: V | smal-lest integer <math>\ell</math> for which a backbone coloring <math>f: V | ||
\rightarrow \{1, 2, \ldots, \ell\}</math> exists. | \rightarrow \{1, 2, \ldots, \ell\}</math> exists. | ||
