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