Sea G = (V, E) un grafo no dirigido con un subgrafo G1 = (V1, El). Los pesos se asignan a los bordes de G de la siguiente manera:
Se ejecuta un algoritmo de ruta más corta de fuente única en el gráfico ponderado (V, E, w) con un vértice arbitrario ν1 de V1 como fuente. ¿Cuál de los siguientes siempre se puede inferir de los costos de ruta calculados?
(A) El número de aristas en los caminos más cortos desde ν1 a todos los vértices de G
(B) G1 está conectado
(C) V1 forma una camarilla en G
(D) G1 es un árbol
Respuesta: (B)
Explicación: Cuando el camino más corto Se calcula la ruta más corta desde v1 (uno de los vértices en V1). G1 está conectado si la distancia de v1 a cualquier otro vértice en V1 es mayor que 0; de lo contrario, G1 está desconectado.
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