Backbone coloring: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Backbone coloring''' --- хребтовая раскраска. Consider a graph <math>G = (V,E)</math> with a spanning tree <math>T = (V,E_{T})</math> (backbon…»)
 
Нет описания правки
 
Строка 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.
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 16:31, 23 октября 2018

Backbone coloringхребтовая раскраска.

Consider a graph [math]\displaystyle{ \,G = (V,E) }[/math] with a spanning tree [math]\displaystyle{ \,T = (V,E_{T}) }[/math] (backbone). A vertex coloring [math]\displaystyle{ f: V \rightarrow \{1,2, \ldots \} }[/math] is proper, if [math]\displaystyle{ |f(u) - f(v)| \geq 1 }[/math] holds for all edges [math]\displaystyle{ (u,v) \in E }[/math]. A vertex coloring is a backbone coloring for [math]\displaystyle{ \,(G,T) }[/math], if it is proper and, additionally, [math]\displaystyle{ |f(u) - f(v)| \geq 2 }[/math] holds for all edges [math]\displaystyle{ (u,v) \in E_{T} }[/math] in the spanning tree [math]\displaystyle{ \,T }[/math].

The backbone coloring number [math]\displaystyle{ \,BBC(G,T) }[/math] of [math]\displaystyle{ \,(G,T) }[/math] is the smal-lest integer [math]\displaystyle{ \ell }[/math] for which a backbone coloring [math]\displaystyle{ f: V \rightarrow \{1, 2, \ldots, \ell\} }[/math] exists.

Литература

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