Game domination number

Материал из WEGA
Версия от 12:24, 16 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Game domination number''' --- игровое число доминирования. We define a 'domination parameter' of an undirected graph <math>G</math> as…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Game domination number --- игровое число доминирования.

We define a 'domination parameter' of an undirected graph [math]\displaystyle{ G }[/math] as the domination number of one of its orientations determined by the following two player game. Players [math]\displaystyle{ A }[/math] and [math]\displaystyle{ D }[/math] orient the unoriented edges of the graph [math]\displaystyle{ G }[/math] alternately with [math]\displaystyle{ D }[/math] playing first, until all edges are oriented. Player [math]\displaystyle{ D }[/math] is trying to minimize the domination number of the resulting digraph, while player [math]\displaystyle{ A }[/math] tries to maximize the domination number. This game gives a unique number depending only on [math]\displaystyle{ G }[/math], if we suppose that both [math]\displaystyle{ A }[/math] and [math]\displaystyle{ D }[/math] play according to their optimal strategies. We call this number the game domination number of [math]\displaystyle{ G }[/math] and denote it by [math]\displaystyle{ \gamma_{g}(G) }[/math].