O Problema do Caixeiro Viajante

                

Desafio 10

[pic 1]

1. Ciclo Hamiltoniano (Problema do Caixeiro viajante):

Primeiramente devemos especificar o que é o ciclo Hamiltoniano para então ver sua aplicação no problema do caixeiro viajante e outras definições.

O ciclo Hamiltoniano é um circuito em que um grafo conexo é um circuito que contém todos os vértices do grafo. Um grafo hamiltoniano possui um circuito hamiltoniano.

Entendendo que, um grafo G é constituído de um conjunto V não-vazio de objetos, chamados vértices (ou nós), e um conjunto A de pares não ordenados de elementos de V, chamados de arestas. Denotamos o grafo pôr G(V,A) ou simplesmente G.

Algumas considerações que devem ser feitas para se considerar um ciclo hamiltoniano são:

1. Arestas paralelas e laços não podem pertencer a um circuito hamiltoniano;
2. Se um vértice possui grau 2, as arestas a ele incidentes devem pertencer ao circuito hamiltoniano;
3. Nenhum subcircuito próprio, isto é um circuito que não possui todos os vértices de G, pode ser formado durante a construção do circuito hamiltoniano;
4.  Uma vez incluído o vértice, todas as arestas a ele incidentes e que não foram inseridas no circuito podem ser desconsideradas.

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, digamos que 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?

Partindo da cidade 1(A), temos n − 1 escolhas para fazer.

Em seguida, a partir da segunda cidade, temos n − 2 arestas para escolher; e assim por diante até a escolha da última aresta.

Ou seja, há (n − 1)! possibilidades; e se considerarmos que as rotas possíveis ((4-1)! =6) teremos que os caminhos seguintes são possíveis:

ABCDA, ABDCA, ACBDA, ACDBA, ADBCA e ADCBA.

Porém metade dessas possibilidades seguem o mesmo percurso a única diferença é que segue de forma contrária, mas seguindo os mesmos vértices. Os circuitos {a, b, c, d, a} e {a, d, c, b, a}, são um exemplo:

[pic 2]

No caso então teremos que o número total de circuitos é dado por (n − 1)!/2.

Ou no caso (4-1)!/2=3 rotas possíveis.

Se neste exemplo colocássemos valores nas rotas, por exemplo a quantidade de km percorridos ou valor que custa por km teríamos somente uma resposta com o menor custo ou menor caminho, como a seguir os números indicando a quantidade de km a perseguir entre as cidades, teríamos:

[pic 3]

Para as rotas válidas:

• ABCDA (5+4+7+3) = ADBCA (5+3+7+4) =19km;
• ACBDA (8+4+6+3) = ADBCA (3+6+4+8) =21km;
• ABDCA (5+6+7+8) =ACDBA (8+7+6+5) =26km.

Ou seja a que teria o menor percurso seriam as rotas ABCDA (5+4+7+3) = ADBCA (5+3+7+4) =19km.

1. Ciclo Euleriano (Problema do Carteiro Chinês):

        Um gráfico G apresenta um ciclo Euleriano se as arestas e vértices do grafo forem percorridos uma única vez e o ponto final for igual ao vértice que iniciou o trajeto. Já o caminho Euleriano é o percurso na qual só se percorre uma vez a aresta e o vértice, mas não retorna ao ponto inicial.

        Existem dois teoremas para que se possa determinar se um grafo apresenta um ciclo Euleriano:

Teorema: Um multigrafo M é euleriano, se e somente se, M é conexo e cada vértice de M tem grau par.

Um multigrafo G que tenha uma trilha contendo todas as arestas de M. Logo G é um grafo cruzável e a trilha é chamada de trilha euleriana.

O teorema a seguir indica rigorosamente quais grafos são cruzáveis:

Teorema: Um multigrafo M é cruzável se e somente se M é conexo e tem exatamente dois vértices de grau ímpar. Por conseguinte, qualquer trilha euleriana de M começa em um dos vértices de grau impar e termina no outro vértice de grau ímpar.

Ou seja :

• Teorema 1: o grafo G terá um ciclo Euleriano se, e somente se, todos os vértices apresentem grau par;
• Teorema 2: o grafo G não será Euleriano se, e somente se, existir dois ou mais vértices com grau ímpar.

Um por problemas mais antigos e que deu fundamento a esse problema foi o da cidade de Königsberg. Esta cidade é cortada por um rio e há duas ilhas nele, elas são conectadas por 7 pontes. O problema enfrentado Euler foi o seguinte: qual é o caminho que percorre todas as pontes, mas que não seja repetido nenhuma rua e ponte. Neste problema, ainda não foi resolvido.