Árboles de peso mínimo
En un árbol de peso mínimo se busca que los costos totales de las aristas sea el mínimo.
Un árbol de peso mínimo se representa por:
-
Gráfica dirigida o no dirigida.
-
Datos simétricos
Sea G=[x,A] una gráfica dirigida que tiene a x como conjunto de nodos y A como aristas. Teniendo también a Ci,j, como costos asociados a las aristas.
La solución a estos problemas es una subgráfica de G, a la que llamamos T (que tiene que ser una gráfica conectada, sin ciclos y con n-1 aristas (nodos).
Para resolver un problema de este tipo, existen dos métodos: el método de Kruskal y el método de Prim.
Estos métodos estudian la gráfica de maneras diferentes, por ejemplo, el método de Kruskal estudia la gráfica por medio de las aristas y el de Prim, la estudia por nodos.
Ejemplo: Encuentra la ruta más corta de la siguiente red.
Para resolver este ejemplo de árbol a costo mínimo, utilizaremos el método de Prim.
Para este método se seguirá el siguiente procedimiento:
1. Elegir cualquier nodo para empezar el algoritmo.
2. A partir del nodo elegido, buscar las aristas adyacentes con menor costo.
3. De la arista con menor costo, elegir el nodo adyacente y buscar nuevas aristas con menor costo.
En este caso, escogeremos como nodo inicial al nodo A, siendo su arista adyacente con el menor costo la que se dirige al nodo B.
Del nodo B, buscamos la siguiente arista con menos costo, sería la arista que lleva al nodo C, con 8 unidades de costo.
Posteriormente del nodo C buscamos las aristas con menos costo, en este caso es la arista que lleva al nodo I.
Del nodo I buscamos la arista con menor costo de los nodos ya analizados, siendo la arista que lleva al nodo G.
Del nodo G buscamos la arista con menor costo, siendo la que va a H, sin embargo si continuamos con esta arista, caeríamos en un ciclo, así que nos decidimos por el nodo F. En el nodo F pasa lo mismo que en el nodo anterior si seguimos la arista con menor costo, así que nos vamos por la arista que va al nodo E.
Entonces, sumamos los costos de las aristas elegidas, siendo ese nuestro costo total para la ruta más corta.
4+8+2+6+2+10= 32