Figura 10.2
Uma placa eletrônica simples. Os círculos são orifícios para os componentes, os quadrados são
componentes. Grupos de quadrados conectados são redes.A maneira mais óbvia de fazê-lo é verificar todos os pares de redes em busca de conexões.
O método mais simples utiliza um “aparelho de teste”, com o qual se cria um circuito que
corre de uma rede ao pólo positivo de uma bateria, e do pólo negativo, passando por uma
lâmpada, a uma segunda rede (Figura 10.3). Se as duas redes estiverem inadvertidamente
conectadas pelos trilhos da placa, haverá fluxo de corrente e a lâmpada se acenderá. Do
contrário, a lâmpada permanecerá apagada. É claro que um aparelho real usaria uma eletrônica
mais sofisticada — como um computador ligado a um robô que descarte automaticamente as
placas defeituosas, sem lâmpada nenhuma —, mas essa é a ideia básica.
Infelizmente, essa abordagem não é prática. Com n redes, o método precisa realizar n(n -
1)/2 testes — o número de pares de redes. Como uma placa típica tem 500 redes, estamos
falando de 125.000 testes por placa, um número totalmente impraticável. Vou agora convencê-
lo de que, aplicando o conceito da espessura do grafo, podemos reduzir rapidamente o número
de testes a apenas 11. Na verdade, pensando um pouco mais, é possível reduzir esse número a
apenas quatro. Dessa forma, podemos testar todas as placas com rapidez e eficiência, de modo
a descartarmos as que tiverem curtos-circuitos acidentais.