Figura 10.4
Grafo de rede para o circuito da Figura 10.2. A cor dos nodos representa a cor das redes. O gráfico tem
cores de modo que nenhum vértice tenha a mesma cor. O teorema de Heawood garante colorir sem
repetição de cor no vértice, mas com 12 cores.Deixe-me explicar essa escolha, que é parcialmente pragmática.
Em princípio, poderia haver curtos-circuitos conectados a redes não adjacentes. No
entanto, quase todos esses curtos-circuitos deveriam também conectar-se a redes adjacentes,
graças ao modo como os circuitos são construídos. No processo de fabricação típico, a
máquina trabalha sobre a placa em duas etapas: uma para imprimir as conexões horizontais,
outra para imprimir as verticais. Os erros ocorrem quando a máquina aplica um excesso de
material condutor, ligando acidentalmente duas redes que deveriam permanecer
desconectadas: vou chamar tal erro de “defeito de fabricação”. Existem outras maneiras
possíveis de criarmos curtos-circuitos, gerando placas defeituosas, mas são muito mais raras
que os defeitos de fabricação, portanto podemos ignorá-las.
Como as conexões são impressas na forma de linhas horizontais ou verticais, qualquer
defeito de fabricação deverá criar alguma ligação indesejada entre duas redes adjacentes. A
linha extra de material condutor poderá correr através de diversas outras redes, mas as duas
primeiras que ligar serão necessariamente adjacentes (Figura 10.5). Em outras palavras,
podemos detectar defeitos de fabricação buscando curtos-circuitos entre redes adjacentes.
Nesse sentido, as arestas do grafo de redes correspondem aos possíveis erros de fabricação. A
condição que determina que não haverá redes intermediárias simplifica o grafo, mas não perde
de vista os demais erros possíveis: em vez de procurar todos os curtos-circuitos, procura
apenas os curtos-circuitos “mínimos”.
Já falei anteriormente que o grafo cujos vértices são formados pelos componentes das
placas têm espessura 2 — uma para cada lado da placa. O grafo de redes também tem
espessura 2, pelo mesmo motivo. Também mencionei um teorema demonstrado por Percy
Heawood: qualquer grafo de espessura m poderá ser colorido com 6m cores. Com m = 2,
deduzimos que qualquer grafo de espessura 2 poderá ser colorido com 12 cores. Isto é, cada
vértice pode receber uma dentre 12 cores, de modo que vértices unidos por uma aresta sempre
tenham cores diferentes. Portanto, o teorema de Heawood determina que o grafo de redes de
qualquer placa pode ser colorido com 12 cores. Podemos transferir essa coloração
(conceitualmente) às redes da placa. Assim, cada uma das redes pode receber uma das 12
cores de modo que não existam redes adjacentes com a mesma cor.