Grafos de arestas


Suponhamos que temos um bairro com uma planta como se mostra abaixo. Um dado profissional tem de efectuar uma distribuição (ou recolha ou leitura ou controle) pelas caixas assinaladas a amarelo nos passeios (carteiro, lixeiro, contador, controlador de parcómetros,...). Para estudar percursos do profissional não interessa considerar ocomprimento das ruas e a sua largura é irrelevante. Só interessa as arestas a percorrer e os vértices que elas ligam, mas ao profissional não importam os vértices. De facto só lhe interessam as arestas que tem de palmilhar.

A um grafo ligado a uma situação deste tipo é que damos o nome de grafo de arestas. O grafo que serve de modelo à situação do profissional é

ou mais simplesmente:

Para apoiar a decisão relativamente a situações do tipo descrito, é preciso encontrar o caminho mais económico para realizar o controle em causa, isto é, é preciso encontrar, caso exista, um caminho que permita percorrer todas as arestas sem repetir qualquer delas ou, caso não exista, encontrar um caminho que considere o mínimo de repetições de arestas. Mais: na generalidade e dado que qualquer agente precisa de um ponto de apoio (onde deixe o carro patrulha, ou o carro com o correio de uma zona mais ampla do que cada uma das partes em estudo...) é preciso encontrar um circuito, um caminho que, partindo de um ponto e voltando ao ponto de partida percorra todas as arestas, sem repetir qualquer delas ou repetindo um mínimo delas (caso não seja possível evitar as repetições).


voltar ao sumário