C. Hamiltoniamos

Um circuito hamiltoniano é um circuito que não repete...

• vértices nem arestas

• vértices (mas pode repetir arestas)

• arestas (mas pode repetir vértices)

É possível ver se um grafo é hamiltoniano observando o grau dos vértices.

• verdade

• Falso

O circuito ABCDECA é hamiltoniano

• verdade!

• falso!

Este grafo é hamiltoniano.

• Verdade

• Falso

Este grafo é ....

• Euleriano e hamiltonian

• Apenas euleriano

• Apenas hamiltoniano

• Nem euleriano, nem hamiltoniano

Existem 2 algoritmos para encontrar o circuito hamiltoniano de peso mínimo que são:

• Alg. dos mínimos sucessivos e alg. do vizinho mais próximo

• Alg. dos mínimos sucessivos e alg. das arestas classificadas

• Alg. por ordenação dos pesos das arestas e alg. das arestas classificadas

Pelo método do vizinho mais próximo, partindo da cidade A, o circuito hamiltonano que se obtém é:

• ADBCA

• ADCBA

• ADBAC

• ABCDA

Pelo método das arestas classificadas, o circuito hamiltonano que se obtém é:

• ADCBA

• ACBDA

• ABCDA