Problemas de Jogos em Triangulações Planares
Liane de Oliveira Germoliato Barostichi
Dissertação apresentada
ao
Centro de Matemática, Computação e Cognição (CMCC)
da
Universidade Federal do ABC (UFABC)
para
obtenção de grau de mestrado
no Programa de Pós-Graduação em Engenharia da Informação
Orientadora: Profa. Dra. Gordana Manić
Durante a elaboração deste trabalho a autora recebeu apoio financeiro da FAPESP
(Processo Número: 2010/13015-8).
Santo André, Julho de 2012.
Problemas de Jogos em Triangulações Planares
Este exemplar corresponde à redação final
da dissertação devidamente corrigida e defendida
por Liane de Oliveira Germoliato Barostichi
e aprovada pela Comissão Julgadora.
Santo André, Julho de 2012.
Banca Examinadora:
Profa. Dra. Gordana Manić (orientadora) – CMCC/UFABC
Prof. Dra. Cristina Gomes Fernandes – IME/USP
Prof. Dr. Gustavo Sousa Pavani – CMCC/UFABC
^
.SSjjim^
f
\
\
PÓS-GRADUAÇÃO EM ENGENHARIA DA
INFORMAÇÃO
Universidade Federal do ABC
FOLHA DE ASSINATURAS
Assinaturas dos membros da Banca Examinadora que avaliou e aprovou
a Defesa de Dissertação de Mestrado da candidata Liane de Oliveira
Germoliato Barostichi em 30 de julho de 2012:
Profa. pra. Gordana Manic (UFABC) - Orientadora e Presidente
ProfaTDra. Cristina Gomes Fernandes (USP) - Titular
L/
^EJQ^^e». Ja
Prof. Dr. Gustavo Sousa Pavani (UFABC) - Titular
Prof. Dr. Carlos Eduardo Ferreira (USP) - Suplente
Prof. Dr. João Ricardo Sato (UFABC) - Suplente
Universidade Federal do ABC , Av. dos Estados, 5.001 - CEP 09210-580 - Santo André - SP
Tel O XX. 1 1 - 4996-0086 www.ufabc.edu.br
Resumo
Os problemas de jogos em triangulações planares pertencem a uma área mais geral de jogos combinatórios que normalmente envolvem dois jogadores. O principal objetivo consiste em determinar,
em cada jogo, qual será o resultado do jogo, ou seja, quem será o ganhador ou se então acontecerá
um empate.
Neste texto, apresentamos alguns jogos combinatórios, como jogos Nim, Kayles e Dawson’s
Kayles. Também, versamos sobre complexidade e completude em PSPACE. Por fim, apresentamos as três grandes categorias de jogos combinatórios em triangulações planares introduzidas por
Aichholzer et al. [1]: construção, transformação e marcação, e detalhamos os jogos de marcação e
construção.
1
Abstract
Games on triangulations belong to the more general area of combinatorial games, which usually
involve two players. The main objective is to determine, in each game, what will be the outcome
of the game, that is, first player wins, second player wins, or it will be a third possible outcome, a
tie.
In this text, we present some combinatorial games like Nim, Kayles and Dawson’s Kayles.
Also, we discuss about complexity and PSPACE-completeness. Finally, we present the three major
categories of Combinatorial Games on Planar Triangulations introduced by Aichholzer et al. [1]:
constructing, flipping, and marking, and discuss in more details constructing and marking games.
2
Sumário
1 Introdução
7
2 Pré-requisitos
9
2.1
Algumas definições importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.1
Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2
Grafo Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Jogos combinatórios
15
3.1
Definição e exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2
O jogo Nim e a Teoria de Sprague-Grundy . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3
Jogo Kayles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4
Jogo Dawson’s Kayles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Complexidade
26
4.1
Completude em PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2
Complexidade do jogo em grafos associado ao jogo Dawson’s Kayles . . . . . . . . . 28
5 Jogos em Triangulações Planares
31
5.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2
Jogos de Construção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3
5.2.1
Jogo do Triângulo Monocromático . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2.2
Jogo da Triangulação Monocromática Completa . . . . . . . . . . . . . . . . 34
5.2.3
Jogo do Triângulo Bicromático . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Jogos de Marcação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3.1
Jogo Colorindo uma Triangulação Monocromático . . . . . . . . . . . . . . . 41
3
5.3.2
Jogo Bicolorindo uma Triangulação . . . . . . . . . . . . . . . . . . . . . . . . 42
6 Comentários Finais
47
Referências Bibliográficas
48
4
Lista de Figuras
2.1
Exemplo de um grafo completo.
2.2
Exemplo de árvore.
2.3
Exemplo de grafo (em preto) com grafo dual (em azul). . . . . . . . . . . . . . . . . 14
5.1
Jogador R joga uv. Este movimento divide C em duas configurações independentes
C1 e C2 .
5.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
A configuração C1 tem duas arestas vermelhas. Jogador B pode agora escolher uma
hyi
hyi
aresta livre xy em C1 onde C1 xy e C1 yx contém, cada um, uma única aresta
vermelha. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3
Exemplo de uma triangulação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.4
Grafo e respectivo dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5
Exemplo do grafo após a jogada do jogador B que colore a aresta e de azul.
. . . . 44
5.6
O movimento do jogador B divide o grafo dual em subgrafos independentes.
. . . . 44
5.7
Se a triangulação contém a aresta e conectando dois pontos internos, então no primeiro movimento, o jogador B colore e em azul.
5.8
. . . . . . . . . . . . . . . . . . . . 46
Exemplo quando a triangulação não contém uma aresta e conectando os dois pontos
internos. Neste caso vamos chamar de ciclo esquerdo e ciclo direito, respectivamente,
os ciclos no grafo dual. Tais ciclos são conectados por um caminho através de dois
vértices a e b, a 6= b. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5
Lista de Tabelas
3.1
Valores de Nim para o jogo Kayles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2
Valores de Nim para o jogo Dawson’s Kayles . . . . . . . . . . . . . . . . . . . . . . 25
6
Capı́tulo 1
Introdução
Neste trabalho, buscamos principalmente estudar os jogos em triangulações planares, os quais
pertencem a uma área mais geral de jogos combinatórios que normalmente envolvem dois jogadores,
R e B. Em um jogo combinatório, uma posição de jogo consiste de um conjunto de opções para
o jogador R e um conjunto de opções para o jogador B. Cada opção em si é uma posição de
jogo, que representa o resultado do movimento. Para maiores informações sobre a teoria dos jogos
combinatórios, consulte [2, 6, 8, 9].
Um jogo combinatório é dito ótimo se os jogadores fazem o seu melhor para ganhar. Qualquer
jogo combinatório ótimo sem empates tem somente dois possı́veis resultados: o primeiro jogador
vence o jogo ou então o segundo jogador vence. Em outras palavras, o primeiro jogador pode forçar
a sua vitória, ou então o segundo pode forçar a sua vitória, não importando como o outro jogador
se move ao longo do jogo. Tais procedimentos são chamados de estratégias vencedoras. Observamos
que os jogos combinatórios podem ter ainda um terceiro êxito (resultado): um dos jogadores pode
forçar o empate.
No trabalho intitulado Games on triangulations, Aichholzer et al. [1] analisaram vários jogos
combinatórios em triangulações planares, envolvendo os vértices, arestas e faces (triângulos) de
uma triangulação. Eles apresentaram os jogos em que dois jogadores R e B jogam alternadamente,
assim como jogos solitários para somente um jogador. Em versões bicromáticas dos jogos para
dois jogadores, o jogador R (Red ) irá usar a cor vermelha e o jogador B (Blue) irá usar azul,
respectivamente, para colorir algum elemento da triangulação, sendo que quem inicia o jogo é
sempre o jogador R. Em variações monocromáticas de jogos, todos os jogadores (ou um único
jogador) usam uma mesma cor.
7
O objetivo principal deste texto é prover um estudo detalhado sobre os jogos em triangulações
planares, com base nas contribuições de Aichholzer et al. [1], buscando detalhar os resultados e
fundamentar as principais noções necessárias para sua compreensão.
A dissertação está estruturada da seguinte forma:
• No capı́tulo 1 apresentamos os pré-requisitos, composto pelas definições necessárias para um
melhor entendimento do texto, como as definições de grafo e árvore.
• No capı́tulo 2 apresentamos alguns jogos combinatórios, dos quais destacamos os jogos Nim,
Kayles e Dawson’s Kayles.
• No capı́tulo 3 versamos sobre complexidade e completude em PSPACE.
• Por fim, no capı́tulo 4, apresentamos as três grandes categorias de jogos combinatórios em
triangulações planares introduzidas por Aichholzer et al. [1]: construção, transformação e
marcação, e detalhamos os jogos de marcação e construção.
8
Capı́tulo 2
Pré-requisitos
Neste capı́tulo, introduziremos algumas noções básicas necessárias para o desenvolvimento deste
trabalho. Dentre tais noções, destaca-se o conceito de grafo que ocupa um papel central nesta
dissertação e o conceito de árvore e grafo dual que utilizaremos no Jogo Bicolorindo uma Triangulação, descrito na seção 4.3 do Capı́tulo 4. As definições e resultados apresentadas aqui podem
ser encontradas nas referências [5] e [7].
2.1
Algumas definições importantes
Definição 2.1 Um grafo é um par (V, E), onde V é um conjunto finito arbitrário e E um conjunto
de pares não-ordenados de elementos de V . Os elementos de V são chamados vértices e os de E
arestas.
Lembremos que um par não-ordenado é um conjunto com exatamente dois elementos. Um par
não-ordenado {v, w} será denotado, indiferentemente, por vw ou wv.
Definição 2.2 Dizemos que dois vértices v e w de um grafo são adjacentes se existe uma aresta
com extremos v e w. Um grafo completo é um grafo onde cada vértice é adjacente a todos os
outros (ver figura 2.1).
Definição 2.3 Um conjunto U no plano é dito convexo se, dados quaisquer dois pontos em U ,
o segmento que os une está contido em U . Definimos a envoltória convexa de n pontos como
sendo o menor conjunto convexo que contém tais pontos.
9
Figura 2.1: Exemplo de um grafo completo.
Como um exemplo, dado um conjunto S formado por três pontos não colineares, a envoltória
convexa de S é o triângulo que tem estes três pontos como vértices.
Definição 2.4 Um n-Simplexo é um polı́topo de dimensão n dado pela envoltória convexa de
(n + 1) vértices.
Definição 2.5 Um passeio em um grafo G é uma sequência (v0 , e1 , v1 , e2 , v2 , . . . , ek , vk ) em que
v0 , . . . , vk são vértices de G e cada ei é uma aresta de G com extremos vi
1
e vi . A origem e
o término do passeio são respectivamente v0 e vk e o passeio é dito um passeio fechado se
vk = v0 e é aberto caso contrário. Um caminho em G é um passeio cujos vértices são dois a dois
distintos.
Definição 2.6 Um ciclo é um passeio fechado onde as arestas são distintas duas a duas.
Definição 2.7 Um grafo G é dito conexo se, para todo par v, w de vértices de G existe um passeio
com origem em v e término em w. Os subgrafos conexos maximais de um grafo são chamados
componentes. Um clique em um grafo é um conjunto de vértices dois a dois adjacentes.
Definição 2.8 Um grafo é planar se ele pode ser desenhado no plano de tal forma que nenhuma
aresta cruze as demais. Um grafo planar G divide o plano em um conjunto de regiões conexas
maximais, conhecidas como as faces de G. A região conexa ilimitada obtida nesta partição do
plano é chamada face ilimitada.
10
Finalmente, definimos a importante noção de triangulação, fundamental para o desenvolvimento
deste trabalho.
Definição 2.9 Um complexo simplicial C é uma colecção finita de simplexos tais que cada face
de um simplexo de C é um simplexo de C e a intersecção de dois simplexos de C é vazia ou uma
face de ambos. Dado um complexo simplicial C, C é uma decomposição simplicial para um
S
conjunto B se B = 2C .
Definição 2.10 Uma triangulação em um conjunto finito de pontos S no plano, tal que quaisquer
três pontos de S são sempre não colineares, é uma decomposição simplicial de envoltória convexa
de S onde os vértices dos simplexos são os pontos de S.
2.1.1
Árvores
Daremos a seguir a definição de árvore, que será utilizada no decorrer do trabalho.
Definição 2.11 Dizemos que um grafo G é uma floresta se G for um grafo sem ciclos. O grafo
G é dito uma árvore se for uma floresta conexa. Como exemplo de árvore veja a figura 2.2.
Lema 2.1 Seja H um grafo com n vértices, m arestas, ⌫ ciclos e p componentes conexas. Então
vale a seguinte fórmula:
p=n
m + ⌫.
Demonstração: Suponha inicialmente que H é conexo, ou seja, p = 1.
Pela fórmula de Euler para grafos conexos, temos que
V
A + F = 2,
sendo V o número de vértices, A o número de arestas e F o número de faces, incluindo a componente
ilimitada determinada pelo grafo.
Assim, com as notações acima, temos que V = n, A = m e F = ⌫ + 1.
Logo,
n
m+⌫ =V
A+F
1=2
1 = 1.
Para o caso geral, sejam Hi , i = 1, . . . , p, as componentes conexas de H. Sendo ni , mi e ⌫i os
números de vértices, arestas e ciclos de Hi , respectivamente, temos pelo caso anterior que
11
ni
mi + ⌫i = 1, para i = 1, ..., p.
Observamos ainda que,
n=
p
X
ni , m =
i=1
Logo,
n
p
X
mi e ⌫ =
i=1
m+⌫ =
p
X
(ni
mi + ⌫ i ) =
i=1
o que conclui a demonstração.
p
X
⌫i .
i=1
p
X
1 = p,
i=1
⇤
Teorema 2.1 ([4]) Seja H um grafo com n vértices. Qualquer uma das seguintes propriedades
equivalentes caracteriza uma árvore:
(a) H é conexo e não possui ciclos;
(b) H não contém ciclos e possui n
(c) H é conexo e possui n
1 arestas;
1 arestas;
(d) H não contém ciclos, e se uma aresta é adicionada de modo a juntar dois vértices não
adjacentes, então um (e apenas um) ciclo é formado;
(e) H é conexo mas perde essa propriedade se qualquer aresta for retirada;
(f ) Todo par de vértices é conectado por um e apenas um caminho.
Demonstração: (a) ) (b). Sendo p o número de componentes, m o número de arestas e ⌫ o
número de ciclos de H, o fato de H ser conexo e não possuir ciclos implica que p = 1 e ⌫ = 0.
Vemos ainda que os números de arestas, componentes e ciclos estão relacionados com a ordem n
do grafo pela relação
m
Assim, temos que m = n
n + p = ⌫ = 0.
1.
(b) ) (c). Com as mesmas notações acima, as hipóteses neste caso nos dizem que ⌫ = 0 e
m=n
1. Logo,
p=⌫
m + n = ⌫ + 1 = 1,
donde segue que H é conexo.
12
(c) ) (d). Temos neste caso que p = 1 e m = n
⌫=m
1. Assim,
n+p=0
e portanto, H não contém ciclos. Além disso, se adicionarmos uma aresta conectando quaisquer
dois vértices não adjacentes, então m passa a ser igual a n e então, ⌫ = 1, ou seja, o grafo tem
exatamente um ciclo.
(d) ) (e). Se H não é conexo, podemos encontrar vértices x e y não conectados por arestas
e assim, quando adicionamos a aresta xy, não formamos um ciclo, o que contraria (d). Portanto,
H é conexo, ou seja, p = 1. Ainda, ao retirar uma aresta, temos m = n
segue que p = ⌫
2. Uma vez que ⌫ = 0,
m + n = 2, e H deixa de ser conexo.
(e) ) (f ). Sendo H conexo, existe um caminho unindo quaisquer dois vértices, digamos x e y.
Se existissem dois caminhos unindo x e y, a eliminação de uma aresta no primeiro caminho que não
pertence ao segundo não torna o grafo desconexo, contrariando assim a hipótese (e). Logo, cada
par de vértices é conectado por um e apenas um caminho.
(f ) ) (a). A conexidade de H é imediata. Supondo que H contém um ciclo, podemos encontrar
um par de vértices conectado por dois caminhos, uma contradição a (f ). Portanto, H não contém
⇤
ciclos.
Figura 2.2: Exemplo de árvore.
13
2.1.2
Grafo Dual
Definição 2.12 Dado um grafo planar G, seu grafo dual é dado da seguinte forma: associamos
a cada face de G um vértice e, quando duas faces compartilham uma aresta em G, seus respectivos
vértices no dual são conectados por uma aresta.
A figura 2.3 mostra um exemplo de um grafo G e seu grafo dual.
Figura 2.3: Exemplo de grafo (em preto) com grafo dual (em azul).
14
Capı́tulo 3
Jogos combinatórios
Neste Capı́tulo, definiremos jogos combinatórios e daremos alguns resultados importantes nesta
teoria, bem como alguns exemplos de jogos combinatórios que serão relevantes ao longo deste texto.
Os jogos combinatórios de especial interesse nesse trabalho são os jogos em triangulações planares, os
quais serão discutidos no capı́tulo 4. Veremos que dois desses jogos, nominalmente o jogo colorindo
uma triangulação e o jogo do triângulo monocromático, têm as mesmas caracterı́sticas dos jogos
Kayles e Dawson’s Kayles, respectivamente, os quais serão apresentados neste capı́tulo. Dessa
forma, os problemas consistindo em buscar estratégias de vitória para esses jogos compartilham
das mesmas propriedades. Em particular, isso continua válido no que se refere à complexidade
desses problemas, conceito este que será abordado no capı́tulo 3. Os resultados deste capı́tulo
podem ser encontrados em [9].
3.1
Definição e exemplos
Definição 3.1 Um jogo combinatório é um jogo que apresenta as seguintes caracterı́sticas:
(a) É jogado por dois jogadores, sendo que os mesmos jogam alternadamente.
(b) É um jogo finito, ou seja, o jogo sempre termina após um número finito de movimentos, e
ainda, em cada jogada, o jogador escolhe uma entre uma quantidade finita de movimentos possı́veis.
(c) É imparcial, ou seja, ambos os jogadores têm as mesmas possibilidades de movimentos.
(d) É um jogo de informação completa, ou seja, não existem informações escondidas.
(e) É determinı́stico, no sentido de que cada movimento leva a uma única posição, e não há
aleatoriedade (como em lançamento de dados).
15
(f ) O jogo termina quando é atingida uma certa posição, a partir da qual não há mais movimentos possı́veis. Sob a regra normal de jogo, o último jogador a executar um movimento possı́vel
vence. Sob a regra misère, o último jogador a executar um movimento perde.
Consideraremos aqui apenas jogos combinatórios com a regra normal de jogo. Destacamos ainda
as seguintes definições.
Definição 3.2 Um jogo combinatório é ótimo se os jogadores fazem o seu melhor para ganhar.
Definição 3.3 Uma posição em um jogo combinatório é uma posição terminal se nenhum movimento a partir dela é possı́vel.
Exemplo 3.1 Damos a seguir um exemplo simples de um jogo combinatório: É dada uma pilha
com 21 feijões. Um movimento de cada um dos dois jogadores, aos quais nos referiremos como
jogador I e jogador II, consiste em retirar da pilha um, dois ou três feijões, e os jogadores realizam
estes movimentos alternadamente. O jogador I inicia o jogo e o vencedor é aquele que remover o
último feijão da pilha.
Observe que existe uma estratégia vencedora para o jogador I: na primeira jogada, o jogador I
retira um feijão, deixando 20 feijões na pilha. Após a jogada do jogador II, o jogador I retira tantos
feijões quantos forem necessários, de modo a deixar 16 feijões na pilha (observe que tal movimento é
sempre possı́vel). Prosseguindo dessa forma, o jogador I deixará, após cinco rodadas, quatro feijões
na pilha. Uma vez que o jogador II pode retirar no máximo três feijões, o próximo movimento do
jogador I consistirá em retirar todos os feijões restantes, levando-o à vitória.
Definição 3.4 Dizemos que uma posição de jogo é uma posição vencedora para um jogador se
existe uma estratégia de vitória a partir desta posição para o mesmo.
Observe que, em jogos combinatórios com regra normal de jogo, toda posição para a qual é possı́vel,
com um movimento, atingir uma posição terminal, é uma posição vencedora.
Definição 3.5 As posições que são vencedoras para o jogador que realizou o último movimento são
chamadas P -posições, e as posições que são vencedoras para o jogador que realizará o próximo
movimento são chamadas N -posições.
16
No exemplo acima, vemos que as P -posições são as pilhas com quantidades de feijões que são
múltiplas de 4. As demais são N -posições.
É possı́vel determinar a priori quais posições em um jogo combinatório com regra normal de jogo
são P -posições e quais são N -posições, por meio de um método de recorrência, o qual destacamos
abaixo.
Passo 1: Nomeamos todas as posições terminais como sendo P -posições.
Passo 2: Nomeamos todas as posições que podem atingir, com um movimento, uma P -posição,
como sendo uma N -posição.
Passo 3: Encontramos todas as posições para as quais todos os movimentos possı́veis levam a
N -posições e as nomeamos como P -posições.
Passo 4: Se, no passo 3, nenhuma nova P -posição é encontrada, o processo termina. Caso
contrário, retornamos ao passo 2.
É fácil ver que as P -posições e N -posições nomeadas a partir do processo de recorrência acima
descrito cumprem os requisitos dados na Definição 3.5.
Podemos sumarizar as caracterı́sticas desses dois tipos de posições para um jogo combinatório
com regra normal de jogo na seguinte proposição.
Proposição 3.1 As P -posições e N -posições podem ser definidas recursivamente pelas seguintes
afirmações:
• Todas as posições terminais são P -posições.
• A partir de toda N -posição, existe pelo menos um movimento que leva a uma P -posição.
• Todo movimento a partir de uma P -posição leva a uma N -posição.
Definiremos abaixo um tipo especial de jogo combinatório, que engloba o Exemplo 3.1.
Definição 3.6 Seja S um conjunto de inteiros positivos. Definimos o jogo de subtração com
conjunto subtração S, como sendo o seguinte. De uma pilha com n feijões, dois jogadores
alternam movimentos. Um movimento consiste em retirar s feijões da pilha, com s 2 S. O último
jogador a realizar um movimento vence.
17
É fácil ver que o jogo definido no Exemplo 3.1 é um jogo de subtração, com n = 21 e cujo
conjunto subtração é S = {1, 2, 3}.
Observação 3.1 Note que em um jogo de subtração, com conjunto subtração S, existem m posições
terminais, sendo m = min (S), posições estas as quais chamamos 0, 1, 2, . . . , m
1. Então todos os
elementos de S serão N -posições (associamos ao elemento s 2 S a posição dada pela pilha com s
feijões), bem como os elementos da forma s + k, sendo k = 0, 1, . . . , m
1 e s 2 S.
Supondo, por exemplo, que 1 2 S e 2 2
/ S, teremos a posição 0 como única posição terminal,
e consequentemente, 2 será uma P -posição, pois o único movimento possı́vel é para 1, que é uma
N -posição.
3.2
O jogo Nim e a Teoria de Sprague-Grundy
Dentre os jogos com o formato de “tirar feijões de uma pilha”, o jogo Nim é sem dúvidas o mais
conhecido. O jogo Nim é um jogo combinatório no qual dois jogadores jogam em turnos removendo
feijões que estão dispostos em n diferentes pilhas. O jogo ocorre da seguinte forma. A cada rodada
o jogador escolhe uma pilha e da pilha escolhida ele retira pelo menos um feijão. Em uma mesma
rodada o jogador pode retirar todos os feijões de uma pilha, desde que sejam retirados feijões de
uma única pilha.
Associado a este jogo, temos uma rica teoria, chamada teoria de Sprague-Grundy, ou teoria do
jogo Nim. Apresentaremos aqui algumas definições e resultados básicos associados a essa teoria.
Para simplificar os argumentos, vamos analisar o jogo Nim jogado com três pilhas, contendo
n1 , n2 e n3 feijões, respectivamente. Observe que existe uma única posição terminal para este jogo,
a qual chamaremos (0, 0, 0). Note também que posições da forma (0, 0, m), ou seja, aquelas que
possuem feijões em apenas uma das três pilhas, são N -posições (não estamos preocupados aqui com
a ordem das pilhas).
Suponha então que existam duas pilhas contendo feijões. Neste caso, vemos que as P -posições
são da forma (0, m, m). De fato, se o oponente realizar um movimento a partir de uma tal posição,
ele se moverá para uma posição com duas pilhas com um número diferente de feijões, e então
podemos na próxima jogada igualar novamente o número de feijões na pilha, e prosseguir dessa
forma até levar à posição terminal.
O caso em que as três pilhas contêm feijões é mais complicado. Para descrever este caso, fazemos
18
uso da noção de soma-nim, a qual definiremos em seguida.
Relembremos que qualquer inteiro não negativo p possui uma única representação em base 2,
ou seja, existem únicos p0 , p1 , . . . , pm tais que pi = 0 ou pi = 1, para todo i = 0, 1, . . . , m, e
p = p m 2m + p m
Utilizamos a notação p = (pm pm
Definição 3.7 Dados p = (pm pm
12
m 1
+ · · · + p1 2 + p 0 .
1 · · · p1 p0 ) 2 .
1 · · · p1 p0 ) 2
e q = (qm qm
1 · · · q1 q0 ) 2 ,
definimos a soma-nim de
p e q como sendo
p
q = (pm pm
1 · · · p1 p0 ) 2
(qm qm
1 · · · q1 q0 ) 2
= (rm rm
1 · · · r1 r0 ),
com ri = (pi + qi ) mod 2, para i = 0, 1, . . . , m, ou seja, ri = 1 se pi + qi = 1 e ri = 0, caso
contrário.
Exemplo 3.2 Ao realizar a soma-nim dos números 23 e 47, obtemos
23
47 = (10111)2
(101111)2 = (111000)2 = 56.
Vale o seguinte teorema.
Teorema 3.1 ([2, 3, 6]) Uma posição (p1 , p2 , . . . , pn ) no jogo Nim é uma P -posição se, e somente
se, p1
p2
···
pn = 0.
Dado um jogo combinatório qualquer, a cada posição podemos associar um número, por meio
do qual podemos dar informações a respeito do jogo.
Definição 3.8 Um nimber é um inteiro em N. Dado um conjunto finito de nimbers S ⇢ N,
definimos o nimber mı́nimo excludente de S como sendo
mex(S) = min{i 2 N : i 2
/ S}.
Podemos associar a uma dada posição de um jogo combinatório um nimber da seguinte forma: se
a posição é terminal, então associamos o nimber 0. Caso contrário, o nimber é o mı́nimo excludente
do conjunto dos nimbers das posições que podem ser atingidas em um movimento.
19
Exemplo 3.3 No caso do Exemplo 3.1, denotando por n(i) o nimber associado à posição i, temos
os seguintes valores:
n(0) = n(4) = n(8) = n(12) = n(16) = n(20) = 0;
n(1) = n(5) = n(9) = n(13) = n(17) = n(21) = 1;
n(2) = n(6) = n(10) = n(14) = n(18) = 2;
n(3) = n(7) = n(11) = n(15) = n(19) = 3.
Vale o seguinte resultado.
Teorema 3.2 ([2, 3, 6]) Em um jogo combinatório, existe uma estratégia vencedora para o jogador que começa o jogo a partir de uma certa posição se, e somente se, o nimber desta posição é
maior ou igual a 1.
No caso do jogo Nim, temos que, se P = (p1 , . . . , pn ) é uma posição, então o nimber de P é
dado por p1
···
pn (ver [3]).
Sendo assim, o Teorema 3.1 é uma consequência direta do Teorema 3.2.
Finalizamos esta seção com as seguintes definições.
Definição 3.9 Dado um jogo combinatório qualquer, a função de Sprague-Grundy associada
a este jogo é a função que, a cada posição de jogo p, associa o nimber de p.
Denotaremos por g(p) a função de Sprague-Grundy associada à posição de jogo p.
Exemplo 3.4 No caso do Exemplo 3.1, é fácil ver que a função de Sprague-Grundy é dada por
g(p) = p mod 4, para todo p = 0, 1, . . . , 21.
Definição 3.10 Dados n jogos combinatórios J1 ,. . . , Jn , podemos definir o jogo soma dos jogos
J1 ,. . . , Jn da seguinte forma. Os dois jogadores jogam alternadamente escolhendo um jogo Ji ,
i 2 {1, 2, . . . , n} e realizando um movimento possı́vel determinado por este jogo. O jogo termina
quando não houver mais movimentos possı́veis em nenhum dos n jogos e o vencedor é aquele que
realizou o último movimento.
20
Observe que o jogo Nim pode ser então definido como uma soma de n jogos Nim, cada um
jogado sobre uma única pilha, sendo n o número de pilhas do jogo.
O próximo resultado nos fornece um método eficiente de se obter a função de Sprague-Grundy
da soma de n jogos combinatórios.
Proposição 3.2 ([2, 3, 6]) Sejam J1 , . . . , Jn jogos combinatórios. Se p = (p1 , . . . , pn ) é uma
posição de jogo para a soma dos jogos J1 , . . . , Jn , sendo pi uma posição de jogo para Ji , então a
função de Sprague-Grundy em p é dada pela soma-nim
g(p) = g(p1 )
g(p2 )
···
g(pn ).
No caso do jogo Nim sobre n pilhas, isso é o mesmo que dizer que, se p = (p1 , . . . , pn ) é uma
posição de jogo, então
···
g(p) = p1
pn ,
o que já foi observado anteriormente.
3.3
Jogo Kayles
O jogo Kayles é um jogo de boliche que começa com n pinos dispostos em uma fileira de pinos
adjacentes e cada jogador, jogando alternadamente, pode, em cada jogada, acertar um único pino
ou dois pinos adjacentes, possivelmente quebrando uma fileira em duas, ou diminuindo uma fileira.
Após cada jogada, restará um certo número de fileiras de pinos adjacentes. Após a primeira
jogada, obtemos ou uma fileira com n
1 ou n
2 pinos, ou duas fileiras com tamanhos n1 e n2 ,
sendo que fileiras com 0 pinos são ignoradas.
Analisemos por exemplo uma situação dentro do jogo Kayles na qual estamos com fileiras de
tamanhos 1, 7 e 3. Denotando por Kj uma pilha com j pinos, caso o movimento acerte a fila com
7 pinos, podemos obter as seguintes configurações:
K 6 ; K5 + K 1 ; K4 + K 2 ; K3 + K 3 ; K5 ; K4 + K1 ; K2 + K3 .
Em outras palavras, após o movimento, pode restar uma fileira apenas com 5 ou 6 pinos, ou
duas fileiras com 5 e 1 pinos, respectivamente, 4 e 2, 3 e 3, 4 e 1 ou 2 e 3. O jogador que não puder
mais derrubar pinos perde o jogo, ou seja, vence o jogo quem derrubar o último pino.
21
Observação 3.2 O jogo Kayles não é um jogo de subtração, com S = {1, 2}. Ele seria um jogo
deste tipo se fosse também permitido aos jogadores derrubar dois pinos quaisquer, mesmo que não
fossem adjacentes.
O Jogo Kayles pode ser reformulado como um jogo combinatório jogado sobre grafos. Nesta
formulação, um grafo qualquer é dado e os dois jogadores jogam alternadamente, escolhendo um
vértice do grafo, sendo que os jogadores não podem escolher um vértice que já tenha sido escolhido
antes nem um vértice adjacente a um vértice escolhido antes. O último jogador a escolher um
vértice vence o jogo. Em outras palavras, o jogo pode ser descrito também como segue: dado um
grafo qualquer, os dois jogadores jogam alternadamente, escolhendo um vértice do grafo. O vértice
escolhido e seus vizinhos são retirados do grafo. O vencedor é aquele jogador cuja jogada resulta
no grafo vazio.
Para o jogo Kayles, podemos determinar uma estratégia vencedora para o primeiro jogador,
qualquer que seja o número de pinos considerado, conforme mostraremos no próximo resultado.
Teorema 3.3 ([2, 3, 6]) No jogo Kayles com n pinos, existe uma estratégia vencedora para o
primeiro jogador.
Demonstração: Chamemos os jogadores de jogador I e jogador II, e mostremos uma estratégia
de vitória para o jogador I.
Suponha que n é ı́mpar, digamos, n = 2k + 1. Neste caso, o jogador I inicia o jogo por derrubar
o pino do meio da fileira, ou seja, de modo a deixar duas fileiras com exatamente k pinos em cada
uma. Pela Proposição 3.2, temos que a função de Sprague-Grundy aplicada nesta posição é dada
por
g(k)
g(k) = 0,
ou seja, esta é uma P -posição. Em outras palavras, existe uma estratégia vencedora para o jogador
I a partir desta posição.
No caso em que n é par, o mesmo raciocı́nio se aplica, bastando ao jogador I derrubar dois pinos
na primeira jogada, em vez de apenas um, deixando também duas fileiras com a mesma quantidade
de pinos. A demonstração do teorema está completa.
⇤
Tendo em vista o Teorema 3.2, concluimos que a única posição com nimber igual a zero para o
Jogo Kayles é a posição terminal, que corresponde à posição com 0 pinos. Mais especificamente, a
tabela 3.3 abaixo nos dá os valores dos nimbers para o jogo Kayles.
22
Temos que a função de Sprague-Grundy para o Jogo Kayles satisfaz
g(n) = g[n
mod 12],
para todos os valores de n com exceção dos seguintes:
g(0) = 0 g(3) = 3 g(6) = 3 g(9) = 4 g(11) = 6 g(15) = 7 g(18) = 3
g(21) = 4 g(22) = 6 g(28) = 5 g(34) = 6 g(39) = 3 g(57) = 4 g(70) = 6
Para os demais valores de n, vale:
g(00
g(01
g(02
g(03
mod
mod
mod
mod
12) = 4
12) = 1
12) = 2
12) = 8
g(04
g(05
g(06
g(07
mod
mod
mod
mod
12) = 1
12) = 4
12) = 7
12) = 2
g(08
g(09
g(10
g(11
mod
mod
mod
mod
12) = 1
12) = 8
12) = 2
12) = 7
Tabela 3.1: Valores de Nim para o jogo Kayles.
3.4
Jogo Dawson’s Kayles
O jogo Dawson’s Kayles é um primo do jogo Kayles. Em termos de boliche o jogo se dá da
seguinte forma: uma fileira de n pinos é dada e o único movimento permitido é derrubar dois pinos
adjacentes.
Diferentemente do jogo Kayles apresentado anteriormente, neste jogo não é permitido derrubar
um único pino e assim são eliminadas quaisquer fileiras compostas por apenas um pino. Desta
forma, a cada jogada, restarão uma ou duas fileiras menores que a anterior, sendo que o jogador
que fizer o último movimento vence o jogo.
A Observação 3.2 também se aplica aqui, ou seja, o fato de que os jogadores têm permissão
apenas para derrubar dois pinos que sejam adjacentes faz com que este jogo seja diferente do jogo
de subtração com S = {2}.
Assim como no caso do jogo Kayles, o jogo Dawson’s Kayles tem a sua formulação sobre
grafos: dado um grafo qualquer, os dois jogadores jogam alternadamente, escolhendo dois vértices
adjacentes do grafo sendo que os jogadores não podem escolher um vértice que já tenha sido
23
escolhido antes, e não podem também escolher um vértice que seja adjacente a um vértice que
tenha sido escolhido anteriormente. O último jogador a escolher um par de vértices vence o jogo.
O problema associado ao jogo Dawson’s Kayles é o seguinte: dado um grafo G, é possı́vel
determinar uma estratégia vencedora para o primeiro jogador quando o Dawson’s Kayles é jogado
sobre G?
Apresentaremos na seção 4.2 uma prova da log-completude em PSPACE (ver definição na
seção 4.1) desse problema.
Temos aqui o seguinte resultado.
Teorema 3.4 ([2, 3, 6]) No jogo Dawson’s Kayles com n pinos, com n par, existe uma estratégia
vencedora para o primeiro jogador.
Demonstração: Chamemos os jogadores de jogador I e jogador II, e mostremos uma estratégia
de vitória para o jogador I.
O jogador I inicia o jogo por derrubar os dois pinos do meio da fileira, ou seja, de modo a deixar
n 2
duas fileiras com exatamente
pinos em cada uma. Pela Proposição 3.2, temos que a função
2
de Sprague-Grundy aplicada nesta posição é dada por
g(
n
2
2
)
g(
n
2
2
) = 0,
ou seja, esta é uma P -posição. Em outras palavras, existe uma estratégia vencedora para o
⇤
jogador I a partir desta posição.
Fica clara aqui a necessidade de n ser par para que o método acima possa ser utilizado, pois
diferentemente do Jogo Kayles, aqui o jogador não tem a opção de derrubar apenas um pino. Como
consequência, temos que todas as posições correspondentes a pilhas com um número par de pinos
(com exceção da posição terminal) são N -posições.
Mais geralmente, segue abaixo uma tabela com os valores de Nim para o jogo Dawson’s Kayles.
Temos que a função de Sprague-Grundy, neste caso, satisfaz g(n) = g [n mod 34], sendo que
esta expressão vale para todos os valores de n, com exceção dos seguintes:
g(0) = 0 g(1) = 0 g(15) = 0 g(17) = 2 g(18) = 2 g(32) = 2 g(35) = 0 g(52) = 2
Nos demais casos, vale:
24
g(00
g(01
g(02
g(03
g(04
g(05
g(06
g(07
g(08
g(09
g(10
g(11
g(12
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
34) = 4
34) = 8
34) = 1
34) = 1
34) = 2
34) = 0
34) = 3
34) = 1
34) = 1
34) = 0
34) = 3
34) = 3
34) = 2
g(13
g(14
g(15
g(16
g(17
g(18
g(19
g(20
g(21
g(22
g(23
g(24
g(25
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
34) = 2
34) = 4
34) = 4
34) = 5
34) = 5
34) = 9
34) = 3
34) = 3
34) = 0
34) = 1
34) = 1
34) = 3
34) = 0
g(26
g(27
g(28
g(29
g(30
g(31
g(32
g(33
mod
mod
mod
mod
mod
mod
mod
mod
34) = 2
34) = 1
34) = 1
34) = 0
34) = 4
34) = 5
34) = 3
34) = 7
Tabela 3.2: Valores de Nim para o jogo Dawson’s Kayles
25
Capı́tulo 4
Complexidade
4.1
Completude em PSPACE
Nesta seção, introduziremos uma noção de complexidade, a qual utilizaremos para mostrar a NPdificuldade do jogo em grafos associado ao jogo Dawson’s Kayles, introduzido na seção 3.4.
Para tanto, apresentamos a seguir a definição da máquina de Turing.
Definição 4.1 Uma máquina de Turing é uma 7-upla M = (Q, ⌃, , s, b, F, ), onde:
• Q é um conjunto finito de estados;
• ⌃ é um alfabeto finito de sı́mbolos;
•
é o alfabeto finito da fita;
• s 2 Q é o estado inicial;
• b2
é o sı́mbolo branco, isto é, o único sı́mbolo que se permite ocorrer na fita infinitamente
em qualquer passo durante a computação;
• F ⇢ Q é o conjunto de estados finais;
•
: Q⇥
a direita e
! Q ⇥ ⇥ { , !} é a chamada função de transição, onde ! é o movimento para
é o movimento para a esquerda.
Em outras palavras, uma máquina de Turing consiste em:
26
• Uma fita dividida em células, sendo que cada célula contém um sı́mbolo de algum alfabeto
finito. O alfabeto contém um sı́mbolo especial chamado de branco e assumimos que as células
que ainda não foram escritas estão preenchidas com o sı́mbolo branco;
• Um cabeçote que pode ler ou escrever sı́mbolos na fita e mover-se para a esquerda e para a
direita;
• Um registrador de estados, que armazena o estado da máquina de Turing. O registrador de
estados é inicializado com um estado especial chamado estado inicial;
• Uma função de transição, que diz à máquina que sı́mbolo escrever, como mover o cabeçote e
qual será o seu novo estado.
Definição 4.2 Dado um alfabeto finito de sı́mbolos qualquer , denotaremos por
⇤
o conjunto de
todas as palavras finitas possı́veis de serem formadas com os caracteres em .
Definição 4.3 Sejam , ⌃ dois alfabetos finitos de sı́mbolos. Dizemos que uma função f :
⇤
!
⌃⇤ é calculável no espaço S(n) se existe uma máquina de Turing tendo uma fita de entrada
somente-leitura de duas vias, uma fita de saı́da somente-escrita de uma via e uma única fita de
trabalho, a qual, para qualquer entrada w 2
⇤,
fornece a saı́da f (w), tendo percorrido no máximo
S(|w|) espaços distintos da fita de trabalho, em que |w| é o número de caracteres da palavra w.
Estamos em condições de dar as próximas definições.
Definição 4.4 Uma função f :
⇤
! ⌃⇤ é calculável em espaço log se for calculável no espaço
c log(n), para alguma constante c > 0. Dizemos que f é calculável em espaço polinomial se
for calculável no espaço cnk , para constantes c, k > 0.
Definição 4.5 Seja
L⇢
⇤
um alfabeto finito de sı́mbolos. Dizemos que um problema de decisão
está na classe PSPACE se a função f :
⇤
! {0, 1} dada por
f (w) = 1 , w 2 L
é calculável em espaço polinomial. Analogamente, dizemos que L é um problema na classe
LOGSP ACE se f for calculável em espaço log.
27
É possı́vel mostrar que P ✓ PSPACE e, assim como no caso dos problemas na classe NP, não
se conhece ainda uma prova de que a classe PSPACE é, de fato, maior que a classe P. Mais que
isso, temos que a classe PSPACE inclue também a classe NP [11].
Definição 4.6 Sejam
e ⌃ dois alfabetos de sı́mbolos e sejam L1 2
⇤
e L2 2 ⌃⇤ dois problemas
quaisquer. Dizemos que L1 pode ser reduzido em espaço log a L2 se existe uma função
⇤
f:
! ⌃⇤ calculável em espaço log tal que, para todo w 2
⇤,
w 2 L1 , f (w) 2 L2 .
Dizemos então que um problema de decisão L é log-completo em PSPACE se L 2 PSPACE
e, para todo problema L0 2 PSPACE, L0 pode ser reduzido em espaço log a L.
Quando L1 pode ser reduzido em espaço log a L2 , usamos a notação L1 lg L2 .
É fácil ver também que, assim como no caso dos problemas NP-completos, vale o seguinte
resultado.
Lema 4.1 Se L0 é um problema log-completo em PSPACE e L 2 PSPACE é um problema tal que
L0 pode ser reduzido em espaço log a L (L0 lg L), então L é log-completo em PSPACE.
Na próxima seção, veremos que o jogo em grafos associado ao jogo Dawson’s Kayles é um
problema log-completo em PSPACE, o que implicará no fato de que tal jogo é um problema NPdifı́cil, conforme diz o próximo resultado.
Proposição 4.1 ([11]) Todo problema log-completo em PSPACE é também NP-difı́cil.
4.2
Complexidade do jogo em grafos associado ao jogo Dawson’s
Kayles
Vamos nesta seção estudar a complexidade em termos de log-completude em PSPACE do jogo
em grafos associado ao jogo Dawson’s Kayles. Para tanto, algumas notações e definições serão
necessárias, as quais apresentaremos a partir de agora. Iniciamos por apresentar a ideia de jogos
em formas proposicionais.
Definição 4.7 Uma forma normal conjuntiva (F N C) é uma conjunção de cláusulas, cada
cláusula ou sentença sendo composta de uma disjunção de variáveis, onde assumimos que cada
28
variável e sua negação não podem aparecer em uma mesma cláusula. Chamamos de 3F N C o
conjunto de todas as fórmulas em F N C com no máximo três variáveis em cada conjunto.
Definimos então o jogo G! (F N C) da seguinte forma: a entrada é um par da forma (A, x),
sendo A uma fórmula em F N C e x = (x1 , . . . , xn ) uma lista de variáveis distintas, incluindo todas
aquelas que aparecem em A. Um movimento em i consiste em atribuir a xi um valor 0 (falso) ou
1 (verdadeiro). Depois de n movimentos, o primeiro jogador vence se a atribuição produzida dessa
forma faz com que A seja verdadeira, e perde caso contrário.
Definição 4.8 Seja J um jogo combinatório qualquer. Denotaremos por Inp(J) o conjunto das
entradas do jogo J. Denotemos ainda por
L(J) := {A 2 Inp(J) : o primeiro jogador tem uma estratégia vencedora para entrada A}.
Ademais,
L̄(J) := Inp(J)
L(J).
Usaremos aqui a notação L(G! (3F N C)) = L! (3F N C). Enunciaremos, sem demonstração, os
próximos resultados (ver [11]), os quais serão utilizados para mostrar a log-completude em PSPACE
do jogo em grafos associado ao jogo Dawson’s Kayles.
Lema 4.2 ([11]) L! (3F N C) é log-completo em PSPACE.
Lema 4.3 ([11]) Sendo J o jogo em grafos associado ao jogo Dawson’s Kayles, temos que L(J) 2
PSPACE.
O principal resultado deste capı́tulo é dado então pelo seguinte teorema.
Teorema 4.1 ([11]) Se J é o jogo em grafos associado ao jogo Dawson’s Kayles, então L(J) é
log-completo em PSPACE.
A prova deste teorema é bastante técnica. Vamos aqui dar a ideia da prova encontrada em [11].
Segue dos Lemas 4.1, 4.2 e 4.3 que é suficiente mostrar que L! (F N C) lg L(J).
De modo a usar o jogo em grafos associado ao jogo Dawson’s Kayles para simular G! (F N C), é
necessária uma forma de restringir os movimentos. Isso é feito por associar, a cada entrada no jogo
29
G! (F N C), um grafo no qual em cada ponto, todos os movimentos possı́veis, exceto uma pequena
quantidade deles, leva à derrota imediata para o jogador que os realiza. Esses poucos movimentos
que não são fatais são chamados movimentos legı́timos. O grafo é construı́do então de modo a
forçar os jogadores a jogar legitimamente.
Mais especificamente, dizemos que o jogo Dawson’s Kayles no grafo G é jogado legitimamente
se para i = 1, 2, . . . , n (onde n é o número de variáveis da entrada do jogo G! (F N C)) o nó jogado
no movimento i é xn
i+1
ou x̄n
i+1 .
Movimentos de um jogo jogado legitimamente imitam os
movimentos no jogo G! (F N C) a partir da entrada A: no primeiro movimento, o primeiro jogador
joga xn ou x̄n . Logo depois, o segundo jogador joga xn
1
ou x̄n
1,
e assim por diante. O grafo
G é construı́do de forma a forçar os jogadores a jogar legitimamente: se em qualquer movimento
(supondo que todos os movimentos anteriores foram legı́timos) o jogador não jogar legitimamente,
ele é sujeito a derrota imediata.
Se A 2 Inp(G! (F N C)) e G é o grafo associado a A, a prova se completa por mostrar que o
primeiro jogador tem uma estratégia vencedora para o jogo G! (F N C) a partir da entrada A se,
e somente se existe uma estratégia vencedora para o primeiro jogador no jogo Dawson’s Kayles
jogado sobre o grafo G.
Segue então da Proposição 4.1 a seguinte conclusão.
Corolário 4.1 ([11]) O problema de decidir o vencedor do jogo em grafos associado ao jogo Dawson’s Kayles é um problema NP-difı́cil.
30
Capı́tulo 5
Jogos em Triangulações Planares
5.1
Introdução
Neste capı́tulo, apresentaremos os jogos em triangulaçẽs planares, o principal tipo de jogo neste
trabalho. Os jogos em triangulações planares pertencem à área mais geral de jogos combinatórios,
definida no Capı́tulo 2, cujos jogos, conforme vimos, envolvem dois jogadores. Nos jogos em triangulações planares, normalmente denotamos estes dois jogadores por R e B.
Observe que qualquer jogo combinatório ótimo sem empates tem dois possı́veis resultados: o
primeiro jogador vence o jogo ou então o segundo jogador vence. Em outras palavras, o primeiro
jogador pode forçar a sua vitória, ou então o segundo pode forçar a sua vitória, não importando como
o outro jogador se move ao longo do jogo, procedimentos estes que foram chamamos no Capı́tulo 2
de estratégias vencedoras. Observamos que os jogos combinatórios podem ter um terceiro resultado:
um dos jogadores pode forçar o empate.
Este capı́tulo foi em grande parte baseado no trabalho intitulado Games on triangulations,
de Aichholzer et al. [1]. Neste trabalho, os autores analisaram vários jogos combinatórios em
triangulações planares.
Daremos a seguir a definição de triangulação, que nos permitirá dar o conceito de jogos em
triangulações planares.
Definição 5.1 Um complexo simplicial C é uma colecção finita de simplexos tais que cada face
de um simplexo de C é um simplexo de C e a intersecção de dois simplexos de C é vazia ou uma
face de ambos. Dado um complexo simplicial C, C é uma decomposição simplicial para um
S
conjunto B se B = 2C .
31
Definição 5.2 Uma triangulação em um conjunto finito de pontos S no plano, tal que quaisquer
três pontos de S são sempre não colineares, é uma decomposição simplicial de envoltória convexa
de S onde os vértices dos simplexos são os pontos de S.
Em [1], os autores consideraram vários tipos de jogos combinatórios envolvendo vértices, arestas, e faces (triângulos) de uma triangulação. Eles apresentaram os jogos em que dois jogadores
R e B jogam alternadamente, assim como jogos solitários para somente um jogador. Em versões
bicromáticas dos jogos para dois jogadores, o jogador R usa a cor vermelha e o jogador B usa a cor
azul, para colorir alguma aresta da triangulação. Em variações monocromáticas desses jogos, todos
os jogadores (ou um único jogador) usam uma mesma cor.
Os jogos combinatórios de triangulações planares apresentados por Aichholzer et al. [1] são
classificados em três grandes categorias, a saber: Jogos de Construção (Constructing Games), Jogos
de Transformação (Transforming Games) e Jogos de Marcação (Marking Games). Apresentaremos
abaixo uma breve descrição de cada um desses jogos e, nas seções 5.1 e 5.2, trataremos mais
detalhadamente os jogos de Construção e de Marcação, respectivamente.
• Jogos de Construção. Os jogadores constroem uma triangulação T (S) sobre um dado conjunto de pontos S. Iniciando sem arestas, os jogadores R e B jogam, por sua vez, desenhando
uma ou mais arestas em cada jogada. Em algumas variações, o jogo termina assim que uma
estrutura é alcançada. Em outros casos, o jogo termina quando a triangulação se completa
e o último movimento ou, eventualmente, alguma forma de pontuação decide quem ganha o
jogo.
• Jogos de Transformação. Uma triangulação T (S) em S é dada inicialmente, com todas
as arestas coloridas inicialmente na cor preta. Em cada turno, um jogador aplica alguma
transformação local na triangulação atual resultando em uma nova triangulação com algumas
arestas possivelmente recoloridas. O jogo termina quando uma configuração especı́fica é
alcançada ou quando não existem mais movimentos possı́veis.
• Jogos de Marcação. Uma triangulação T (S) em S é dada, com todas as arestas e vértices
coloridos inicialmente na cor preta. Em cada turno, alguns dos seus elementos são marcados
(coloridos, por exemplo), de um modo de jogo especı́fico. O jogo termina quando alguma configuração de elementos marcados é atingida (possivelmente a triangulação inteira) ou quando
32
não existem mais movimentos possı́veis.
O objetivo em cada jogo é determinar quem ganha o jogo e elaborar algoritmos eficientes para
determinar o vencedor e calcular uma estratégia vencedora, ou então mostrar que acontecerá um
empate. Os resultados obtidos por Aichholzer et al. [1], em contraste com muitos dos trabalhos em
teoria de jogos combinatórios, nos quais os jogos acabam por ser computacionalmente desafiadores,
no sentido de NP-dificuldade, conceito definido no capı́tulo 3, são todos positivos. Ou seja, apesar da natureza desafiadora desses jogos em relação à complexidade (conforme veremos adiante),
Aichholzer et al. [1] conseguiram algoritmos de tempo polinomial para resolver muitas classes particulares de jogos em triangulações planares. Uma dessas classes particulares é, por exemplo, o
caso em que os pontos de S estão em posição convexa, ou seja, os pontos de S são os vértices de
um polı́gono convexo.
Como um exemplo, um dos resultados positivos obtidos por Aichholzer et al. [1] é que para o
Jogo da Triangulação Monocromática Completa (Monochromatic Complete Triangulation Game)
(ver definição na seção 5.2.2), existe uma estratégia simples quando os pontos de S estão em
posição convexa. Neste caso, dependendo da paridade de |S|, o primeiro jogador pode sempre
ganhar (quando |S| é ı́mpar) ou qualquer jogador pode forçar um empate (quando |S| é par) (ver
Teorema 5.3).
5.2
Jogos de Construção
Vamos, nesta seção, apresentar três tipos de jogos de construção.
5.2.1
Jogo do Triângulo Monocromático
O primeiro tipo de jogo de construção que vamos analisar é o Jogo do Triângulo Monocromático.
Neste jogo, dois jogadores desenham arestas em turnos, e o primeiro jogador a completar um
triângulo vazio vence o jogo. Supondo que S está em posição convexa, vamos apresentar aqui uma
estratégia de vitória para este jogo, a qual foi provada em [1].
Uma observação valiosa para este jogo é o fato de que uma aresta só deve ser desenhada se a
mesma conecta dois vértices que não tenham sido usados anteriormente. Caso contrário, vamos
obter um vértice v de grau no mı́nimo 2, ou seja, com pelo menos duas arestas desenhadas a partir
de v, o que vai permitir ao jogador adversário realizar um movimento vencedor: basta fechar o
33
triângulo formado pelas duas arestas adjacentes de v.
Portanto, ao desenhar uma diagonal xy em S, os dois vértices x e y são desconsiderados no
decorrer do jogo. Note ainda que a aresta xy divide o conjunto S em dois subconjuntos, cujas
cardinalidades n1 e n2 satisfazem n1 + n2 = n
2. O jogador que desenhar a última aresta de
acordo com a estratégia acima é o vencedor.
Observe que, neste jogo, nenhuma aresta pode ser desenhada em conjuntos de cardinalidade de
no máximo 1, pois neste caso, ou não há movimentos possı́veis, ou o movimento dá ao oponente
um movimento vencedor. Este último argumento mostra que o jogo do triângulo monocromático
possui a mesma estrutura do jogo em grafos associado ao Dawson’s Kayles de n pinos, apresentado
na Seção 3.4.
Em termos de complexidade, o Corolário 4.1 implica então no seguinte resultado.
Teorema 5.1 O problema de decidir o vencedor no Jogo do Triângulo Monocromático é um problema NP-difı́cil.
A despeito dessa natureza desafiadora dada pelo teorema acima, no artigo de Aichholzer et.
al. ([1]), encontramos o seguinte resultado acerca do Jogo do triângulo monocromático:
Teorema 5.2 ([1]) O jogo do triângulo monocromático sobre n pontos em posição convexa é um
jogo onde o segundo jogador vence quando n ⌘ 5, 9, 21, 25 e 29( mod 34) e para casos especiais
n = 15 e n = 35; caso contrário, o tipo em que o primeiro jogador vence. Cada movimento em
uma estratégia vencedora pode ser computado em tempo linear no tamanho da triangulação.
Sabemos do Teorema 3.2 que uma posição de jogo é uma P -posição se, e somente se, o nimber
dessa posição é igual a zero. Sendo assim, de acordo com a tabela 2.2, os valores de n para os
quais existe uma estratégia vencedora para o segundo jogador são n ⌘ 5, 9, 21, 25 e 29 ( mod 34)
e os casos excepcionais n = 15 e n = 35. Nos demais casos, existe uma estratégia vencedora para
o primeiro jogador.
No caso em que n é par, para provar este fato é suficiente seguir a estratégia apresentada na
prova do Teorema 3.4.
34
5.2.2
Jogo da Triangulação Monocromática Completa
O segundo jogo de construção que apresentamos a seguir, é semelhante ao jogo do triângulo monocromático, discutido na seção anterior.
O Jogo da Triangulação Monocromática Completa é jogado seguindo as mesmas regras do
jogo do triângulo monocromático, exceto que, quando um jogador completa um ou mais triângulos
monocromáticos vazios, ele deve jogar novamente, e o jogo continua até que uma triangulação inteira
tenha sido desenhada. O vencedor é o jogador que completou mais triângulos monocromáticos
vazios.
Conforme observado anteriormente, para este jogo é possı́vel dar informações precisas a respeito
de qual jogador pode vencer o jogo ou quando um empate pode ser forçado. De fato, o fator
determinante neste problema é a paridade do conjunto S, como veremos a seguir.
Para analisar este problema, necessitamos estabelecer algumas notações e definições.
Definição 5.3 Duas arestas compartilhando um vértice p são chamadas um triângulo aberto se
pudermos construir um triângulo válido, ou seja, sem intersecções com outras arestas, por conectar
os dois pontos finais (distintos de p) dessas arestas, criando assim uma terceira aresta que fecha o
triângulo. Essa terceira aresta será chamada aresta de fechamento.
Observe que, à medida que vamos construindo a triangulação, esta consistirá de várias componentes conexas. Entretanto, se uma aresta é de fechamento, então ela será desenhada entre vértices
de uma mesma componente conexa.
Definição 5.4 Quando desenharmos uma aresta conectando duas componentes conexas distintas,
chamaremos tal aresta de conectante.
Definição 5.5 Definimos o peso de uma aresta conectante como sendo o número de pontos
finais que possuem anteriormente uma outra aresta incidente à aresta conectante.
Observe que, uma vez que os pontos estão em posição convexa, o peso de uma aresta conectante
é 0, 1 ou 2, sendo que as arestas conectantes de peso 0 são aquelas que conectam pontos isolados,
as arestas de peso 1 são aquelas que produzem um novo triângulo aberto, e as arestas de peso 2
são aquelas que darão origem a dois triângulos abertos. Observe ainda que, em um jogo sobre n
pontos, o número total de arestas conectantes será n
35
1.
Definição 5.6 Um outro tipo de aresta que podemos destacar são as chamadas arestas redundantes, que consistem nas arestas que conectam dois pontos em uma mesma componente conexa
mas sem ser uma aresta de fechamento, ou seja, sem fechar um triângulo.
É claro que, em uma estratégia de vitória, nenhuma aresta redundante é desenhada, isto é, sempre
que há a possibilidade de se fechar um triângulo, deve-se fazê-lo imediatamente.
A estratégia gulosa para se buscar a vitória é então a seguinte: enquanto existe alguma aresta de
fechamento, desenhe-a. Lembremos que depois que um triângulo é fechado, o jogador que realizou
este movimento tem direito a jogar novamente. O movimento deve consistir então em desenhar
uma aresta conectante com o menor peso possı́vel.
Denotemos por ei o número de arestas conectantes de peso i, i = 0, 1, 2, desenhados ao longo
do jogo. Observe que a primeira vez que um ponto de S é utilizado, a aresta então desenhada é
uma aresta conectante de peso 0 ou 1. Além disso, uma aresta conectante de peso 0 é desenhada
ligando dois pontos que não foram anteriormente utilizados, enquanto que uma aresta conectante
de peso 1 utiliza um ponto não utilizado anteriormente. Isso nos leva à seguinte igualdade:
2e0 + e1 = n.
Ainda, uma vez que e0 + e1 + e2 = n
que e0 + (n
2e0 ) + e2 = n
1 (pois arestas conectantes formam uma árvore), segue
1, ou seja,
e2 = e0
1.
Estamos então em condições de mostrar os próximos resultados.
Lema 5.1 ([1]) Para n ı́mpar, existe uma estratégia vencedora para o jogador R (o primeiro jogador).
Demonstração: Sabemos que e0 + e1 + e2 = n
1, que é par. Assim, haverá
(n
1)
rodadas nas
2
quais ambos os jogadores desenharão arestas conectantes. Em cada rodada, o jogador R escolhe
primeiro uma aresta, e escolhe de acordo com a estratégia gulosa acima descrita. Assim, em cada
rodada o jogador R vence ou empata com o jogador B.
Para ocorrer um empate no jogo, o jogador B deve empatar com R em todas as rodadas, mas
para isso precisamos que e0 , e1 , e2 sejam todos números pares, o que não é possı́vel pois e2 = e0
⇤
36
1.
Lema 5.2 ([1]) Para n par, o jogador B pode forçar um empate.
Demonstração: Temos que e0 +e1 +e2 = n 1, que é ı́mpar neste caso. O primeiro movimento do
jogador R consiste em desenhar uma aresta de peso 0. Depois deste primeiro movimento, restarão
(n 2)
n 2 arestas conectantes, e os jogadores B e R escolherão essas arestas em
rodadas. Em
2
cada rodada o jogador B escolhe primeiro segundo a estratégia gulosa anteriormente descrita, e
dessa forma em cada rodada o jogador B ou ganha ou empata com o jogador R. Assim, B ou ganha
⇤
ou empata o jogo, jogando dessa forma.
Lema 5.3 ([1]) Para n par, o jogador R pode forçar um empate.
Demonstração: A prova neste caso difere das anteriores. Aqui não utilizaremos a mesma estratégia gulosa utilizada antes, pois se e0 terminou par, então o jogador B ganharia por dois
triângulos por jogar segundo a nossa estratégia gulosa anterior, uma vez que, neste caso, apenas
e2 é ı́mpar. Ao invés disso, o jogador R aplica uma estratégia de simetria para garantir que e0
termine ı́mpar, de modo que ambos e1 e e2 sejam pares, levando a um empate.
Assumimos que o jogador B jogue de maneira ótima, ou seja, faça o melhor para obter a vitória,
o que claramente inclui fechar os triângulos abertos sempre que houver essa possibilidade. O jogador
R inicia desenhando uma diagonal dividindo S em dois conjuntos iguais (lembramos que n é par).
Então enquanto o jogador B não deixar desnecessariamente triângulos abertos, o jogador R pode
jogar simetricamente: fechar triângulos abertos e imitar o que o jogador B faz na parte oposta da
diagonal S. Desta forma, garante-se que e0 é ı́mpar, uma vez que as arestas conectantes de peso
0 serão a primeira diagonal desenhada, mais duas vezes o número de arestas conectantes que B
desenhou, o que garante o empate para o jogador R.
⇤
Resumimos esses resultados no próximo teorema.
Teorema 5.3 ([1]) O Jogo da Triangulação Monocromática Completa jogado sobre n pontos em
posição convexa é um jogo no qual o primeiro jogador vence se n é ı́mpar e ambos os jogadores
podem forçar um empate se n é par.
Observe que, uma vez que existe a possibilidade de empate neste jogo, o mesmo não é um tipo
de jogo no qual a teoria de Sprague-Grundy pode ser aplicada.
37
5.2.3
Jogo do Triângulo Bicromático
Um outro jogo de construção é o Jogo do Triângulo Bicromático (Bichromatic Triangle Game).
Ele é definido da seguinte forma: dado um conjunto S de pontos no plano, os jogadores constroem
uma triangulação T (S). Começando com o conjunto vazio de arestas, os jogadores R e B jogam
alternadamente, desenhando uma aresta em cada jogada. O jogador R usa a cor vermelha e o
jogador B usa a cor azul. O primeiro jogador que completa um triângulo vazio monocromático é o
vencedor.
Este é um jogo mencionado por Aichholzer et al. [1] em seu artigo, porém decidir qual é o
resultado do jogo é um problema deixado em aberto, assim como alguns outros problemas de jogos
em triangulações planares.
Sobre o Jogo do Triângulo Bicromático, quando se trata do caso em que o conjunto de pontos
dado está em posição convexa, Manic, Martin e Stojakovic [10] demonstraram que o jogador B
pode forçar um empate. Vamos apresentar aqui a demonstração deste resultado.
Iniciamos por estabelecer algumas notações.
Definição 5.7 Denotamos por (V, ER , EB ) uma configuração do jogo do Triângulo Bicromático,
sendo V um conjunto de pontos no plano e ER , EB são os conjuntos de arestas desenhadas pelos
jogadores R e B, respectivamente, de modo que tais arestas não se cruzem.
Definição 5.8 Uma aresta livre com respeito a (V, ER , EB ) é uma aresta que não está em ER [EB
e que não cruza nenhuma aresta de ER [ EB . Definimos ainda a configuração induzida de uma
0 , E 0 ),
configuração C = (V, ER , EB ) sobre um conjunto W ✓ V como sendo a tripla C [W ] = (W, ER
B
0 , E 0 as arestas desenhadas pelos jogadores R e B, respectivamente, que unem apenas
sendo ER
B
pontos em W . Duas configurações são ditas independentes se elas compartilham apenas uma
aresta que já tenha sido desenhada por um dos dois jogadores em ambas as configurações.
Definição 5.9 Suponha que V = {v1 , . . . , vn } está em posição convexa e que esses pontos estão
y
em sentido horário. Se x = vi e y = vj , com 1  i, j  n, denotamos por xy o conjunto dos pontos
{vi , vi+1 , . . . , vj }, sendo que os ı́ndices são considerados módulo n. Finalmente, para x, y 2 V , se
x = vi e y = vi+1 , dizemos que x e y são consecutivos em V .
Estamos agora em condições de enunciar e provar o seguinte resultado.
38
Lema 5.4 ([10]) Seja C = (V, ER , EB ) uma configuração do Jogo do Triângulo Bicromático onde
V é um conjunto de pontos em posição convexa no plano e todas as arestas desenhadas, isto é,
arestas em ER [ EB , estão entre os pontos consecutivos em V . Se |ER | < 2, então B pode forçar
um empate em C .
Demonstração Essa demonstração é feita por indução em |V |.
Para |V |  3, o lema é trivialmente válido.
Suponha então que |V | = n > 3 e suponha que a afirmação é verdadeira para |V | < n. A
cardinalidade de ER será denotada aqui por r.
Seja uv a aresta que o jogador R desenha e seja C 0 a configuração resultante, ou seja, C 0 =
(V, ER [ {uv}, EB ).
y
O movimento realizado divide C em duas configurações independentes C1 e C2 , onde C1 = C 0 [uv]
y
e C2 = C 0 [vu] sendo uv pertencente às duas configurações e quando u e v são consecutivos em V ,
C1 consiste em uma única aresta. Para que o jogador B consiga forçar um empate ele precisa forçar
o empate tanto em C1 quanto em C2 . Veja a figura 5.1.
$2
1= u
6
$1
2
5
v
4
3
Figura 5.1: Jogador R joga uv. Este movimento divide C em duas configurações independentes C1
e C2 .
Se r = 1, podemos assumir, sem perda de generalidade, que C1 tem duas arestas vermelhas e
39
C2 tem uma aresta vermelha, lembrando que a aresta uv está tanto em C1 quanto em C2 . Quando
a configuração tem no máximo três pontos o empate pode ser facilmente forçado, assim vamos
assumir que C1 tem pelo menos quatro pontos. Então B pode agora escolher uma aresta livre xy
hyi
hyi
em C1 onde C1 xy e C1 yx contém cada uma, uma única aresta vermelha. É possı́vel garantir
a existência desta aresta pela propriedade de C1 , ou seja, ela tem pelo menos quatro pontos, os
vértices estão em posição convexa, e as arestas são desenhadas entre pontos consecutivos (observe
que duas arestas vermelhas podem ter um vértice comum). Veja a figura 5.2.
$1
1 =u
y= 2
6
5
4 =v =x
3
b
Figura 5.2: A configuração C1h tem
vermelhas. Jogador B pode agora escolher uma
i duash arestas
i
y
y
aresta livre xy em C1 onde C1 xy e C1 yx contém, cada um, uma única aresta vermelha.
Quando o jogador B desenha a aresta xy, obtemos uma configuração C10 que passa a ser dividida
hyi
hyi
em duas configurações independentes C10 xy e C10 yx . Pela hipótese de indução, o jogador B pode
forçar um empate em ambas as configurações e dessa forma ele pode forçar um empate em C1 .
Quanto a C2 , caso ela tenha uma única aresta fica trivial. Caso contrário, pela hipótese de
indução, B pode forçar um empate.
Se no entanto r = 0 e u e v não são consecutivos em V , temos que C1 e C2 possuem, cada, uma
aresta vermelha e, pela hipótese de indução, B pode forçar um empate em C1 e em C2 .
No caso em que r = 0 e u e v são consecutivos em V , é só colocar C = C 0 e aplicar o seguinte
40
argumento: se B é o próximo a jogar ele pode escolher desenhar qualquer aresta livre que não
conecte dois pontos consecutivos de V , dividindo C em duas configurações independentes C1 e C2 .
Pela hipótese de indução o jogador B pode forçar o empate em C1 e em C2 . Portanto, B pode forçar
um empate em C .
⇤
Podemos agora demonstrar o seguinte teorema.
Teorema 5.4 ([10]) O jogador B pode forçar um empate no Jogo do Triângulo Bicromático quando
os pontos em V estão em posição convexa.
Demonstração O jogador R inicia jogando e desenha uma aresta vermelha. Tal aresta divide
a configuração inicial C em duas configurações independentes (uma possivelmente trivial). Pelo
Lema 5.4, B pode forçar um empate em ambas as configurações, e portanto, B pode forçar um
empate em C .
⇤
Ainda para o jogo do Triângulo Bicromático, Manic, Martin e Stojakovic [10] demonstraram que
o jogador B pode forçar um empate quando o conjunto de pontos possui um único ponto interno.
Observamos também que, assim como no caso do jogo da triangulação monocromática completa, a
teoria de Sprague-Grundy não se aplica aqui.
5.3
Jogos de Marcação
Veremos, nesta seção, dois tipos de jogos de marcação.
5.3.1
Jogo Colorindo uma Triangulação Monocromático
No jogo Colorindo uma Triangulação Monocromático (Monochromatic Triangulation Coloring Game),
dois jogadores jogam em turnos colorindo em verde as arestas de uma triangulação T (S) dada, inicialmente coloridas em preto. O primeiro jogador que completar um triângulo vazio (sem pontos
internos) verde ganha. Obviamente, este jogo termina após um número
de movimentos linear no número de pontos e não há empate.
41
Suponha que os pontos em S estejam em posição convexa. Dada então uma triangulação T (S),
consideremos o dual de T (S), ou seja, o grafo GT que possui um vértice para cada triângulo de
T (S) e, se dois triângulos compartilham uma aresta, então os vértices correspondentes no dual são
conectados por uma aresta.
Observe agora que, se colorirmos uma aresta de um triângulo, esse triângulo deve ser descartado
ao longo de todo o jogo, pois o movimento de desenhar uma segunda aresta nesse triângulo levaria
obviamente à vitória imediata do oponente. Dessa forma, ao olhar para o grafo dual, vemos que
colorir uma aresta faz com que um vértice seja tirado do grafo dual, no caso que a aresta colorida
está na envoltória convexa de S, ou dois vértices no caso em que a aresta colorida é uma diagonal.
Vértices já marcados não podem ser marcados novamente e o jogador que marca o último vértice
vence o jogo.
A discussão acima nos permite ver que o jogo colorindo uma triangulação monocromático tem
exatamente a mesma estrutura do jogo Kayles (jogado sobre o grafo dual GT ).
Portanto, segue imediatamente do Teorema 3.3 o seguinte resultado.
Teorema 5.5 ([1]) Se S é um conjunto de pontos em um plano em posição convexa, então o jogo
colorindo uma triangulação monocromático jogado sobre uma triangulação de S é um jogo no qual
o primeiro jogador possui uma estratégia vencedora, qualquer que seja a quantidade de pontos em
S.
5.3.2
Jogo Bicolorindo uma Triangulação
No jogo Bicolorindo uma Triangulação (Bichromatic Triangulation Coloring Game), dois jogadores
R e B jogam em turnos colorindo em vermelho e azul, respectivamente, as arestas de uma triangulação dadas inicialmente em preto. O primeiro jogador a completar um triângulo monocromático
vazio ganha.
Aichholzer et al. [1] apresentam o seguinte teorema.
Teorema 5.6 ([1]) O jogador B pode forçar um empate no Jogo Bicolorindo uma Triangulação
em uma triangulação sobre um conjunto de pontos S com no máximo dois pontos internos.
Demonstração: Inicialmente vamos mostrar que o resultado vale para S em posição convexa.
Seja T (S) a triangulação dada e considere o dual de T (S). Observamos que o dual de T (S) é uma
42
árvore onde as arestas da envoltória convexa de S correspondem às folhas. Veja como exemplo as
figuras 5.3 e 5.4.
Figura 5.3: Exemplo de uma triangulação.
Figura 5.4: Grafo e respectivo dual.
Ao colorirmos uma aresta da triangulação em vermelho, colorimos também a aresta relacionada
do grafo dual. Vértices do grafo dual correspondentes aos triângulos na triangulação inicial possuem
grau três. Logo, para obter um triângulo vermelho, o jogador R precisa de meios para colorir três
arestas vermelhas. Quando o jogador B colore uma aresta azul, ele retira das possibilidades de
43
vitória do jogador R dois triângulos adjacentes a esta aresta (ou um triângulo, se aresta for na
envoltória convexa). No grafo dual, removemos a aresta correspondente e depois dividimos cada um
de seus extremos em uma ou duas folhas dependendo do número de arestas incidentes no extremos
(uma folha para cada aresta incidente). Como exemplo, veja as figuras 5.5 e 5.6.
e
Figura 5.5: Exemplo do grafo após a jogada do jogador B que colore a aresta e de azul.
B1
2
E 2
1
Figura 5.6: O movimento do jogador B divide o grafo dual em subgrafos independentes.
Dessa forma, o grafo dual apresenta apenas as arestas em preto e as já coloridas de vermelho
(movimentos do jogador R), sendo que os movimentos do jogador B dividem o grafo dual em
subgrafos independentes. É importante observar que enquanto um subgrafo não contém mais que
duas arestas vermelhas o jogador R não pode vencer.
Agora estamos prontos para dar uma estratégia de defesa para o jogador B, descrita na confi44
guração dual.
Suponha que é a vez do jogador B jogar e existe no máximo um subgrafo com duas arestas
vermelhas. Todos os demais subgrafos contém no máximo uma aresta vermelha. Claro, o jogador
B pode dividir o subgrafo contendo duas arestas vermelhas em pelo menos dois grafos, cada um
contendo no máximo uma aresta vermelha. Cada vez que o jogador R joga, ele pode adicionar
apenas uma aresta vermelha e, sendo assim, obtemos a situação similar à anterior. Portanto o
jogador B pode repetir sempre a mesma técnica de defesa até que todas as arestas estejam coloridas.
Ao iniciar com um conjunto de pontos S em posição convexa, após o primeiro movimento do
jogador R existe exatamente uma aresta colorida em vermelho e, pela aplicação da estratégia de
defesa acima, B pode forçar um empate.
Passamos agora para a prova da validade do teorema quando S possui um ponto interno.
Se S possui um ponto interno, então o grafo dual possui um ciclo. O primeiro movimento
de B tem que ser colorir uma aresta adjacente ao vértice interno de azul e assim dividir o ciclo
correspondente do grafo dual. Logo, depois do segundo movimento de R, o jogador B pode aplicar
a estratégia de defesa descrita acima.
Segue a estratégia do jogador B quando S tem dois pontos internos.
Suponha que S contém dois pontos internos e assim dois ciclos no grafo dual. Se a triangulação
contém uma aresta e conectando dois pontos internos, então no primeiro movimento, o jogador B
colore e ou uma das outras quatro arestas dos dois triângulos adjacentes a e em azul. Assim, ambos
ciclos são cortados. Como exemplo, veja a figura 5.7. Portando, depois que o jogador R faz seu
movimento pela segunda vez, o jogador B pode novamente aplicar a estratégia de defesa descrita
acima.
Suponha agora que não exista tal aresta e. Neste caso vamos chamar de ciclo esquerdo e ciclo
direito, respectivamente, os ciclos no grafo dual. Tais ciclos são conectados por um caminho através
de dois vértices a e b, a 6= b (veja a figura 5.8). Sem perda da generalidade, podemos assumir que
o primeiro movimento de R é à esquerda de b (pois, caso contrário, trocamos a por b). Então, o
jogador B colore uma aresta do triângulo correspondente ao vértice a em azul, dividindo (cortando)
o ciclo esquerdo. Enquanto R continuar jogando à esquerda de b, o jogador B joga (localmente) de
acordo com a estratégia de defesa descrita acima. No primeiro movimento de R para a direita de b,
o jogador B colore uma aresta do triângulo correspondente a b. Observe que pelo menos uma das
três possibilidades de arestas ainda está em preto, e que depois não só o ciclo direito será dividido,
45
e
Figura 5.7: Se a triangulação contém a aresta e conectando dois pontos internos, então no primeiro
movimento, o jogador B colore e em azul.
mas também a última aresta de R é separada de todas as outras arestas vermelhas. Assim, após
o próximo movimento de R, o jogador B pode continuar (globalmente) com a estratégia de defesa
usual descrita acima.
b
a
Figura 5.8: Exemplo quando a triangulação não contém uma aresta e conectando os dois pontos
internos. Neste caso vamos chamar de ciclo esquerdo e ciclo direito, respectivamente, os ciclos no
grafo dual. Tais ciclos são conectados por um caminho através de dois vértices a e b, a 6= b.
⇤
46
Capı́tulo 6
Comentários Finais
Buscamos, neste texto, apresentar com maiores detalhes, alguns dos resultados apresentados no
trabalho de Aichholzer et al. [1], referentes a estratégias de vitória para jogos em triangulações
planares. O conteúdo do artigo não foi esgotado neste texto, de modo que existem outros resultados
relacionados, os quais não foram abordados aqui. Sendo assim, recomendamos a leitura do artigo
aqui referido para mais informações e resultados nesta direção.
Procuramos também acrescentar a este estudo uma investigação a respeito da complexidade
dos problemas de jogos combinatórios, utilizando para isso a teoria de Sprague-Grundy e as noções
de PSPACE-completude. Quanto a estes assuntos, apenas uma pequena introdução foi dada neste
trabalho, de modo que o leitor interessado encontrará nas referências aqui relacionadas um maior
aprofundamento nestas teorias.
47
Referências Bibliográficas
[1] Aichholzer, O., D. Bremner, E. D. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S.
Ramaswami, S. Sethia and J. Urrutia, Games on triangulations, Theor. Comput. Sci., 343
(2005), 42–71.
[2] Berlekamp, E. R., J. H. Conway and R. K. Guy, Winning Ways of your mathematical
plays, Academic Press, 1982.
[3] Bodlaender, H.L. and D. Kratsch, Kayles and Nimbers, Journal of Algorithms, 43 (2002),
106–119.
[4] Bondy J.A. and U.S.R. Murty, Graph Theory With Applications, Elsevier Science, 1976.
[5] Cerioli, M., Feofilo↵, P., Fernandes, C. G., Miyazawa, F. K., Uma Introdução Sucinta a
Algoritmos de Aproximação, 23o Colóquio Brasileiro de Matemática, IMPA, 2001.
[6] Conway, J. H., On Numbers and Games, Academic Press, 1976.
[7] Cormen, T. H., C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2a
edição, Columbia University, 2001.
[8] Demaine, E. D., Playing games with algorithms: Algorithmic combinatorial game theory,
Proc. 26th Symp. on Math Found. in Comp. Sci., Lect. Notes in Comp. Sci., SpringerVerlag (2001), 18–32.
[9] Fraenkel,
Succinct
A.
S.,
Gourmet
Combinatorial
games:
Introduction,
Electronic
http://www.wisdom.weizmann.ac.il/⇠fraenkel
48
Selected
Journal
Bibliography
of
with
a
Combinatorics,
[10] Manic, G., D. Martin and M. Stojakovic. Bichromatic Triangle Games, Electronic Notes
in Descrete Applied Mathematics, 37 (2011), 105–110.
[11] Schaefer T. J., On the Complexity of Some Two-Person Perfect-Information Games, J.
Comput. Syst. Sci. 16 (1978), 185–225.
49