ColoraçãO De Mapas E O Problema Das Quatro Cores Desenvolvendo Um Puzzle

O Problema das Pontes de Königsberg, resolvido por Euler em 1736, foi o primeiro a envolver os conceitos do que viria a ser a Teoria dos Grafos. No segundo capítulo deste trabalho podemos verificar como Euler, através de seus teoremas, demonstrou a solução para o enigma das pontes.
A partir de então muitos problemas foram resolvidos utilizando a Teoria dos Grafos. Como, por exemplo, o Problema das Quatro Cores suscitado por Francis Guthrie em 1852.
Os jogos tiveram grande importância na solução de vários problemas matemáticos nos últimos tempos. O que nos mostra que os jogos podem ter desempenhado um papel evolutivo relevante. Por ser agradável a atividade intelectual, talvez o jogo facilite a aprendizagem das regras e do pensamento lógico.

1. FACULDADE AVANTIS




BRUNO RIBEIRO CAMPIGOTTO
FERNANDO R. CAMILO DE MEDEIROS
JULIANA LILIAN DE SOUZA
ROBERTO NOVAES DE CARVALHO









COLORAÇÃO DE MAPAS E O PROBLEMA DAS
QUATRO CORES:
DESENVOLVENDO UM PUZZLE
















Balneário Camboriú
Junho de 2010

2. BRUNO RIBEIRO CAMPIGOTTO
FERNANDO R. CAMILO DE MEDEIROS
JULIANA LILIAN DE SOUZA
ROBERTO NOVAES DE CARVALHO











COLORAÇÃO DE MAPAS E O PROBLEMA DAS
QUATRO CORES:
DESENVOLVENDO UM PUZZLE









Atividade Prática da disciplina de Estrutura
de Dados II, curso de Sistemas de Informação da
Faculdade Avantis.

Prof. Ivan Correia Filigrana








Balneário Camboriú
2010/I

3. LISTA DE ILUSTRAÇÕES

Figura 1. a) Pontes de Königsberg b) Grafo das Pontes de Königsberg .......................................... 4
Figura 2. Leonhard Euler ..................................................................................................................... 5
Figura 3. Grafo do problema de coloração da estrada. ......................................................................... 6
Figura 4. (a) grafo não planar, (b) grafo planar e (c) planar com todas as linhas retas. ....................... 7
Figura 5. a) Francis Guthrie b) Alfred Bray Kempe ........................................................................... 8
Figura 6. a) Wolfgang Appel (2002) b) Kenneth Haken (2002) ........................................................ 8
Figura 7. a) Neil Robertson b) Paul Seymour c) Robin Thomas d) Daniel Sanders .......................... 9
Figura 8. Print da tela de execução do algoritmo da prova do Teorema das Quatro Cores ............... 10
Figura 9. Figura a ser colorida do Puzzle .......................................................................................... 12
Figura 10. Uma solução para o Puzzle ............................................................................................... 14
Figura 11. Algoritmo em Python de Busca em Profundidade ............................................................ 15
Figura 12. Teste do grafo do PUZZLE utilizando o plug-in Planar Graphs ...................................... 16

4. SUMÁRIO
1
INTRODUÇÃO ...................................................................................... 3
1.1 OBJETIVOS .......................................................................................................... 3
2 FUNDAMENTAÇÃO TEÓRICA ........................................................ 4
2.1 HISTÓRIA DA TEORIA DOS GRAFOS ............................................................ 4
2.2 COLORAÇÃO DE MAPAS E O TEOREMA DAS QUATRO CORES ... ......... 6
2.2.1 Colorações Mínimas ........................................................................................... 6
2.2.2 Grafo Planar ........................................................................................................ 7
2.2.3 O Teorema das Quatro Cores .............................................................................. 7
3 PUZZLE DAS QUATRO CORES ..................................................... 12
3.1 O PROBLEMA .................................................................................................... 12
3.2 DESENVOLVIMENTO DO PUZZLE ............................................................... 13
3.2.1 Como Jogar ....................................................................................................... 13
3.2.2 Aplicação da Teoria das Quatro Cores ............................................................. 14
CONSIDERAÇÕES FINAIS ................................................................... 17
REFERÊNCIAS ........................................................................................ 18
APÊNDICE A - CÓDIGO FONTE DO JOGO ..................................... 19
ANEXO A – EULER (PONTES DE KONIGSBERG) ........................ 28
ANEXO B – COLORAÇÃO COM BUSCAS EM LARGURA .... .. 29

5. 3


1 INTRODUÇÃO
O Problema das Pontes de Königsberg, resolvido por Euler em 1736, foi o primeiro a
envolver os conceitos do que viria a ser a Teoria dos Grafos. No segundo capítulo deste trabalho
podemos verificar como Euler, através de seus teoremas, demonstrou a solução para o enigma das
pontes.
A partir de então muitos problemas foram resolvidos utilizando a Teoria dos Grafos. Como,
por exemplo, o Problema das Quatro Cores suscitado por Francis Guthrie em 1852.
Os jogos tiveram grande importância na solução de vários problemas matemáticos nos
últimos tempos. O que nos mostra que os jogos podem ter desempenhado um papel evolutivo
relevante. Por ser agradável a atividade intelectual, talvez o jogo facilite a aprendizagem das regras
e do pensamento lógico.
1.1 OBJETIVOS
Compreender como surgiu a Teoria dos Grafos e apresentar algumas soluções propostas ao
longo dos anos para um dos grandes problemas que deram origem ao estudo deste tema tão antigo,
porém ainda atual nos dias de hoje: A Coloração de Mapas e O Problema das Quatro cores.
A fim de aplicar o conhecimento adquirido em sala de aula e nesta pesquisa, pretendemos
desenvolver um pequeno Puzzle
1
utilizando um algoritmo de busca em largura com coloração de
vértices.






