Árboles de Expansión

rboles de expansin.
Definicin: Un rbol de expansin de un grafo no dirigido G=(V, A) y

conexo es un subgrafo G=(V, A) no dirigido, conexo y sin ciclos.
Ejemplo: si el grafo ND es conexo, el rbol abarcador (en
profundidad o anchura) es un rbol de expansin.
Si el grafo es ponderado, el coste del rbol de expansin ser la
suma de los costes de las aristas.
Problema del rbol de expansin de coste mnimo:
Dado un grafo ponderado no dirigido, encontrar el rbol de
expansin de menor coste.
Algoritmo de Prim
Escoger un vrtice cualquiera v. El rbol consta slo del nodo v.
Del resto de vrtices, buscar el que est ms prximo a v (con una
arista (w, v) de mnimo costo). Aadir w y la arista (w, v) al rbol.
Buscar el vrtice ms prximo a cualquiera de estos dos, aadir
ese vrtice y la arista al rbol de expansin.
As sucesivamente hasta haber aadido los n vrtices.
Los rboles de expansin son tiles para difundir y recoger informacin de

control en las redes; a veces son tiles tambin para el enrutamiento
Para difundir datos desde el nodo n: El nodo n realiza una amplia difusin
de los datos en todos los arcos Otros nodos retardan los datos en los arcos de
otros rboles adyacentes
Para recoger datos en el nodo n: Todas las ramas del rbol (todas salvo la n)
envan datos Los otros nodos (todos salvo el n) esperan la recepcin de datos
en todos sus arcos salvo en uno adyacente y, a continuacin, envan los datos
Eytan Modiano Diapositiva 10 del rbol adyacente recibidos ms los propios
por el arco restante
Construccin general de un rbol de expansin

Algoritmo para construir un rbol de expansin para un grafo conexo G =
(N,A):
1) Seleccionar cualquier nodo n en N; N' = {n}; A' = { }
2) Si N' = N, entonces parar (T =(N',A') es un rbol de expansin)
3) Elegir (i,j) A, i N', j N' N' := N'{j}; A' := A'{(i,j)}; ir al paso 2
La conectividad de G garantiza que se puede elegir un arco en el paso 3

siempre
Algoritmo de los rboles de expansin

El algoritmo nunca forma un ciclo, puesto que cada nuevo arco va a un nuevo
nodo
T = (N',A') es un rbol en cada paso del algoritmo, dado que T est siempre
conectado y cada vez que aadimos un arco aadimos
Teorema: si G es un grafo conexo de n nodos, entonces: 1) G contiene al
menos n-1 arcos 2) G contiene un rbol de expansin 3) Si G contiene
exactamente n-1 arcos, G es un rbol de expansin
Algoritmos distribuidos para detectar rboles de expansin
1) Un nodo fijo enva un mensaje de "inicio" por cada arco ad yacen t e del
grafo
2) Cada uno de los otros nodos marca el primer arco en el que se ha recibido el
mensaje de inicio como un arco del rbol de expansin y, a continuacin, enva
Esto es una implementacin distribuida del algoritmo general de los rboles
de expansin
Presenta varios problemas que comparten muchos otros algoritmos.
rbol de expansin de peso mnimo
Dado un grafo con pesos asignados a cada arco, encontrar un rbol de
expansin de peso total mnimo (MST)
Definir un "fragmento" como subrbol de un MST
Teorema:
Dado un fragmento F de un MST, sea a(i,j) un arco de peso mnimo que sale
desde F, donde j no se encuentra en F
Entonces, F extendido con el arco a(i,j) y el nodo j es un fragmento
Demostracin:
Sea M el MST que no incluye a(i,j)
Puesto que a(i,j) no forma parte de M, al aadirlo a M se crea un ciclo. Debe
haber algn enlace en el ciclo b a que sale desde F
Al eliminar b y aadir a se crea un nuevo rbol de expansin. Dado que el

peso de b no puede ser menor que el de a , M' tiene que ser un MST: Si el peso
de a = peso de b, entonces ambos son MST; de lo contrario, M podra no ser un
MST.
rbol de expansin mnima
Aplicaciones:
La aplicacin de estos problemas se ubica en las redes de comunicacin
elctrica, telefnica, carretera, ferroviaria, area, martima, etc. En
donde los nodos representan un consumo elctrico, telfonos
aeropuertos, computadoras,etc
En sistemas distribuidos, interpretacin de datos climatolgicos, visin
artificial, anlisis de imgenes, extraccin de rasgos de parentesco,
anlisis de clusters y bsqueda de superestructuras de quasar,
plegamiento de protenas, reconocimiento de clulas cancerosas, y
otros).
Ejemplo, si la compaa de televisin por cable desea instalar en un
vecindario sus cables pero estos solamente pueden recorrer por
patrones o caminos especficos, seria til saber cuales caminos son los
mas cortos para as ahorrar la mayor cantidad de cable posible.
Otra aplicacin es la de las redes de telecomunicacin para optimizar las
distancias recorridas y asi mismo el material utilizado. Una similar a esta
ltima es utilizada en redes de informacin entre servidores y
computadoras cliente, para disminuir la distancia, aumentar la velocidad
de transmisin de informacin y reducir los costos.
Otra aplicacin mas, aunque menos obvia es que el rbol de expansin
total mnima puede ser usado como solucin aproximada al problema
del viajante de comercio (traveling salesman problem), recuerde que
encontrar la solucin ptima a este problema es NP-Hard.
Representacin:
Nuestro grafo tiene un numero de vrtices, as como ramas o conexiones
entre estos vrtices, adems tiene un numero representante de la
distancia o expansin entre ambos vrtices. Matemticamente se
expresa G(V, E) donde V = (v1, v2, vn ) es un conjunto finito de
vrtices (nodos) y E = Eij en un conjunto finito de enlaces que
representan la conexin entre los terminales o estaciones. Cada enlace
tiene un nmero positivo real asociado denotado por W

= Wijrepresentando distancia, costo, etc.

Árboles de Expansión

Cargado por

Copyright:

Formatos disponibles

Árboles de Expansión

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Árboles de Expansión

Cargado por

Copyright:

Formatos disponibles

rboles de expansin.

Definicin: Un rbol de expansin de un grafo no dirigido G=(V, A) y

Los rboles de expansin son tiles para difundir y recoger informacin de

Construccin general de un rbol de expansin

La conectividad de G garantiza que se puede elegir un arco en el paso 3

Algoritmo de los rboles de expansin

Al eliminar b y aadir a se crea un nuevo rbol de expansin. Dado que el

rbol de expansin mnima

tiene un nmero positivo real asociado denotado por W

También podría gustarte