Implementação computacional do problema do carteiro chinês

uma abordagem algorítmica para otimização de rotas em grafos não-eulerianos

Resumo

O Problema do Carteiro Chinês (PCC) constitui um dos problemas fundamentais da teoria dos grafos e otimização combinatória, com aplicações práticas em logística, planejamento urbano e sistemas de distribuição. Este trabalho apresenta uma implementação computacional para resolução do PCC em grafos não-eulerianos, utilizando algoritmos de emparelhamento mínimo e busca de caminhos mais curtos. A metodologia proposta foi aplicada a um grafo exemplo de 12 nós representando um sistema de ruas urbanas, onde foram identificados 6 nós com grau ímpar. Através da aplicação do algoritmo de emparelhamento de peso mínimo, foi possível transformar o grafo não-euleriano em um grafo euleriano com um custo adicional de apenas 8 unidades, representando um aumento de 12,7% no peso total do grafo original. Os resultados demonstram a eficácia da abordagem algorítmica proposta, permitindo a obtenção de um circuito euleriano que percorre todas as arestas do grafo pelo menos uma vez, minimizando o custo total da travessia. A implementação desenvolvida em Python utilizando as bibliotecas NetworkX e Matplotlib fornece uma ferramenta robusta para análise e visualização de soluções do PCC, contribuindo para o avanço das técnicas de otimização em problemas de roteamento.