Carteiro Chinês

Curso Bacharelado em Informática

Carteiro Chinês (PCC)

Salvador
2014

Carteiro Chinês (PCC)

Este trabalho destina-se ao cumprimento de créditos da disciplina de Teoria dos Grafos.

Salvador
2014

1 - INTRODUÇÃO

O propósito deste trabalho é abordar caminhos fechados em grafos, caminho eurelianos e hamiltonianos. E explorar algumas de suas propriedades.
Abordar ainda o problema do menor caminho, partindo-se de um vértice inicial específico para outro vértice final, também especificado a priori.
Mostrar o que consiste o estudo do Carteiro Chinês (PCC) e os Problemas nele existente. Viabilizando minimizar a distância total percorrida por um carteiro em seu roteiro de entregas procurando o caminho mais curto ou circuito fechado de tal forma que o carteiro passe por todas as arestas do grafo (conectado) não-direcionado.
Quando o grafo possui um circuito euleriano esse circuito é uma solução ótima.

2 - CAMINHOS

Caminho é qualquer sequência de arestas onde o vértice final de uma aresta é o vértice inicial da próxima. Assim, na figura (1), as sequências de arestas {e1, e6, e3, e4}, {e6, e3, e4}, {e2, e3, e4, e5}, {e1, e2, e3, e4, e5} são exemplos de caminhos.
As sequências de arestas acima poderiam ser escritas também na forma de sequencias de vértices, como {v2, v1,v3,v4,v5}, {v1,v3,v4,v5}, {v2, v3,v4,v5,v1}, {v1, v2,v3,v4,v5, v1}. Como um caminho de k vértices é formado por (k-1) arestas v1v2, v2v3,..., vk-1 vk, diz-se que o valor (k-1) é o comprimento do caminho.
Se todos os vértices do caminho são distintos, então a sequência recebe o nome do caminho simples.

Fig. (1)

Um ciclo é um caminho fechado, isto é, uma sequência formada e v1v2, v2v3,..., vk-1 vk, vkv1 e k ≥ 3.
Se o caminho fechado for simples, então o ciclo é dito simples.
Um grafo que não possui ciclo é dito ser acíclico.

3 -