Ah Ja

UNIVERSIDAD INDUSTRIAL DE SANTANDER
Trabajo sobre Algoritmo de Prim
Autores del Documento:
Cristian Arias Londoño Código: 2101718
William Oliveros Valencia Código: 212200

ALGORITMO DE PRIM

* QUE ES EL ALGORITMO DE PRIM
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido ycuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
* QUE ES UN ÁRBOL RECUBRIDORMINIMO
Dado un grafo conexo, un árbol recubridor mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.. , y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de lasaristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bósque recubridor mínimo.

Un ejemplo de árbol recubridor mínimo. Cada punto representa un vértice, cada arista está etiquetada con su peso, que en este caso equivale a su longitud.

* QUE ES UN GRAFO CONEXO
Ungrafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinarsi un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).
En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexascuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos. 

* QUE ES UN GRAFO PONDERADO O ETIQUETADO

Un grafo ponderado o grafo con pesos es un grafo G(V, E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso . El peso de un subgrafo de un grafoponderado es la suma  de los pesos de todas sus aristas.
Ejemplo Dado el grafo con pesos:

* QUE PROBLEMA RESUELVE EL ALGORITMO DE PRIM?
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar sonaquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

* QUE ESTRUCTURA DE DATOS UTILIZA EL ALGORITMO
El tipo de estructura de datos, que este emplea es el de cola de prioridad, ya que se van a indicando conforme a su prioridad se puede implementar con un “heap”  o en español un montículoes una estructura de datos  del tipo árbol con información perteneciente a un conjunto ordenado. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos.
Un árbol cumple la condición de montículo si satisface dicha condición...