jump to navigation

2.3 Problema árbol expandido mínimo

2.3 Problema árbol expandido mínimo

Árbol de expansión mínima

Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar un loop.

El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.

EL TRANSITO DEL DISTRITO METROPOLITANO

· La ciudad de Vancouver está planificando el desarrollo de una nueva línea en sistemas de tránsito.

· El sistema debe unir 8 residencias y centros comerciales.

· El distrito metropolitano de transito necesita seleccionar un conjunto de líneas que conecten todos los centros a un mínimo costo.

· La red seleccionada debe permitir:

Factibilidad de las líneas que deban ser construidas.

Mínimo costo posible por línea.

Algoritmo

Los algoritmos que pueden dar solución a este problema son:

En este artículo trataremos el algoritmo de Prim como forma de solución para la cobertura minima, debido a la simplicidad que este algoritmo conlleva puede ser aprovechado sin necesidad de ser un gran experto en programación.

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 de Jarnik.Consiste en un algoritmo de la teoría de los grafos para encontrar un árbol de cobertura mínimo en un grafo conexo (grafo que  para cada par de nodos está conectado por un camino, o sea, si para cualquier par de nodos A y B, existe al menos un camino posible desde B hacia A), no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo (grafo donde hay nodos que no pueden ser conectados por medio de un camino).

Pseudocódigo

Traza


Siguiendo el algoritmo de Prim, se tiene:

Código en Java

Demostración

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 es el árbol recubridor mínimo.

Si no, sea e la primera arista agregada durante la construcción de Y, que no está en Y1 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 Y1 es el árbol recubridor mínimo de G hay un camino en Y1 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:

Sea Y2 el grafo obtenido al remover f y agregando Es fácil mostrar que Y2 conexo tiene la misma cantidad de aristas que Y1, y el peso total de sus aristas no es mayor que el de Y1, 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



<!–[if gte mso 9]> Normal 0 21 false false false ES X-NONE X-NONE MicrosoftInternetExplorer4 <![endif]–><!–[if gte mso 9]> <![endif]–> <!–[endif]–>

Comentarios»

No comments yet — be the first.

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: