Resumêra

Questão 1 – Média

1.50 pontos Média

Qual das alternativas abaixo descreve corretamente a condição necessária para que um grafo conexo possua um caminho de Euler?

A) Todos os vértices devem ter grau par. B) O grafo deve ter exatamente três vértices de grau ímpar. C) O número de vértices de grau ímpar deve ser zero ou dois. D) O grafo pode ser desconexo, contanto que cada componente tenha um caminho de Euler. E) Cada vértice deve ter grau exatamente três.

Resposta correta: C) O número de vértices de grau ímpar deve ser zero ou dois.

Esta é a condição clássica do teorema de Euler para caminhos de Euler.

Questão 2 – Difícil

2.50 pontos Difícil

Considere o grafo abaixo (representado por sua matriz de adjacência). Determine se ele possui um caminho de Euler e indique o ponto de início e fim, caso exista. \[ A = \begin{pmatrix} 0&1&1&0\\ 1&0&1&1\\ 1&1&0&1\\ 0&1&1&0 \end{pmatrix} \]

A) Não possui caminho de Euler. B) Possui, iniciando e terminando no vértice 1. C) Possui, iniciando no vértice 2 e terminando no vértice 3. D) Possui, iniciando no vértice 4 e terminando no vértice 1. E) Possui, iniciando no vértice 3 e terminando no vértice 4.

Resposta correta: C) Possui, iniciando no vértice 2 e terminando no vértice 3.

Graus: v1=2 (par), v2=3 (ímpar), v3=3 (ímpar), v4=2 (par). Dois vértices ímpares → caminho de Euler entre 2 e 3.

Questão 3 – Difícil

2.50 pontos Difícil

Qual das afirmações abaixo sobre circuitos Hamiltonianos é FALSA?

A) Todo grafo completo \(K_n\) possui um circuito Hamiltoniano para \(n \ge 3\). B) Se um grafo tem um caminho de Euler, ele necessariamente tem um circuito Hamiltoniano. C) O problema de decidir a existência de um circuito Hamiltoniano é NP‑completo. D) Um grafo bipartido regular de grau 2 pode ter um circuito Hamiltoniano. E) Em um grafo Hamiltoniano, remover um vértice pode destruir a propriedade Hamiltoniana.

Resposta correta: B) Se um grafo tem um caminho de Euler, ele necessariamente tem um circuito Hamiltoniano.

Existência de caminho de Euler não implica existência de ciclo Hamiltoniano.

Questão 4 – Extrema

3.50 pontos Extrema

Dado um grafo simples conexo com 8 vértices onde exatamente 4 vértices têm grau ímpar, qual é a conclusão correta?

A) O grafo possui um caminho de Euler. B) O grafo possui um ciclo de Euler. C) O grafo não pode ter caminho nem ciclo de Euler. D) O grafo pode ter caminho de Euler apenas se for completo. E) O grafo tem exatamente dois componentes conexos.

Resposta correta: C) O grafo não pode ter caminho nem ciclo de Euler.

Para caminho de Euler são permitidos 0 ou 2 vértices ímpares; 4 ímpares viola a condição.

Caminho de Euler e Circuito Hamiltoniano em Grafos

Questões sobre o assunto