teoría de grafos Árbol recubridor mínimo distancias

Teoría de Grafos

Árbol recubridor mínimo Distancias

El problema del mínimo árbol recubridor

Boruvka en 1926 se planteo el problema de minimizar el coste del tendido eléctricoen las áreas rurales de Moravia (Republica Checa).Tenemos unas ciertas aldeas representadas por vértices y queremos conectar las líneas telefónicas con el menor coste posible.

Entonces es un árbol

2

5 5

43

2

6

1

2

Tiene que ser conexo.

No debería tener ciclos.

Algoritmo de Boruvka

Encuentra un árbol recubridor de tamaño mínimo cuando todas las aristas tienendistintos pesos.

1.- Inicializar F como el conjunto de vertices del grafo.Mientras el numero de aristas en F sea menor que p.2.- Unir cada componente con otra componente a traves de una arista de coste mínimo.

Coste=0Numero de aristas=0

e3=5

e7=9 e8=8

e6=4e5=3

e4=2

e9=6

e1=1

e2=7

u1

u4

u3

u5

u2

e3=5

e7=9 e8=8

e6=4e5=3

e4=2

e9=6

e1=1

e2=7

u1

u4

u3

u5

u2

Coste=8Numero de aristas=3

e3=5

e7=9 e8=8

e6=4e5=3

e4=2

e9=6

e1=1

e2=7

u1

u4

u3

u5

u2

Coste=11Numero de aristas=4

Algoritmo de Kruskal (1956)• Inicializar el conjunto S al conjunto vacio. S consistirá de las aristas del árbol

recubridor mínimo.• Mientras el numero de aristas sea menor que p

– Añadir a S la arista e de peso mínimo que no forme ciclo

1.- Ordenar las aristas en función del peso.2.- Crear un vector C de longitud p con valores desde 1 hasta p.3. Si queremos añadir la arista vj vk entonces

-si C(vj) es distinto de C(vk) no forma ciclo.Lo añadimos y actualizamos C. Sea m=mínimo (j ,k) y M=máximo (j ,k).Para todo vértice cuyo valor en C es M le asignamos m.- Si son iguales entonces forman ciclo y no utilizamos esa aristas.

Como determinar algorítmicamente si al añadir una arista se crea un ciclo?

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

C=[1 2 3 4 5]Coste=0Numero de aristas=0

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

C=[1 1 3 4 5]Coste=1Numero de aristas=1

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

C=[1 1 1 4 5]Coste=3Numero de aristas=2

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

C=[1 1 1 4 5]Coste=3Numero de aristas=2

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

C=[1 1 1 4 4]Coste=5Numero de aristas=3

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

C=[1 1 1 1 1]Coste=8Numero de aristas=4

Algoritmo de Prim(1957)

1.- Inicializar un árbol T con un vértice aleatorio.2.- Mientras el árbol no tenga mas de p-1 aristas

-añadir el vértice que no pertenece a T que se une a T a través de una arista con coste mínimo

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

Coste=0Numero de aristas=0

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

Coste=2Numero de aristas=1

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

Coste=5Numero de aristas=2

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

Coste=6Numero de aristas=3

e3=2

e7=5 e8=5

e6=4e5=3

e4=2

e9=6

e1=1

e2=2

u1

u4

u3

u5

u2

Coste=8Numero de aristas=4

Teorema (Formula de Cayley). Sea G un grafo completo etiquetado de orden p.Entonces existen p p-2 árboles recubridores mínimos de G.

Ejemplo. Si p=4. Entonces tendremos 42 = 16 árboles recubridores mínimos

v1

v3 v4

v2

v1

v3 v4

v2v1

v3 v4

v2v1

v3 v4

v2

v1

v3 v4

v2v1

v3 v4

v2 v1

v3 v4

v2v1

v3 v4

v2

v1

v3 v4

v2

v1

v3 v4

v2

v1

v3 v4

v2 v1

v3 v4

v2

v1

v3 v4

v2

v1

v3 v4

v2

v1

v3 v4

v2 v1

v3 v4

v2

W1 W7W8

W5W3

W4

W10 W6

W9

W2

¿Cómo mandar un mensaje desde la Workstation 1 a la Workstation 2 de la forma mas rápida. Dos posibles opciones serian:(i) W1-W3-W5-W4-W2(ii) W1-W10-W6-W9-W2

Definición: Dado un grafo G y un par de vértices u y v , la distancia de u a v es la longitud del camino mas corto de u a v. Si no existe un camino de u a v entonces la distancia se define como ∞.

La distancia de u a v es 2 La distancia de x a y es ∞

u v x

y

Teorema. Dado un grafo G. Se cumple:(i) d(u,v) ≥ 0 y d(u,v)=0 si y solo si u=v.(ii) d(u,v)= d(v,u) para todo u, v Є V(G)(iii) d(u,v) ≤ d(u,w) + d(w,v) para todo u, v, w Є V(G)

(i) Evidentemente d(u,v) ≥ 0, ya la distancia es el mínimo numero de aristas para llegar de u a v. Si no están conectados será ∞. Si es 0 no hay aristas y es el mismo vértice.

(ii) Simplemente recorrer el camino al revés.(iii) Sea P el camino mas corto de u a w y Q el camino mas corto de w a v. Entonces P seguido de Q es una cadena de u a v que tiene longitud d(u,w)+d(w,v). Vimos que dada una cadena existe un camino de u a v. Por tantod(u,v) ≤ d(u,w) + d(w,v)

Algoritmo extendido Moore’s Breadth First Search

Permite encontrar el camino más corto desde un vértice u a cualquier vértice v del grafo.

1.- Inicializar la distancia l de u a a u a 0, l (u ,u)=0 y la distancia de u a v donde v ≠ ua ∞, l( u, v)= ∞ .2.- Poner u en la cola.Hasta que la cola se quede vacía

