PUERTA | Puerta TI 2007 | Pregunta 25

¿Cuál es el entero más grande m tal que cada gráfico conexo simple con n vértices y n aristas contiene al menos m árboles de expansión diferentes?
(A) 1
(B) 2
(C) 3
(D) n

Respuesta: (C)
Explicación: Un grafo es conexo si y solo si todos los Nodes se pueden atravesar desde cada Node. Para un gráfico con n Nodes, habrá n-1 número mínimo de aristas.
Dado que hay n aristas, eso significa que hay un ciclo en el gráfico.
El grafo simplex con estas condiciones puede ser:

Ahora podemos hacer un árbol de expansión diferente eliminando un borde del ciclo, uno a la vez.
La duración mínima del ciclo puede ser 3. Por lo tanto, debe haber al menos 3 árboles de expansión en cualquier gráfico de este tipo.

Cuestionario de esta pregunta