Sea G un gráfico no dirigido conectado ponderado con distintos pesos de arista positivos. Si el peso de cada borde aumenta en el mismo valor, ¿cuál de las siguientes afirmaciones es VERDADERA?
P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
(A) P solamente
(B) Solo Q
(C) Ni P ni Q
(D) Tanto P como Q
Respuesta: (A)
Explicación: El camino más corto puede cambiar. La razón es que puede haber un número diferente de aristas en diferentes caminos de s a t. Por ejemplo, deje que el camino más corto tenga un peso de 15 y tenga 5 aristas. Sea otro camino con 2 aristas y un peso total de 25. El peso del camino más corto aumenta en 5*10 y se convierte en 15 + 50. El peso del otro camino aumenta en 2*10 y se convierte en 25 + 20. Entonces, el la ruta más corta cambia a la otra ruta con un peso de 45.
El árbol de expansión mínimo no cambia. Recuerda el algoritmo de Kruskal donde ordenamos los bordes primero. SI aumentamos todos los pesos, entonces el orden de los bordes no cambiará.
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
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