4625
правок
Число Гранди: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Число Гранди''' (''Grundy number'') - раскраской Гранди порядка <math>k</math> графа <math>G</m...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>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] | ||