Uma Aplicação de Coloração de Grafos em Testes de Placas de Circuitos Impressos

An Application of Graph Coloring to Printed Circuit Testing
“Uma Aplicação de Coloração de Grafos em Testes de Placas de Circuitos
Impressos”

I.

Introdução

O artigo escolhido analisa problemas de coloração de grafos para minimizar o número de testes elétricos realizados em placas de circuitos(grids), afim de encontrar falhas decorrentes do processo de fabricação e instalação dos circuitos elétricos. As placas de circuitos(grids) são compostas por vários micro pontos de conexões elétricas alinhados horizontal e verticalmente, divididas simetricamente numa área retangular de tamanho finito, onde diferentes componentes são instalados.
Os micro pontos de conexão chamaremos de Nodes. Cada Node tem a opção de se conectar a quatro outros Nodes, chamaremos essas opções de Line-of-Sight desse
Node, que pode ter tamanho fixo ou variado. O Line-of-Sight condutor, chamaremos de
Grid Segment. O conjunto de Nodes e Grid Segments, que representam o conjunto de ligações elétricas de um caminho do circuito, é chamado de Net, representado pelo conjunto N, com n elementos. Nets num mesmo Grid formam o conjunto Net Pattern, representado pelo conjunto P. O caminho condutor que é indesejado, que não deveria ter sido feito(falha), é chamado de Short Circuit ou simplesmente Short e conecta dois
Nets. O esquema abaixo simplifica o entendimento:

Net A + Net B + Net C = Net Pattern (P)
Net A

Net B

A

Net C
B

C

Grid

Nodes
Line-of-Sight
Grid Segment
Short Circuit

Os pares de Nets que são testados afim de se encontrarem as falhas são chamados de Supernets, representados pelo conjunto S, subconjunto de N, com k elementos. No nosso exemplo teríamos três Supernets a serem testados: AB, BC e AC.
Porém, logo percebemos que o teste no Supernet AC não precisa ser realizado, pela

localização dos mesmos no Grid. Esse Supernet AC, é considerado Non Critical Pair.
Os outros Supernets do exemplo, são considerados Critical Pairs.
Nosso objetivo