1
Puzzle: É um quebra-cabeça onde um jogador deve resolver um problema proposto. Nesse tipo de jogo, o raciocínio é
bem mais importante que a agilidade e a força física. Os quebra-cabeças são normalmente usados como passatempo.
Acredita-se que a história começou quando no século XVIII um cartógrafo colou um mapa a uma tábua de madeira.

6. 4


2 FUNDAMENTAÇÃO TEÓRICA
O problema das quatro cores surgiu historicamente em conexão com a coloração de mapas.
Para entendermos melhor o trabalho a seguir, devemos voltar um pouco na história onde os grandes
matemáticos sugeriram tais questionamentos, dando origem a Teoria dos Grafos.
2.1 História da Teoria dos Grafos
A Teoria dos Grafos nasceu no século XVII a partir de um problema que intrigava os
habitantes de uma cidade da antiga Prússia chamada
Königsberg (hoje Kalingrado, Rússia). Ali
existia um conjunto de sete pontes que cruzavam o rio Pregel e conectavam duas ilhas entre si e as ilhas
com as margens (veja a figura 1. a) A questão era a possibilidade de se cruzar as setes pontes num
passeio contínuo passando uma única vez por cada ponte.
Este problema foi elucidado por Leonhard
Euler
(1707-1783) em 1736 que reduziu o mesmo a um esquema mais simples (veja a figura 1. b)
que hoje chamamos de grafo.

a) b)

Figura 1. a) Pontes de Königsberg b) Grafo das Pontes de Königsberg
Fonte: en.wikipedia.org
É talvez a partir do raciocínio deste matemático que se deu o surgimento de um novo ramo
da geometria que, não considerando as dimensões da figura, analisa a ordem da disposição e a
relação entre os vários elementos dessa figura: A Teoria dos grafos.

7. 5



Figura 2. Leonhard Euler
Fonte: Pintura a óleo de Jakob Handmann Emanuel
Segundo Eves (2002), para a compreensão deste problema se fazem necessárias algumas
definições. Os grafos possuem vértices de onde saem suas linhas. Uma linha que faz a ligação entre
dois vértices consecutivos chama-se arco. O grau de um vértice é o número de arcos que sai dele.
Um vértice pode ser par ou ímpar de acordo com o seu grau. Uma cadeia simples consiste em certo
número de arcos que podem ser percorridos consecutivamente sem passar mais de uma vez por
nenhum deles. Unicursal é o nome dado a um grafo que pode ser percorrido totalmente, segundo
uma cadeia simples, e multicursal o que não possuir tal propriedade. Com estes conceitos Euler
estabeleceu os seguintes teoremas:
1. O número de vértices ímpares de qualquer grafo é um número par.
2. Se um grafo não possui nenhum vértice ímpar, então ele pode ser percorrido
unicursalmente segundo uma cadeia simples que termina no ponto de partida.
3. Um grafo que possui exatamente dois vértices ímpares pode ser percorrido
unicursalmente, começando num dos vértices ímpares e terminando no outro.
4. Todo grafo com mais de dois vértices ímpares é multicursal.
Através destes teoremas Euler conseguiu elucidar o famoso problema das pontes de
Königsberg,
pois como podemos ver na figura 2, o grafo que representa o problema das pontes é multicursal.

8. 6


2.2 Coloração de Mapas e o Teorema das Quatro Cores
Quantas cores precisamos para colorir os países de um mapa de tal forma que os países
adjacentes possuam cores diferentes? Quantos dias devem ser agendados para reuniões das
comissões de um parlamento de cada comissão, a possibilidade de reunir para um dia e alguns
membros do parlamento servir em várias comissões? Como podemos encontrar um calendário
escolar de comprimento total mínimo, com base nas informações de quantas vezes cada professor
tem que ensinar a cada classe?
Segundo Diestel (2005), a coloração de um conjunto de vértices de um dado grafo é a
atribuição de cores aos vértices de maneira que vértices adjacentes possuam cores diferentes. Seja
G(V, A) um grafo e C um conjunto de cores. Uma coloração de G é a atribuição de uma cor de C
para cada vértice de G respeitando a regra da adjacência. Assim sendo, uma coloração de G é uma
função f: V ® C tal que para cada par de vértices v,w Î V tem se (v,w) Î E
⇒ f(v) ¹ f(w).
De acordo com Feofilloff Et all (2009, p.), “É muito fácil produzir uma coloração dos
vértices de um grafo: basta atribuir uma cor diferente a cada vértice! É bem mais difícil encontrar
uma coloração com poucas cores.”
2.2.1 Colorações Mínimas
O número cromático de um grafo G é o menor número de cores k, para o qual existe uma k-
coloração de G. A k-coloração pode ser referente à coloração de vértices ou arestas de um grafo,
como podemos ver na figura 4.

Figura 3. Grafo do problema de coloração da estrada.
Fonte: pt.wikipedia.org

9. 7


Ao se trabalhar com representações através de mapas coloridos é necessário que cada região
se distinga das demais. Para isso uma solução é atribuir uma cor diferente para cada região. Mas
todo este esforço não é preciso, pois existe uma técnica de coloração de mapas que faz uso de
apenas quatro cores para colorir qualquer mapa planar (
Nonato, 2000).
2.2.2 Grafo Planar
Um grafo é dito planar se for possível redesenhá-lo em um plano sem que lhe sejam
alteradas as propriedades de seus vértices e arestas. Isto às vezes pode ser possível deformando,
entortando, encolhendo ou esticando suas arestas. Um grafo é plano quando seus vértices e arestas
estão todos em um plano.

