Defina o que é um grafo Hamiltoniano.

Passo 1

O enunciado pede para definirmos o que é um grafo Hamiltoniano: estamos em Teoria dos Grafos e precisamos entender os conceitos de caminho Hamiltoniano e ciclo Hamiltoniano para chegar à definição.

Passo 2

Um caminho Hamiltoniano em um grafo é uma sequência de vértices na qual cada vértice de $V$ aparece exatamente uma vez e há arestas ligando vértice a vértice consecutivo nessa sequência. Ou seja, é um passeio que visita todos os vértices sem repetir nenhum.

Passo 3

Um ciclo Hamiltoniano é um caminho Hamiltoniano que volta ao vértice de partida por uma aresta, fechando um circuito. Assim, ele visita cada vértice de $V$ exatamente uma vez e retorna ao início, formando um ciclo simples que passa por todos os vértices.

Passo 4

Dado isso, dizemos que um grafo $G = (V, E)$ é Hamiltoniano se existir pelo menos um ciclo Hamiltoniano em $G$. Em outras palavras, o grafo deve permitir um circuito que passe por todos os vértices exatamente uma vez.

Resposta

Um grafo G = (V, E) é Hamiltoniano se existir em G um ciclo Hamiltoniano, ou seja, um percurso fechado que visita cada vértice de V exatamente uma vez antes de retornar ao vértice inicial.

Exercícios relacionados