3.-Eliminar el primer elemento x de la cola.4.-Añadir los vecinos y del vértice eliminado que tienen distancia infinita a la cola y asignarles l( y) = l( x)+1.

.

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

Colau

u

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞

Colav1 v2 v5

u

v1v5

D=1

v2

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞

Colav2 v5 v4

u

v1v5

D=1

v2

D=2v4

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞

Colav5 v4 v3

u

v1v5

D=1

v2

D=2v4 v3

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 2 ∞ ∞ ∞ 2

Colav4 v3 v6 v10

u

v1v5

D=1

v2

D=2v4 v3

v6 v10

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 2 ∞ ∞ ∞ 20 1 1 2 2 1 2 3 ∞ ∞ 2

Colav3 v6 v10 v7

u

v1v5

D=1

v2

D=2v4 v3

v6 v10

D=3 v7

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 2 ∞ ∞ ∞ 20 1 1 2 2 1 2 3 ∞ ∞ 2

Colav6 v10 v7

u

v1v5

D=1

v2

D=2v4 v3

v6 v10

D=3 v7

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 2 ∞ ∞ ∞ 20 1 1 2 2 1 2 3 ∞ ∞ 2

Colav10 v7

u

v1v5

D=1

v2

D=2v4 v3

v6 v10

D=3 v7

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 2 ∞ ∞ ∞ 20 1 1 2 2 1 2 3 ∞ ∞ 2

Colav7

u

v1v5

D=1

v2

D=2v4 v3

v6 v10

D=3 v7

v1

v7

v4

v10

v8

v9

v6

v3v2

v5

u

u v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞0 1 1 ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞0 1 1 ∞ 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 ∞ ∞ ∞ ∞ ∞0 1 1 2 2 1 2 ∞ ∞ ∞ 20 1 1 2 2 1 2 3 ∞ ∞ 2

Colau

v1v5

D=1

v2

D=2v4 v3

v6 v10

D=3 v7

v8

v9D=∞

Algoritmo de Dijkstra

1.- Inicializa la distancia de u a todos los vértices v ≠ u a ∞ y la distancia de u a u a 0.Crear un conjunto S donde están los vértices cuya distancia ya esta determinada S<-u.Contador=0.

Mientras contador sea menor que p -1. Siendo p el orden del grafo.

2.- Para cada vértice v que no pertenece a S y es adyacente al ultimo vértice añadido a S: si l(v) ≤ l(ui) +w(ui,v) entonces no hacer nada, de otra forma l(v) = l(ui) +w(ui,v).

3.- De los vértices que no pertenecen a S, Determinar el que tiene menor distancia y añadirlo a S

4.Contador= Contador+1.

v1 v5

v6

v2 v3

v4

v7

u0

16

13

10

911

6

14 5

7

8

17

l(u0) v1 v2 v3 v4 v5 v6 v7 activo (S)

0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) u0

(∞,-) (13,u0) (∞,-) (16,u0) (8,u0) (∞,-) (∞,-) v5

(18,v5) (13,u0) (25,v5) (15,v5) (∞,-) (∞,-)

(8)

v2 (13)

(18,v5) (25,v5) (15,v5) (∞,-) (∞,-) v4 (15)

(18,v5) (20,v4) (∞,-) (∞,-) v1 (18)

(20,v4) (∞,-) (∞,-) v3 (20)

(∞,-) (∞,-)

l(u0) v1 v2 v3 v4 v5 v6 v7 activo (S)

0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) u0

(∞,-) (13,u0) (∞,-) (16,u0) (8,u0) (∞,-) (∞,-) v5

(18,v5) (13,u0) (25,v5) (15,v5) (∞,-) (∞,-)

(8)

v2 (13)

(18,v5) (25,v5) (15,v5) (∞,-) (∞,-) v4 (15)

(18,v5) (20,v4) (∞,-) (∞,-) v1 (18)

(20,v4) (∞,-) (∞,-) v3 (20)

(∞,-) (∞,-)

V3(20)

V4(15)

V5(8)

u0

V1(18)

V2(13)

V6 (∞) V7 (∞)

Observación: El algoritmo de Dijkstra es mas general que Moore ya que poniendo 1 como peso también encontraría el camino con menos aristas

Centro y mediana de un grafo

Si en el grafo anterior, las aristas representan calles y los vértices intersecciones.¿Dónde colocar un puesto de policía? ¿Y un quiosco?

El puesto de policía debería estar en el vértice que minimice el tiempo de respuesta entre la estación y el posible punto de acción. ES decir, minimizar la distancia mas larga.El quiosco debería minimizar el promedio de las distancias al puesto.

Se define la excentricidad de un vértice v en un grafo como la distancia de v al vértice mas lejano.

Se define el radio de un grafo como el mínimo de las excentricidades de los vértices del grafo.

Se define el diámetro de un grafo como el máximo de las excentricidades del grafo.

Se define el centro del grafo como el subgrafo inducido por los vértices con excentricidad igual al radio.

Se define la distancia de un vértice v en un grafo como la suma de las distancias de v a cada vértice de G.Se define la mediana como el subgrafo inducido por los vértices que tienen mínima distancia

v7

v4

v9

v6

v3

v1

v8

v5

v2e=6

e=3

e=5

e=4

e=3

e=3

e=5

e=6

e=4

Distancias:

V1: 1 2 3 3 3 4 5 6->27

V3: 1 1 2 2 2 3 4 5->20

V6: 2 1 1 1 1 2 3 4->15

V9->16

V8->15

V7->15

V6->15

V5->20

V4->15V2->27

RadioDiámetroCentroMediana

36

<v4 v6 v7 v8>

<v4 v7 v9> Policía

Quiosco