PUERTA | PUERTA-CS-2001 | Pregunta 50

¿Cuántos grafos no dirigidos (no necesariamente conectados) se pueden construir a partir de un conjunto dado V = {v1, v2, … vn} de n vértices?
(A) n(n-1)/2
(B) 2 ⁿ
(C) n!
(D) 2 ^n(n-1)/2

Respuesta: (D)
Explicación: Hay un total de n*(n-1)/2 aristas posibles. Para cada borde, hay dos opciones posibles, o lo seleccionamos o no lo seleccionamos. Entonces, el número total de gráficos posibles es 2 ^n(n-1)/2 .
Cuestionario de esta pregunta