Si G es un bosque con n vértices y k componentes conexas, ¿cuántas aristas tiene G?
(A) piso (n/k)
(B) techo (n/k)
(C) nk
(D) n-k+1
Respuesta: (C)
Explicación: Cada componente tendrá n/k vértices ( principio del casillero ). Por lo tanto, para cada componente habrá (n/k)-1 aristas.
Como hay k componentes, el número total de aristas = k*((n/k)-1) = nk.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA