ARBOL DE EXPANSION MINIMA

¿Qué es un Árbol de Expansión Mínima?

• Un grafo con ciclos mínimos

• Un subgrafo que conecta todos los nodos con el menor costo total

• Un grafo dirigido con pesos mínimos

• Un árbol que incluye ciclos controlados

¿Cuál de los siguientes algoritmos es adecuado para grafos densos?

• Kruskal

• Borůvka

• Prim

• Dijkstra

¿Qué característica define al Árbol de Expansión Mínima?

• Conexión de algunos vértices

• Conexión de todos los vértices sin ciclos

• Contar con ciclos redundantes

• Maximizar el costo de las conexiones

¿Qué propiedad garantiza que un Árbol de Expansión Mínima tenga V−1 aristas?

• Ausencia de ciclos

• Conexión total

• Unicidad bajo condiciones específicas

• Minimización del costo total

¿Qué algoritmo utiliza una estrategia iterativa y paralela para construir el Árbol de Expansión Mínima?

• Kruskal

• Borůvka

• Prim

• Floyd-Warshall

¿Cuál es el principal criterio para seleccionar aristas en el algoritmo de Kruskal?

• Ordenar por nodos

• Seleccionar aristas de menor peso

• Elegir aristas aleatorias

• Minimizar la distancia entre nodos consecutivos

¿Qué limita la eficiencia del algoritmo de Prim en grafos dispersos?

• La cantidad de nodos

• La falta de ciclos

• El alto número de bordes

• La representación del grafo como matriz de adyacencia

¿Qué problema resolvió inicialmente el algoritmo de Borůvka?

• Diseño de redes de comunicación

• Optimización de sistemas eléctricos en Checoslovaquia

• Construcción de carreteras

• Minería de datos

¿Qué sucede si dos aristas tienen el mismo peso en un grafo?

• El MST será único

• Puede haber múltiples MST válidos

• El algoritmo falla

• Se elige la arista con mayor peso

¿Cuál de los siguientes NO es una aplicación del Árbol de Expansión Mínima?

• Optimización logística

• Codificación de datos

• Creación de redes sociales

• Planificación de rutas de transporte