Universidade de BrasíliaInstituto de Ciências Exatas

Departamento de Ciência da Computação

Lições sobre o Problema das Quatro Cores

Adriano Teles da Costa e Oliveira

Monografia apresentada como requisito parcialpara conclusão do Curso de Computação — Licenciatura

OrientadorProf. Dr. José Carlos Loureiro Ralha

Brasília2010

Universidade de Brasília — UnBInstituto de Ciências ExatasDepartamento de Ciência da ComputaçãoCurso de Computação — Licenciatura

Coordenador: Prof. Dr. Homero Luiz Píccolo

Banca examinadora composta por:

Prof. Dr. José Carlos Loureiro Ralha (Orientador) — CIC/UnBProf.a Dr.a Maria de Fátima Ramos Brandão — CIC/UnBProf.a Dr.a Maria Emília Machado Telles Walter — CIC/UnB

CIP — Catalogação Internacional na Publicação

Oliveira, Adriano Teles da Costa e.

Lições sobre o Problema das Quatro Cores / Adriano Teles da Costa eOliveira. Brasília : UnB, 2010.42 p. : il. ; 29,5 cm.

Monografia (Graduação) — Universidade de Brasília, Brasília, 2010.

1. Problema das Quatro Cores, 2. Teoria dos Grafos, 3. Coloração deMapas

CDU 004

Endereço: Universidade de BrasíliaCampus Universitário Darcy Ribeiro — Asa NorteCEP 70910-900Brasília–DF — Brasil

Universidade de BrasíliaInstituto de Ciências Exatas

Departamento de Ciência da Computação

Lições sobre o Problema das Quatro Cores

Adriano Teles da Costa e Oliveira

Monografia apresentada como requisito parcialpara conclusão do Curso de Computação — Licenciatura

Prof. Dr. José Carlos Loureiro Ralha (Orientador)CIC/UnB

Prof.a Dr.a Maria de Fátima Ramos Brandão Prof.a Dr.a Maria Emília Machado Telles WalterCIC/UnB CIC/UnB

Prof. Dr. Homero Luiz PíccoloCoordenador do Curso de Computação — Licenciatura

Brasília, 29 de setembro de 2010

Lista de Tabelas

4.1 Divisão das atividades da oficina. . . . . . . . . . . . . . . . . . . . . . . . 27

iv

Agradecimentos

Ao professor Guilherme Albuquerque Pinto, que me auxiliou na fase da pesquisa e queme mostrou como melhor atingir o objetivo traçados.

Ao professor José Carlos Loureiro Ralha, pela orientação e principalmente pelo respeitoque demonstrou em aceitar a condução já iniciada dessa monografia. O resultado foi umarica discussão de ideias que engrandeceram o conteúdo e possibilitaram sua conclusão.

Aos professores e funcionários com quem convivi nos anos de universidade, em especialaos que transmitiram conhecimento nas disciplinas relacionadas à Computação e quecontribuiram na minha formação acadêmica.

Aos colegas de curso que compartilharam comigo a jornada da graduação.

À minha família, principalmente à minha mãe cuja vontade e garra muito me ensinaram.

Finalmente, minha gratidão à Palloma, fiel companheira, pela ajuda, compreensão e pa-ciência, que sempre esteve ao meu lado incentivando e torcendo pelo êxito do trabalho.

v

Resumo

Este trabalho aborda o Problema das Quatro Cores que assegura ser possível colorir qual-quer mapa com até quatro cores distintas, sem que regiões vizinhas possuam a mesma cor.Por ser fácil de entender, desperta a curiosidade das pessoas de distintas áreas e diversosinteresses, o que o destaca dos demais problemas que apenas são entendidos por mate-máticos profissionais Ore (1967). Tendo por finalidade conhecer as diferentes formas decontribuição científica que se desenvolveram sobre o tema, inicia-se pelos principais con-ceitos e pela investigação de trabalhos que tentaram solucionar o Problema das QuatroCores proposta pelo jovem matemático Francis Guthrie em 1852. Confronta-se os dife-rentes métodos aplicados e procura-se estabelecer qual a contribuição do uso do Problemadas Quatro Cores no ensino pré-universitário no Brasil.

Palavras-chave: Problema das Quatro Cores, Teoria dos Grafos, Coloração de Mapas

vi

Abstract

This work approaches the Four Colors Problem. This problem assures to be possibleto color any map with up to four different colors, without neighboring areas sharing thesame color. Being easily posed and understandable, it wakes up the people’s curiosity whatdetaches it of other problems that are only understood by professional mathematicians Ore(1967). The work presents, from a historical perspective, the most relevant developmentsthat led to the solution of one of the most difficult problems ever. It also describestwo classroom experiences using the Four Colors Problem as the basis for teaching, on amultidisciplinary approach, subjects of Brazilian High School grade.

Keywords: Four Colors Problem, Graph Theory, Map Coloring

vii

Sumário

1 Introdução 1

2 O Problema das Quatro Cores 4

2.1 Mapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Minimal Criminal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 A abordagem de Kempe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.1 Kempe Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.4.2 O erro de Kempe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Complexidade do Teorema das Quatro Cores 23

3.1 Sobre o Método de Kempe . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Definições de Kittell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.3 Solução do Problema das Quatro Cores . . . . . . . . . . . . . . . . . . . . 25

4 Coloração de Mapas na Sala de Aula 26

4.1 Coloração de Mapas I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.2 Análise Combinatória e Probabilidade . . . . . . . . . . . . . . . . . . . . . 27

4.3 Epílogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Conclusões e Trabalhos Futuros 30

Referências 31

viii

Lista de Figuras

1.1 Mapa do Brasil. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1 Países vizinhos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Quatro países vizinhos entre si. . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Três cores necessárias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.4 Quatro cores necessárias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.5 Mapa pizza de 8 fatias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.6 Tabuleiro de xadrez. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.7 Regiões de um mesmo país. . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.8 Região externa como se fosse um país que circunda todas as outras regiões. 7

2.9 Região externa, em azul, sendo o oceano. . . . . . . . . . . . . . . . . . . . 7

2.10 Mapa em duas partes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.11 Mapa unido por um único ponto. . . . . . . . . . . . . . . . . . . . . . . . 7

2.12 Países com um único ponto de fronteira. . . . . . . . . . . . . . . . . . . . 8

2.13 Três linhas limítrofes em cada ponto de encontro. . . . . . . . . . . . . . . 8

2.14 Grafo Planar 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.15 Grafo Planar 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.16 Grafo não Planar pois arestas se cruzam. . . . . . . . . . . . . . . . . . . . 9

2.17 Estados representados por vértices. . . . . . . . . . . . . . . . . . . . . . . 10

2.18 Estados vizinhos ligados por arestas. . . . . . . . . . . . . . . . . . . . . . 10

