Edge t-ranking: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Edge <math>t</math>-ranking''' --- реберное <math>t</math>-ранжирование. Let <math>G = (V,E)</math> be a graph and <math>t</math> be a pos…») |
KVN (обсуждение | вклад) |
||
| Строка 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 | *''[[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.