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

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