Portal de Periódicos da CAPES

O problema do Carteiro Chinês: Modelagens e Métodos de Solução

2018; Volume: 6; Issue: 2 Linguagem: Português

2359-0793

Drielly Alves de Carvalho, Michelli Maldonado,

Graph Theory and Algorithms

Conta a historia que os habitantes da cidade de Konigsberg (atual Kaliningrado), antiga capital da Prussia Oriental, viviam em quatro ilhas ligadas por sete pontes. Os moradores tinham a seguinte duvida, Sera que era possivel fazer um caminho que passe por todas as pontes uma unica vez, e retornar ao local de partida? O problema foi resolvido por Leonhard Euler em 1735, que afirmou ser impossivel tracar um caminho que passe uma unica vez por cada ponte e, no final, tenha atravessado todas elas. Euler mostrou isso, elegantemente propondo algumas condicoes para que fosse possivel a resolucao do problema e acredita-se que assim surgiu a Teoria dos Grafos. ( [3]) Considere a seguinte situacao, os pontos representam casas de uma cidade, e as linhas representam os possiveis caminhos entre essas casas. Se um carteiro tem que visitar cada uma dessas casas entregando suas cartas, o ideal seria que ele conseguisse passar uma unica vez por cada caminho e voltasse ao ponto de origem. Quando esse problema e levado para a Teoria dos Grafos e possivel descrever as possiveis solucoes e propor os melhores caminhos para o carteiro. Esse problema, em Teoria dos Grafos, e classico e conhecido como o Problema do Carteiro Chines (PCC) ( [4]). Segundo [5], e um dos mais antigos problemas da teoria de grafos. Tal solucao e circuito e e denominado de Euleriano, pelo fato de Euler ter sido o primeiro a reportar um estudo sobre a sua determinacao, no ano de 1736, como descrito acima. O PCC e um problema de otimizacao que tem como objetivo cobrir com um percurso de todos os arcos do grafo, minimizando a distancia total percorrida. O percurso do carteiro distingui-se do circuito (ou ciclo) Euleriano por nele ser permitida, se necessario, a repeticao de arestas. Claramente no caso do grafo possuir circuitos Eulerianos, tais circuitos solucionam o problema. A classificacao variada dos diversos tipos de problemas de percursos em arcos, abrevia-se no interesse deste trabalho, as principais abordagens do Problema do Carteiro Chines sao: Problema do Carteiro Chines Nao Direcionado (PCCND), o Problema do Carteiro Chines Direcionado (PCCD); e o Problema do Carteiro Chines Misto (PCCM). O PCC pode ser usado em situacoes praticas como: servicos de varricao de ruas por equipamentos mecanicos; de remocao de neve das vias, de aspersao de sal em vias como Bolsista PET