Figura 4. (a) grafo não planar, (b) grafo planar e (c) planar com todas as linhas retas.
Fonte: en.wikipedia.org
2.2.3 O Teorema das Quatro Cores
Este teorema afirma que é possível colorir qualquer mapa com quatro cores, respeitando a
condição de que países vizinhos, com alguma linha de fronteira em comum, tenham cores
diferentes.
Tal problema foi suscitado por Francis Guthrie em 1852. Ele fez a pergunta a seu irmão
Frederick, que era então um estudante de matemática em Cambridge. O problema foi levado ao
conhecimento do grande público quando Arthur Cayley apresentou-o no London Mathematical
Society em 1878.

10. 8


Em 1879, Alfred Bray Kempe, foi o primeiro a publicar uma prova para o problema das
quatro cores. Sua prova estava incorreta, e foi modificada em 1890 por Percy John Heawood
através de uma prova do Teorema de Cinco Cores.
a) b)
Figura 5. a) Francis Guthrie b) Alfred Bray Kempe
Fonte: Domínio Publico
A primeira prova realmente aceita foi publicada por Wolfgang Appel e Kenneth Haken, em
1977. Baseadas em ideias de Kempe, que foram desenvolvidas em grande parte por Birkhoff e
Heesch. Eles demostraram que quatro cores são suficientes para colorir qualquer mapa no plano.
Porém, tal demonstração gerou controvérsias, pelo fato de depender do uso de computadores de
grande porte que levaram seis meses para rodar casos e mais casos de configurações.
a) b)
Figura 6. a) Wolfgang Appel (2002) b) Kenneth Haken (2002)
Fonte: News Letter nº46 da Sociedade Europeia de Matemática

11. 9


Em 1990, uma nova demonstração do teorema das quatro cores no plano foi desenvolvida
por quatro matemáticos, Neil Robertson, Daniel P. Sanders, Paul Seymour e Robin Thomas. A
demonstração deles ainda fez uso de computadores, mas a parte computacional pôde ser realizada,
em um laptop, em apenas algumas horas.
Figura 7. a) Neil Robertson b) Paul Seymour c) Robin Thomas d) Daniel Sanders
Fonte: Página pessoal dos autores
Um argumento é o de que a nossa «prova» não é uma prova no sentido tradicional,
porque ela contém passos que nunca poderão ser verificados por seres humanos. Em
particular, não podemos provar a justeza do compilador em que compilamos os nossos
programas, nem a infalibilidade do hardware em que os executamos. Isto é, estas questões
têm de ser tomadas com base na fé, pois é concebível a possibilidade de erros. No entanto,
a partir de um ponto de vista prático, a chance de um erro informático aparecer
constantemente exatamente da mesma maneira em todas as execuções de nossos programas
em todos os compiladores sob todos os sistemas operacionais que os nossos programas são
executados é infinitamente pequena em comparação com a chance de um erro humano
durante a mesma quantidade de verificações. Para além desta possibilidade hipotética de
um computador sempre dar uma resposta errada, o resto da nossa prova pode ser verificado
da mesma forma como as tradicionais provas de matemática. (ROBERTSON et all., 1996,
p. 24)
a) b)
c) d)

12. 10



Encontramos os arquivos necessários, para testar esta nova prova do Teorema das Quatro
Cores disponíveis no site de Robin Thomas
2
, bem como as instruções para utilizá-los. Os
algoritmos se encontram em linguagem C, e o seu uso é permitido para fins de pesquisa acadêmica.
Na figura abaixo podemos verificar um print da tela de execução do algoritmo de redutibilidade que
é a parte um de dois programas que servem de complemento ao documento que registra a Nova
Prova do Teorema das Quatro Cores
3
.


Figura 8. Print da tela de execução do algoritmo da prova do Teorema das Quatro Cores
Fonte: Dev C++ 4.9.9.2



2
Disponível em <http://people.math.gatech.edu/~thomas/FC/fourcolor.html#Main>
3
A New Proof of the Four Color Theorem, Electronic Research announcements of the American Mathematic Society –
Anúncios eletrrônicos de Investigação da Sociedade Americana de Matemática

13. 11


A título de curiosidade, rodamos este algoritmo em um notebook com 4 Gb de memória e
um processador Intel Core 2 Duo de 2.1GHz. O tempo de execução foi de aproximadamente 13
minutos como mostra a Figura 8.

14. 12


3 PUZZLE DAS QUATRO CORES
Os “quebra-cabeças” são brincadeiras seculares e sempre desafiadoras para aqueles que
gostam de passar horas na busca de suas soluções. Normalmente, quem aprecia esse tipo de desafio
procura encontrar alguma lógica na solução do problema, a fim de evitar o processo desgastante e
desestimulante das tentativas aleatórias. É nesse contexto que se apresenta um processo lógico para
a resolução do Puzzle das Quatro Cores.
3.1 O PROBLEMA
O Puzzle de Quatro Cores nada mais é do que uma variação do problema da coloração de
mapas utilizando quatro cores. Trata-se de uma imagem dividida em várias partes, as quais vamos
chamar de “faces”, onde o jogador vai utilizar o botão esquerdo do mouse para aplicar cores às
diversas faces da imagem. Na figura 8 podemos verificar o desenho a ser colorido.


