Problema do carteiro chinês

UNIVERSIDADE CATÓLICA DO SALVADOR
CIÊNCIAS EXATAS E TECNOLOGIA
CURSO DE INFORMATICA

Problema do Carteiro Chinês

Aluno(a)s:
.
.
.
.

Profa. .

SALVADOR - BA
2011
.
.
.
.

Problema do Carteiro Chinês

Trabalho apresentado a Universidade Católica do Salvador, como parte de requisito de avaliação da disciplina Teoria dos Grafos, do curso de Informática sobre a orientação da Professora .

SALVADOR - BA
2011

1. Introdução

Iniciando –se de e uma simples pergunta “A fim de minimizar a distância total que o carteiro percorre, como deverá ser a sua rota de forma que ele passe por todas as ruas ao menos uma vez ? Essa questão é conhecida como o Chinese Postman Problem, nome derivado do fato de ter sido no jornal Chinese Mathematics em 1952 a primeira vez em que esse problema foi discutido. A história desse problema é bastante interessante. No século XVIII, os moradores da cidade russa de Königsberg queriam realizar um desfile que pudesse passar pelas sete (Figura 1) pontes sobre o rio Prevel apenas uma vez e passaram o problema para o matemático suíço Leonhard Euler resolver . No entanto, Euler provou que era impossível encontrar uma solução, pois, ao transformar o mapa em um grafo, onde as ilhas e o continente são os vértices e as pontes arestas, conforme ilustra a figura abaixo, notou que os vértices possuíam grau ímpar.

Figura 1.1 Representação da Setes Pontes de Konigsberg

Figura 1.2 Grafo da Setes Pontes de Konigsberg

É iniciado o marco no estudo da teoria dos grafos. Conhecido como Problema do Carteiro Chinês, discutiremos, nesse trabalho, algumas maneiras de encontrar soluções em diferentes, situações, tais como grafos orientados, não o orientados e mistos.

2. O Problema do Carteiro Chinês