Sea G=(V,E) un gráfico dirigido y ponderado con una función de peso w:E→R. Para alguna función f:V→R, para cada arista (u,v)∈E, define w′(u,v) como w(u,v)+f(u)−f(v).
¿Cuál de las opciones completa la siguiente oración para que sea VERDADERA?
“Los caminos más cortos en G bajo w también son caminos más cortos bajo w′, _________”.
(A) para todo f:V→R
(B) si y solo si ∀u∈V, f(u) es positivo
(C) si y solo si ∀u∈V, f(u) es negativo
(D) si y solo si f(u) es la distancia de s a u en el gráfico obtenido al agregar un nuevo vértice s a G y aristas de peso cero desde s a cada vértice de G
Respuesta: (A)
Explicación:
prueba 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