O problema do carteiro chinês (parte 1)

Apresentamos o problema do carteiro chinês em sua formulação básica, em que existem apenas dois vértices u e v de grau ímpar no grafo não Euleriano de entrada G. O primeiro passo consiste na duplicação das arestas do caminho mínimo entre u e v, de modo a transformar G em um grafo Euleriano G*. O segundo passo consiste na extração de um circuito Euleriano a partir no novo grafo G*.