Аноним

Упорядоченная раскраска вершин: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Упорядоченная раскраска вершин''' (''Ordered colouring of vertices'') - такая раскраска <mat...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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.]