Figura 10.3
Teste para curto-circuito entre a rede vermelha e a rede verde.O ponto de partida para esses aprimoramentos consiste em transformar a estrutura da placa
num grafo. A ideia é definirmos o grafo mais simples que nos forneça informações sobre
curtos-circuitos entre as diferentes redes: vamos chamá-lo de grafo de redes do circuito. O
critério de simplicidade torna a construção do grafo de redes um pouco mais sutil. Por
exemplo, como estamos tentando descobrir se existem ou não curtos-circuitos entre as
diferentes redes, não faz sentido pensarmos em cada vértice do grafo de redes como um
componente individual do circuito. Em vez disso, associamos cada vértice a uma rede. As
arestas do grafo representam os curtos-circuitos possíveis, e não reais — pois se soubéssemos
onde estão os verdadeiros curtos-circuitos, não precisaríamos testar o circuito. Para ser mais
preciso, uniremos dois vértices do grafo de redes por uma aresta sempre que as redes
correspondentes forem “adjacentes” — ou seja, sempre que puderem ser conectadas por linhas
retas horizontais ou verticais que não atravessem nenhuma outra rede intermediária (Figura
10.4).