Arboles Expansion Minima

Programación IV / Clase 9 / Ciclo 02 - 2015 1

Universidad Don Bosco

Facultad de Ingeniería

Escuela de Ingeniería en Computación

Ciclo 02 – 2015 / Grupo: 03T

Asignatura: Programación IV

ÁRBOLES DE EXPANSIÓN MÍNIMA: ALGORITMO DE PRIM Y KRUSKAL

Introducción

Los grafos no dirigidos se emplean para modelar relaciones simétricas entre entes, los vértices del

grafo.

Cualquier arista (v, w) de estos grafos es igual que (w, v), por lo que las aristas en un grafo no

dirigido se dicen formadas por un par ordenado de vértices. Como consecuencia directa, la

representación de un grafo no dirigido da lugar a matrices simétricas.

Una propiedad que normalmente interesa conocer de un grafo no dirigido es “si para todo par de

vértices hay un camino que los une”, en definitiva, si el grafo es conexo. A los grafos conexos

también se les denomina red conectada.

El problema del árbol de expansión de coste mínimo consiste en buscar un árbol que abarque todos

los vértices del grafo, con suma de pesos de aristas mínimo.

Conceptos básicos

Red Conectada. Es una red tal, que cualquier par de vértices pueden ser unidos mediante

un camino.

Árbol. En una red es un subconjunto G’ del grafo G que es conectado y sin ciclos.

Los árboles tienen dos propiedades importantes:

Todo árbol de “n” vértices contiene exactamente “n-1” arcos.

Si se añade un arco al árbol, entonces resulta un ciclo.

Árbol abarcador o árbol de expansión. Es un árbol que contiene a todos los vértices de

una red. Buscar un árbol de expansión de una red es una forma de averiguar si la red es

conectada.


Un árbol abarcador de un grafo conexo no dirigido G = (V, A) es un árbol libre con el conjunto de

nodos V que es un subgrafo de G; esto es, un árbol de expansión es conexo, acíclico y tiene a todo

V como nodos y a parte de A como conjunto de aristas.

Un árbol libre. Es un grafo sencillo no dirigido que es a la vez conexo y acíclico.

Recuérdese que un grafo acíclico es un grafo que carece de ciclos. Es decir que un árbol

libre no contiene ciclos, y todos sus pares de nodos están conectados. En la siguiente figura

se muestran ejemplos de árboles libres:

En la figura siguiente se muestra un grafo no dirigido y su árbol de expansión.

Según el árbol de expansión el grafo es una red conectada.

Ahora que conocemos el concepto de árbol libre, podemos continuar con el estudio de un árbol

abarcador.

Hay muchos enfoques para generar un árbol de expansión correspondiente a un grafo dado. Un

enfoque consiste en eliminar las aristas que pertenezcan a ciclos uno tras otro hasta que no queden

ciclos en el grafo. Si sólo se eliminan aristas de ciclos, entonces el grafo seguirá siendo conexo, y

esto es esencial para la generación de un árbol de expansión.

Como ejemplo de esta aproximación, considérese el grafo (a) de la siguiente figura. Podemos

empezar por borrar la arista {v2, v5}. Esto elimina un ciclo sencillo, el subgrafo resultante sigue

siendo conexo. Los pasos siguientes eliminan las aristas {v2, v6}, {v3, v6}, {v3, v7}, {v4, v7} y {v6, v7}


una tras otra. Esta sucesión de eliminaciones de aristas da lugar al subgrafo (b) de la siguiente

figura:

Observe que se podrían generar muchos árboles de expansión para el grafo dado.

En la siguiente figura se pueden ver otros árboles de expansión para el grafo, por ejemplo:

También puede generarse un árbol de expansión a partir de un recorrido en amplitud y en

profundidad, así consideremos un recorrido en amplitud para el grafo dado, si se utiliza para el grafo

una representación en forma de matriz de adyacencia, la cual se muestra a continuación:

Una búsqueda en amplitud que comience en el nodo V1 dará lugar a un árbol dirigido cuya raíz es

V1. Para el grafo dado como ejemplo, que comienza en V1, una búsqueda primero en amplitud

incluye arcos que van a los nodos V2, V5 y V6. Dado que estas son las únicas aristas incidentes en

V1, se pasa a continuación a incluir los nodos que sean adyacentes a V2, es decir, a los arcos que


van a parar a los nodos V3 y V7. Prosiguiendo de esta manera se llega al árbol con raíz de la

siguiente figura:

Bien hasta este punto la idea es comprender que es un árbol de expansión y que este puede

generarse a partir de los métodos de recorrido antes estudiados, sin embargo podemos ver que

estos árboles no generados no tienen un costo, es decir las aristas del grafo no tienen un peso, por

lo tanto hasta aquí hemos aprendido a generar y comprender el concepto de árbol de expansión; sin

