Arboles Generadores Minimales

Arboles Generadores Minimales

Un árbol generador mínimo en un grafo conexo y ponderado es un árbol generador que minimiza la suma de pesos de las aristas.

Por Ejemplo sea un grafo ponderado ( con peso) con cinco vértices. La idea es constuir un subgrafo que una a todos los puntos pero con el mínimo de peso (el peso se refiere al valor que se le da a cada uno de los lados de un grafo). Este subgrafo debe ser un árbol generador, ya que debe unir todos los vértices, debe ser conexo y debe haber un único camino entre cada par de vértices, por lo tanto, lo que se necesita es un árbol generador con el mínimo de peso, es a esto lo que se llama árbol generador minimal.

Si dos nodos en una red conexa están unidos mediante dos rutas, una de estas rutas debe contener una rama cuya eliminación no desconecte a la red. El eliminar la rama puede solamente abatir el costo total. Un árbol de recorrido mínimo puede encontrase al seleccionar inicialmente cualquier nodo y determinar cual de las ramas que coinciden con el nodo seleccionado tienen el menor costo.

A esta rama se le acepta como parte de la red final. Después se completa la red interactivamente. En cada etapa del proceso iterativo la atención se centra en aquellos nodos que ya se han eslabonados. Todas las ramas que conectan a estos nodos con nodos inconexos se consideran, y se identifica a la más barata de las ramas.

Los empates se resuelven arbitrariamente a esta rama se le acepta como parte de la red final. El proceso iterativo termina cuando se han eslabonado todos los nodos. Algoritmos para calcular MST ( ) y son : Prim, Kruskal, Sollin y son métodos para construir un árbol generador mínimo:

· Algoritmo de Prim: Se parte de un vértice y se elige la arista de menor peso incidente en él. Una vez construido un árbol con k vértices, se elige la arista de menor peso entre las que conectan vértices de con vértices que no son de

. Se continúa hasta alcanzar todos los vértices.

· Algoritmo de Kruskal: Se parte de la arista de menor peso. Se sigue eligiendo en cada paso la arista de menor peso, (de las que resten), que no forme ciclo con las aristas anteriores. Se termina al elegir n-1 aristas.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad