ARBOL DE EXPANSION MINIMA

Vista previa del material en texto

Luis Medina Aquino
CICLO 2014-2 
INVESTIGACION DE OPERACIONES II
1
2
Árbol de Expansión Mínima
Luis Medina Aquino
Investigación de Operaciones II
2
3
Introducción
No se minimiza el número de arcos, que se puede demostrar es igual a |V|-1. (uno hacia el padre por vértice, menos la raíz)
Hay varios problemas en los que se desea minimizar la interconexión de varios puntos. Por ejemplo en la confección de circuitos impresos.
El problema consiste buscar el árbol cuya suma de pesos de sus arcos sea mínima en un grafo no dirigido. 
Hay dos algoritmos que resuelven este problema: Algoritmo de Kruskal y algoritmo de Prim (parecido al de Dijkstra - por verse).
Ambos algoritmos corren en tiempo O(E lg V). Si se usa un heap especial (de Fibonacci) el algoritmo de Prim puede correr en O(E + V lg V) lo cual presenta ventajas cuando |V| << |E|
Ambos algoritmos son ejemplos de la heurística de optimización llamada “greedy” (avaro, acaparador)
3
4
Ejemplo de árbol de expansión de mínimo peso
h
i
d
e
g
f
b
c
8
4
11
8
1
2
7
7
2
14
10
6
9
4
a
4
5
Una estrategia de avance
h
i
d
e
g
f
b
c
8
4
11
8
1
2
7
2
14
10
6
9
a
V-S
S
7
4
S
V-S
5
6
Algoritmo Genérico
La idea es ir haciendo crecer el número de nodos que pertenecen al árbol de peso mínimo.
Debemos ir buscando nodos y arcos que puedan ser agregados y que satisfagan la propiedad de mantener mínimo peso.
6
7
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
1
8
4
2
6
7
11
(a)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(c)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(e)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(b)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(d)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(f)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(h)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(g)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(i)
Ejemplo del algoritmo de Prim
2
7
8
Algoritmo de Kruskal (1956)
Aspecto previo: Conjuntos disjuntos
El algoritmo de Kruskal queda mejor definido si utilizamos conjuntos en su descripción. Por ello veremos la definición de un tipo de datos para conjuntos disjuntos.
Consideremos una colección , S, de conjuntos disjuntos S = {S1,S2,S3, .. Sk}.
Cada conjunto será representado por un representante, el cual es un elemento cualquiera del conjunto.
8
9
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
(a)
(c)
(e)
(g)
(b)
(d)
(f)
(h)
Algoritmo de Kruskal :Ejemplo
9
10
Algoritmo de Kruskal :Ejemplo (continuación)
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
2
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
6
7
11
c
b
d
a
h
i
g
f
e
4
8
7
9
14
10
2
1
8
4
6
7
11
(j)
(l)
(n)
(i)
(k)
(m)
10