PUERTA | PUERTA-CS-2007 | Pregunta 23

¿Cuál de los siguientes gráficos tiene un circuito euleriano?
(A) Cualquier gráfico k-regular donde ki es un número par.
(B) Un gráfico completo en 90 vértices
(C) El complemento de un ciclo en 25 vértices
(D) Ninguna de las anteriores

Respuesta: (C)
Explicación: Un gráfico tiene un circuito euleriano si las siguientes condiciones son verdaderas.

….a) Todos los vértices con grado distinto de cero están conectados. No nos importan los vértices con grado cero porque no pertenecen al ciclo o camino euleriano (solo consideramos todas las aristas).
….b) Todos los vértices tienen grado par.

Analicemos todas las opciones.
A) Cualquier gráfico k-regular donde k es un número par . no es euleriano ya que un grafo regular k puede no ser conexo (la propiedad b es verdadera, pero a puede no serlo)

B) Un grafo completo de 90 vértices no es euleriano porque todos los vértices tienen grado 89 (la propiedad b es falsa)

C) El complemento de un ciclo de 25 vértices es euleriano. En un ciclo de 25 vértices, todos los vértices tienen un grado de 2. En el gráfico de complemento, todos los vértices tendrían un grado de 22 y el gráfico estaría conectado.
Cuestionario de esta pregunta