Pregunta 67

Técnico Auxiliar Informática del Estado - 2010 - GSI - Gestión de Sistemas e Informática (Libre)

Dado un grafo G = (V, E) donde V es el conjunto de vértices y E es conjunto de aristas. Diremos que es hamiltoniano si:

  • A.Todos los vértices tienen el mismo grado.
  • B.Contiene un ciclo que pasa por todos los vértices del grafo.Respuesta correcta
  • C.No contiene ciclos.
  • D.Es conexo y contiene un ciclo.

Explicación

La respuesta correcta es B: un grafo es hamiltoniano si contiene un ciclo que pasa exactamente una vez por cada vértice. Un grafo regular, con todos los vértices del mismo grado, no tiene por qué serlo, y un grafo acíclico no puede contener ciclos, por lo que tampoco puede ser hamiltoniano. Que un grafo sea conexo y tenga algún ciclo no garantiza que exista uno que recorra todos los vértices. No debe confundirse con el ciclo euleriano, que recorre todas las aristas.