3 5 e 3 6 (1)

Prévia do material em texto

Tópicos 3.5 e 
3.6
Livro: Grafos - Uma Introdução
Tiago Antônio Modolo Ronchi
2021
3.5 Grafos e Ciclos Hamiltonianos
Um problema aparentemente similar ao dos grafos eulerianos é o de procurar 
em G uma trilha fechada que passe por todos os vértices uma e só uma vez.
Grafo:
● Euleriano - trilha fechada de comprimento m 
● Semieuleriano - trilha aberta de comprimento m
 
● Hamiltoniano - ciclo que passa por todos os vértices de G
● Semihamiltoniano - caminho que passa por todos os vértices de G
3.5 Grafos e Ciclos Hamiltonianos
3.5 Grafos e Ciclos Hamiltonianos
O nome homenageia Sir Willian R. Hamilton, que estudou e divulgou o 
problema – embora a primeira formulação tenha sido feita por Kirkman em 
1885. 
Around the world
3.5 Grafos e Ciclos Hamiltonianos
3.5 Grafos e Ciclos Hamiltonianos
3.5 Grafos e Ciclos Hamiltonianos
As semelhanças, entretanto, param por aqui. O problema de saber se um grafo 
é ou não hamiltoniano é um dos mais estudados da teoria dos grafos por sua 
aplicabilidade em comunicação, transporte e planejamento. Entretanto, até 
hoje, nenhuma condição necessária e suficiente elegante para que um grafo 
seja hamiltoniano foi encontrada. Na verdade, todos os teoremas se encontram 
muito longe de oferecer uma previsão razoável de solução
3.6 O Problema do Caixeiro Viajante - PCV
O PCV é um dos problemas mais estudados no campo da pesquisa 
operacional, mas até hoje não foi encontrado um algoritmo 
computacionalmente eficiente para resolvê-lo. 
Sua formulação é simples: dado um grafo completo valorado G, desejamos 
determinar o valor do menor ciclo hamiltoniano de G.
3.6 O Problema do Caixeiro Viajante - PCV
Uma solução óbvia seria analisar todas as permutações dos vértices, que nos 
dariam todos os ciclos possíveis, no caso em questão teríamos 6! = 720 
permutações possíveis (esse caso é uma permutação circular).
Porém, assim como visto no tópico 3.2 “Estrutura de Dados”, para grafos de 
muitos vértices essa solução torna-se inviável até mesmo para os 
computadores com maior capacidade de processamento do mundo.
3.6 O Problema do Caixeiro Viajante - PCV
O que fazer então?
Procurar a resposta através de algoritmos heurísticos, que usa uma ideia 
razoável, mas que não garante que a melhor solução seja encontrada.
● “Algoritmo Guloso”;
● “Arestas de menor valor geral”.
3.6 O Problema do Caixeiro Viajante - PCV
Notamos que nos dois algoritmos heurísticos, embora o ciclo seja válido, o valor 
obtido não é o melhor possível, uma vez que o menor ciclo possível teria valor de 
2092.
É claro, se tivermos que examinar o PCV para 20 cidades teríamos que examinar 
cerca de 20! permutações e já vimos que este é um número muito grande. Pior ainda, 
não foi descoberto até o momento um algoritmo eficiente para este problema (como 
no caso euleriano, em que o teorema de Euler nos salvou). E, ainda pior, os cientistas 
da computação acreditam que ele pertença a uma classe de problema para os quais 
não há uma solução “elegante”. Vamos falar um pouco sobre isto adiante.