Algoritmos

O que define um grafo como hamiltoniano?

• Se todos os vértices possuem o mesmo grau.

• Se todos os vértices possuem grau par.

• Se existe um caminho que passa por todos os vértices exatamente uma vez.

• Se existe um ciclo que passa por todos os vértices exatamente uma vez.

Answer explanation

Um grafo hamiltoniano é caracterizado por um ciclo especial: o ciclo hamiltoniano, que passa por todos os vértices exatamente uma vez, terminando no ponto inicial.

Algoritmo que garante encontrar um caminho entre dois vértices em um grafo:

(a)  

Quais os 2 teoremas mais famosos dentro do assunto Grafos Hamiltonianos?

• Teorema de Ore

• Teorema de Newton

• Teorema de Euler

• Teorema de Dirac

Answer explanation

Teorema de Ore:

• Para cada par de vértices não adjacente a soma dos graus deve ser maior ou igual a n.

• Teorema de Dirac:

  • Se todo vértice se liga a pelo menos

    metade dos vértices do conjunto V.

A busca em largura é um algoritmo que utiliza uma abordagem de "exploração em profundidade"

• Verdadeiro

• Falso

A busca em largura pode ser implementada em Python utilizando uma fila para armazenar os vértices a serem explorados.

• Verdadeiro

• Falso

Para um grafo ser Hamiltoniano ele precisa essencialmente conter:

• Um ciclo Hamiltoniano

• Um caminho Hamiltoniano

A busca em largura é um algoritmo guloso.

• Verdadeiro

• Falso

Answer explanation

• A Busca em Largura não é gulosa: ela explora o espaço de busca de forma sistemática.

Considerando o seguinte caso fictício:
Gustavo, trabalhador do IBGE, precisa visitar algumas casas (vértices) para realizar registros.
Sendo sua casa o vértice 1, sua rota pode ser considerada hamiltoniana?

• Sim

• Não

Answer explanation

Esta rota não poderia ser considerada um grafo Hamiltoniano por não é possível fazer um ciclo que inicie e termine no mesmo vértice, sem repetições.

Existe um ciclo Hamiltoniano no grafo? Se sim, indique-o no desenho.

Este é um grafo hamiltoniano?

• Sim

• Não

Answer explanation

Não, este não é um grafo Hamiltoniano pois o mesmo não é conexo.