Árboles
Árboles. Árboles enraizados I Búsqueda en profundidad. Búsqueda en anchura I Árboles de expansión mínimos

3.3. Árboles de expansión mínimos.

Definición 3.3.1. Un grafo ponderado o grafo con pesos es un grafo G(V, E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso . El peso de un subgrafo de un grafo ponderado es la suma  de los pesos de todas sus aristas.

Ejemplo 3.3.2. Dado el grafo con pesos:

El peso total del grafo es

El peso del subgrafo H formado por los vértices a, b, c, d seria W(H)=8+2+12+6=28.

Definición 3.3.3. Un árbol generador mínimo de un grafo conexo G con pesos es un árbol generador de G que tiene el menor peso. En general no es único. Lo denotaremos por MST(G) (minimum spanning tree).

Proposición 3.3.4. Todo grafo conexo con pesos tiene un árbol generador mínimo.

Proposición 3.3.5. Dado un grafo G con peso, la arista de mayor peso de un ciclo no pertenece a ningún MST(G).

Algoritmos para hallar árboles generadores mínimos.

Algoritmo de Prim. Se parte de un vértice y se van alcanzando los demás, de uno en uno, del modo más económico posible, con respecto al peso de las aristas.

1.      Seleccionar un vértice arbitrario u.

2.      Hacer S={u} y T={}.

3.      Para cada vértice z de V-S asignar t(z)=w(u, z) si existe la arista (u, z). Si esta arista no existe asignar .

4.      Elegir el vértice v de V-S tal que t(v) sea el menor de los números t(z) para todo z de V-S.

5.      Insertar v en S

6.      Insertar la arista (u, v) en T

7.      Mientras :

a)      Para cada z de V-S se actualiza t(z)=min{t(z),w(v, z)}.

b)      Elegir el vértice v de V-S tal que t(v) sea el menor de los números t(z) para todo z de V-S.

c)      Insertar v en S

d)      Insertar en T la arista (u,v) tal que u está en S y t(v)=w(u,v).

Ejemplo 3.3.6. Aplicar el algoritmo de Prim al grafo con pesos del ejemplo 3.3.2

Algoritmo de Kruskal. Se eligen aristas de la forma más económica. Inicialmente se ordenan las aristas por su peso. A continuación se van eligiendo las aristas de menor peso de modo tal, que no formen ciclo con las aristas anteriormente seleccionadas. Para evitar que se formen ciclos se asignan etiquetas a los vértices de modo que los vértices que formen parte de las aristas ya elegidas tengan todos la misma etiqueta.

1.      T={}

2.      Asignar etiquetas a todos los vértices t(i)=i, i=1, 2, ..., n.

3.      Mientras halla vértices con etiquetas diferentes repetir.

a)      Escoger la arista (u, v) de menor peso tal que t(u) sea diferente de t(v). Agregarla a T

b)      Asignar a todos los vértices de una componente conexa de T la misma etiqueta.

Ejemplo 3.3.7. Aplicar el algoritmo de Kruskal al grafo con pesos del ejemplo 3.3.2