Figura 9. Figura a ser colorida do Puzzle

15. 13


3.2 DESENVOLVIMENTO DO PUZZLE
Para o desenvolvimento do jogo utilizamos a versão 2.6.4 do Python
4
, e o VPython v5.3
5

release. O jogo é composto dos seguintes arquivos, os quais se encontram no APÊNDICE A deste
trabalho:
· main.py: Filtra os parâmetros de linha de comando, executa as ações, e instância a
classe App;
· app.py: Contém a classe da aplicação, e instancia classe Item;
· item.py: Contem classe Item, que herda a classe "Faces" da API Vpython;
· layout1.txt: Layout da imagem. Ele contém informações sobre os triângulos,
posições X, Y e Z deles, e suas ligações. Assim, é possível usar o mesmo programa
para desenhos diferentes sem mexer no código, criando um novo arquivo de layout;
· RODAR – Fullscreen.bat: Passa parâmetros de linha de comando, sem necessidade
de abrir um Prompt e digitar tudo;
· RODAR – Janela.bat: Passa parâmetros de linha de comando, sem necessidade de
abrir um Prompt e digitar tudo.
3.2.1 Como Jogar
Para usar o jogo, descompacte o arquivo ZIP em qualquer pasta. O arquivo main.py recebe
os argumentos por linha de comando e executa as ações necessárias. Para rodar o jogo utilize um
dos arquivos bat: Um roda o jogo em janela, permitindo ao usuário acompanhar as linhas de
comando que validam a ação, mostrando qual face está colorida de forma incorreta. O outro bat
roda o jogo no modo full screen.
Outros comandos:
1 Segure o botão direito do mouse e mova o mouse para girar o ângulo da imagem.



4
Disponível em: <http://www.python.org/ftp/python/2.6.4/python-2.6.4.msi>
5
Disponível em: <http://vpython.org/contents/download/VPython-Win-Py2.6-5.32.exe >

16. 14


2 Segure os dois botões do mouse e mova o mouse para cima e para baixo para regular o zoom.
3 Funções do teclado: Pressione (V) para validar a cor escolhida e (R ou S) para solucionar
automaticamente o puzzle.

Figura 10. Uma solução para o Puzzle
3.2.2 Aplicação da Teoria das Quatro Cores
Para a resolução automática do Puzzle utilizamos um algoritmo de busca em profundidade,
adaptado de pseudocódigo
6
, na linguagem Python. O Quadro 1 mostra o trecho do código que
realiza a busca em profundidade.
1
def solucao(self):
2 """
3 solucao()
4 Soluciona o problema do teorema de quatro c ores.
5 """
6 q=[]
7 maiorGrau=0
8 item=None
9 for i in self.itens:
10 if i.getGrau() > maiorGrau:
11 maiorGrau=i.getGrau()



6
Disponível em: http://www.lcad.icmc.usp.br/~nonato/ED/Coloracao/lcoloracao.html>

17. 15


12
item=i
13 self.colorirItem(item)
14 q.append(item)
15 #while(len(q)>0 and not self.validar()):
16 while(not self.validar()):
17 x=q.pop(0)
18 for j in x.getLigacoes():
19 self.colorirItem(j)
20 q.append(j)
21 return False
22 #self.validar()
23
24 def colorirItem(self,item):
25 """
26 colorirItem(item)
27 Aplica uma cor ao item / face.
28 """
29 item.setCor(self.getCorAdequada(item))
30
31 def getCorAdequada(self,item):
32 """
33 getCorAdequada(item)
34 Analisa os vertices adjacentes, e retorna u ma cor das quatro
35 que nao conflite com os vertices adjacentes .
36 Caso nao haja uma cor adequada, retorna uma randomica.
37 """
38 c=[]
39 p=[]
40 for i in item.getLigacoes():
41 c.append(i.getColor(True))
42 for i in range(4):
43 if i not in c:
44 #return i
45 p.append(i)
46 if len(p)>0:
47 return random.choice(p)
48 return random.randint(0,3)
Figura 11. Algoritmo em Python de Busca em Profundidade
Fonte: Adaptado do ANEXO A (NONATO, 2010 ).

Para facilitar a análise da imagem a ser colorida criamos o grafo (ver figura 10) da mesma
utilizando um aplicativo chamado Tulip 3.3.1, que é um software de criação e visualização de
grafos escritos e mantido pela Universidade Bordeaux I na França. O projeto Tulip está sob licença

18. 16


PL e todos podem dar sua contribuição para este software. No site do projeto encontram-se mais
informações sobre o Tulip
7
.
O Tulip possui diversos plug-ins, com os quais podem ser feitos vários testes no grafo
criado. Alguns exemplos de plug-ins para o Tulip:
· Planar Graphs: Verifica se o grafo é planar. A definição de grafo planar se encontra
no item 2.3.1 do capítulo 3 deste trabalho.
· Kruskal: Este plug-in de seleção implementa o chamado algoritmo de Kruskal. Este
algoritmo permite encontrar uma árvore geradora mínima em um grafo conexo.
Permite encontrar todos os nós e arestas, a uma distância fixa de um conjunto de
nós. Isso só funciona em grafos não orientados. Como parâmetro é preciso o peso
da borda, este parâmetro define o peso de cada aresta no gráfico.

Figura 12. Teste do grafo do PUZZLE utilizando o plug-in Planar Graphs
Fonte: Tulip 3.3.1



7
Disponível em: <http://www.tulip-software.org>

19. 17


