Число Гранди: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Число Гранди''' (''Grundy number'') - раскраской Гранди порядка <math>k</math> графа <math>G</m...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Число Гранди''' (''Grundy number'') | '''Число Гранди''' (''[[Grundy number]]'') — ''[[раскраска|раскраской]] Гранди порядка <math>\,k</math> графа <math>\,G</math>'' называется [[k-Раскраска|<math>\,k</math>-раскраска]] | ||
раскраской Гранди порядка <math>k</math> графа <math>G</math> называется <math>k</math>-раскраска | [[вершина|вершин]] цветами <math>\{1,2, \ldots, k\}</math> такая, что для любой вершины <math>\,x</math> ее цвет <math>\,c(x)</math> есть минимальное целое число, не использованное на ее | ||
вершин цветами <math>\{1,2, \ldots, k\}</math> такая, что для любой вершины <math>x</math> | соседях. '''Число Гранди''' <math>\,\Gamma(G)</math> — наибольшее <math>\,k</math>, для которого <math>\,G</math> имеет раскраску Гранди порядка <math>\,k.</math> Известно, что | ||
ее цвет <math>c(x)</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 B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994. | |||
Текущая версия от 12:54, 6 октября 2011
Число Гранди (Grundy number) — раскраской Гранди порядка [math]\displaystyle{ \,k }[/math] графа [math]\displaystyle{ \,G }[/math] называется [math]\displaystyle{ \,k }[/math]-раскраска вершин цветами [math]\displaystyle{ \{1,2, \ldots, k\} }[/math] такая, что для любой вершины [math]\displaystyle{ \,x }[/math] ее цвет [math]\displaystyle{ \,c(x) }[/math] есть минимальное целое число, не использованное на ее соседях. Число Гранди [math]\displaystyle{ \,\Gamma(G) }[/math] — наибольшее [math]\displaystyle{ \,k }[/math], для которого [math]\displaystyle{ \,G }[/math] имеет раскраску Гранди порядка [math]\displaystyle{ \,k. }[/math] Известно, что
- [math]\displaystyle{ \chi(G) \leq \Gamma(G) \leq \Psi(G), }[/math]
где [math]\displaystyle{ \,\chi(G) }[/math] и [math]\displaystyle{ \,\Psi(G) }[/math] — хроматическое и ахроматическое числа.
Литература
- Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.