Cientista da Computação

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
COORDENAÇÃO DE BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO
CURSO SUPERIOR DE BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO

BERNARDO HENRIQUE OLBERTZ NETO
GABRIEL DE ANDRADE SILVA

RELATÓRIO – CAMINHOS HAMILTONIANOS

PONTA GROSSA
2013
BERNARDO HENRIQUE OLBERTZ NETO
GABRIEL DE ANDRADE SILVA

RELATÓRIO – CAMINHOS HAMILTONIANOS

Orientador: Sheila de Morais de Almeida

PONTA GROSSA 2013
1.Introdução

Para que o conceito de caminhos hamiltonianos esteja claro, dependemos de conceitos básicos que servem de alicerce para o assunto, tais conceitos são passeio, trilha e caminho. Tais definições foram abordadas em aula, todas repassadas e posteriormente apresentadas para a turma em apresentação. Um caminho hamiltoniano é um problema que serve de base para muitos outros problemas, de modo que sua definição é um tanto quanto básica. Demonstraremos algoritmos que podem ser usados para percorrer em grafos e identificar se existem caminhos hamiltonianos, porém o problema dos caminhos hamiltonianos é NP-Completo, deste modo, abordaremos brevemente sobre estes. Richard M. Karp foi de grande importância nesta parte, pois conseguiu provar que alguns problemas eram NP completos, inclusive, dois referentes a caminhos hamiltonianos.

2. Definições

As definições necessárias para que seja abordado caminhos hamiltonianos são de passeio, trilha e caminho.

2.1 Passeio

Definição: O passeio em um grafo G, entre vértices quaisquer, que podem ser v0 e vk, é toda sequência de vértices da forma:

W : v0, v0v1, v1,...,vk-1, vk-1vk, vk Possuem livre repetição de vértices e arestas. Neste exemplo, os vértices v0 e vk são os extremos do passeio (onde v0 é o inicio e vk o final). Desta forma diz-se que W é um passeio de v0-vk. Tendo a figura a seguir:

Vemos um exemplo de passeio, onde partindo de qualquer vértice, podemos ficar infinitamente