CONSIDERAÇÕES FINAIS
Neste trabalho realizamos uma pesquisa sobre dois problemas da matemática que muito
contribuíram para a origem da Teoria dos Grafos: A Coloração de Mapas e o Teorema das Quatro
Cores. Vimos que os dois problemas surgiram paralelamente um ao outro, quando Guthrie em 1852
fez o questionamento sobre a quantidade mínima de cores que seriam necessárias para colorir um
mapa.
Percorremos a história da famosa Teoria das Quatro Cores e conhecemos um pouco mais
sobre os matemáticos e suas tentativas de provarem sua veracidade. Verificamos que tal teoria
ainda continua sob o estudo de muitos matemáticos. Apesar de, Neil Robertson e seus amigos terem
conseguido apresentar em 1990 uma prova mais simples e rápida que a de Appel & Haken (1977),
esta prova ainda recebeu muitas críticas da Sociedade de Matemática por fazer uso de um
computador em suas verificações.
Por fim, tivemos a oportunidade de aplicar os conceitos de “Coloração de Mapas e o
Teorema das Quatro Cores” no desenvolvimento de um pequeno jogo; onde aplicamos o
conhecimento adquirido, nesta pesquisa e na disciplina de Estrutura de Dados II, que de muito nos
valeu no entendimento deste tema tão interessante.

20. REFERÊNCIAS

ROBERTSON, Neil; SANDERS, Dan; SEYMOUR, Paul; THOMA S, Robin. A New Proof of the
Four Color Theorem, Electronic Research announcements of the American Mathematic Society.
Vol.2, Number 1, 1996.

NONATO, Luis Gustavo. Coloração em Grafos. Disponível em:
< http://www.lcad.icmc.usp.br/~nonato/ED/Coloracao/coloracao.html >. Acesso em: 01 jun. 2010.

NICOLETTI, Maria do Carmo; HRUSCHKA, Estevam Rafael . Fundamentos da teoria dos
grafos para computação. São Carlos : EdUFSCar, 2009.

THOMAZ, R. (1995, November 12). The Four Color Theorem. Acessado em 24 de junho 2010,
em <http://people.math.gatech.edu/~thomas/FC/fourcolor.html#Main>

DIESTEL, Reinhard. Graph Theory: Eletronic Edition. 3. ed. New York: Springer, 2005.

BONDY, J.A ; MURTY, U.S.R . Graph Theory with applications. 6. ed. New York: Sole, 1982.

FEOFILOFF, Paulo ; KOHAYAKAWA, Y; WAKABAYASHI, Y . Uma Introdução Sucinta à
Teoria dos Grafos. . ed. São Paulo, 1982.

KLYV, Dominic; STEMKOSKI, Lee. The works of Leonhard Euler online. Disponível em:
< http://www.math.dartmouth.edu/~euler/ >. Acesso em: 25 jun. 2010.

21. 19


APÊNDICE A - CÓDIGO FONTE DO JOGO
Arquivo mayn.py
#-*- coding: UTF-8 -*-
1 from app import App
2 from visual import *
3 import sys
4 import re

5 scene.width=800
6 scene.height=500
7 scene.fullscreen=False
8 scene.title="O Prof. Ivan usa Linux"
9 #scene.visible=True
10 lay=""
11 vmod=0 #Hackzinho baaaaaaaaaasico...
12 wZoom=600
13 hZoom=300
14 zZoom=100

