ALGORITMO DE PRIM

Vista previa del material en texto

Sebastián Ricardo
Roosevelt Santos
Dilan Ortega
ALGORITMO DE PRIM
TEORÍA DE GRAFOS
UNIVERSIDAD DE CÓRDOBA
¿QUÉ ES?
Es un algoritmo clásico utilizado en teoría de grafos para resolver el problema del árbol de expansión mínimo en un grafo ponderado conexo. 
UNIVERSIDAD DE CÓRDOBA
Un árbol de expansión mínimo es aquel que conecta todos los vértices del grafo con el costo total mínimo. 
¿QUÉ ES UN ARBOL DE EXPANSIÓN MINIMO?
UNIVERSIDAD DE CÓRDOBA
Construir gradualmente un árbol mediante la selección de las aristas de menor peso que conectan los vértices.
¿QUÉ SE BUSCA CON EL ALGORITMO DE PRIM?
UNIVERSIDAD DE CÓRDOBA
Inicializar un árbol vacío.
01
02
Seleccionar un vértice inicial arbitrario y agregarlo al árbol.
PROCESO DE EJECUCIÓN
El proceso de ejecución del algoritmo se puede resumir en los siguientes pasos:
03
Repetir hasta que todos los vértices estén en el árbol
04
Encontrar la arista de menor peso que conecta un vértice del árbol con un vértice fuera del árbol.
Agregar esta arista al árbol.
Agregar el vértice conectado por esta arista al árbol.
05
06
UNIVERSIDAD DE CÓRDOBA
EJEMPLO
Aplicamos el algoritmo de PRIM paso por paso en el siguiente grafo:
UNIVERSIDAD DE CÓRDOBA
EJEMPLO
El Arbol mínimo quedaría de la siguiente forma:
SOLUCIÓN: 2 + 5 + 6 + 1 + 3 + 4 + 8 = 29 
UNIVERSIDAD DE CÓRDOBA
Distribuciónd de productos y minimizar costos
DISTRIBUCIÓN DE RECURSOS
Ruta más corta o de menor costo
PLANIFICACIÓN DE RUTAS
Disposición óptima de cables o en la planificación de redes de internet 
REDES DE COMUNICACIÓN
APLICACIÓN EN
LA VIDA REAL
UNIVERSIDAD DE CÓRDOBA