Аноним

Число Гранди: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Число Гранди''' (''Grundy number'') - раскраской Гранди порядка <math>k</math> графа <math>G</m...)
 
Нет описания правки
Строка 1: Строка 1:
'''Число Гранди''' (''Grundy number'') -  
'''Число Гранди''' (''[[Grundy number]]'') -  
раскраской Гранди порядка <math>k</math> графа <math>G</math> называется <math>k</math>-раскраска
раскраской Гранди порядка <math>k</math> графа <math>G</math> называется <math>k</math>-[[раскраска]]
вершин цветами <math>\{1,2, \ldots, k\}</math> такая, что для любой вершины <math>x</math>
[[вершина|вершин]] цветами <math>\{1,2, \ldots, k\}</math> такая, что для любой вершины <math>x</math>
ее цвет <math>c(x)</math> есть минимальное целое число, не использованное на ее
ее цвет <math>c(x)</math> есть минимальное целое число, не использованное на ее
соседях. '''Ч.Г.''' <math>\Gamma(G)</math> ---  наибольшее <math>k</math>, для которого <math>G</math>
соседях. '''Число Гранди''' <math>\Gamma(G)</math> -  наибольшее <math>k</math>, для которого <math>G</math>
имеет раскраску Гранди порядка <math>k</math>. Известно, что
имеет раскраску Гранди порядка <math>k</math>. Известно, что


<math>\chi(G) \leq \Gamma(G) \leq \Psi(G),</math>
<math>\chi(G) \leq \Gamma(G) \leq \Psi(G),</math>


где <math>\chi(G)</math> и <math>\Psi(G)</math> --- хроматическое и ахроматическое числа.
где <math>\chi(G)</math> и <math>\Psi(G)</math> - [[хроматическое число|хроматическое]] и ахроматическое числа.
==Литература==
==Литература==
[Toft-Jensen]
[Toft-Jensen]