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

Autores

  • Drielly Alves de Carvalho
  • Michelli Maldonado

Resumo

Conta a história que os habitantes da cidade de Konigsberg (atual Kaliningrado), antiga capital da Prússia Oriental, viviam em quatro ilhas ligadas por sete pontes. Os moradores tinham a seguinte dúvida, Será que era possı́vel fazer um caminho que passe por todas as pontes uma única vez, e retornar ao local de partida? O problema foi resolvido por Leonhard Euler em 1735, que afirmou ser impossı́vel traçar um caminho que passe uma única vez por cada ponte e, no final, tenha atravessado todas elas. Euler mostrou isso, elegantemente propondo algumas condições para que fosse possı́vel a resolução do problema e acredita-se que assim surgiu a Teoria dos Grafos. ( [3])
Considere a seguinte situação, os pontos representam casas de uma cidade, e as linhas representam os possı́veis 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 única vez por cada caminho e voltasse ao ponto de origem. Quando esse problema é levado para a Teoria dos Grafos é possı́vel descrever as possı́veis soluções e propor os melhores caminhos para o carteiro. Esse problema, em Teoria dos Grafos, é clássico e conhecido como o Problema do Carteiro Chinês (PCC) ( [4]).
Segundo [5], é um dos mais antigos problemas da teoria de grafos. Tal solução é circuito e é denominado de Euleriano, pelo fato de Euler ter sido o primeiro a reportar um estudo sobre a sua determinação, no ano de 1736, como descrito acima. O PCC é um problema de otimização que tem como objetivo cobrir com um percurso de todos os arcos do grafo, minimizando a distância total percorrida. O percurso do carteiro distingui-se do circuito (ou ciclo) Euleriano por nele ser permitida, se necessário, a repetição de arestas. Claramente no caso do grafo possuir circuitos Eulerianos, tais circuitos solucionam o problema. A classificação variada dos diversos tipos de problemas de percursos em arcos, abrevia-se no interesse deste trabalho, as principais abordagens do Problema do Carteiro Chinês são: Problema do Carteiro Chinês Não Direcionado (PCCND), o Problema do Carteiro Chinês Direcionado (PCCD); e o Problema do Carteiro Chinês Misto (PCCM). O PCC pode ser usado em situações práticas como: serviços de varrição de ruas por equipamentos mecânicos; de remoção de neve das vias, de aspersão de sal em vias como Bolsista PET

Downloads

Não há dados estatísticos.

Downloads

Publicado

2018-12-19

Edição

Seção

Resumos