- 10 –
Impérios e a eletrônica
Se para você o capítulo anterior não passou de uma abstração absurda, sem
nenhuma aplicação concebível, pense novamente. Essa abstração leva a um método
incrivelmente eficiente para testarmos circuitos eletrônicos em busca de curtos-
circuitos. Enquanto o método óbvio exige a execução de centenas de milhares de
testes, o método baseado nos impérios lunares requer menos de uma dúzia.No capítulo anterior, analisamos diversos problemas de coloração de mapas, relacionando-
os aos grafos: diagramas nos quais unimos pontos chamados “vértices” por meio de linhas
chamadas “arestas”. Uma boa ideia matemática possui muitas interpretações diferentes no
mundo real. Embora os problemas ligados à coloração de mapas pareçam frívolos, a
matemática subjacente a eles é útil na indústria e no comércio. Em particular, o conceito da
“espessura” de um grafo, ao qual fomos levados pelo cenário improvável dos mapas de
impérios na Terra e na Lua, encontrou recentemente sua utilidade na fabricação de circuitos
eletrônicos. Vou descrever agora essa aplicação, descoberta por pesquisadores dos Bell Labs
da AT&T, em Murray Hill. É utilizada no teste de placas de circuito impresso para localizar
curtos-circuitos e é incrivelmente eficiente, reduzindo uma quantidade impraticável de testes,
digamos, 125.000, a apenas quatro.
Lembre-se que um grafo é planar se puder ser desenhado no plano sem que ocorram
cruzamentos de arestas. Depois dos grafos planares vêm os de espessura 2 — aqueles cujas
arestas podem ser separadas em dois conjuntos tais que cada um deles, contendo todos os
vértices, seja planar. Um grafo tem espessura 3 se suas bordas puderem ser separadas em três
conjuntos como esse, e assim por diante. Você pode pensar num grafo de espessura 2 como
uma espécie de “sanduíche”. Numa fatia de pão, desenhamos as arestas do primeiro conjunto,