embargo, para ser un árbol de expansión mínimo se requiere que las aristas estén ponderadas o

posean un peso, esto lo estudiamos a continuación.

Construcción de un Árbol de Expansión de Costo Mínimo

Un árbol de expansión para un grafo no dirigido conectado G = (V, E) es un subgrafo de G que es un

árbol no dirigido y contiene todos los vértices de G.

En un grafo ponderado G = (V, E, W), el peso de un subgrafo es la suma de los pesos de las aristas

incluidas en ese subgrafo.

Un árbol de expansión mínimo (AEM ó MST, por sus siglas en inglés) para un grafo ponderado es

un árbol de expansión cuyo peso es mínimo.

Hay muchas situaciones en las que es preciso hallar árboles de expansión mínimos. Siempre que se

busca la forma más económica de conectar un conjunto de terminales, trátese de ciudades,

terminales eléctricas, computadoras o fábricas, empleando por ejemplo carreteras, cables o líneas

telefónicas; una solución es un árbol de expansión mínimo para el grafo que tienen una arista por

cada posible conexión, ponderada con el costo de dicha conexión.

Hallar árboles de expansión mínimos también es un subproblema importante en diversos algoritmos

de ruteo, esdecir, algoritmos para hallar caminos eficientes a través de un grafo que visiten todos los

vértices (o todas las aristas).

V1

V2 V5 V6

V3 V7

V4


La figura siguiente muestra un grafo ponderado, el cual podría tener más de un árbol de expansión

asociado.

Los árboles de expansión de costo mínimo gozan de una propiedad que sirve como base para todos

los algoritmos utilizados para la construcción de los mismos. Esta propiedad establece que si G = (V,

A) es un grafo conexo, U es un subconjunto propio del conjunto de vértices V, y (u, v) es una arista

de costo mínimo tal que u ∈ U y v ∈ V – U, entonces existe un árbol de expansión de costo mínimo

que incluye a (u, v) entre sus aristas.

Algoritmos de Árboles de Ancho Mínimo

Los grafos no dirigidos pueden representarse mediante las estructuras utilizadas para representar

grafos dirigidos, es decir: matriz de adyacencia y lista de adyacencia. Para ello se debe cambiar

cada arista no dirigida entre “u” y “v” por dos aristas dirigidas, una de “u” a “v” y otra de “v” a “u”; por

lo tanto, la matriz de adyacencia resultará una matriz simétrica, y en la lista de adyacencia el vértice

“u” estará en la lista de adyacencia del vértice “v”, y viceversa.

Ahora bien si recuerda anteriormente se estudió el algoritmo de Dijkstra, el cual nos permite

encontrar la ruta mínima desde un vértice o nodo de partida hacia el resto de los vértices de un

grafo, ahora bien este algoritmo sólo es para aplicarlo en los grafos dirigidos no así para los grafos

no dirigidos; para los grafos no dirigidos se utilizan otros algoritmos que permiten construir un árbol

abarcador de costo mínimo o árbol de expansión mínimo. A continuación estudiaremos dichos

algoritmos.

Algoritmo de Prim

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al

que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto

significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya

pertenecen al árbol.


El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por

agregar.

El objetivo del algoritmo de Prim es encontrar el árbol recubridor más corto.

Requisitos:

Ser un grafo conexo.

Ser un grafo sin ciclos.

Tener todos los arcos etiquetados.

La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un árbol previamente

construido. Más explícitamente:

Paso 1. Se elige un vértice u de G y se considera el árbol S={u}

Paso 2. Se considera la arista “e” de mínimo peso que une un vértice de S y un vértice que

no es de S, y se hace S=S+e.

Paso 3. Si el número de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve

al paso 2.


Ejemplo:

Algoritmo de Kruskal

Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo

para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST)

también llamado árbol recubridor euclídeo mínimo.

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos

sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

El Algoritmo de Kruskal que resuelve la misma clase de problema que el de Prim, salvo que en esta

ocasión no partimos desde ningún nodo elegido al azar. Para resolver el mismo problema lo que

hacemos es pasarle a la función una lista con las aristas ordenada de menor a mayor, e iremos

tomando una para formar el ARM.


El algoritmo de Kruskal permite hallar el árbol de expansión mínima 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:

Ejercicio:

Encontrar el árbol de expansión mínima para el siguiente grafo, aplicando algoritmo de Kruskal.


Ejercicio:

1. Determinar el árbol de mínima expansión para el siguiente grafo (aplicar algoritmo de

Kruskal).

1. Elegimos, por ejemplo, la arista (5, 6) = 1 (menor valor) y la marcamos.

2. Elegimos la siguiente arista con menor valor (1, 3) = 1 y la marcamos.

3. 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.



5. 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.






8. 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 lo tanto, el árbol de expansión mínima sería:

Arboles Expansion Minima

Documents

Transcript of Arboles Expansion Minima