sem nenhum cruzamento; na segunda fatia desenhamos as demais arestas, novamente sem
nenhum cruzamento. Os vértices formam o recheio (Figura 10.1). Um grafo que precisa de e
fatias de pão tem espessura e.
Essa imagem esclarece a relevância dos grafos e suas espessuras para os circuitos
eletrônicos. Para começar, pense num circuito eletrônico também como um grafo. Os vértices
são os componentes eletrônicos e as arestas são as conexões elétricas. Se o circuito impresso
for construído num dos lados de uma placa, deverá ser planar para evitar curtos-circuitos. Se
usarmos os dois lados da placa — como as duas fatias de pão no sanduíche —, obtemos grafos
de espessura 2. Usando várias placas podemos aumentar a espessura do grafo. Considerações
semelhantes também se aplicam ao mundo hipertecnológico dos chips de silício, porque os
circuitos VLSI (da sigla em inglês para Circuitos Integrados em Alta Escala) precisam ser
construídos em camadas.
Figura 10.1
Um grafo K 5 completo com cinco vértices representado como um sanduíche. Cada fatia do pão é um grafo
planar, e os vértices, o recheio. O grafo K 5 surge se o sanduíche for visto de cima, sobrepondo as duas
fatias.Uma placa típica possui um arranjo de 100 × 100 orifícios — os números exatos variam
— aos quais podemos ligar componentes. Tais orifícios são unidos por linhas verticais ou
horizontais que podem ser recobertas com “trilhos” de material condutor que conectam os
componentes. Um problema sério para os fabricantes de placas é detectar as que trazem
conexões incorretas — porções adicionais de trilhos que resultam na ligação elétrica de
componentes que deveriam permanecer isolados.
Por questões práticas, os fabricantes dispõem os componentes de uma placa em “redes”.
Uma rede é uma coleção de componentes conectados por trilhos que não formam voltas
fechadas (Figura 10.2). Numa placa bem construída, redes diferentes não devem se conectar
eletricamente. O problema que nos interessa é determinar, de maneira eficiente, se ocorreu a
ligação acidental de redes distintas por algum pedaço de trilho — um “curto-circuito”.