Análisis y Diseño de AlgoritmosÁrboles de Mínima Expansión

(Minimum Spanning Trees)

DR. JESÚS A. GONZÁLEZ BERNAL

CIENCIAS COMPUTACIONALES

INAOE

Problema de Cableado de Circuitos Electrónicos2

Diseño de circuitos electrónicosInterconectar pines de componentes eléctricamente equivalentes

Interconectar n pines con n-1 cables (cada uno un par de pines)

Preferible cableado que usa menor cantidad de cable

Modelar problema con un grafo conectado no dirigido

V conjunto de pines

E conjunto de conexiones entre pines

W costo de conectar dos pines asociado a los arcos

Problema de Cableado de Circuitos Electrónicos3

Encontrar el subconjunto acíclico T ⊆ E conectando todos los vértices peso total mínimo

T es acíclico y conecta todos los vértices es un árbol conocido como árbol de expansión “spanningtree”

El problema de determinar este árbol se conoce como el problema del árbol de expansión mínimo

∑∈

=Tvu

vuwTw),(

),()(

Algoritmos Cubiertos4

Algoritmo Kruskal

Algoritmo Prim

Tiempo de ejecuciónO(E lgV), implementados con heaps binarios

Mejora para PrimO(E + VlgV) con Fibonacci heaps

Mejora cuando |V| es mucho menor que |E|

Los dos algoritmos son voraces (greedy)Generalmente no garantiza (por lo general) encontrar soluciones globales óptimas

Para MST se puede probar que algunas estrategias sí llevan a un ST con mínimo peso

Creciendo un MST5

Dado un grafo conectado, no dirigido G = (V, E) con una función de peso w : E R

Queremos encontrar un MST para G

Si consideramos estrategia vorazAlgoritmo genérico

Loop Invariante Alg.l Genérico MST6

Antes de cada iteraciónA es un conjunto de algún MST

Cada pasoDeterminar un arco (u,v) que se pueda agregar a A sin violar esta invariante

A ∪ {(u,v)} también es un subconjunto del MST

Un arco con esta característica se llama “arco seguro de A” (safeedge for A)

Porque se puede añadir de forma segura manteniendo la invariante

Algoritmo Genérico MST7

InicializaciónDespués de la línea 1, el conjunto A satisface trivialmente el loopinvariante

MantenimientoEl loop en las líneas 2-4 mantienen la invariante añadiendo sólo arcos seguros

TerminaciónTodos los arcos añadidos a A están en el MST, entonces el conjunto A regresado en la línea 5 debe ser un MST

¿Cómo Encontramos Arcos Seguros?8

Esta es la parte difícil

Regla para reconocer arcos segurosTeorema 23.1

Definiciones9

Un Corte (S, V – S ) (cut) de un grafo no dirigido G = (V, E) es una partición de V.

Un arco (u,v) ∈ E cruza (crosses) el corte (S, V – S) si uno de sus puntos finales esta en S y el otro esta en V – S.

Se dice que un corte respeta un conjunto A de arcos si ningún arco en A cruza el corte

Un arco es un arco ligero cruzando un corte si su peso es el mínimo de los arcos cruzando el corte

Un arco es un arco ligero satisfaciendo una propiedad si su peso es el mínimo entre cualquier arco que satisfaga la propiedad

MST para un Grafo Conectado10

Peso total: 37

No es único, reemplazando (b,c) por (a,h) tenemos otro MST con peso 37

Ejemplos de un Corte11

Teorema 23.1, para reconocer arcos seguros12

Sea G = (V, E) un grafo conectado y no-dirigido con una función de pesos w de valores reales definida sobre E.

Sea A un subconjunto de E que se incluye en algún MST de G, sea (S, V – S) cualquier corte de G que respeta A, y sea (u,v) un arco ligero cruzando (S, V –S). Entonces el arco (u,v) es seguro para A.

Prueba del Teorema 23.113

Sea T un MST que incluye A

Asumimos que T no contiene el arco ligero (u,v)

Construiremos otro MST T’ que incluya A ∪ {(u,v)}Técnica cortar y pegar

Probando que (u, v) es un arco seguro para A

Prueba del Teorema 23.1

Prueba del Teorema 23.115

El arco (u,v) forma un ciclo con los arcos en la ruta p de u a v en TComo u y v están en lados opuestos del corte (S, V – S), entonces hay al menos un arco en T en la ruta p que también cruza el corte

Sea (x,y) ese arco que también cruza el corte

(x,y) no esta en A porque el corte respeta a AComo (x,y) esta en la única ruta de u a v en T, quitando (x,y) rompe a T en dos componentesAñadiendo (u,v) reconectamos los componentes y formamos un nuevo MST T’ = T – {(x,y)} ∪ {(u,v)}

Prueba del Teorema 23.116

Probar ahora que T’ también es un MST

Como (u,v) es un arco ligero que cruza (S, V – S) y (x,y) también cruza este corte

w(u,v) ≤ w(x,y)

Por tantow(T’) = w(T) – w(x,y) + w(u,v)

≤ w(T)

Pero T es un MST, entonces w(T) ≤ w(T’)Entonces T’ también debe ser un MST

Prueba del Teorema 23.117

Ahora probar que (u,v) es realmente un arco seguro para A

Como A ⊆ T’ porque A ⊆ T y (x,y) ∉AEntonces A ∪ {(u,v)} ⊆ T’

Consecuentemente, como T’ es un MST, (u,v) es seguro para A.

Corolario 23.218

Sea G = (V,E) un grafo conectado y no dirigido con una función de pesos w definida sobre E con valores reales.

Sea A un subconjunto de E que esta incluido en algún MST de G

y sea C = (VC, EC) un componente conectado (árbol) en el bosque GA = (V,A)

Si (u,v) es un arco ligero que conecta C a algún otro componente en GA, entonces (u,v) es seguro para A.

Algoritmos de Kruskal y Prim19

Variaciones del algoritmo genérico

Usan regla específica para determinar un arco seguro

KruskalEl conjunto A es un bosque

El arco seguro añadido a A es siempre el arco de menor peso en el grafo que conecta dos componentes distintos

Prim’sEl conjunto A forma un solo árbol

El arco seguro añadido a A es siempre el arco de menor peso que conecta el árbol a un vértice que no esta en el árbol

Kruskal20

El arco seguro a añadir al bosque es aquel arco (u,v) que conecta cualesquiera dos árboles en el bosque pero que tenga el menor peso

Como (u,v) debe ser un arco ligero que conecta C1 a otro árbol

El corolario 23.2 implica que (u,v) es un arco seguro para C1

Kruskal’s es voraz

Algoritmo Kruskal21

Ejemplo de Kruskal22

Ejemplo de Kruskal23

Ejemplo de Kruskal

Tiempo de Ejecución de Kruskal

Depende de la implementación de la estructura de datos conjunto-disjunto (disjoint-set)

O(E lgV).

Prim

Parecido al algoritmo de Dijkstra para encontrar rutas más cortas en un grafo (lo vamos a ver)

PropiedadLos arcos en el conjunto A siempre forman un solo árbol

El árbol se inicia con un vértice raíz arbitrario y crece hasta que el árbol se expande a todos los vértices en V

Cada paso se añade un arco ligero al árbol A que lo conecta con un vértice que esta sin conectar

Por el corolario 23.2, la regla añade sólo arcos que son seguros para A, por tanto al terminar, los arcos de A forman un MST

Prim’s es voraz

Algoritmo Prim

Algoritmo Prim

Priority Queue en un campo llavePara cada vértice v, key[v] es el mínimo peso de cualquier arco que conecta v a un vértice en el árbol

Por convención key[v] = ∞ si ese arco no existe

π[v] nombra al padre de v en el árbol

TAREAEstudiar el “loop-invariant” del algoritmo MST-PRIM

Ejemplo de Prim

Ejemplo de Prim

Ejemplo de Prim

Tiempo de Ejecución de Prim

O(E lgV)

Se puede mejorar con Fibonacci-HeapsO(E + VlgV)