4194
правки
Упорядоченная раскраска вершин: различия между версиями
Перейти к навигации
Перейти к поиску
Упорядоченная раскраска вершин (посмотреть исходный код)
Версия от 12:48, 17 февраля 2010
, 17 февраля 2010нет описания правки
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.] | ||