Edge t-ranking: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Edge <math>t</math>-ranking''' --- реберное <math>t</math>-ранжирование. Let <math>G = (V,E)</math> be a graph and <math>t</math> be a pos…»)
 
 
Строка 7: Строка 7:
value of <math>t</math> such that <math>G</math> has an edge <math>t</math>-ranking.
value of <math>t</math> such that <math>G</math> has an edge <math>t</math>-ranking.
==See also==
==See also==
*''Vertex <math>t</math>-ranking''.
*''[[Vertex t-ranking]]''.

Текущая версия от 11:54, 3 ноября 2011

Edge [math]\displaystyle{ t }[/math]-ranking --- реберное [math]\displaystyle{ t }[/math]-ранжирование.

Let [math]\displaystyle{ G = (V,E) }[/math] be a graph and [math]\displaystyle{ t }[/math] be a positive integer. An edge [math]\displaystyle{ t }[/math]-ranking is an edge coloring [math]\displaystyle{ c': \; E \rightarrow \{1, \ldots, t\} }[/math] such that for every pair of edges [math]\displaystyle{ e }[/math] and [math]\displaystyle{ f }[/math] with [math]\displaystyle{ c'(e) = c'(f) }[/math], there is an edge [math]\displaystyle{ g }[/math] on every path between [math]\displaystyle{ e }[/math] and [math]\displaystyle{ f }[/math] with [math]\displaystyle{ c'(g) \gt c'(e) }[/math]. The edge ranking number, [math]\displaystyle{ \chi'_{r}(G) }[/math], is the smallest value of [math]\displaystyle{ t }[/math] such that [math]\displaystyle{ G }[/math] has an edge [math]\displaystyle{ t }[/math]-ranking.

See also