Число игровое хроматическое: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Число игровое хроматическое''' (''[[Game chromatic number]]'') -
'''Число игровое хроматическое''' (''[[Game-chromatic number|Game chromatic number]]'')
Пусть имеются [[граф]] <math>G</math>, множество цветов <math>\{1,2, \ldots, k\}</math> и два
Пусть имеются [[граф]] <math>\,G,</math> множество цветов <math>\{1,2, \ldots, k\}</math> и два
игрока <math>A</math> и <math>B</math>, которые делают свои ходы поочередно. Ход состоит в
игрока <math>\,A</math> и <math>\,B,</math> которые делают свои ходы поочередно. Ход состоит в
выборе неокрашенной [[вершина|вершины]] <math>v \in V(G)</math> и в окрашивании ее в цвет,
выборе неокрашенной [[вершина|вершины]] <math>v \in V(G)</math> и в окрашивании ее в цвет,
отличный от цветов уже окрашенных ее соседей из <math>N_{G}(v)</math>. Игра
отличный от цветов уже окрашенных ее соседей из <math>\,N_{G}(v).</math> Игра заканчивается и <math>\,A</math> объявляется победителем, если после <math>\,|V(G)|</math> ходов граф <math>\,G</math> становится [[k-Раскрашиваемый граф|<math>\,k</math>-раскрашиваемым]]. Игра заканчивается и <math>\,B</math> объявляется победителем, если при некотором ходе выбранная вершина не может быть
заканчивается и <math>A</math> объявляется победителем, если после <math>|V(G)|</math>
раскрашена одним из цветов <math>\{1, 2, \ldots, k\}</math>. ''Игровым хроматическим числом'' <math>\,\chi_{g}(G)</math> называется такое наименьшее <math>\,k,</math> для которого игрок <math>\,A</math> имеет выигрышную стратегию. Известно, что
ходов граф <math>G</math> становится [[k-Раскрашиваемый граф|<math>k</math>-раскрашиваемым]]. Игра заканчивается и <math>B</math> объявляется победителем, если при некотором ходе выбранная вершина не может быть
раскрашена одним из цветов <math>\{1, 2, \ldots, k\}</math>. ''Игровым хроматическим числом'' <math>\chi_{g}(G)</math> называется такое наименьшее <math>k</math>,
для которого игрок <math>A</math> имеет выигрышную стратегию. Известно, что


<math>\chi(G) \leq \chi_{g}(G) \leq |V(G)|,</math>
:::::<math>\chi(G) \leq \chi_{g}(G) \leq |V(G)|,</math>


где <math>\chi(G)</math>  - [[хроматическое число]]. Если <math>G</math> - [[плоский граф]], то
где <math>\,\chi(G)</math>  [[хроматическое число]]. Если <math>\,G</math> [[плоский граф]], то


<math>7 \leq \chi_{g}(G) \leq 33.</math>
:::::<math>7 \leq \chi_{g}(G) \leq 33.</math>
==Литература==
==Литература==
[Toft-Jensen]
* Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.

Навигация