Число игровое хроматическое: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Число игровое хроматическое''' (''[[Game chromatic number]]'') | '''Число игровое хроматическое''' (''[[Game-chromatic number|Game chromatic number]]'') — | ||
Пусть имеются [[граф]] <math>G</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>\,\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 B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994. | |||
Текущая версия от 13:56, 6 октября 2011
Число игровое хроматическое (Game chromatic number) — Пусть имеются граф [math]\displaystyle{ \,G, }[/math] множество цветов [math]\displaystyle{ \{1,2, \ldots, k\} }[/math] и два игрока [math]\displaystyle{ \,A }[/math] и [math]\displaystyle{ \,B, }[/math] которые делают свои ходы поочередно. Ход состоит в выборе неокрашенной вершины [math]\displaystyle{ v \in V(G) }[/math] и в окрашивании ее в цвет, отличный от цветов уже окрашенных ее соседей из [math]\displaystyle{ \,N_{G}(v). }[/math] Игра заканчивается и [math]\displaystyle{ \,A }[/math] объявляется победителем, если после [math]\displaystyle{ \,|V(G)| }[/math] ходов граф [math]\displaystyle{ \,G }[/math] становится [math]\displaystyle{ \,k }[/math]-раскрашиваемым. Игра заканчивается и [math]\displaystyle{ \,B }[/math] объявляется победителем, если при некотором ходе выбранная вершина не может быть раскрашена одним из цветов [math]\displaystyle{ \{1, 2, \ldots, k\} }[/math]. Игровым хроматическим числом [math]\displaystyle{ \,\chi_{g}(G) }[/math] называется такое наименьшее [math]\displaystyle{ \,k, }[/math] для которого игрок [math]\displaystyle{ \,A }[/math] имеет выигрышную стратегию. Известно, что
- [math]\displaystyle{ \chi(G) \leq \chi_{g}(G) \leq |V(G)|, }[/math]
где [math]\displaystyle{ \,\chi(G) }[/math] — хроматическое число. Если [math]\displaystyle{ \,G }[/math] — плоский граф, то
- [math]\displaystyle{ 7 \leq \chi_{g}(G) \leq 33. }[/math]
Литература
- Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.