PUERTA | PUERTA-CS-2003 | Pregunta 8

Sea G un grafo arbitrario con n Nodes y k componentes. Si se quita un vértice de G, el número de componentes en el gráfico resultante debe estar necesariamente entre
(A) k y n
(B) k – 1 y k + 1
(C) k – 1 y n – 1
(D) k + 1 y n – k

Respuesta: (C)
Explicación: Mínimo: El vértice eliminado en sí mismo es un componente conectado separado. Entonces, la eliminación de un vértice crea componentes k-1.

Máximo: es posible que el vértice eliminado desconecte todos los componentes. Por ejemplo, el vértice eliminado es el centro de una estrella. Entonces, la eliminación crea componentes n-1.

Cuestionario de esta pregunta