En el gráfico dado en la pregunta anterior, ¿cuál es el peso mínimo posible de un camino P desde el vértice 1 al vértice 2 en este gráfico tal que P contiene como máximo 3 aristas? (A) 7 (B) 8 (C) 9 (D) 10 Respuesta: (B) Explicación: Ruta: 1 -> 0 -> 4 -> 2 … Continue reading «Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 4»
Considere un gráfico completo ponderado G en el conjunto de vértices {v1,v2,v} tal que el peso de la arista (v,,v) es 2|ij|. El peso de un árbol de expansión mínimo de G es: (GATE CS 2006) (A) n — 1 (B) 2n — 2 (C) nC2 (D) 2 Respuesta: (B) Explicación: el árbol de expansión … Continue reading «Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 8»
Un grafo no dirigido G tiene n Nodes. Su array de adyacencia viene dada por una array cuadrada de n × n cuyos (i) elementos diagonales son 0 y (ii) elementos no diagonales son 1. ¿Cuál de las siguientes es VERDADERA? (A) El gráfico G no tiene un árbol de expansión mínimo (MST) (B) El … Continue reading «Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 5»
Considere un gráfico no dirigido completo con el conjunto de vértices {0, 1, 2, 3, 4}. La entrada Wij en la array W a continuación es el peso de la arista {i, j}. ¿Cuál es el peso mínimo posible de un árbol de expansión T en este gráfico tal que el vértice 0 sea un … Continue reading «Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 3»