2.19 Um minimal criminal não pode conter um país com dois vizinhos (umdígono) Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.20 Um minimal criminal não pode conter um país com três vizinhos (umtriângulo) Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.21 Minimal criminal que contém quatro países vizinhos (um quadrado) Wilson(2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.22 Minimal criminal que contém cinco países vizinhos (um pentágono) Wilson(2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

ix

2.23 Encolher um país até um ponto (Wilson, 2002a). . . . . . . . . . . . . . . . 14

2.24 Nenhum minimal criminal pode conter um triângulo Wilson (2002a). . . . 14

2.25 Quadrado e pentágono cercado por quatro cores Wilson (2002a). . . . . . . 15

2.26 Duas situações de ligação entre as partes vermelha-verde acima e verde-vermelha abaixo de S Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . 15

2.27 Parte vermelha-verde acima de S não se ligando à parte verde-vermelhaabaixo de S Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.28 Parte azul-amarela à esquerda de S separada da parte amarela-azul à direitade S Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.29 Caso do país restaurado sendo um pentágono Wilson (2002a). . . . . . . . 17

2.30 Parte amarela-vermelha acima de P não se ligando à parte vermelha-amarelaabaixo de P Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.31 Parte amarela-vermelha acima de P se ligando à parte vermelha-amarelaabaixo de P Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.32 Parte verde-vermelha acima de P não se ligando à parte vermelha-verdeabaixo de P Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.33 Parte verde-vermelha acima de P se ligando à parte vermelho-verde abaixode P Wilson (2002a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.34 Troca de cores da parte amarela-azul à direita de P Wilson (2002a). . . . . 18

2.35 Troca de cores da parte verde-azul à esquerda de P Wilson (2002a). . . . . 19

2.36 Pentágono após as trocas de cores à direita e à esquerda de P Wilson (2002a). 19

2.37 Contra-exemplo de Heawood para a prova de Kempe Wilson (2002a). . . . 20

2.38 Troca de cores da cadeia vermelha-verde acima de P Wilson (2002a). . . . 21

2.39 Troca de cores da cadeia vermelha-amarela abaixo de P Wilson (2002a). . . 21

2.40 Países A e B, vizinhos e coloridos por vermelho Wilson (2002a). . . . . . . 22

3.1 Kittell (1935) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.1 Óleos sobre tela. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

x

Capítulo 1

Introdução

Na história das ciências encontramos diversos problemas que encantam a humanidade aolongo de seu curso. Os mais fascinantes são certamente aqueles de “enunciado simples.”Em razão de sua aparente simplicidade, tais problemas acabam se transformando empassatempos para leigos e desafios para os estudiosos da área à qual o problema pertence.

Para tornar claro o significado que estamos atribuindo ao termo “problema de enun-ciado simples” usaremos dois exemplos da Matemática, a saber: (1) o Último Teoremade Fermat ; (2) o Problema das Quatro Cores. Como veremos, tais problemas podem serenunciados e compreendidos através do uso de linguagem coloquial.

Último Teorema de Fermat

O último teorema de Fermat está relacionado ao problema de se encontrar números inteirospositivos a, b e c tais que para todo número inteiro n maior que 2, a soma das potênciasn de a e b seja c a potência n. Matematicamente esse enunciado é expresso pela equação

an + bn = cn. (1.1)

Em 1637 Pierre de Fermat escreveu no rodapé de um livro ter encontrado uma provanegativa verdadeiramente simples para tal problema mas que tal prova não cabia naquelerodapé. O problema resistiu a todo tipo de investida através dos séculos até que Wiles(1995) apresenta a demonstração que de fato não existem números inteiros positivos cujasoma da n-ésima potência satisfaça a equação (1.1). A demonstração ocupa 140 páginase se baseia na Teoria das Curvas Elípticas e Super-simetria, entre outros conceitos, e nãoé nem um pouco trivial!

Problema das Quatro Cores

Quando colorimos mapas, desejamos que regiões vizinhas tenham cores diferentes paraque as mesmas possam ser identificadas mais facilmente, conforme ilustrado na Fig. 1.1.De forma coloquial, o Problema das Quatro Cores expressa a ideia que mapas, quaisquerque sejam, possam ser coloridos usando no máximo quatro cores distintas.

1

Figura 1.1: Mapa do Brasil.

A primeira referência a este problema data de 1852 e está associado ao matemáticoFrancis Guthrie (cf. May (1965)) e a busca de sua solução se baseia tipicamente naTeoria dos Grafos (Errera, 1921; Kittell, 1935; Krantz, 2007; Morgenstern and Shapiro,1991; Robertson et al., 1997). Na terminologia da Teoria dos Grafos, o Problema dasQuatro Cores expressa o fato que os vértices de todo grafo planar pode ser colorido comno máximo quatro cores de modo que não hajam dois vértices adjacentes com a mesmacor (Calude and Calude, 2010).

Ao longo do tempo, várias tentativas de demonstrar a veracidade do Problema dasQuatro Cores foram feitas mas a primeira prova irrefutável para o problema foi obtidaem 1977 por Appel, Haken e Koch através do uso intensivo de computador (Appel et al.,1977a,b) apud (Calude and Calude, 2010; Wilson, 2002b).

Podemos portanto perceber que há uma grande distância entre a simplicidade naenunciação de problemas e a simplicidade de suas soluções.

Este trabalho tem por objetivo apresentar um levantamento bibliográfico sobre o Pro-blema das Quatro Cores e as tentativas de demonstração para o mesmo. A razão paraisso é que:

• o Problema das Quatro Cores pode ser usado na produção didática pedagógica noensino de tópicos relacionados a matemática, artes e biologia etc. (cf. Pinto (2008));

• a metodologia introduzida em Kempe (1879) pode ser usada para o aprendizadode tópicos relacionados a Teoria dos Grafos, Análise Combinatória e Probabilidade(Pinto, 2008);

• a compreensão de tais tópicos venha a ser usada no desenvolvimento futuro deferramentas computacionais que auxiliem o processo didático-pedagógico presencialou a distância.

2

Para isso, este trabalho está organizado da seguinte maneira. No Capítulo 2 apresentamosas ideias subjacentes a “prova” de Kempe (1879) – posteriormente refutada por Heawood(1890) – onde as posteriormente denominadas cadeias de Kempe foram introduzidas. Ape-sar do erro na demonstração efetuada por Kempe (1879), as cadeias de Kempe podemser utilizadas na base do desenvolvimento de ferramenta didática-pedagógica no ensinode conteúdos considerados difíceis. Como as cadeias de Kempe não bastam para resolvercertas instâncias do Problema das Quatro Cores, o Capítulo 3 introduz as operações deKittell (Kittell, 1935). Neste capítulo apresentamos também, ainda que de forma extre-mamente reduzida, as ideias subjacentes a demonstração computadorizada apresentadaem Appel et al. (1977a,b). O Capítulo 4 apresenta um dois casos de uso do Problemadas Quatro Cores em sala de aula para abordar de forma transversal conteúdos do EnsinoMédio. Em um dos casos foi feita uma experiência com alunos da sexta série do EnsinoFundamental. Por fim, o Capítulo 5 apresenta as conclusões e propõe desdobramentos naforma de trabalhos futuros.

3

Capítulo 2

O Problema das Quatro Cores

O problema de determinar o número mínimo de cores suficientes para se colorir qualquermapa foi formulado pela primeira vez em 1852, pelo jovem matemático Francis Guthrie,quando estava colorindo o mapa dos condados da Inglaterra e conseguiu fazê-lo com apenasquatro cores, sem pintar regiões vizinhas com a mesma cor.

Para iniciarmos o estudo sistemático do Problema das Quatro Cores precisamos res-ponder algumas perguntas tais como: (i) o que é um mapa? (ii) como podemos representá-los?

2.1 Mapas

Pode-se imaginar um mapa como sendo um conjunto de países, ou regiões. Essas regiõespodem ser condados no caso da Grã Bretanha, ou estados no caso do Brasil. As fronteirasde cada estado são indicadas por várias linhas limítrofes, e essas linhas se interceptam emvários pontos de encontro. Dois países com linhas limítrofes em comum são chamados depaíses vizinhos. No mapa da Fig. 2.1, A e B são países vizinhos.

Figura 2.1: Países vizinhos.

Ao se colorir um mapa, deve-se colorir países vizinhos com cores diferentes. Observeque alguns mapas precisam de quatro cores: o mapa da Fig. 2.2 possui quatro países,cada um vizinho dos outros três, sendo assim, necessário colorir cada um deles com umacor diferente, totalizando quatro cores.

4

Figura 2.2: Quatro países vizinhos entre si.

Alguns mapas não precisam de quatro cores. Por exemplo, nos dois mapas da Fig. 2.3,a cadeia externa de países pode ser colorida com duas cores (verde e amarelo), que sealternam quando avançamos na cadeia; o país do centro deve assumir então uma outracor (azul) e assim apenas três cores são necessárias.

Figura 2.3: Três cores necessárias.

Observe que quatro cores pode ser necessário mesmo que quatro países não façamfronteira entre si. No mapa da Fig. 2.4, a cadeia externa de cinco países não pode sercolorida com duas cores alternadamente, necessitando de uma terceira cor. Assim, opaís central precisará de uma cor diferente das outras três presentes na cadeia externa,totalizando então quatro cores.

Figura 2.4: Quatro cores necessárias.

Pode-se fazer ainda mais uma consideração sobre o que é um mapa. Quando duas oumais regiões se tocam apenas por um ponto, pode-se colorí-las com a mesma cor. Essaconvenção é necessária, caso contrário poderíamos construir mapas pizza, que requeremtantas cores quanto regiões existirem. O mapa pizza de 8 fatias da Fig. 2.5 requer oitocores, uma vez que todas as fatias se encontram no centro. Com essa convenção esse maparequer apenas duas cores.

Outro mapa conhecido que necessita de apenas duas cores é o tabuleiro de xadrez.Para cada ponto de encontro entre quatro casas do tabuleiro alterna-se as cores preto ebranco, construindo um tabuleiro de xadrez convencional.

Um atributo interessante e praticamente desconhecido da maioria das pessoas do mapada América do Sul é que a Guiana Francesa é uma parte do país França do qual estáseparada pelo Oceano Atlântico. Dessa forma, as duas regiões deveriam estar coloridoscom a mesma cor. Nesse caso, não há nenhuma dificuldade em colorir o mapa com quatrocores, porém, podem surgir situações em que um país ou estado dividido em duas ou mais

5

Figura 2.5: Mapa pizza de 8 fatias.

Figura 2.6: Tabuleiro de xadrez.

regiões poderá implicar que uma quinta cor seja necessária. Considere um mapa ondeduas regiões coloridas por verde são separações de um mesmo país. Nesse caso, cada umdos cinco países tem uma fronteira em comum com os outros quatro, sendo cinco coresnecessárias como mostra a Fig. 2.7.

Figura 2.7: Regiões 1, em verde, de um mesmo país. O mapa requer cinco cores.

De agora em diante, convenciona-se que não se deseja situações como a acima, e todopaís deve estar contido em apenas uma região. Caso um mesmo país ou região possuaduas ou mais regiões, cada uma será tratada como se fossem regiões distintas, ou seja,poderão assumir cores diferentes.

Algumas pessoas também gostam de incluir a região externa nas suas colorações. Issonão faz diferença, pois pode-se considerar essa região externa como se fosse um país quecircunda todas as outras regiões (vide Fig. 2.8). Se for pensado que o mapa está desenhadonum globo, a região externa é nada mais que uma outra região qualquer, ou o Oceano.

Na verdade, desenhar mapas no plano é equivalente a desenhar mapas num globo, ouna linguagem matemática, na superfície de uma esfera. Dado qualquer mapa numa esfera,pode-se projetá-lo no plano. O inverso também é válido; dado qualquer mapa no plano,pode-se projetá-lo numa esfera.

6

Figura 2.8: Região externa como se fosse um país que circunda todas as outras regiões.

Figura 2.9: Região externa, em azul, sendo o oceano.

É importante ressaltar que essas projeções não afetam as projeções de cores dos mapas.Se duas regiões vizinhas são coloridas por verde e amarelo, depois de sua projeção, noplano ou na esfera, elas continuarão verde e amarela.

É quase desnecessário dizer que um mapa é uma figura contínua e não está separadoem duas ou mais partes, pois pode-se tratar cada parte como parte de um único mapa ecolorí-los separadamente. Similarmente pode-se unir essas partes separadas do mapa poruma fronteira de um único ponto, não afetando a coloração do mapa final. Em particular,deve-se ignorar países com fronteira em apenas um único ponto. Assim, deve-se ignorarmapas como os das Fig. 2.10, 2.11 e 2.12.

Figura 2.10: Mapa em duas partes.

Figura 2.11: Mapa unido por um único ponto.

7

Figura 2.12: Países com um único ponto de fronteira.

Finalmente, pode-se assumir que existem pelo menos três linhas limítrofes em cadaponto de encontro, conforme Fig. 2.13. Se existirem apenas duas linhas em um ponto deencontro, então pode-se remover um ponto sem afetar a coloração.

Figura 2.13: Três linhas limítrofes em cada ponto de encontro.

Na verdade, ao tentar solucionar o Problema das Quatro Cores, pode-se semprerestringir-se a mapas onde existem exatamente três linhas limítrofes em cada ponto deencontro. Esses mapas são muito comuns e possuem um nome especial: mapas cúbicos.

Agora que caracterizamos informalmente a noção de mapas podemos passar a outraquestão, qual seja: Como representá-los? Formalmente, mapas são representados atravésde grafos.

2.2 Grafos

O marco inicial da Teoria dos Grafos ocorreu com a resolução do Problema das Pontes deKognisberg pelo matemático suíço Leonhard Euler, que visitou a cidade das pontes em1736.

Grafos são objetos matemáticos que encontram aplicações nas mais diversas áreasdo conhecimento humano, principalmente por sua simplicidade, seu apelo visual, e poresconder em sua estrutura, princípios combinatórios importantes. Intuitivamente, umgrafo é um conjunto de vértices ligados por arestas (Wilson, 2002a).

Um mapa é um grafo planar1, ou seja, pode ser desenhado em um plano, de talforma que duas arestas não se encontrem, exceto, possivelmente, no vértice em que ambasincidem.

1As Figs. 2.14, 2.15 e 2.16 são reproduções encontradas emhttp://en.wikipedia.org/wiki/File:Butterfly_graph.svg (2010), http://en.wikipedia.org/wiki/File:GoldnerHarary_graph.svg (2010) e http://en.wikipedia.org/wiki/File:Complete_graph_K5.svg (2010)

8

Figura 2.14: Grafo Planar 1.

Figura 2.15: Grafo Planar 2.

Figura 2.16: Grafo não Planar pois arestas se cruzam.

Se G é um grafo planar, então qualquer desenho plano de G divide o plano em regiõeschamadas de faces. Uma destas faces é ilimitada e é chamada de face infinita. Se F é umaface qualquer de G, então o grau de F é o número de arestas encontradas na fronteira deF (se uma aresta é uma ponte, então ela deve ser contada duas vezes) e é denotado pelaletra grega ρ.

Uma maneira de representar um mapa qualquer é construir o seu grafo dual. Seja Mum mapa. Desenhe um vértice no interior de cada face de M e ligue dois vértices comuma aresta se as respectivas faces são vizinhas (isto é, têm alguma aresta em comum).O novo grafo assim obtido é chamado de grafo dual do mapa M (Godinho and Gomes,2006).

A Fig. 2.17 mostra o mapa do Brasil com os estados marcados com um ponto. Essespontos representam os estados enquanto vértices no grafo dual exibido na Fig. 2.18. Noteque as arestas representam as fronteiras entre estados.

9

Figura 2.17: Estados representados por vértices.

Figura 2.18: Estados vizinhos ligados por arestas.

Outras considerações são:

• Um mapa é um grafo planar onde todas as faces tem grau pelo menos igual a três.

• Diz-se que uma aresta de um grafo é uma ponte se a retirada dela deixa o grafodesconexo.

• Um grafo é conexo se existe a possibilidade de sair de qualquer um de seus vérticese chegar à outro, caminhando por sobre as arestas desse grafo.

Tendo visto como podemos transformar um mapa em um grafo, resta-nos agora iniciara discussão de como podemos colorir os vértices usando apenas quatro cores.

2.3 Minimal Criminal

Uma outra maneira de abordar o problema é supor que quatro cores é insuficiente. Seassim for, devem existir mapas que não possam ser coloridos com apenas quatro cores.Entre esses mapas existe algum com o menor número possível de países. Pode-se cha-mar esse mapa de mínimo contra-exemplo, ou minimal criminal já que eles apresentam

10

“comportamentos criminosos” em que não podem ser coloridos com quatro cores, e sãomínimos porque tem a menor quantidade de países possível para possuir cinco ou maiscores. Pode-se ver que:

Um minimal criminal não pode ser colorido com quatro cores, mas qualquer mapa commenos países pode ser colorido com quatro cores.

Para provar que quatro cores é suficiente, deve-se provar que nenhum minimal criminalexiste, e para isso deve-se encontrar mais condições restritivas para aplicar a eles. Naverdade, deve-se dificultar tanto o caso, que eles não possam existir.

Como exemplo, pode-se facilmente mostrar que nenhum minimal criminal pode conterum país com dois vizinhos (um dígono). Para isso, suponha que um minimal criminalcontenha um dígono, como mostrado na Fig. 2.19. Se for possível removermos uma linhade fronteira do dígono, mesclando o dígono com um de seus vizinhos, obtem-se um novomapa com menos países. Pela hipótese, pode-se agora colorir esse novo mapa com quatrocores.

Figura 2.19: Um minimal criminal não pode conter um país com dois vizinhos (umdígono) Wilson (2002a).

Agora restaura-se o dígono, colocando de volta a linha retirada. Uma vez que quatrocores estão disponíveis, e uma vez que os países vizinhos ao dígono usam apenas duasdelas, devem existir uma cor extra para o dígono. Assim, pode-se colorir o minimalcriminal com quatro cores, o que contradiz a hipótese. Assim, mostra-se que um minimalcriminal não pode conter um dígono.

De maneira semelhante, pode-se mostrar que o minimal criminal não pode conter umpaís com três vizinhos (triângulo). Suponha que ele tenha. Remove-se a linha de fronteira,mesclando o triângulo com um de seus vizinhos. Assim, obtem-se um mapa com menospaíses que pode-se colorir com quatro cores, como antes.

Agora, restaura-se o triângulo. Uma vez que os países perto do triângulo usam apenastrês cores, pode-se usar a quarta cor para colorir o triângulo. Assim, colore-se o minimalcriminal com quatro cores, contradizendo a hipótese. Assim, um minimal criminal nãopode conter um triângulo.

O que acontece se tentar estender essas idéias para um minimal criminal que contémum país com quatro vizinhos (um quadrado)? Como antes, remove-se uma linha de

11

Figura 2.20: Um minimal criminal não pode conter um país com três vizinhos (umtriângulo) Wilson (2002a).

Figura 2.21: Minimal criminal que contém quatro países vizinhos (um quadrado) Wilson(2002a).

fronteira, mescla-se o quadrado com um de seus vizinhos e obtem-se um mapa com menospaíses. De novo, pode-se colorir esse novo mapa com quatro cores.

Mas, quando tenta-se restaurar o quadrado, os países vizinhos a ele, podem já terutilizado todas as quatro cores, nesse caso não sobra nenhuma cor extra para colorir oquadrado e a prova não pode proceder como antes.

Um problema similar acontece quando tenta-se estender essa idéia para o minimalcriminal que contém um país com cinco vizinhos (um pentágono). Como antes, remove-se a linha de fronteira, mesclando o pentágono com um de seus vizinhos e obtem-se ummapa com menos países. Como em todos os casos anteriores, esse novo mapa pode sercolorido com menos cores.

Quando se restaura o pentágono, os países vizinhos a ele podem já ter usado todas asquatro cores, não restando nenhuma cor extra para o pentágono. De novo, a prova nãopode proceder.

A seguir, será apresentado como Alfred Kempe superou essas dificuldades quando ominimal criminal contém um quadrado, usando o método de Kempe Chains.

12

Figura 2.22: Minimal criminal que contém cinco países vizinhos (um pentágono) Wilson(2002a).

2.4 A abordagem de Kempe

O interesse de Kempe em coloração de mapas surgiu da pergunta de Cayley no encon-tro da London Mathematical Society. Kempe tinha obtido a solução do problema dasquatro-cores, e em 17 de julho ele publicou uma prévia in Nature. A versão completaapareceu no final do ano, no Volume 2 do American Journal of Mathematics. Em 26 defevereiro de 1880 Kempe publicou versões simplificadas in Nature e o Proceedings of theLondon Mathematical Society, que corrigia alguns pequenos erros no seu artigo originalmas deixava intacto um erro (Wilson, 2002a).

Em uma seção, Kempe derivou uma extensão da fórmula de Euler para mapas, citandoa versão de correspondência planar de Cauchy. A partir daí, ele deduziu a fórmula

5d1 + 4d2 + 3d3 + 2d4 + d5 − . . . = 0

onde cada dk denota o número de regiões com k fronteiras. Uma vez que apenas os cincoprimeiros termos são positivos, ele deduziu que nem todas as quantidades d1, d2, d3, d4 oud5 pudessem ser zero. Esse é o resultado conhecido pelo nome de teorema de "ApenasCinco Vizinhos (Only Five Neighbours Theorem)”.

Usando esse resultado, Kempe então descreveu um método de colorir qualquer mapa,que pode ser resumido em seis passos:

I. Localize um país com cinco ou menos vizinhos (tal país existe, pelo resultado acima).

II. Cubra esse país com um pedaço branco de papel (um remendo (patch)) com o mesmoformato, mas um pouco maior.

III. Extenda todas as fronteiras que alcançam esse remendo e junte-as em um únicoponto dentro do remendo, como na Fig. 2.23, o que resulta em encolher o país atéum ponto. Isso tem o efeito de reduzir o número de países em 1.

IV. Repita o procedimento acima com o novo mapa, continuando até que haja apenasum país sobrando: o mapa todo agora é dito ter sido remendado.

13

Figura 2.23: Encolher um país até um ponto (Wilson, 2002a).

V. Colora o único país remanescente com uma das quatro cores.

VI. Reverta o referido processo, tirando os remendos na ordem inversa, até que o mapaoriginal seja restaurado. Em cada etapa, colora cada país restaurado com qualquercor disponível até que o mapa inteiro esteja colorido com quatro cores (Kempe, 1879;Wilson, 2002a).

Foi tentando prosseguir com esse último estágio que Kempe fez sua maior contribuiçãopara a coloração de mapas. Um problema surge: como pode-se ter certeza que uma dasquatro cores estará disponível quando um país é restaurado? Como foi visto anterior-mente, não há dificuldade se nosso país restaurado tiver no máximo três países vizinhos.Por exemplo, se for um país triangular, então ele é cercado por três países que são co-loridos com apenas três cores; existindo assim uma quarta cor disponível para colorir otriângulo, como mostrado abaixo. Isso mostra que nenhum minimal criminal pode conterum triângulo.

Figura 2.24: Nenhum minimal criminal pode conter um triângulo Wilson (2002a).

Mas se o país restaurado tiver quatro ou cinco fronteiras – se ele for um quadrado oupentágono? Em ambos os casos, o país restaurado pode estar cercado por países que estãocoloridos com todas as quatro cores, como ilustrado abaixo. Assim, não haverá nenhumacor disponível para colorir o quadrado ou pentágono.

2.4.1 Kempe Chains

Para superar essas dificuldades, Kempe introduziu um método agora conhecido comométodo de Kempe Chains ou argumento de Kempe-chain, ou seja, método das Cadeiasde Kempe. Nesse método, olha-se para as cores dos países que cercam o país centrale escolhe-se dois que não sejam adjacentes – por exemplo: vermelho e verde. Olha-se

14

Figura 2.25: Quadrado e pentágono cercado por quatro cores Wilson (2002a).

então apenas para os países que são coloridos com essas cores. O método de Kempe seráilustrado primeiro mostrando como ele lidou com o caso do quadrado (denotado por S),cercado por quatro países de diferentes cores: esse é o caso quando o minimal criminalcontém um quadrado.

Olha-se primeiro para os vizinhos vermelho e verde do quadrado S. Cada um desses é ocomeço para uma parte vermelho-verde do mapa – isto é, uma parte do mapa consistindoapenas de países coloridos por vermelho ou verde. (Apesar de serem chamados de Cadeiasde Kempe, essas partes bicolores do mapa não são geralmente cadeias, mas podem conter‘interrupções’, como nos diagramas que seguem: essas interrupções podem conter umarranjo arbitrário de países. Desde que sejam coloridos corretamente, a sua presença nãoafeta o problema de como será colorido S.)

Agora pergunta-se se essas partes vermelho-verde são separadas umas das outras, ouse elas se unem. Duas situações podem surgir e estão ilustradas na Fig. 2.26.

Figura 2.26: Duas situações de ligação entre as partes vermelha-verde acima e verde-vermelha abaixo de S Wilson (2002a).

Caso 1 Aqui, os países vermelho e verde acima de S que podem ser alcançados pelovizinho vermelho de S não se unem aos países vermelho e verde abaixo de S que pode seralcançado pelo vizinho verde de S. Assim, pode-se alternar as cores dos países vermelhoe verde acima de S, como mostrado abaixo, sem afetar a coloração dos países vermelho everde abaixo de S. O quadrado S então é cercado apenas de cores verde, azul e amarelo,sendo que S pode ser colorido por vermelho. Isso completa a coloração do mapa.

15

Figura 2.27: Parte vermelha-verde acima de S não se ligando à parte verde-vermelhaabaixo de S Wilson (2002a).

Caso 2 Aqui a parte vermelho-verde acima de S une-se a parte vermelho-verde abaixode S. Isso faz os procedimentos um pouco mais difíceis, uma vez que nada é ganhadoalternando as cores vermelho e verde: o vizinho vermelho de S se torna verde, e o vizinhoverde de S se torna vermelho, e a situação do quadrado não fica melhor do que a anterior.

Direciona-se a atenção então para os países azul e amarelo, e para as partes azul-amarelo do mapa à esquerda e direita do quadrado S. Aqui, a parte azul-amarelo à direitade S não se une a parte azul-amarelo à esquerda de S, porque a cadeia de países vermelhoe verde atravessa o caminho.

Figura 2.28: Parte azul-amarela à esquerda de S separada da parte amarela-azul à direitade S Wilson (2002a).

Assim, pode-se alternar as cores dos países azul e amarelo à direita de S sem afetar acoloração dos países azul e amarelo à esquerda de S. O quadrado S é então cercado apenaspelas cores amarelo, vermelho e verde, sendo que S pode ser colorido de azul.

Isso completa a coloração do mapa quando o país restaurado é um quadrado, e mostraque nenhum minimal criminal pode conter um quadrado.

Kempe então voltou suas atenções para o caso quando o país restaurado é um pen-tágono (denotado por P), cercado por cinco países coloridos com quatro cores diferentes.(É nessa parte da prova que encontra-se a falha fundamental).

Ele novamente escolhe duas cores vizinhas que não são adjacentes. Primeiro ele con-sidera os países não adjacentes amarelo e vermelho acima e abaixo de P. Se as partesamarelo-vermelho acima de P não se unem as partes amarelo-vermelho abaixo de P, então

16

Figura 2.29: Caso do país restaurado sendo um pentágono Wilson (2002a).

pode-se alternar as cores dos países amarelo e vermelho acima de P sem afetar a coloraçãodaqueles abaixo de P.

Figura 2.30: Parte amarela-vermelha acima de P não se ligando à parte vermelha-amarelaabaixo de P Wilson (2002a).

O pentágono P é então cercado apenas pelas cores vermelho, verde e azul, sendo queP pode ser colorido de amarelo, completando assim a coloração do mapa para este caso.Tem-se ainda o caso quando a parte vermelho-amarelo acima de P une-se com a partevermelho-amarelo abaixo de P.

Figura 2.31: Parte amarela-vermelha acima de P se ligando à parte vermelha-amarelaabaixo de P Wilson (2002a).

Kempe considerou os países não adjacentes verde e vermelho acima e abaixo de P.Se a parte verde-vermelho acima de P não se une com a parte verde-vermelho abaixo deP, então pode-se alternar as cores verde e vermelho dos países acima de P sem afetar acoloração daqueles abaixo e P.

17

Figura 2.32: Parte verde-vermelha acima de P não se ligando à parte vermelha-verdeabaixo de P Wilson (2002a).

O pentágono é então cercado apenas pelas cores vermelho, amarelo e azul, sendo queP pode ser colorido de verde, completando a coloração de mapas para este caso. Tem-se ainda o caso onde a parte verde-vermelho acima de P une-se a parte verde-vermelhoabaixo de P. Combinando isso ao caso anterior foram-se a Fig. 2.33.

Figura 2.33: Parte verde-vermelha acima de P se ligando à parte vermelho-verde abaixode P Wilson (2002a).

Observa-se que a parte azul-amarelo à direita de P está separada da parte azul-amareloà esquerda de P, porque a cadeia vermelho-verde atravessa o caminho. Pode-se assim,alternar as cores da parte de azul-amarelo à direita de P sem afetar a coloração da parteazul-amarelo à esquerda de P.

Figura 2.34: Troca de cores da parte amarela-azul à direita de P Wilson (2002a).

18

Similarmente, a parte azul-verde à esquerda de P está separada da parte azul-verdeà direita de P, porque a cadeia vermelho-amarelo atravessa o caminho. Pode-se assimalternar as cores da parte azul-verde à esquerda de P sem afetar a coloração da parteazul-verde à direita de P:

Figura 2.35: Troca de cores da parte verde-azul à esquerda de P Wilson (2002a).

Se for feita as duas intercalações, o pentágono P fica cercado apenas pelas cores ama-relo, vermelho e verde, sendo que P pode ser colorido de azul.

Figura 2.36: Pentágono após as trocas de cores à direita e à esquerda de P Wilson (2002a).

Isso completa a coloração de mapas quando o país restaurado é um pentágono, emostra que nenhum minimal criminal pode conter um pentágono.

A abordagem de Kempe não está correta e um contra-exemplo foi apresentado porHeawood (1890).

2.4.2 O erro de Kempe

Kempe usou duas trocas simultâneas de cor para recolorir os países em cada lado dopentágono tal que o pentágono pudesse ser colorido. Cada troca de cor é perfeitamenteválida, mas fazê-las ao mesmo tempo não é permitido.

Para explicar porque essa troca simultânea não é permitida, Heawood introduziu omapa exibido na Fig. 2.37. Nesse mapa, cada um dos vinte e cinco países foram coloridosred, blue, yellow ou green, exceto o pentágono (denotado por P) no meio. Esse mapa

19

certamente pode ser colorido com quatro cores, mas o ponto de Heawood é mostrar queo método de provar de Kempe está incorreto.

Figura 2.37: Contra-exemplo de Heawood para a prova de Kempe Wilson (2002a).

De acordo com Kempe, deve-se tentar recolorir dois vizinhos do pentágono de maneiraque haja uma cor disponível para o pentágono P. Nota-se que os vizinhos azul e amarelo deP estão conectados por uma cadeia azul-amarela de países que separa a parte vermelho-verde acima de P da parte vermelho-verde abaixo de P, como mostra a Fig. 2.38(a).Pode-se assim, alternar as cores da parte vermelho-verde acima de P sem afetar a partevermelho-verde abaixo de P, como mostra a Fig. 2.38(b).

Alternativamente, pode-se fazer uma alternância diferente. Os vizinhos azul e verdede P estão conectados por uma cadeia azul-verde de países que separam a parte vermelho-amarela acima de P da parte vermelho-amarela abaixo de P, como mostra a Fig. 2.39(c).Pode-se assim alternar as cores da parte vermelho-amarela abaixo de P sem afetar a partevermelho-amarela abaixo de P, como na Fig. 2.39(d).

20

Figura 2.38: Troca de cores da cadeia vermelha-verde acima de P Wilson (2002a).

Figura 2.39: Troca de cores da cadeia vermelha-amarela abaixo de P Wilson (2002a).

21

As duas alternâncias são possíveis sozinhas, mas o erro de Kempe foi em tentar fazê-las simultaneamente. Assim, se forem alternadas as cores da parte vermelho-verde abaixode P e da parte vermelho-amarela abaixo de P, então o país verde A e o país amareloB, ambos se tornam vermelhos, o que não é permitido. Assim, a prova de Kempe quepermitia a alternância simultânea de cores, é falsa.

Figura 2.40: Países A e B, vizinhos e coloridos por vermelho Wilson (2002a).

Neste capítulo vimos o histórico do Problema das Quatro Cores numa linha tempocentrada no século XIX. No próximo capítulo focaremos os desdobramentos ocorridos aolongo do século XX e XXI e como foi provada formalmente existir uma solução posi-tiva para o Problema das Quatro Cores. Em função da demonstração, daqui por dianteusaremos os termos Problema das Quatro Cores e Teorema das Quatro Cores de modointercambiável.

22

Capítulo 3

Complexidade do Teorema das QuatroCores

Como vimos, as “soluções” apresentadas ao longo do século XIX baseavam-se na constru-ção de grafos. Sabemos contudo que problemas modelados por grafos podem ser muitodifíceis e isso é corroborado pelos estudos realizados em Complexidade de Algoritmos,desenvolvida a partir dos anos 70 do século XX. Neste capítulo, faremos uma breve apre-sentação das tentativas de prova do Problema das Quatro Cores bem como sua provarealizada por Appel et al. (1977a) e Appel et al. (1977b). Essa prova faz uso intensivo decomputador para verificar a enorme variedade de possíveis configurações de grafos. Umaprova mais recente é apresentada em Gonthier (2008) o qual mapeia o problema a resolu-ção de equações Diofantinas. A demonstração usa o assistente de prova Coq. Terminamoso capítulo apresentando um resultado comparativo entre o Último Teorema de Fermat eo Problema das Quatro Cores(Calude and Calude, 2010).

3.1 Sobre o Método de Kempe

Aparentemente, o método de Kempe funciona nos grafos mais genéricos e falha apenasem condições mais restritas. Isto é, para a prova de Kempe estar certa, faltaram algumasconfigurações específicas para o caso do pentágono resolver a coloração.

De acordo com o método de Kempe, qualquer minimal criminal do pentágono poderiaser solucionado com até duas substituições. Para os casos mais complicados, onde haviaduas cadeias de Kempe ocorrendo sobre os vértices de cores que não se repetiam, elesugeriu que uma das cores que se repetisse, digamos R, fosse substituída por uma cordiferente e de um vértice não adjacente à ela (o que oferece uma única opção), e queo outro vértice R fosse colorido usando a mesma lógica. Assim, ele pensou que tivesseprovado o Problema das Quatro Cores.

23

3.2 Definições de Kittell

Heawood mostrou que o minimal criminal do pentágono, quando não colorido com quatrocores, possui quatro cores A, B, C e D, e apenas uma dessas cores se repete, digamos B, eesse anel do pentágono pode assumir as cores DBABC em ordem. Também foi mostradoque se um mapa é colorido dessa forma, haverá duas cadeias de Kempe que se interceptam,entre A e C, e A e D, respectivamente. Diz-se que um mapa minimamente colorido ounão, que estiver parcialmente colorido pela maneira acima é um impasse (Heawood, 1890).A situação está ilustrada na Fig. 3.1.

Figura 3.1: Kittell (1935)

A Fig. 3.1 não tenta mostrar aonde ou quantas vezes os circuitos A e C, e A e D seinterceptam. A região A é chamada de vertex do anel. É a região no anel que encontra-seentre duas regiões de mesma cor. Denomina-se o circuito AC de circuito esquerdo e ocircuito AD de circuito direito. Denomina-se a cadeia BD que inclui a região B do anelentre A e C de cadeia esquerda e a cadeia BC que inclui a outra região B de cadeia direita.Denomina-se a cadeia CD que inclui as regiões C e D do anel de cadeia tangente terminal;a cadeia BC que toca o anel nas adjacências das regiões B e C de cadeia tangente esquerda;e a cadeia que toca o anel nas adjacências das regiões B e D de cadeia tangente direita.Finalmente, denomina-se a cadeia AB que inclui o vertex, de cadeia osculante.

A Fig. 3.1 serve também de exemplo para a caracterização de nove operações, a saber:

operação significadoα transpor as cores da cadeia esquerdaβ transpor as cores da cadeia direitaγ transpor as cores do circuito esquerdoδ transpor as cores do circuito direitoε transpor as cores da cadeia tangente terminalζ transpor as cores da cadeia tangente esquerdaη transpor as cores da cadeia tangente direitaθ transpor as cores da cadeia osculanteι não alterar as cores

Em todas essas operações, nenhuma cor será atribuída a região externa.

Usando os conceitos definidos por Kittell (1935), fica mais fácil entender onde Kempeerrou. Reescrevendo as condições do problema tem-se: qualquer impasse do pentágonopode ser solucionado com até duas operações. A primeira operação, por estar ocorrendo

24

sobre o vértice que tem a cor que se repete e recebendo uma cor de um vértice de cordiferente e não adjacente, configura a operação α ou β. A segunda operação, se tivesseocorrido antes da primeira, também teria sido do tipo α ou β, mas como não aconteceu, éna verdade γ ou δ, pois o vertex mudou após a primeira operação. E é aí que encontra-sea falha do método de Kempe apontada por Heawood.

3.3 Solução do Problema das Quatro Cores

O Problema das Quatro Cores foi demonstrado em Appel et al. (1977a) e Appel et al.(1977b) baseando seus métodos na redutibilidade usando as cadeias de Kempe. A provacontinha um algoritmo que rodava recursivamente reduzindo o grafo planar Gi, em gra-fos planares menores, Gi+1, de maneira que qualquer quatro-coloração de Gi+1 pudessefacilmente induzir uma quatro-coloração de volta em Gi. Para garantir o sucesso, foramusadas 487 regras de descarte, a investigação manual de cerca de 10000 vizinhanças depaíses com carga positiva, e cerca de 2000 configurações de redução testadas computacio-nalmente (denominadas conjunto completo de reduções), aonde muitas reduções precisa-vam de várias transposições de cores usando Kempe Chains para induzir a coloração deGi+1 em Gi (Morgenstern and Shapiro, 1991; Wilson, 2002a).

Foram encontradas algumas falhas na prova original de Appel e Haken, mas todasforam sanadas. Para entendê-las, era necessário lidar com 50 páginas de textos e diagra-mas, mais 85 páginas com quase 2500 diagramas adicionais e 400 páginas de microfichacontendo mais diagramas e milhares de verificações individuais (Krantz, 2007). Essesfatos e a questão da dificuldade em se acompanhar a prova computacional incita a buscapor novos métodos de prova (Swart, 1980). Nesse sentido, uma prova mais simples, masainda assim usando as mesmas idéias e dependendo de computador, foi publicada em 1997por Robertson, Sanders, Seymour e Thomas. A prova é mais eficiente porque reduziu adificuldade representacional do problema ao requer apenas 633 configurações Neil et al.(1996).

Em 2005, o teorema foi provado por Benjamin Werner e Georges Gonthier utilizandoo software que tem como objetivo geral provar teoremas, Coq, removendo a necessidadede ter que confiar em vários programas computacionais para verificar casos particulares,sendo necessário agora apenas confiar no kernel do Coq (Gonthier, 2008).

Calude and Calude (2010) apresenta uma nova prova baseada na redução a um sistemade equações Diofantinas. A prova é feita com o uso do Coq. Usando uma metodologiade classificação para exprimir a dificuldade de problemas apresentada em Calude et al.(2006), Calude and Calude (2010) apresentam uma comparação entre problemas. Deacordo com os autores, o Último Teorema de Fermat está na classe CU,1, a Hipótese deRiemann está na classe CU,3 e o Problema das Quatro Cores está na classe CU,4.

25

Capítulo 4

Coloração de Mapas na Sala de Aula

A coloração de grafos é uma abstração da coloração de mapas e dessa forma perguntastais como “De quantas maneiras pode-se colorir um mapa de um estado, usando apenas ncores, de forma que municípios com fronteira comum tenham cores distintas?” podem serpropostas durante um processo de aprendizagem (cf. Bria (2004); Lozano et al. (2010);Pinto (2008)). Na verdade, o tema “coloração” pode ser conduzido de modo transversale servir de base para a iniciação ao estudo de tópicos considerados não triviais em áreastais como Computação, Matemática, Física, Artes, entre outras.

4.1 Coloração de Mapas I

Segundo Bria (2004), o uso de grafos no Brasil é tema inédito no que diz respeito a Edu-cação Básica sendo o assunto muitas vezes desconhecido por parte dos professores tantodo nível Fundamental quanto do Médio. O tema, entretanto, possui vasta aplicabilidadeem função das inúmeras possibilidades de modelagem no que tange situações-problemasdo cotidiano. De acordo com Lozano et al. (2010), o estudo da Teoria dos Grafos e suasaplicações apesar de fundamental ao mundo atual ainda não foi incluído nos cursos delicenciatura em Matemática e por essa razão não está incluído na estrutura curricular doEnsino Fundamental e Médio. Em função de sua aplicabilidade, caráter combinatório,algébrico e algoritmico, Teoria dos Grafos é um tema que pode ser utilizado no ensinopré-universitário.

Uma experiência nesse sentido é relatada em Lozano et al. (2010) a qual usa colo-ração de mapas e grafos como ferramenta. Nessa experiência, as atividades da oficinade coloração foram agrupadas em dois blocos de quatro atividades cada, resumidas naTabela 4.1.

Segundo os autores, o objetivo do primeiro bloco é trabalhar o Problema de Coloraçãode Mapas e o do segundo bloco o Problema de Coloração em Grafos. As oficinas – duas– foram realizadas na escola E. E. Pio X – São José do Rio Preto – SP, sendo uma paraa 2a série do Ensino Médio e outra para a 6a série do Ensino Fundamental. A oficina doEnsino Médio ocupou duas aulas consecutivas de 50 minutos cada enquanto a outra durousessenta minutos. Nas considerações finais, Lozano et al. (2010) concluem que o tempo

26

Tabela 4.1: Divisão das atividades da oficina.

Bloco I Bloco IIAtividade 1: Coloração de

mapasAtividade 5: Associar a cada mapa proposto um grafo

Atividade 2: Questionário Atividade 6: Problema de coloração de vértices de umgrafo

Atividade 3: Problema daHerança

Atividade 7: Problema dos Químicos

Atividade 4: Teorema dasQuatro Cores

Atividade 8: Avaliação final

de duração das atividades do Bloco I é suficiente para os alunos do Ensino Médio poréminsuficiente para os alunos do Fundamental. Os autores relatam o sucesso da experiênciaem passar a ideia da importância de estratégias para a resolução de problemas bem comorever o processo de resolução quando uma resposta não é alcançada e que nem semprerecomeçar é a melhor alternativa.

4.2 Análise Combinatória e Probabilidade

Em Pinto (2008) encontramos o relato de um projeto realizado em Paranavaí, Paraná, noColégio Estadual Prof. Bento Munhoz da Rocha Neto. Nesse projeto, a autora usou – emsuas próprias palavras – “O Problema de Guthrie como metodologia no ensino da AnáliseCombinatória e Probabilidade” em uma classe do Ensino Médio. O conteúdo em questãoé típico da disciplina de Matemática mas a autora usou o Tratamento da Informaçãocomo estruturador interdisciplinar entre Matemática, Arte e Biologia. Os experimentosocorreram durante o 1o semestre de 2009 e usaram como base as seguintes perguntas:

1. É possível colorir estas regiões do mapa, utilizando apenas quatro cores, mas respei-tando a condição de que regiões que possuem linhas de fronteiras comuns tenhamcores diferentes?

2. O conceito usado para este caso pode ser estendido à outros mapas?

Segundo a autora, a relação entre o problema proposto e a Matemática é induzir noaluno a busca por conceitos e técnicas que venham a resolver tal situação; neste caso,Teoria dos Grafos, apesar deste tópico não ser contemplado no currículo do Ensino Médio(cf. Lozano et al. (2010).)

O problema de coloração induz perguntas do tipo “De quantas maneiras pode-se coloriro mapa das regiões do estado do Paraná, usando apenas quatro cores, de forma quemunicípios com fronteira comum tenham cores diferentes?”

27

Para responder a esta pergunta a autora interoperou arte e matemática o que levou anecessidade de se conhecer algumas características relativas às cores. Para tanto, a autorausou quadros do artista plástico Roberto Pereira da Silva1 como o mostrado na Fig. 4.1.

Figura 4.1: Óleos sobre tela.

Em sua abordagem transversal ao assunto a autora recorre a colorimetria como aciência que estuda os métodos de quantificação da cor e tom, saturação e intensidade.Remete ainda a espectroscopia de Newton através da decomposição através de um prismada luz branca nas sete cores do arco-íris. Associa ainda noções tais como quantidade deluz (saturação), reflexão (luminosidade) e emissão de luz (brilho) as sensações emocionais,aos tipos de cores (primárias, secundárias, terciárias), cores quentes, frias e neutras e assimpor diante.

Para alcançar seu objetivo, a autora propõe inicialmente a atividade de coloração defiguras usando apenas quatro cores mas obedecendo a restrição de que espaços comparti-lhando segmentos de reta tenham cores distintas. As figuras propostas eram abstraçõesdas bandeiras dos estados do Acre, Alagoas, Paraná, Amazonas, Bahia e a projeção deum tetraedro em um plano. Na sequência, usa problemas de genética exemplificados pela:

• herança de cabelo crespo;

• codificação da cor dos olhos da Drosophila Melanogaster cujo gene pode apresentartrinta e dois alelos.

A autora termina o relatório retomando o problema inicial da coloração dos municípiosdo Paraná. Nas páginas 13 e 14, figuras 14, 15, 16 e 17, a autora exemplifica o númerode possíveis colorações para as 10 regiões usando o princípio multiplicativo para concluirque teríamos 1.296 possibilidades de colorir o mapa ((Pinto, 2008)).

1Roberto Pereira da Silva, Persil, é pintor parnavaiense e já expôs seus trabalhos em inúmeras expo-sições por várias cidades brasileiras. Em 2006 foi reconhecido internacionalmente com o projeto Arte naEscola. Persil é também professor da rede pública de ensino do Estado do Paraná.

28

4.3 Epílogo

Conforme apontado por Lozano et al. (2010) é escassa a literatura quanto ao uso daTeoria dos Grafos no Ensino Fundamental e Médio. Este capítulo procurou sintetizar asduas experiências realizadas. De comum, as duas experiências deixam claro que o usoda Coloração de Grafos é uma valiosa ferramenta no ensino de tópicos Combinatória,Probabilidade, Física, Artes, Biologia.

29

Capítulo 5

Conclusões e Trabalhos Futuros

Este trabalho procurou identificar as abordagens que tratam do Problema das QuatroCores, proposta em 1852 por Francis Guthrie, enfocando as principais abordagens para asua solução. Para tanto, um amplo levantamento bibliográfico foi realizado e apresentadonesta monografia.

Vimos que dentre as tentativas de solução mais famosas destaca-se a de Alfred BrayKempe apresentada em 1879, refutada posteriormente pelo contra-exemplo de Heawood.Independente do erro apresentado por Heawood, a “prova” de Kempe introduziu um mé-todo, as cadeias de Kempe, amplamente usado posteriormente para coloração de ma-pas/grafos. O capítulo 2 apresentou as cadeias de Kempe de forma sucinta porém didá-tica.

Como as cadeias de Kempe não solucionam a coloração de todos os tipos de mapasusando apenas quatro cores, o capítulo 3 apresentou as operações de Kittell as quais podemser usadas na funtamentação de uma metodologia didático-pedagógica para o ensino detópicos tais como Análise Combinatória. Uma ressalva deve ser feita neste momento:não de nossa parte nenhuma implicação que as operações de Kittell, ou qualquer outraabordagem aparentemente “simples” possam resolver o Problema das Quatro Cores. Naverdade, o capítulo 3 fecha mostrando a dificuldade deste problema colocando-o em termoscomparativos com outros dois problemas amplamente conhecidos.

Por fim, o capítulo 4 apresentou de modo simplificado uma maneira pela qual usar asoperações de Kittell na proposição e resolução de problemas.

Como trabalhos futuros, esperamos que o material apresentado nesta monografia possaconstituir a base para o desenvolvimento de uma metodologia didático pedagógica trans-versal para que a mesma possa ser usada em áreas que não apenas aquelas relacionadasa Computação e a Matemática.

30

Referências

K. Appel, W. Haken, and J. Koch. Every planar map is four colourable, i: Discharging.Illinois J. Math., 21(21):429–490, 1977a. 2, 3, 23, 25

K. Appel, W. Haken, and J. Koch. Every planar map is four colourable, ii: Reducibility.Illinois J. Math., 21(21):491–567, 1977b. 2, 3, 23, 25

Jorge Bria. Conheça grafos: Interdisciplinaridade e contextualização. In Anais VIIIEncontro Nacional de Educação Matemática, jullho 2004. CD-ROM. 26

Cristian S. Calude and Elena Calude. The complexity of the four colour theorem.LMS Journal of Computation and Mathematics, 13:414–425, 2010. doi: 10.1112/S1461157009000461. 2, 23, 25

Cristian S. Calude, Elena Calude, and M. J. Dinneen. A new measure of the difficulty ofproblems. Journal of Multi Valued Logic Software Computing, 12:285–307, 2006. 25

Alfred Errera. Du Coloriage des Cartes et de Quelques Questions d’Analysis Situs. PhDthesis, Gauthier-Villars, Paris, 1921. 2

Hemar Godinho and O. R. Gomes. Teoria dos grafos. Pasta 145 da Fotocopiadora daUnB, Universidade de Brasília, Brasília - DF, Maio 2006. 9

Georges Gonthier. Formal proof – the four-color theorem. Notices of the AmericanMathematical Society, 55(11):1382–1393, 2008. 23, 25

Percy John Heawood. Map-colour theorem. Quarterly Journal of Mathematics, 24:332–338, 1890. 3, 19, 24

http://en.wikipedia.org/wiki/File:Butterfly_graph.svg, Julho 2010. 8

http://en.wikipedia.org/wiki/File:Complete_graph_K5.svg, Julho 2010. 8

http://en.wikipedia.org/wiki/File:Goldner Harary_graph.svg, Julho 2010. 8

A. B. Kempe. On the geographical problem of the four colours. American Journal ofMathematics, 2(3):193–200, 1879. 2, 3, 14

Irvin Kittell. A group of operations on a partially colored map. Bulletin of the AmericanMathematical Society, 41:407–413, 1935. x, 2, 3, 24

Steven G. Krantz. The four-color problem: Concept and solution. PDF, October 2007.2, 25

31

Daniele Lozano, Socorro Rangel, and Célia Pires. Uma Proposta de Oficina de Coloraçãode Mapas e Grafos para o Ensino Fundamental e Médio. Revista Eletrônica PesquisaOperacional para o Desenvolvimento, 2(3):216–225, 2010. 26, 27, 29

Kenneth O. May. The origin of the four-color conjecture. Isis, 56:346–348, 1965. 2

Craig A. Morgenstern and Henry D. Shapiro. Heuristics for rapidly four-coloring largeplanar grahs. Algorithmica, 6:869–891, 1991. 2, 25

Robertson Neil, Daniel P. Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. Proceedings of the twenty-eighth annual ACM symposium onTheory of computing, 28:571–575, 1996. 25

Oystein Ore. The Four-Color Problem. Academic Press, New York - London, 1967. vi,vii

Neuza Pinto. O problema de guthrie como metodologia no ensino da análise combinatóriae probabilidade. Technical report, UEM/FAFIPA, Paranavaí–Pr, 2008. 2, 26, 27, 28

Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. The Four-ColourTheorem, volume 70 of B. Journal of Combinatorial Theory, Maio 1997. 2

E. R. Swart. The philosophical implications of the four-color problem. The AmericanMathematical Monthly, 87(9):697–707, November 1980. 25

Andrew Wiles. Modular Elliptic Curves and Fermat’s Last Theorem. The Annals ofMathematics, 141(3):pp. 443–551, 1995. ISSN 0003486X. URL http://www.jstor.org/stable/2118559. 1

Robin Wilson. Four Colors Suffice: How the Problem was Solved. Princeton UniversityPress, Princeton, New Jersey, 2002a. ix, x, 8, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,22, 25

Robin Wilson. Four Colors Suffice. Penguin Books, London, 2002b. 2

32