PUERTA | PUERTA CS 2008 | Pregunta 23

¿Cuál de las siguientes afirmaciones es verdadera para cada gráfico plano en n vértices?
(A) El gráfico es conexo
(B) El gráfico es euleriano
(C) El gráfico tiene una cubierta de vértices de tamaño máximo 3n/4
(D) El gráfico tiene un conjunto independiente de tamaño mínimo n/3

Respuesta: ( C)
Explicación: Un gráfico plano es un gráfico que se puede dibujar en un plano sin que ningún par de aristas se crucen entre sí.

A) FALSO: Un gráfico inconexo puede ser plano ya que se puede dibujar en un plano sin cruzar bordes.

B) FALSO: Un Grafo Euleriano puede o no ser plano. Un grafo no dirigido es euleriano si todos los vértices tienen grado par .

Por ejemplo, el siguiente gráfico es euleriano, pero no plano.

C) VERDADERO:

D) FALSO:

Cuestionario de esta pregunta