Matematica discreta

Turma: MATEMÁTICA DISCRETA (CCT0025/1309240) 3001

Data de entrega: 27/11/2013

Para elaboração desta atividade, utilize o Template disponibilizado no Sistema Acadêmico .

TÍTULO DA ATIVIDADE ESTRUTURADA: Análise do problema do Caixeiro Viajante

O problema do caixeiro viajante é um problema que deve fazer parte da bagagem de todo profissional competente da área matemática e computacional. Sua importância resume-se em duas capacidades: de modo simples e concreto, exemplifica a enorme velocidade de crescimento da fatorial ; prova-se que muitos problemas combinatórios envolvem tantas alternativas de solução quanto este problema, de modo que ele é uma espécie de "metro" com o qual medimos a complexidade computacional dos problemas combinatórios ocorrendo em engenharia e no trabalho científico. (Disponível em http://www.mat.ufrgs.br/~portosil/caixeiro.html . Acesso em 07.11.2013)
Formulando o problema do caixeiro

Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.

Exemplificando o caso n = 4: se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve considerar poderia ser: saia de A e daí vá para B, dessa vá para C, e daí vá para D e então volte a A. Quais são as outras possibilidades ? É muito fácil ver que existem seis rotas possíveis:
ABCDA
ABDCA
ACBDA
ACDBA
ADBCA
ADCBA
Resolução: -> Seja um grafo G completo, tal que cada aresta e possui um peso c(e) maior ou igual a zero. Um percurso de caixeiro viajante é simplesmente um ciclo hamiltoniano (um caminho que contenha cada vértice do grafo uma vez) de G. O peso de um percurso é a soma dos pesos das arestas que o formam. Um percurso de caixeiro viajante ótimo é