Упорядоченная раскраска вершин: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Упорядоченная раскраска вершин''' (''Ordered colouring of vertices'') - такая раскраска <mat...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Упорядоченная раскраска вершин''' (''Ordered colouring of vertices'') - | '''Упорядоченная раскраска вершин''' (''[[Ordered colouring of vertices]]'') - | ||
такая раскраска <math>f</math> вершин графа <math>G</math> упорядоченным множеством цветов | такая [[раскраска]] <math>f</math> [[вершина|вершин]] [[граф|графа]] <math>G</math> упорядоченным множеством цветов | ||
<math>C = \{1,2, \ldots, c\}</math>, что для любых двух вершин <math>x, 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>f(x) = f(y)</math>, и любого [[простой путь|простого пути]] <math>P(x,y)</math>, их | ||
соединяющего, должна существовать внутренняя вершина | соединяющего, должна существовать внутренняя вершина | ||
<math>z</math>, цвет которой <math>f(z) > f(x) = f(y)</math>. | <math>z</math>, цвет которой <math>f(z) > f(x) = f(y)</math>. | ||
Аналогично определяется ''упорядоченная раскраска ребер''. | Аналогично определяется ''[[упорядоченная раскраска ребер]]''. | ||
Упорядоченная раскраска, очевидно, является правильной. | Упорядоченная раскраска, очевидно, является [[правильная раскраска|правильной]]. | ||
==Литература== | ==Литература== | ||
[Discrete Math.] | [Discrete Math.] | ||
Версия от 12:48, 17 февраля 2010
Упорядоченная раскраска вершин (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.]