PUERTA | PUERTA-CS-2005 | Pregunta 83

Sean s y t dos vértices en un gráfico no dirigido G + (V, E) que tienen distintos pesos de borde positivos. Sea [X, Y] una partición de V tal que s ∈ X y t ∈ Y. Considere la arista e que tiene el peso mínimo entre todas aquellas aristas que tienen un vértice en X y un vértice en Y

La arista e definitivamente debe pertenecer a:
(A) el árbol de expansión ponderado mínimo de G
(B) el camino más corto ponderado de s a t
(C) cada camino de s a t
(D) el camino más largo ponderado de s a

t : (A)
Explicación: El borde de peso mínimo en cualquier corte de st siempre es parte de MST. Esto se llama propiedad de corte .

Esta es la idea utilizada en el algoritmo de Prim . El borde de corte de peso mínimo es siempre un borde de árbol de expansión mínimo.

¿Por qué B (el camino más corto ponderado de s a t) no es una respuesta?
Vea el ejemplo a continuación, el borde 4 (el más claro en el corte rojo resaltado de s a t) no forma parte de la ruta más corta. Cuestionario de esta pregunta