PUERTA | PUERTA CS 2018 | Pregunta 49

Considere el siguiente gráfico no dirigido G:

Elija un valor para x que maximizará el número de árboles de expansión de peso mínimo (MWST) de G. El número de MWST de G para este valor de x es _________.

Nota: esta fue una pregunta de tipo numérico.
(A) 4
(B) 5
(C) 2
(D) 3

Respuesta: (A)
Explicación: Para maximizar el número de árboles de expansión de peso mínimo de G, el valor de x será 5 porque tendrá dos opciones más para vértice de esquina que maximizará el número máximo de MST.

Ahora, según el algoritmo de Kruskal para MST:

1. Los bordes con pesos 1 y 3 se seleccionarán primero,
2. Ahora el borde inferior con peso 4 no se seleccionará ya que provocará un ciclo en MST,
3. ambos vértices de las esquinas tienen dos o dos opciones para seleccionar los vértices, por lo que estos bordes de las esquinas con pesos 4 y 5 darán como resultado 2*2 = 4 MST.

Por lo tanto, el número total de MST es 2*2 = 4, que es la respuesta.

Tenga en cuenta que el valor de x es 5, pero el número de MWST es 4, como se muestra arriba.

La opción (A) es correcta.

Cuestionario de esta pregunta