Problema do Carteiro Chinês
Problema do Carteiro Chinês
Um carteiro tem de fazer a distribuição da correspondência em determinada
localidade. Será que consegue fazê-lo e regressar ao posto dos correios, passando
uma única vez em cada rua? Caso não seja possível, qual é o caminho mais curto
(o que repete menos ruas)?
A solução ótima para este tipo de problemas obtém-se quando o grafo que traduz a
situação admite um circuito de Euler.
Problema do Carteiro Chinês
Trajeto de Euler (ou euleriano) – é uma sequência de vértices e arestas de um
grafo, que percorre todas as arestas uma única vez.
Circuito de Euler (ou euleriano) – é um trajeto euleriano que começa e acaba no
mesmo vértice.
Problema do Carteiro Chinês
Para identificar:
Regra 1 – Num grafo conexo podemos encontrar um trajeto de Euler se e só se
existirem, no máximo, dois vértices de grau ímpar. Tal trajeto começa sempre num
dos vértices de grau impar e termina no outro vértice de grau impar.
Regra 2 – Um grafo conexo admite um circuito de Euler se e só se todos os
vértices tiverem grau par.
Problema do Carteiro Chinês
A
Exemplo: Dado o grafo conexo,
B
Vamos calcular o grau de cada vértice:
C
A: 3
B: 4
C: 3
D: 4
D
E
E: 4
Como tem apenas dois vértices de grau ímpar podemos dizer que é possível
encontrar neste grafo um trajeto de Euler mas não um circuito.
Problema do Carteiro Chinês
A
B
Exemplo: Dado o grafo conexo,
G
Vamos calcular o grau de cada vértice:
A: 2
B: 4
C: 4
D: 2
E: 4
F: 4
F
E
C
G: 4
D
Como os vértices têm todos grau par podemos dizer que este grafo tem um circuito
de Euler.
Problema do Carteiro Chinês
A
Exemplo: Dado o grafo conexo,
B
C
Vamos calcular o grau de cada vértice:
G
D
A: 2
B: 3
C: 3
D: 5
E: 2
F: 3
G: 5
H: 3
H
E
F
Como tem mais do que dois vértices de grau ímpar podemos dizer que não é
possível encontrar neste grafo nem um trajeto nem um circuito de Euler.
Problema do Carteiro Chinês
Para resolver problemas do tipo do Carteiro Chinês, temos de encontrar forma de
conseguir “eulerizar a situação”, isto é, repetindo o mínimo de arestas possível, conseguir
definir um circuito de Euler.
Eulerizar grafos – Consiste em acrescentar arestas a um grafo de forma a tornar possível
encontrar nele um circuito de Euler.
Regra – Para se adicionarem arestas corretamente é preciso que o número de repetições de
arestas seja igual ao número de arestas acrescentadas.
Problema do Carteiro Chinês
A
Vamos eulerizar
X
B
Uma vez que os vértices de grau
ímpar
são
A
e
C
C
poderíamos
acrescentar uma aresta de A para C,
mas não respeitaria a regra.
D
E
Assim acrescentamos uma aresta de A para B, e outra de B para C.
Agora todos os vértices têm grau par, logo é possível encontrar um circuito de
Euler neste grafo.
Problema do Carteiro Chinês
A
Vamos eulerizar
B
C
Uma vez que os vértices de grau
ímpar são B, C, D, F, G e H podemos:
- acrescentar uma aresta de B para C;
- acrescentar uma aresta de D para G;
G
D
H
E
F
- acrescentar uma aresta de H para F.
Agora todos os vértices têm grau par, logo é possível encontrar um circuito de
Euler neste grafo.