O problema das quatro cores

O problema das quatro cores

Imagine um mapa político desenhado no plano, com países que fazem fronteira entre si. Quantas cores são necessárias para colorir o mapa de modo que dois vizinhos nunca tenham a mesma cor? A intuição diz que pode ser preciso muitas, mas a resposta é surpreendente: bastam quatro.

Do mapa ao grafo

Para estudar o problema, troca-se cada país por um ponto (um vértice) e cada fronteira entre dois países por uma linha (uma aresta). O resultado é um grafo. Colorir o mapa é o mesmo que colorir os vértices de modo que vértices ligados tenham cores diferentes. O menor número de cores que faz isso é o número cromático do grafo.

Na aula, o mapa de 10 regiões é o grafo de vizinhança de um mapa desenhado sem cruzamentos. K4 é o caso extremo entre os mapas: cada região é vizinha das outras três, e por isso precisa de 4 cores. K5 não é planar, então não pode ser o grafo de um mapa desenhado no plano; ainda assim, ele mostra que nem todo grafo precisa de 4 cores: precisa de 5.

Uma conjectura de estudante

Em 1852, Francis Guthrie notou que quatro cores bastavam para os mapas do condado inglês onde estudava. Ele perguntou ao irmão, que levou a questão a De Morgan. Desde então, a pergunta ficou conhecida como a conjectura das quatro cores.

Um século de tentativas

Durante mais de cem anos, matemáticos tentaram provar a conjectura e erraram. Em 1879, Kempe publicou uma prova que pareceu correta por uma década, até que Heawood encontrou uma falha em 1890. Ainda assim, a parte útil da ideia de Kempe, corrigida por Heawood, mostrou que cinco cores bastam para qualquer mapa.

A prova com computador

Em 1976, Kenneth Appel e Wolfgang Haken provaram o teorema. A estratégia foi reduzir todos os mapas possíveis a um conjunto finito de configurações (cerca de 1.900, no artigo original), e um computador verificou cada uma delas. Foi um dos primeiros grandes teoremas provados com ajuda de máquina, e a discussão sobre o que conta como prova continua até hoje.

Como a aula calcula

A coloração com k cores é testada por backtracking: coloca-se uma cor em cada região, em ordem, e volta-se atrás sempre que um vizinho já colorido tem a mesma cor. Para grafos pequenos, isso encontra a melhor coloração possível. O painel mostra o número cromático, χ, do grafo escolhido.

Note que o teorema garante que 4 cores bastam para grafos planares, mas não diz que o número cromático é sempre 4. Muitos mapas precisam de menos.

Aplicações

• Alocação de frequências: antenas vizinhas não podem usar a mesma frequência; é um problema de coloração.
• Horários: provas ou aulas que compartilham alunos não podem ocorrer no mesmo horário.
• Compiladores: a alocação de registradores do processador é uma coloração do grafo de interferência entre variáveis.

Curiosidade

A solução de Appel e Haken não foi aceita de imediato por todos, porque ninguém conseguia verificar as configurações à mão. Até hoje se busca uma prova curta que possa ser conferida à mão, e nenhuma é conhecida.

Perguntas de revisão

1. Quantas cores bastam para colorir qualquer mapa planar?

Resposta: quatro. Três não bastam para todos os mapas.

1. Como Appel e Haken provaram o teorema em 1976?

Resposta: reduzindo os mapas a um número finito de casos que o computador verificou.