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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Число игровое хроматическое''' (''Game chromatic number'') - Пусть имеются граф <math>G</math...)
 
Нет описания правки
Строка 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>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]

Версия от 17:17, 18 мая 2010

Число игровое хроматическое (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-Jensen]