diversão inocente (e bastante despropositada), mas tem utilidades muito sérias — como
veremos no próximo capítulo. Por ora, vou apenas apresentar a ideia e explicar brevemente
sua matemática.
Imagine que o planeta Terra foi dividido em países separados que possuem, cada um, uma
região de terra e mar. Além disso, cada país terráqueo anexou uma região na Lua, criando um
império formado por duas regiões: uma na Terra, outra em seu satélite. Essas regiões cobrem
completamente a superfície de cada um dos mundos. Qual é o menor número de cores com as
quais poderemos colorir um mapa que represente qualquer disposição de territórios, de modo
que os dois territórios de qualquer império recebam a mesma cor, e que regiões adjacentes
sempre tenham cores diferentes — tanto na Terra como na Lua?
Não sabemos a resposta: ela é 9, 10, 11 ou 12. É um problema divertido, ainda que
extremamente artificial.
Será um produto inútil de intelectuais presos numa torre de marfim?
De maneira alguma.
Em 1993, Joan P. Hutchinson, da Faculdade Macalester, em St. Paul, Minnesota, publicou
uma pesquisa meticulosa sobre essas questões na Mathematics Magazine. Numa seção do
artigo, ela descreveu uma aplicação do problema da coloração de mapas Terra/Lua ao teste de
circuitos impressos, descoberta por pesquisadores dos Bell Labs, da AT&T, em Murray Hill.
A conexão entre os dois temas não é nem um pouco óbvia, mas fácil de entender. Os conceitos
que utiliza são interessantes para os matemáticos recreativos e, de toda forma, merecem ser
mais bem divulgados. O primeiro deles é a chamada “espessura” de um grafo.
Neste capítulo descreverei a matemática dos mapas, impérios e grafos, explicando no que
consiste a “espessura”. No próximo, vamos dar uma olhada em sua aplicação aos circuitos
impressos eletrônicos.
Um mapa é um arranjo de regiões, seja no plano ou numa superfície como a da esfera.
Cada região é uma única porção contínua do plano ou da superfície, e as regiões fazem contato
entre si por meio de fronteiras comuns, que são curvas. Muitas vezes temos pressupostos
adicionais — por exemplo, o de que nenhuma região está inteiramente cercada por outra.
Um grafo é um diagrama formado por diversos pontos, chamados vértices ou nodos,
unidos por linhas chamadas arestas. Os grafos são mais simples e abstratos que os mapas.
No entanto, podemos representar qualquer mapa designando um vértice a cada região e
unindo dois vértices por uma aresta, se e somente se as regiões correspondentes tiverem uma
fronteira comum (Figura 9.1). Imagine os vértices como as capitais dos países e as arestas
como rodovias que unem as cidades de países adjacentes, cruzando sua fronteira comum. Esse
é o grafo do mapa, que representa as regiões com fronteiras comuns, desconsiderando
diversas complicações que trariam distrações para a análise, como os formatos das regiões.
Em muitos casos os formatos não importam, sendo assim mais fácil nos livrarmos deles
completamente — daí o grafo do mapa.
Dizemos que um grafo é planar se puder ser desenhado no plano sem que ocorra nenhum
cruzamento de arestas. Se começarmos com um mapa no plano, seu grafo será obviamente
planar. Mais surpreendente é o fato de que, se o mapa for desenhado numa esfera, ou em
diversos planos e esferas desconectados — como no caso dos mapas Terra/Lua —, o grafo
resultante ainda será planar. Para entender por que, imagine um mapa desenhado numa esfera.
Ponha um vértice em cada região, e sempre que duas regiões tiverem uma fronteira comum,
conecte os vértices correspondentes com arestas. O resultado é um grafo que pode ser
desenhado numa esfera na qual não ocorrem cruzamentos de arestas. Porém, qualquer grafo
como esse poderá ser aberto e estendido sobre um plano. Para fazer isto, imagine que
recortamos um pequeno buraco na esfera, que não esteja ocupado por nenhum dos vértices ou