ALGORITMO DE PRIM

DEMOSTRACION

Sea $G$ un grafo conexo y ponderado.
En toda iteración del algoritmo de Prim, se debe encontrar una arista que conecte un nodo del subgrafo a otro nodo fuera del subgrafo.
Ya que $G$ es conexo, siempre habrá un camino para todo nodo.
La salida $Y$ del algoritmo de Prim es un árbol porque las aristas y los nodos agregados a $Y$ están conectados.
Sea $Y$ el árbol recubridor mínimo de $G$ .
Si $Y_1 = Y \Rightarrow Y$ es el árbol recubridor mínimo.
Si no, sea $e$ la primera arista agregada durante la construcción de $Y$ , que no está en $Y 1$ y sea $V$ el conjunto de nodos conectados por las aristas agregadas antes que $e$ . Entonces un extremo de $e$ está en $V$ y el otro no. Ya que $Y 1$ es el árbol recubridor mínimo de $G$ hay un camino en $Y 1$ que une los dos extremos. Mientras que uno se mueve por el camino, se debe encontrar una arista $f$ uniendo un nodo en $V$ a uno que no está en $V$ . En la iteración que $e$ se agrega a $Y$ , $f$ también se podría haber agregado y se hubiese agregado en vez de $e$ si su peso fuera menor que el de $e$ . Ya que $f$ no se agregó se concluye:

$P(f) \geq P(e)$

Sea $Y 2$ el grafo obtenido al remover $f$ y agregando $e \in Y_1$ . Es fácil mostrar que $Y 2$ conexo tiene la misma cantidad de aristas que $Y 1$ , y el peso total de sus aristas no es mayor que el de $Y 1$ , entonces también es un árbol recubridor mínimo de $G$ y contiene a $e$ y todas las aristas agregadas anteriormente durante la construcción de $V$ . Si se repiten los pasos mencionados anteriormente, eventualmente se obtendrá el árbol recubridor mínimo de $G$ que es igual a $Y$ .
Esto demuestra que $Y$ es el árbol recubridor mínimo de $G$ .

GRAFO CONEXO:
Un grafo 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 fuertemente 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 determinar si 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) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

HISTORIA DEL ALGORITMO DE PRIM

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo

ALGORITMO: En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del latín, dixit algorithmus y éste a su vez del matemático persa Al Juarismi^[1] ) es un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad.Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.

VOJTECH JARNIK: (22 de diciembre de 1897 - 22 de septiembre de 1970) fue un matemático checo. Su principal área de trabajo fue en la teoría de los números y el análisis matemático, demostró una serie de resultados en problemas de punto de celosía. También descubrió el algoritmo sobre la teoría de grafos conocido como el algoritmo de Prim.