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 que la arista e tiene el peso mínimo entre todas las aristas que tienen un vértice en X y un vértice en Y.
Sea el peso de una arista e la congestión en esa arista. La congestión en un camino se define como el máximo de las congestiones en los bordes del camino. Deseamos encontrar el camino de s a t con mínima congestión. ¿Cuál de los siguientes caminos es siempre un camino de mínima congestión?
(A) un camino de s a t en el árbol de expansión ponderado mínimo
(B) un camino más corto ponderado de s a t
(C) un camino de Euler de s a t
(D)un camino hamiltoniano de s a t
Respuesta: (A)
Explicación: supongamos que el camino más corto desde A->B es 6, pero en MST, tenemos A->C->B (A->C = 4, C->B = 3), luego a lo largo de la ruta en MST, tenemos una congestión mínima, es decir, 4
Cuestionario de esta pregunta
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