Problema Arbol Expandido.docx

Problema Árbol Expandido Mínimo Este problema surge cuando todos los nodos de una red deben conectarse entre ellos. El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, el flujo a lo largo de los arcos se considera instantáneo. Este problema se refiere a utilizar las ramas o arcos de la red para llegar a todos los nodos de la red, de manera talque se minimiza la longitud total. La aplicación de estos problemas de optimización se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc.; donde los nodos representan puntos de consumo eléctrico, teléfonos, aeropuertos, computadoras. Otro ejemplo es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por una o más poblaciones adicionales. Y los arcos podrían ser de alta tensión, cable de fibra óptica, rutas aéreas, etc. Si n = número de nodos, entonces la solución óptima debe incluir n-1 arcos.



Árbol: Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como:

o o



Un grafo conexo y sin ciclos. Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.

Grado de un nodo en un árbol es el número de subárboles de aquel nodo (en el ejemplo, el grado de v1 es 2 y de v2 1).

  

Denominamos hojas en un árbol a los nodos finales (v3, v5 y v6). Un árbol de máximo alcance es aquel que obtenemos en un grafo conexo y sin ciclos. Árbol de mínima expansión: Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es mínima.

ALGORITMO DE KRUSKAL El algoritmo de Kruskal permite hallar el árbol minimal de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos: 1.

Se marca la arista con menor valor. Si hay más de una, se elige cualquiera de ellas.

2.

De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera de ellas.

3.

Repetir el paso 2 siempre que la arista elegida no forme un ciclo con las ya marcadas.

4.

El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo.

Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo:

Siguiendo el algoritmo de Kruskal, tenemos:

  

Elegimos, por ejemplo, la arista (5, 6) = 1 (menor valor) y la marcamos. Elegimos la siguiente arista con menor valor (1, 3) = 1 y la marcamos. Elegimos la siguiente arista con menor valor (5, 7) = 2 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.



Elegimos la siguiente arista con menor valor (1, 2) = 3 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.



Elegimos la siguiente arista con menor valor (6, 7) = 4 y la desechamos, ya que forma ciclos con las aristas (5,

7) y (5, 6) marcadas anteriormente.



Elegimos la siguiente arista con menor valor (2, 5) = 5 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.



Elegimos la siguiente arista con menor valor (4, 5) = 6 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.



FIN. Finalizamos dado que los 7 nodos del grafo están en alguna de las aristas, o también ya que tenemos marcadas 6 aristas (n-1).



Por tanto el árbol de mínima expansión resultante sería:

ALGORITMO DE PRIM El algoritmo de Prim permite hallar el árbol minimal de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos: 1.

Se marca un nodo cualquiera, será el nodo de partida.

2.

Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.

3.

Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

4.

El proceso termina cuando tenemos todos los nodos del grafo marcados.

Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo:

Siguiendo el algoritmo de Prim, tenemos:

 

Elegimos, por ejemplo, el nodo 1 y lo marcamos. Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.



Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.



Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.



Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.



Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.



Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.

 

FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo. Por tanto el árbol de mínima expansión resultante sería:

Ejemplo 1: Dada la siguiente red obtenga el árbol de expansión mínima.