Grafos Hamiltonianos: Teoria e Exercícios

Grafos Hamiltonianos Teoria dos Grafos 20232 Prof Roberto C de Araujo Teoria dos Grafos 20232 1 Caminhos e Circuitos Hamiltonianos Um caminho hamiltoniano em um grafo G é um caminho que contém todos os vértices de G Exercício O grafo abaixo tem um caminho hamiltoniano Justifique Um circuito hamiltoniano em um grafo G é um circuito que contém todos os vértices de G Exercício O grafo anterior tem um circuito hamiltoniano Justifique Exercício O grafo abaixo tem um circuito hamiltoniano Justifique Exercício O grafo abaixo tem um caminho hamiltoniano Justifique 2 Grafos Hamiltonianos Um grafo G é hamiltoniano se G contém um circuito hamiltoniano Ao contrário do que ocorre com os grafos eulerianos não se conhece nenhum teorema poderoso que caracterize precisamente os grafos hamiltonianos Isto é não existe nenhum teorema da forma um grafo G é hamiltoniano sse G tem tal propriedade Dispomos de teoremas como esses abaixo em geral eles são baseados em se um grafo G tiver MUITAS arestas então G é hamiltoniano Teorema Se G é um grafo hamiltoniano então para todo subconjunto próprio SVG o número de componentes do grafo GS é menor que S Teorema Dirac 1952 Se G é um grafo simples com VGn e gvn2 para todo vVG então G é hamiltoniano Teorema Ore 1960 Se G é um grafo simples com VGn 3 tal que para quaisquer vértices distintos e não adjacentes u e v gugvn então G é hamiltoniano Teorema Bondy Chvátal 1976 Seja G é um grafo simples de ordem n 3 e sejam u e v vértices não adjacentes tais que gugvn Então G é hamiltoniano sse Guv é hamiltoniano Apesar de se tratar de um problema importante e útil em muitas aplicações práticas não se conhece nenhum algoritmo eficiente para obter um circuito hamiltoniano em um grafo Qualquer solução conhecida tem complexidade exponencial ou pior O Problema de obter um circuito hamiltoniano em um grafo é um problema do tipo NPcompleto tal classe de complexidade é apresentada na disciplina Teoria da Computação Para os problemas Ncompletos são conhecidos apenas algoritmos de complexidade exponencial para resolvêlos No entanto não existe nenhuma prova de que tal complexidade é realmente necessária Por isso muitos pesquisadores tentam provar que um problema NPcompleto necessita realmente de tempo exponencial para ser resolvido ou alternativamente encontrar uma solução eficiente polinomial para um problema NPcompleto Teoria dos Grafos 20232 Como não se conhecem algoritmos eficientes para obter um circuito hamiltoniano este problema é chamado de intratável 3 O Problema do Caixeiro Viajante Um problema de interesse é encontrar um circuito hamiltoniano em um grafo com custos nas arestas Nesse caso o custo do circuito é definido como a soma dos custos das arestas do circuito Exemplo Dado o grafo G abaixo O circuito C2 k1 k2 k5 k8 k3 k4 k7 k6 k1 é um circuito de custo 25 Será que existe um circuito de custo menor que 25 Você consegue obter um circuito hamiltoniano de custo mínimo O problema do caixeiro viajante é dado um grafo com custos nas arestas obter um circuito hamiltoniano de custo mínimo Exercício Obter um circuito hamiltoniano de custo mínimo no grafo abaixo 4 Exercícios Exercício Apresente um grafo hamiltoniano com 7 vértices e uma quantidade mínima de arestas Exercício Será que todo grafo hamiltoniano é também euleriano Justifique Exercício Será que todo grafo euleriano é também hamiltoniano Justifique