15 # Taste the Wild... Lick the wind...
16 # Tratar parametros de cli
17 for i in range(len(sys.argv)):
18 if sys.argv[i]=='--res':
a. if sys.argv[i+1]:
i. if re.match('[0-9]{3,4}x[0-9]{3,4}',sys.argv[i+1]):
1. l=sys.argv[i+1].split('x')
2. scene.width=int(l[0])
3. scene.height=int(l[1])
ii. else:
1. print("Fornecido parametro --res, mas dados nao
batem com RE")
b. else:
i. print("Fornecido parametro --res, mas sem dados
adicionais")
19 if sys.argv[i]=='--fullscreen':
a. scene.fullscreen=True

20 if sys.argv[i]=='--layout':
a. if sys.argv[i+1]:
i. lay=sys.argv[i+1]

21 if sys.argv[i]=='--vmod':
a. if sys.argv[i+1]:
i. vmod=int(sys.argv[i+1])

22 if sys.argv[i]=='--center':
a. if sys.argv[i+1]:
i. if re.match('[0-9]{3,4}x[0-9]{3,4}x[0-
9]{1,4}',sys.argv[i+1]):
1. l=sys.argv[i+1].split('x')
2. wZoom=int(l[0])
3. hZoom=int(l[1])

22. 20


4.
zZoom=int(l[2])
ii. else:
1. print("Fornecido parametro --center, mas dados nao
batem com RE")
b. else:
i. print("Fornecido parametro --center, mas sem dados
adicionais")

23 scene.center=(wZoom,hZoom,zZoom)
24 #scene.center=(scene.width,scene.height*0.70,0)
25 a=App(lay,vmod)



Arquivo app.py
#-*- coding: UTF-8 -*-
1 from visual import *
2 from item import Item
3 import os
4 import re
5 import random
6
7 class App(object):
8
9 def __init__(self,layout,vmod=0):
10 self.arqLayout=layout
11 self.rc=re.compile('\([0-9.,]+?\)') #RE que busca tuplas
na linha
12 self.itens=[]
13 self.vmod=vmod
14
15 self.lerLayout()
16 self.findTuplas()
17 self.makeTxt()
18 self.listen()
19
20 def parseTuple(self,strTuple,parseInt=1,parseFl oat=0):
21 """
22 parseTuple(strTuple,parseInt=0,parseFloat=1 )
23 Recebe uma string contendo uma tupla, e ret orna um objeto
tupla dos dados da string.
24 Se a flag parseInt estiver ON, faz um cast dos dados pra
int. O mesmo para float.
25 Por padrão, sem cast, os dados são tratad os como string.
26 """
27 s=strTuple
28 l=[]
29 s=s.replace('(','')
30 s=s.replace(')','')
31 for i in s.split(','):
32 if parseInt: i=int(i)
33 elif parseFloat: i=float(i)
34 l.append(i)
35 if self.vmod > 0:

23. 21


36
l[1]=self.vmod-l[1]
37 return tuple(l)
38
39 def lerLayout(self):
40 """
41 lerLayout()
42 Lê o arquivo de layout, setado dentro do c onstructor,
salva em duas variaveis locais,
43 uma com o texto cru (RAW) e outra com o tex to limpo
(Retirando comentarios)
44 """
45 self.txtLayoutRaw=open(self.arqLayout).read ()
46 self.txtLayout=self.limpaTexto(self.txtLayo utRaw)
47 #print self.txtLayout
48 def limpaTexto(self,txt):
49 """
50 limpaTexto(txt)
51 Remove C-Style comentarios, Python-style co mentarios, e
linhas em branco. Entao, retorna o txt.
52 Python-style, me refiro aos sustenidos. Mui ta gente usa
docstrings como comentarios.
53 """
54 txt=re.sub('#.*','',txt)
55 txt=re.sub('//.*','',txt)
56 txt=re.sub(re.compile('/\**?.*?\*/',re.DOTA LL),'',txt)
57 txt=os.linesep.join([l for l in txt.splitli nes() if
l.strip()])
58 return txt
59
60 def findTuplas(self):
61 """
62 findTuplas()
63 Encontra as tuplas com posicoes e adiciona uma instancia
de Item com as posicoes
64 """
65 for i in self.txtLayout.splitlines():
66 if i[:4]=='ITEM':
67 l=re.findall(self.rc,i[5:])
68 pos=[]
69 for j in l:
70 pos.append(self.parseTuple(j))
71 self.itens.append(Item(pos))
72 self.itens[-1].make_twosided()
73 if i[:4]=='LIGA':
74 t=str(i[5:]).split('-')
75 try:
76 p1=int(t[0])
77 p2=int(t[1])
78 if self.itens[p1-1] and self.it ens[p2-1]:
79 self.itens[p1-1].addLigacao (self.itens[p2-
1])
80 self.itens[p2-1].addLigacao (self.itens[p1-
1])
81 else:
82 print("Itens {0} e {1} - Fo ra de

24. 22


alcance".format(p1,p2))
83 except:
84 print("Pau:",t,i[5:-1],i)
85
86 def makeTxt(self):
87 """
88 makeTxt()
89 Cria o texto embaixo
90 """
91 #self.txt=text(width=600,pos=(600,-
100,0),height=100,align='center',text='Incorreto',c olor=color.red)
92 self.txt=text(width=600,pos=(600,-
100,0),height=100,align='center',depth=20,text='',c olor=color.red)
93
94 def listen(self):
95 """
96 listen()
97 'Escuta' eventos de teclado e mouse, filtra e aplica
acoes.
98 """
99 p=None
100 rate(100) # Limita 100 FPS
101 while(True):
102 if scene.mouse.events:
103 m=scene.mouse.getevent()
104 #print dir(m)
105 if m.click and m.pick:
106 #print(m)
107 try:
108 m.pick.swapColor()
109 print("Validando")
110 self.validar()
111 except:
112 self.solucao()
113 pass
114
115 if scene.kb.keys:
116 s=scene.kb.getkey()
117 if len(s)==1:
118 char=s.upper()
119 if char == 'V':
120 self.validar()
121 elif char == 'R' or char == 'S' :
122 self.solucao()
123 char=''
124
125 def validar(self):
126 """
127 validar()
128 Valida todos os itens
129 """
130 a=True
131 for i in range(len(self.itens)):
132 if not self.itens[i].validate():
133 self.txt.color=color.red

25. 23


134
self.txt.text="Incoreto"
135 a=False
136 print("Item {0} com problema".forma t(i+1))
137 return False
138 #else:
139 # print("Item {0} OK!".format(i+1))
140
141 if a:
142 self.txt.text="Correto"
143 self.txt.color=color.green
144 return True
145
146 def solucao(self):
147 """
148 solucao()
149 Soluciona o problema do teorema de quatro c ores.
150 """
151 q=[]
152 maiorGrau=0
153 item=None
154 for i in self.itens:
155 if i.getGrau() > maiorGrau:
156 maiorGrau=i.getGrau()
157 item=i
158 self.colorirItem(item)
159 q.append(item)
160 #while(len(q)>0 and not self.validar()):
161 while(not self.validar()):
162 x=q.pop(0)
163 for j in x.getLigacoes():
164 self.colorirItem(j)
165 q.append(j)
166 return False
167 #self.validar()
168
169 def colorirItem(self,item):
170 """
171 colorirItem(item)
172 Aplica uma cor ao item / face.
173 """
174 item.setCor(self.getCorAdequada(item))
175
176 def getCorAdequada(self,item):
177 """
178 getCorAdequada(item)
179 Analisa os vertices adjacentes, e retorna u ma cor das
quatro
180 que nao conflite com os vertices adjacentes .
181 Caso nao haja uma cor adequada, retorna uma
randonomica.
182 """
183 c=[]
184 p=[]
185 for i in item.getLigacoes():
186 c.append(i.getColor(True))

26. 24


187
for i in range(4):
188 if i not in c:
189 #return i
190 p.append(i)
191 if len(p)>0:
192 return random.choice(p)
193 return random.randint(0,3)

Arquivo item.py
1 #-*- coding: UTF-8 -*-
2 from visual import *
3
4 class Item(faces):
5
6 def __init__(self,pos,initColor=color.yellow):
7 faces.__init__(self)
8 self.color=color.yellow
9 self.__ligacoes=[]
10 self.pos=pos
11 self.flagCores=0
12 self.cores=[color.yellow,color.red,color.bl ue,color.green]
13
14 def getLigacoes(self):
15 return self.__ligacoes
16
17 def getColor(self,returnFlag=False):
18 if returnFlag:
19 return self.flagCores
20 return self.color
21
22 def getLigacoesFromPos(self,pos):
23 """
24 getLigacoesFromPos(pos)
25 Retorna uma
26 """
27 if self.__ligacoes[pos]:
28 return self.__ligacoes[pos]
29
30 def addLigacao(self,i):
31 """
32 addLigacao(i)
33 Adiciona uma referencia a outra instancia d a classe Item,
34 representando uma ligação por ponteiros.
35 É mantido um array com as ligacoes existen tes em cada
classe.
36 """
37 self.__ligacoes.append(i)
38
39 def validate(self):
40 """

27. 25


41
validate()
42 Valida as ligacoes, para ver se nao tem out ra instancia da
43 classe Item, vizinha, com a mesma cor.
44 """
45 for i in self.getLigacoes():
46 if i.getColor(True) == self.getColor(Tr ue):
47 return False
48 return True
49
50 def swapColor(self):
51 """
52 swapColor()
53 Troca a cor da peca
54 Usa um array associativo (Dict) para tal
55 """
56 #R, G, B, W
57 #self.color=self.cores[self.color]
58 #Tentei várias maneiras de armazenar em ar raysm dicts, e
etc.
59 #Mas NumPy é foda =|
60
61 if self.flagCores == len(self.cores)-1:
62 self.flagCores=0
63 else:
64 self.flagCores=self.flagCores+1
65 self.color=self.cores[self.flagCores]
66
67 def getGrau(self):
68 """
69 getGrau()
70 Retorna o grau do vertice.
71 """
72 return len(self.__ligacoes)
73
74 def setCor(self,c):
75 self.color=self.cores[c]
76 self.flagCores=c


Arquivo layout.py

1 ## HOW TO CREATE YOUR OWN:
2 ## Os primeiros 4 caracteres sao os identificadores do
3 ## registro. Para figuras, use ITEM
4 ## Basicamente, todos os itens 3D sao varios
5 ## triangulos juntos.
6 ## Crie um registro ITEM, e coloque as cordenadas dos
7 ## triangulos (X,Y,Z), separados por virgula.
8 ## Ex: ITEM:[(1,0,0),(1,1,0),(0,1,0)]
9 ## Se houver mais de um triangulo na figura, coloque
10 ## dentro dos colchetes, separado por virgula.
11 ## Ex: ITEM:[(1,0,0),(1,1,0),(0,1,0),(2.1,1.3,0),...]

28. 26


12 ##
13 ## Isso vai fazer com que o programa desenhe os
14 ## triangulos, mas nao vai fazer as ligacoes. Para
15 ## fazer isso, use o registro LIGA.
16 ## Ex: LIGA:7-32
17 ## Isso vai fazer uma ligacao do registro 7 com o 32
18 ##
19 ## Ah, comentarios com '#' ou '//' serao removidos

20 #ITEM:[(,,0),(,,0),(,,0)]
21 ITEM:[(11,738,0),(124,738,0),(11,434,0)] #Item 1
22 ITEM:[(49,520,0),(129,738,0),(592,738,0)] #Item 2
23 ITEM:[(11,419,0),(11,210,0),(49,511,0),(11,210,0),(49,511,0),(599,738,0)] #Item 3
24 ITEM:[(607,738,0),(699,738,0),(453,600,0),(453,600,0),(699,738,0),(551,500,0)] #Item 4
25 ITEM:[(450,596,0),(356,511,0),(548,495,0)] #Item 5
26 ############## ITEM 6 IS A LIE
27 #Itens abaixo estao com numero a mais
28 #Exemplo, o item 7 eh o item 6 no desenho
29 ITEM:[(461,345,0),(363,508,0),(546,490,0)] #Item 7
30 ITEM:[(351,508,0),(171,347,0),(458,340,0),(171,347,0),(458,340,0),(370,193,0)] #Item 8
31 ITEM:[(366,188,0),(167,342,0),(107,11,0),(107,11,0),(167,342,0),(11,82,0),(107,11,0),(11,82,0),
(11,11,0)] #Item 9
32 ITEM:[(11,205,0),(11,91,0),(155,332,0)] #Item 10
33 ITEM:[(128,19,0),(539,185,0),(371,186,0)] #Item 11
34 ITEM:[(132,15,0),(552,185,0),(647,43,0)] #Item 12
35 ITEM:[(650,40,0),(634,11,0),(177,11,0)] #Item 13
36 ITEM:[(374,191,0),(547,191,0),(460,336,0)] #Item 14
37 ITEM:[(556,186,0),(727,186,0),(653,43,0)] #Item 15
38 ITEM:[(640,11,0),(735,186,0),(907,187,0)] #Item 16
39 ITEM:[(644,11,0),(915,186,0),(978,11,0)] #Item 17
40 ITEM:[(733,192,0),(820,339,0),(554,192,0),(820,339,0),(554,192,0),(464,341,0),(464,341,0),
(820,339,0),
41 (553,490,0),(820,339,0),(553,490,0),(732,490,0)] #Item 18
42 ITEM:[(642,637,0),(556,495,0),(729,495,0)] #Item 19
43 ITEM:[(645,644,0),(735,498,0),(706,738,0),(735,498,0),(706,738,0),(1049,738,0)] #Item 20
44 ITEM:[(740,495,0),(915,495,0),(1048,732,0)] #Item 21
45 ITEM:[(738,490,0),(911,490,0),(825,346,0)] #Item 22
46 ITEM:[(1057,738,0),(1190,738,0),(830,345,0),(1190,738,0),(830,345,0),(1190,491,0)] #Item 23
47 ITEM:[(824,336,0),(911,192,0),(738,192,0)] #Item 24
48 ITEM:[(828,339,0),(917,192,0),(1190,487,0)] #Item 25
49 ITEM:[(983,14,0),(920,187,0),(1190,76,0),(1190,76,0),(920,187,0),(1190,482,0)] #Item 26
50 ITEM:[(1190,71,0),(1190,11,0),(988,11,0)] #Item 27
51 #ITEM:[(,,0),(,,0),(,,0)]
52 #ITEM:[(,,0),(,,0),(,,0)]
53 #ITEM:[(,,0),(,,0),(,,0)]
54 #ITEM:[(,,0),(,,0),(,,0)]
55 #ITEM:[(,,0),(,,0),(,,0)]
56 #ITEM:[(,,0),(,,0),(,,0)]
57 #ITEM:[(,,0),(,,0),(,,0)]
58 #ITEM:[(,,0),(,,0),(,,0)]
59 #ITEM:[(,,0),(,,0),(,,0)]
60 #ITEM:[(,,0),(,,0),(,,0)]
61 #ITEM:[(,,0),(,,0),(,,0)]
62 #ITEM:[(,,0),(,,0),(,,0)]

29. 27


63 #ITEM:[(,,0),(,,0),(,,0)]
64 LIGA:1-2
65 LIGA:1-3
66 LIGA:2-3
67 LIGA:3-9
68 LIGA:3-5
69 LIGA:9-8
70 LIGA:3-7
71 LIGA:7-8
72 LIGA:3-4
73 LIGA:4-5
74 LIGA:5-6
75 LIGA:5-7
76 LIGA:6-7
77 LIGA:8-10
78 LIGA:10-11
79 LIGA:11-12
80 LIGA:7-13
81 LIGA:10-13
82 LIGA:11-14
83 LIGA:12-15
84 LIGA:14-15
85 LIGA:14-17
86 LIGA:13-17
87 LIGA:6-17
88 LIGA:4-18
89 LIGA:18-19
90 LIGA:4-19
91 LIGA:19-20
92 LIGA:17-18
93 LIGA:17-21
94 LIGA:20-21
95 LIGA:20-22
96 LIGA:21-22
97 LIGA:17-23
98 LIGA:15-23
99 LIGA:15-16
100 LIGA:16-25
101 LIGA:23-24
102 LIGA:24-25
103 LIGA:22-24
104 LIGA:25-26


Arquivo rodar-fullscreen.py

C:\Python26\python main.py --layout layout1.txt --res 600x500 –fullscreen

Arquivo rodar-fullscreen.py
C:\Python26\python main.py --layout layout1.txt --res 600x500

30. 28


ANEXO A – EULER (PONTES DE KONIGSBERG)

31. 29


ANEXO B – COLORAÇÃO COM BUSCA EM LARGURA
montar a lista de adjacências
inicializar a estrutura de cores
inicializar a estrutura de fila
escolher o vertice Vi de maior grau para ser colorido primeiro
chamar a sub-rotina Colore_Vertice para colorir o vertice Vi escolhido
inserir o vertice Vi na fila Q
enquanto a fila Q nao estiver vazia faca
remove o vertice Vk da fila
para todo vertice Vj adjacente a Vk faça
chamar a sub-rotina Colore_Vertice para colorir o vertice Vj
inserir Vj na fila
fim para
fim enquanto

Sub-rotina Colore_Vertice: Vk

se o vertice Vk ainda nao foi colorido
procurar a cor C apropriada
se nao existir cor apropriada para colorir o vertice Vk
criar uma nova cor C
fim se
colorir o vertice Vk com a cor C
fim se

32. 30


Algoritmo Passo a Passo

33. 31







Número Cromático = 3

Custo Computacional

Considerando que N seja o número de vértices, E o número de arestas, NC seja o número de cores e
NVZ seja o número de vizinhos(vértices adjacentes), temos:
1. montar a lista de adjacência= O(N+E)
2. escolher o vertice de maior grau= O(N)
3. procurar cor= O(NVZ*NC)
4. colorir o vertice= O(1)

34. 32


5. inserir e remover da fila= O(1)
6. para todos os vertices colorir todos os seus adjacentes: O((N-1)*(NVZ*NC))

Custo Total= O(N+E) + O(N) + O(N*(NVZ*NC))
de onde podemos concluir que o custo total é da ordem de O(N*(NVZ*NC)), em que no pior caso
teremos um custo de ordem cúbica.



Fonte: http://www.lcad.icmc.usp.br/~nonato/ED/Coloracao/lcoloracao.html