Problema Carteiro Chines

[Andryas]

Lendo sobre uma solução classica para resolver o problema do carteiro chines, encontrei os seguintes passos:

O problema do carteiro chines fornece um grafo e pede para achar o menor caminho saindo de um vertice e voltando para ele.É preciso passar por todas as arestas pelo menos uma vez.

Solução 2: Se o grafo nao for de Euler, algumas arestas terao que ser repetidas.Uma forma de resolver é acrescentando arestas artificiais ao grafo original de forma a obter um novo grafo G'=(V,E´). Isto deve ser feito de maneira que as arestas artificias acrescentadas transformem todos os vertices de grau impar de G, em verticies de grau par. As arestas artificiais correspondem aos eventuais percursos repetidos de custo minimo entre pares de vertices de grau impar.

Determinando as combinacoes possiveis de vertices de grau impar, interligando-os com arestas artificiais, formando grafos expandidos, contendo somente vertices de grau par.

Apos isso selecione o grafo G = (V,E) expandido que apresentar a menor extensão total de arestas artificiais.

Depois determine um roteiro de euler para o Grafo G = (V,E)

Nao entendi o ultimo passo. Uma vez que eu obti o grafo expandido com apenas vertices pares, se eu localizar o caminho de euler dele estarei passando por uma aresta inexistente no grafo original.Como faço para localizar a aresta que devera ser repetida caso o grafo original nao tenha caminho de Euler.

[Andryas]

upandooooooooooooo