Eulerizar um grafo (10)
(que não admita um circuito de Euler)

Agora vejamos o que o teorema de Euler nos pode informar acerca da possibilidade de vigilância dos parcómetros de três blocos residenciais de um bairro, representados por pontos na figura seguinte:
 
A figura (b) representa o grafo correspondente, em que só representamos os passeios por onde o agente tem de passar. Este grafo tem duas valências ímpares e, por isso, de acordo com o teorema de Euler, o grafo não admite um circuito de Euler.
Nestas condições, ficamos a saber que vai ser preciso que algumas arestas sejam percorridas mais do que uma vez num giro do agente, o problema agora será procurar que o comprimento das arestas a repetir seja o mínimo possível. Este tipo de problema que consiste em minimizar o comprimento de um circuito por uma escolha criteriosa de quais as arestas a repetir é conhecido pelo problema do carteiro chinês (tal como para os roteiros de vigilância de parcómetros, também os roteiros das distribuição postal devem ser eficientes). O problema foi estudado pelo matemático chinês Meigu Guan em 1962; daí o nome. Embora a teoria do circuito de Euler não trate directamente com arestas repetidas ou arestas de diferentes comprimentos, podemos ampliar essa teoria para ajudar a resolver o problema do carteiro chinês. Vamos dedicar-nos à resolução deste problema, discutindo aplicações para além do controle dos parcómetros.
 
Num problema do carteiro chinês realista, precisamos de considerar os comprimentos dos passeios, ruas ou o que quer que seja que as arestas representem, dado que queremos minimizar o comprimento total das arestas repisadas. Contudo, para simplificar as coisas à partida, podemos supor que todas as arestas têm o mesmo comprimento. (A isto chamaremos o problema do carteiro chinês simplificado). Neste caso, precisamos tão só de contar as arestas a repetir e não precisamos de nos preocupar com os seus comprimentos. Resolver o problema simplificado é encontrar um circuito que considere todas as arestas e que tenha o mínimo de arestas repetidas.
 
Para seguir o processo que vamos desenvolver, consideremos o grafo (a) da figura serguinte, que é o mesmo grafo (b) da figura anterior, mas que tem os vértices designados por letras.


Este grafo não admite um circuito de Euler, mas há um circuito que tem só uma aresta repetida (CG), a saber ABCDHGCGFEA. Representamos este circuito, desenhando no nosso grafo inicial uma nova aresta GC. Duplicar a aresta CG equivale a repeti-la. Fazemos isso, acrescentando uma aresta extra ao nosso grafo que ligue os dois vértices que já estão de facto unidos pela aresta que teríamos de repetir ou duplicar. (Não é boa ideia repetir caminhos sobre a mesma aresta ). Deste modo, criamos o grafo (b) da figura. Este novo grafo já pode ser percorrido como um circuito de Euler. O circuito está representado em (c)da figura. Assim a nossa teoria terá por base esta ideia, a saber:
 
1. Tome-se o grafo dado e acrescentem-se arestas, por duplicação das existentes até que se obtenha um grafo conexo e só com valências par. A este processo chamamos eulerização de um grafo, porque o grafo que produzimos admite um circuito de Euler. Nos nossos grafos, as arestas que juntamos desenhamo-las a cor diferente, para as distinguir das arestas originais (o que constitui um sistema razoável para ajudar a lembrar quais e quantas arestas foram duplicadas na eulerização.)
 
2. Descobrir um circuito de Euler no grafo eulerizado.
 
3. Depois disso já pode sobrepor-se este circuito de Euler do grafo eulerizado sobre o grafo original, repetindo as arestas do grafo original cada vez que o circuito no grafo eulerizado usa uma aresta acrescentada.

voltar ao sumário