Dejando solo los vertices y las aritas del arbol obtenido quedaria de la siguiente manera.Finalmente este es el arbol recubridor minimo obtenido para el mapa de colombia, teniendo en cuenta que el valor de cada una de las aristas es un valor que se ha dado manejando la escala del mapa, no es un valor real de la distancia entre cada uno de los departamentos del mapa.
Se a añadido un vertice para cada departamento, cada uno con una letra diferente. como se puede ver se ha conectado cada uno de los vertices con aristas, como no conosco la distancia que hay entre los departamentos del pais lo que he hecho es tomar la medida de cada una de las lineas que en este caso son las aristas y colocar ese valor a la arista, esto con el objetivo de dar un valor aproximado a cada arista como si se tratara de una distancia real.
La manera de conocer el arbol recubridor minimo seria la siguiente
| E | M |
| Ø | B |
| {B,C} | C |
| {C,A} | A |
| | C |
| {C,F} | F |
| {F,H} | H |
| | F |
| {F,E} | E |
| {E,D} | D |
| {D,G} | G |
| {G,J} | J |
| {J,O} | O |
| {O,R} | R |
| {R,V} | V |
| | O |
| {O,S} | S |
| {S,X} | X |
| {X,W} | W |
| | O |
| {O,P} | P |
| {P,K} | K |
| {K,L} | L |
| {L,M} | M |
| {M,I} | I |
| | K |
| {K,Q} | Q |
| {Q,T} | T |
| {T,Y} | Y |
| {Y,U} | U |
| {U,N} | N |
| | Y |
| {Y,Z} | Z |
614
Dado un grafo conectado y no dirigido, su árbol abarcador mínimo es un subgrafo en forma de árbol que mantiene la conectividad del grafo y tal que la suma de los pesos de las ramas seleccionadas es mínimo. El algoritmo de Prim resuelve este problema en tiempo polinómico mediante una estrategia voraz(esto es, seleccionar en cada paso lo que más convenga). Las aplicaciones de los árboles abarcadores mínimos son múltiples: obtención de redes eléctricas o de comunicaciones eficientes, creación de laberintos aleatorios, solución aproximada de problema del viajante etc.
Para lograr este objetivo, hemos utilizado un algoritmo voraz, que empezará seleccionando la arista de menor coste partiendo de un nodo inicial, es decir el camino de menor recorrido desde un nodo determinado. Luego repetirá dicho proceso seleccionando una nueva arista hasta que todos los nodos sean visitados. Cada uno de estas nuevas aristas será la de menor peso entre las que no estén repetidas y, por lo tanto, permitirá el acceso a un nodo nuevo.
Funcionamiento
- . Se inicia escogiendo un nodo cualquiera, del cual de desprenda una arista con una peso pequeño y este será el nodo de partida.
- . Escogemos la arista de menor peso o valor que sale del nodo marcado y lo conectamos con el siguiente nodo.
- Repetir el paso 2 escogiendo las aristas de menor peso.
- El algoritmo termina una vez estén todos los nodos conectados.
