PUERTA | PUERTA 2017 MOCK II | Pregunta 18

Sean X e Y los números enteros que representan el número de gráficos simples posibles con 3 vértices etiquetados y 3 vértices no etiquetados respectivamente. Sea X – Y = N. Luego, encuentre el número de árboles de expansión posibles con el gráfico completo de N vértices etiquetados.

(A) 4
(B) 8
(C) 16
(D) 32

Respuesta: (C)
Explicación: El número de gráficos simples posibles con n vértices etiquetados es 2^(n(n-1)/2).
El número de gráficos simples posibles con n vértices sin etiquetar es n+1.
Número de árbol de expansión posible con n vértices gráfico completo n^(n-2)

X = 8
Y = 4
XY = 4

Por lo tanto, la respuesta requerida es 4^2=16.

Cuestionario de esta pregunta