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

  1. . Se inicia escogiendo un nodo cualquiera, del cual de desprenda una arista con una peso pequeño y este será el nodo de partida.
  2. . Escogemos la arista de menor peso o valor que sale del nodo marcado y lo conectamos con el siguiente nodo.
  3. Repetir el paso 2 escogiendo las aristas de menor peso.
  4. El algoritmo termina una vez estén todos los nodos conectados.

 
This entry was posted on 16:43 You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.