Упорядоченная раскраска вершин: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Упорядоченная раскраска вершин''' (''[[Ordered colouring of vertices]]'') | '''Упорядоченная раскраска вершин''' (''[[Ordered coloring of vertices|Ordered colouring of vertices]]'') — такая [[раскраска]] <math>\,f</math> [[вершина|вершин]] [[граф|графа]] <math>\,G</math> упорядоченным множеством цветов <math>C = \{1,2, \ldots, c\}</math>, что для любых двух вершин <math>\,x, y</math> одинакового цвета, <math>\,f(x) = f(y)</math>, и любого [[простой путь|простого пути]] <math>\,P(x,y)</math>, их соединяющего, должна существовать внутренняя вершина | ||
такая [[раскраска]] <math>f</math> [[вершина|вершин]] [[граф|графа]] <math>G</math> упорядоченным множеством цветов | <math>\,z</math>, цвет которой <math>\,f(z) > f(x) = f(y)</math>. Аналогично определяется ''[[упорядоченная раскраска ребер]]''. Упорядоченная раскраска, очевидно, является [[правильная раскраска|правильной]]. | ||
<math>C = \{1,2, \ldots, c\}</math>, что для любых двух вершин <math>x, y</math> одинакового | |||
цвета, <math>f(x) = f(y)</math>, и любого [[простой путь|простого пути]] <math>P(x,y)</math>, их | |||
соединяющего, должна существовать внутренняя вершина | |||
<math>z</math>, цвет которой <math>f(z) > f(x) = f(y)</math>. | |||
Аналогично определяется ''[[упорядоченная раскраска ребер]]''. | |||
Упорядоченная раскраска, очевидно, является [[правильная раскраска|правильной]]. | |||
==Литература== | ==Литература== | ||
[Discrete Math.] | * [Discrete Math.] | ||
Текущая версия от 10:46, 23 сентября 2011
Упорядоченная раскраска вершин (Ordered colouring of vertices) — такая раскраска [math]\displaystyle{ \,f }[/math] вершин графа [math]\displaystyle{ \,G }[/math] упорядоченным множеством цветов [math]\displaystyle{ C = \{1,2, \ldots, c\} }[/math], что для любых двух вершин [math]\displaystyle{ \,x, y }[/math] одинакового цвета, [math]\displaystyle{ \,f(x) = f(y) }[/math], и любого простого пути [math]\displaystyle{ \,P(x,y) }[/math], их соединяющего, должна существовать внутренняя вершина [math]\displaystyle{ \,z }[/math], цвет которой [math]\displaystyle{ \,f(z) \gt f(x) = f(y) }[/math]. Аналогично определяется упорядоченная раскраска ребер. Упорядоченная раскраска, очевидно, является правильной.
Литература
- [Discrete Math.]