Programa de teora

Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones. 2. Conjuntos y diccionarios. 3. Representacin de conjuntos mediante rboles.

4. Grafos.

Parte II. Algortmica.

1. Anlisis de algoritmos. 2. Divide y vencers. 3. Algoritmos voraces. 4. Programacin dinmica. 5. Backtracking. 6. Ramificacin y poda.

A.E.D.

PARTE I: ESTRUCTURAS DE DATOS

Tema 4. Grafos.
4.1. Introduccin, notacin y definiciones. 4.2. Representacin de grafos. 4.3. Problemas y algoritmos sobre grafos.
4.3.1. Recorridos sobre grafos. 4.3.2. rboles de expansin mnimos. 4.3.3. Problemas de caminos mnimos. 4.3.4. Algoritmos sobre grafos dirigidos. 4.3.5. Algoritmos sobre grafos no dirigidos. 4.3.6. Otros problemas con grafos.
A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo de carreteras entre ciudades.

Corua
17 1

Oviedo
45 5 356

304
28 0

Bilbao
32

3 95

Vigo

Zaragoza
296

0 10

Gerona

4
32
25

Valladolid
40 3

Barcelona
34 9
19 1
2 41

335

19 3

Madrid
1

Badajoz Sevilla
12 5

Albacete
0 15
99

Valencia

Jan
2 24 25 6

2 78

Murcia

Cdiz

Granada

A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo de carreteras entre ciudades.

Problemas
Cul es el camino ms corto de Murcia a Badajoz? Existen caminos entre todos los pares de ciudades? Cul es la ciudad ms lejana a Barcelona? Cul es la ciudad ms cntrica? Cuntos caminos distintos existen de Sevilla a Zaragoza? Cmo hacer un tour entre todas las ciudades en el menor tiempo posible?

A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo de transiciones de un AFD.

b inicio a b 1 b a a a 2 b 3

A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo de transiciones de un AFD.

Problemas La expresin: a b b a b a b b b a, es una

expresin vlida del lenguaje? Cul es la expresin vlida ms corta? Transformar el grafo en una expresin regular y viceversa.

A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo de planificacin de tareas.

Licencia de obras

Aplanar terreno

Comprar piedras

Hacer camino

Cincelar piedras

Pintar pirmide

Colocar piedras

A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo de planificacin de tareas.

Problemas
En cuanto tiempo, como mnimo, se puede construir la pirmide? Cundo debe empezar cada tarea en la planificacin ptima? Qu tareas son ms crticas (es decir, no pueden sufrir retrasos)? Cunta gente necesitamos para acabar las obras?
A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo asociado a un dibujo de lneas.

Modelo 1
2 2 5 5 6 6

Escena
1 1 3 3 4 4 7 7

Modelo 2

a a

b b e e

c c

d d

A.E.D.

4.1.1. Ejemplos de grafos. Ejemplo: Grafo asociado a un dibujo de lneas.

Problemas
Cuntos grupos hay en la escena? Qu objetos estn visibles en la escena y en qu posiciones? Qu correspondencia hay entre puntos del modelo y de la escena observada? Qu objetos son isomorfos?

A.E.D.

4.1.1. Ejemplos de grafos.

Corua
171

Oviedo
45 5 356

304
28 0

Bilbao Zaragoza
296
0 10

395

Vigo

Gerona

b a

Valladolid
3 40

5 32

4 32

Barcelona

Madrid
335
25 1

34 9

3 19

inicio

191
241

b a

Badajoz

Albacete
150

Valencia

12 5

42 Sevilla 2 25 6

Jan
99

278

Murcia

Cdiz

Granada

A|6 B|4 D|3 C|2 E|8 F|9

G|3

A.E.D.

4.1. Introduccin y definiciones. Un grafo G es una tupla G= (V, A), donde V es un conjunto no vaco de vrtices o nodos y A es un conjunto de aristas o arcos. Cada arista es un par (v, w), donde v, w V.

Tipos de grafos v Grafo no dirigido. Las aristas no estn ordenadas: (v, w) = (w, v) Grafos dirigidos (o digrafos). v Las aristas son pares ordenados: <v, w> <w, v> <v, w> w = cabeza de la arista, v = cola.
A.E.D.

4.1.2. Terminologa de grafos. Nodos adyacentes a un nodo v: todos los nodos unidos a v mediante una arista. En grafos dirigidos:
Nodos adyacentes a v: todos los w con <v, w> A. Nodos adyacentes de v: todos los u con <u, v> A.

Un grafo est etiquetado si cada arista tiene asociada una etiqueta o valor de cierto tipo. Grafo con pesos: grafo etiquetado con valores numricos.
Grafo etiquetado: G= (V, A, W), con W: A TipoEtiq
A.E.D.

4.1.2. Terminologa de grafos. Camino de un vrtice w1 a wq: es una secuencia w1, w2, ..., wq V, tal que todas las aristas (w1, w2), (w2, w3), ..., (wq-1, wq) A. Longitud de un camino: nmero de aristas del camino = n de nodos -1. Camino simple: aquel en el que todos los vrtices son distintos (excepto el primero y el ltimo que pueden ser iguales). Ciclo: es un camino en el cual el primer y el ltimo vrtice son iguales. En grafos no dirigidos las aristas deben ser diferentes. Se llama ciclo simple si el camino es simple.
A.E.D.

4.1.2. Terminologa de grafos. Un subgrafo de G=(V, A) es un grafo G=(V, A) tal que VV y AA. Dados dos vrtices v, w, se dice que estn conectados si existe un camino de v a w. Un grafo es conexo (o conectado) si hay un camino entre cualquier par de vrtices. Si es un grafo dirigido, se llama fuertemente conexo. Un componente (fuertemente) conexo de un grafo G es un subgrafo maximal (fuertemente) conexo.
A.E.D.

4.1.2. Terminologa de grafos. Un grafo es completo si existe una arista entre cualquier par de vrtices. Para n nodos, cuntas aristas tendr un grafo completo (dirigido o no dirigido)? Grado de un vrtice v: nmero de arcos que inciden en l. Para grafos dirigidos: Grado de entrada de v: n de aristas con <x, v> Grado de salida de v: n de aristas con <v, x>

A.E.D.

4.1.3. Operaciones elementales con grafos. Crear un grafo vaco (o con n vrtices). Insertar un nodo o una arista. Eliminar un nodo o arista. Consultar si existe una arista (obtener la etiqueta). Iteradores sobre las aristas de un nodo: para todo nodo w adyacente a v hacer accin sobre w para todo nodo w adyacente de v hacer accin sobre w
A.E.D.

Mucho menos frecuente

4.2. Representacin de grafos.

Representacin de grafos:
Representacin del conjunto de nodos, V. Representacin del conjunto de aristas, A.
1 3 4 5 2

Ojo: las aristas son relaciones muchos a muchos entre nodos...

A.E.D.

 Representacin del conjunto de aristas, A.

Mediante matrices de adyacencia.
M 1 2 3 4 5 T T 1 2 T 3 T T T T T 4 5

4.2. Representacin de grafos.

1 3 4

Mediante listas de adyacencia.

1 2 3 4 5 2 3 1 4 3 5 4 5

+ +t

A.E.D.

4.2.1. Matrices de adyacencia. tipo GrafoNoEtiq= array [1..n, 1..n] de booleano Sea M de tipo GrafoNoEtiq, G= (V, A). M[v, w] = cierto (v, w) A
M 1 3 4 5 2
1 2 3 4 5 T T 1 T T 2 T T T T T T T T 3 4 T T 5

Grafo no dirigido Matriz simtrica: M[i, j] = M[j, i]. Resultado: se desperdicia la mitad de la memoria.
A.E.D.

4.2.1. Matrices de adyacencia. Grafos etiquetados: tipo GrafoEtiq[E]= array [1..n, 1..n] de E El tipo E tiene un valor NULO, para el caso de no existir arista.
1 M
1 2 3 1 2 3 4

3 2 4 2 2 4

3 2 0 4 2

Cmo seran los iteradores: para todo adyacente a, y adyacente de? Y contar nmero de aristas? Cunto es el tiempo de ejecucin?
A.E.D.

Uso de memoria
k2 bytes/etiqueta

4.2.1. Matrices de adyacencia.

Memoria usada: k2n2

Ventajas
Representacin y operaciones muy sencillas. Eficiente para el acceso a una arista dada.

Inconvenientes
El nmero de nodos del grafo no puede cambiar. Si hay muchos nodos y pocas aristas (a<<n2) se desperdicia mucha memoria (matriz escasa).
A.E.D.

4.2.2. Listas de adyacencia. tipo Nodo= entero (1..n) tipo GrafoNoEtiq= array [1..n] de Lista[Nodo] Sea R de tipo GrafoNoEtiq, G= (V, A). La lista R[v] contiene los w tal que (v, w) A.
1 1 1 2 1 2 2 2 4 3 4 5 4 3 5

1 3 4

2 3 4

Grafo no dirigido Las aristas estn repetidas. Resultado: tambin se desperdicia memoria.
A.E.D.

4.2.2. Listas de adyacencia. Grafos etiquetados: tipo GrafoEtiq[E]= array [1..n] de Lista[Nodo,E]
1 a b 4 2 d c 3 a
1 2 3 4

2 a 4 b 1 a 2 c 4 d

Cmo seran los iteradores: para todo adyacente a, y adyacente de? Y contar nmero de aristas? Cunto es el orden de complejidad? Se suponen: n nodos y a aristas.
A.E.D.

Uso de memoria

4.2.2. Listas de adyacencia.

k1 bytes/puntero, k2 bytes/etiqueta o nodo Memoria usada: k1(n+a) + 2k2a Con matrices de adyacencia: k2n2 Cul usa menos memoria?

Ventajas
Ms adecuada cuando a<<n2.

Inconvenientes
Representacin ms compleja. Es ineficiente para encontrar las aristas que llegan a un nodo.
A.E.D.

4.2.3. Listas mltiples de adyacencia. Alternativa: Usar estructuras de listas mltiples.

Lista de arcos de salida. Lista de arcos de entrada a 1 d 3 array de nodos 1 2 3
lista_ent lista_sal

b c e registros de aristas 2

a b

d e
sig_ent valor sig_sal

A.E.D.

4.3. Problemas y algoritmos sobre grafos.

4.3.1. Recorridos sobre grafos. 4.3.2. rboles de expansin mnimos. 4.3.3. Problemas de caminos mnimos. 4.3.4. Algoritmos sobre grafos dirigidos. 4.3.5. Algoritmos sobre grafos no dirigidos. 4.3.6. Otros problemas con grafos.

A.E.D.

4.3.1. Recorridos sobre grafos. Idea similar al recorrido en un rbol. Se parte de un nodo dado y se visitan los vrtices del grafo de manera ordenada y sistemtica, movindose por las aristas. Tipos de recorridos:
Bsqueda primero en profundidad. Equivalente a un recorrido en preorden de un rbol. + Bsqueda primero en amplitud o anchura. Equivalente a recorrer un rbol por niveles.

Los recorridos son una herramienta til para resolver muchos problemas sobre grafos.
A.E.D.

4.3.1. Recorridos sobre grafos. El recorrido puede ser tanto para grafos dirigidos como no dirigidos. Es necesario llevar una cuenta de los nodos visitados y no visitados. var marca: array [1, ..., n] de (visitado, noVisitado) operacin BorraMarcas para i:= 1, ..., n hacer marca[i]:= noVisitado

A.E.D.

4.3.1.1. Bsqueda primero en profundidad.

operacin bpp (v: nodo) marca[v]:= visitado para cada nodo w adyacente a v hacer si marca[w] == noVisitado entonces bpp(w) finpara operacin BsquedaPrimeroEnProfundidad BorraMarcas para v:= 1, ..., n hacer si marca[v] == noVisitado entonces bpp(v) finpara
A.E.D.

4.3.1.1. Bsqueda primero en profundidad.

El recorrido no es nico: depende del nodo inicial y del orden de visita de los adyacentes. El orden de visita de unos nodos a partir de otros puede ser visto como un rbol: rbol de expansin en profundidad asociado al grafo. Si aparecen varios rboles: bosque de expansin en profundidad. Ejemplo. Grafo no dirigido.

2 7 6 8

9 5

A.E.D.

4.3.1.1. Bsqueda primero en profundidad.

Bosque de expansin en profundidad

1 2 6 3
1 2

4 5

7 8

9
4 5

Arcos del rbol

9

Arcos no del rbol

Arcos no del rbol: si marca[v] == noVisitado ... se detectan cuando la condicin es falsa. +
A.E.D.

4.3.1.1. Bsqueda primero en profundidad.

Ejemplo: Grafo dirigido.

b c
a

Bosque de expansin
1

b c d e

e a

Arco de Arco de retroceso cruce

Arco de avance

Cunto es el tiempo de ejecucin de la BPP? Imposible predecir las llamadas en cada ejecucin. Solucin: medir el trabajo total realizado. A.E.D.

4.3.1.2. Bsqueda primero en anchura (o amplitud).

Bsqueda en anchura empezando en un nodo v:

Primero se visita v. Luego se visitan todos sus adyacentes. Luego los adyacentes de estos y as sucesivamente.

El algoritmo utiliza una cola de vrtices. Operaciones bsicas:

Sacar un nodo de la cola. Aadir a la cola sus adyacentes no visitados.
operacin BsquedaPrimeroEnAnchura BorraMarcas para v:= 1, ..., n hacer si marca[v] == noVisitado entonces bpa(v) A.E.D.

4.3.1.2. Bsqueda primero en anchura (o amplitud). operacin bpa (v: Nodo) var C: Cola[Nodo] x, y: Nodo marca[v]:= visitado InsertaCola (v, C) mientras NOT EsVacaCola (C) hacer x:= FrenteCola (C) SuprimirCola (C) para cada nodo y adyacente a x hacer si marca[y] == noVisitado entonces marca[y]:= visitado InsertaCola (y, C) finsi finpara finmientras
A.E.D.

4.3.1.2. Bsqueda primero en anchura (o amplitud).

Ejemplo. Grafo no dirigido.

2 6 7 8

4 9 5

Bosque de expansin en anchura.

1 2 6
4 2 1

4 3
3

5 7
5

Arcos de cruce

A.E.D.

4.3.1.2. Bsqueda primero en anchura (o amplitud).

Ejemplo: Grafo dirigido.

b c
a

Bosque de expansin
1

b c
3

e a

Cunto es el tiempo de ejecucin de la BPA? Cmo comprobar si un arco es de avance, cruce, etc.? Solucin: Construir el bosque explcitamente.
A.E.D.

4.3.1. Recorridos sobre grafos. Construccin explcita del bosque de expansin: Usamos una estructura de punteros al padre. marca: array [1, ..., n] de entero marca[v] vale: -1 si v no est visitado 0 si est visitado y es raz de un rbol En otro caso indicar cual es el padre de v

Modificar BorraMarcas, bpp y bpa, para construir el bosque de expansin.

Arco de avance <v, w>: w es hijo de v en uno de los rboles del bosque. Arco de retroceso <v, w>: v es hijo de w. Arco de cruce <v, w>: si no se cumple ninguna de las anteriores. A.E.D.

4.3.1.3. Ejemplos de aplicacin de los recorridos.

Problema 1: Encontrar los componentes conexos de un grafo no dirigido.

1 8 6 2 9 10 4 5

Problema 2: Prueba de aciclicidad. Dado un grafo (dirigido o no dirigido) comprobar si tiene algn ciclo o no.
A.E.D.

4.3.1.3. Ejemplos de aplicacin de los recorridos.

Prueba de aciclicidad.
Grafo no dirigido. Hacer una BPP (o BPA). Existe algn ciclo si y slo si aparece algn arco que no es del rbol de expansin. Grafo dirigido. Hacer una BPP (o BPA). Existe un ciclo si y slo si aparece algn arco de retroceso.

Orden de complejidad de la prueba de aciclicidad: igual que los recorridos. Con matrices de adyacencia: O(n2). Con listas de adyacencia: O(a+n).

A.E.D.

4.3.2. rboles de expansin mnimos. Definicin: Un rbol de expansin de un grafo G=(V, A) no dirigido y conexo es un subgrafo G=(V, A) conexo y sin ciclos. Ejemplo: los rboles de expansin en profundidad y en anchura de un grafo conexo. En grafos con pesos, el coste del rbol de expansin es la suma de los costes de las aristas. Problema del rbol de expansin de coste mnimo: Dado un grafo ponderado no dirigido, encontrar el rbol de expansin de menor coste.

A.E.D.

4.3.2. rboles de expansin mnimos.

3 1 5 6 6 2 4 3 2

Problema: Conectar todos los ordenadores con el menor coste total. Solucin: Algoritmos clsicos de Prim y Kruskal. + A.E.D.

4.3.2.1. Algoritmo de Prim.

Esquema:
1. Empezar en un vrtice cualquiera v. El rbol consta inicialmente slo del nodo v. 2. Del resto de vrtices, buscar el que est ms prximo a v (es decir, con la arista (v, w) de coste mnimo). Aadir w y la arista (v, w) al rbol. 3. Buscar el vrtice ms prximo a cualquiera de estos dos. Aadir ese vrtice y la arista al rbol de expansin. 4. Repetir sucesivamente hasta aadir los n vrtices.
+ A.E.D.

4.3.2.1. Algoritmo de Prim.

Ejemplo de ejecucin del algoritmo.
1 1 5 4 6 6 5 5 2 4 6 3 2 2

3 3

A.E.D.

4.3.2.1. Algoritmo de Prim. La solucin se construye poco a poco, empezando con una solucin vaca. Implcitamente, el algoritmo maneja los conjuntos:
V: Vrtices del grafo. U: Vrtices aadidos a la solucin. V-U: Vrtices que quedan por aadir.

Cmo implementar eficientemente la bsqueda: encontrar el vrtice de V-U ms prximo a alguno de los de U?
A.E.D.

 Se usan dos arrays: MAS_CERCANO: Para cada vrtice de V-U indica el vrtice de U que se encuentra ms prximo. MENOR_COSTE: Indica el coste de la arista ms cercana.

4.3.2.1. Algoritmo de Prim.

Estructura del algoritmo de Prim: C[v, w] Matriz de costes

1. Inicialmente U= {1}. MAS_CERCANO[v]= 1. MENOR_COSTE[v]= C[1, v], para v= 2..n 2. Buscar el nodo v, con MENOR_COSTE mnimo. Asignarle un valor muy grande (para no volver a cogerlo). 3. Recalcular MAS_CERCANO y MENOR_COSTE de los nodos de V-U. Para cada w de V-U, comprobar si C[v, w] es menor que MENOR_COSTE[w]. 4. Repetir los dos puntos anteriores hasta que se hayan aadido los n nodos. A.E.D.

4.3.2.1. Algoritmo de Prim.

Ejemplo: Mostrar la ejecucin del algoritmo sobre el grafo.
3 3 1 5 4 6 1 2 2 2 5 5 4 6 3

Dnde est almacenado el resultado del algoritmo? Cul es el orden de complejidad del algoritmo?
A.E.D.

4.3.2.2. Algoritmo de Kruskal.

Esquema: G= (V, A)
1. Empezar con un grafo sin aristas: G= (V, ) 2. Seleccionar la arista de menor coste de A. 3. Si la arista seleccionada forma un ciclo en G, eliminarla. Si no, aadirla a G. 4. Repetir los dos pasos anteriores hasta tener n-1 aristas. Cmo saber si una arista (v, w) provocar un ciclo en el grafo G?
A.E.D.

4.3.2.2. Algoritmo de Kruskal.

Ejemplo: Mostrar la ejecucin del algoritmo en el siguiente grafo.
3 3 1 5 4 6 1 6 5 5 2 4 6 3 2 2

A.E.D.

4.3.2.2. Algoritmo de Kruskal.

Implementacin del algoritmo Necesitamos:

Ordenar las aristas de A, de menor a mayor: O(a log a). Saber si una arista dada (v, w) provocar un ciclo. Cmo comprobar rpidamente si (v, w) forma un ciclo? Una arista (v, w) forma un ciclo si v y w estn en el mismo componente conexo. La relacin estar en el mismo componente conexo es una relacin de equivalencia.

A.E.D.

4.3.2.2. Algoritmo de Kruskal.

Usamos la estructura de relaciones de equivalencia con punteros al padre:

Inicializacin: crear una relacin de equivalencia vaca (cada nodo es un componente conexo). Seleccionar las aristas (v, w) de menor a mayor. La arista forma ciclo si: Encuentra(v)=Encuentra(w) Aadir una arista (v, w): Unin(v, w) (juntar dos componentes conexos en uno).

Mostrar la ejecucin sobre el grafo de ejemplo. Cul es el orden de complejidad del algoritmo?
A.E.D.

4.3.2. rboles de expansin mnimos.

Conclusiones Ambos algoritmos (Prim y Kruskal) encuentran siempre la solucin ptima. La solucin obtenida ser la misma, o no... La estructura de los dos algoritmos es muy parecida:
Empezar con una solucin vaca. Aadir en cada paso un elemento a la solucin (Prim: un nodo; Kruskal: una arista). Una vez aadido un elemento a la solucin, no se quita (no se deshacen las decisiones tomadas).
A.E.D.

4.3.3. Problemas de caminos mnimos. Coste de un camino: suma de los costes de las aristas por las que pasa. Problemas de caminos mnimos:
Camino mnimo entre dos nodos, v y w. Caminos mnimos entre un nodo v y todos los dems. Caminos mnimos entre todos los pares de nodos.
Corua
17 1

Oviedo
45
356

304

Bilbao
4 32

395

Vigo

28 0

Zaragoza
2 96

0 10

Gerona

Valladolid
40 3

25

Barcelona
34 9
191
241

335

3 19

Madrid
25 1

Valencia

Badajoz Jan Sevilla

12 5
24 2

Albacete
15 0
99

25 6

2 78

Murcia

Cdiz

Granada

A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Algoritmo de Dijkstra Supongamos un grafo G, con pesos positivos y un nodo origen v. El algoritmo trabaja con dos conjuntos de nodos: Escogidos: S. Nodos para los cuales se conoce ya el camino mnimo desde el origen. Candidatos: T. Nodos pendientes de calcular el camino mnimo, aunque conocemos los caminos mnimos desde el origen pasando por nodos de S.
A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Camino especial: camino desde el origen hasta un nodo, que pasa slo por nodos escogidos, S. S
1 2 6 3 8 7 5 4

T
9

Idea: En cada paso, coger el nodo de T con menor distancia al origen. Aadirlo a S. Recalcular los caminos mnimos de los dems candidatos, pudiendo pasar por el nodo cogido.
A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Algoritmo de Dijkstra Inicializacin: S= {1}, T= {2, ..., n}, caminos especiales mnimos = caminos directos. Repetir n-1 veces: Seleccionar el nodo v de T con el camino especial ms corto. Proposicin: el camino mnimo para este nodo v, coincide con su camino especial. Recalcular los caminos especiales para los nodos de T, pudiendo pasar por v.

A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Implementacin del algoritmo de Dijkstra Suponemos que el origen es el nodo 1. D: array [2..n] de real. D[v] almacena el coste del camino especial mnimo para el nodo v. P: array [2..n] de entero. P[v] almacena el ltimo nodo en el camino especial mnimo de v. Inicializacin: D[v]:= C[1, v], P[v]:= 1 Nodo seleccionado: nodo de T con mnimo D[v] Actualizacin: para todos los w de T hacer si D[v] + C[v, w] < D[w] entonces D[w]:= D[v] + C[v, w] P[w]:= v finsi
A.E.D.

4.3.3.1. Caminos mnimos desde un origen.

D[v]
1

v w

T C[v, w]

D[w]
Camino especial para w:
Sin pasar por v: D[w] Pasando por v: D[v] + C[v,w] Nos quedamos con el menor.

Si el menor es pasando por v entonces: P[w]= v. Camino especial para w: 1 ... P[P[P[w]]] P[P[w]] P[w] w
A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Algoritmo de Dijkstra Entrada:

C: array [1..n, 1..n] de real Matriz de costes

Salida:
D: array [2..n] de real Costes de caminos mnimos P: array [2..n] de entero Nodos de paso

Datos para clculos intermedios: Inicializacin:

S: array [2..n] de booleano Nodos escogidos

para v:= 2, ..., n hacer D[v]:= C[1, v] P[v]:= 1 S[v]:= FALSE finpara A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Algoritmo de Dijkstra

para i:= 1, ..., n-1 hacer v:= nodo con S[v]==FALSE y mnimo D[v] S[v]:= TRUE para cada nodo w adyacente a v hacer si (NOT S[w]) AND (D[v]+C[v,w]<D[w]) entonces D[w]:= D[v] + C[v, w] P[w]:= v finsi finpara finpara

+
A.E.D.

4.3.3.1. Caminos mnimos desde un origen. Ejemplo: Mostrar la ejecucin del algoritmo de Dijkstra sobre el siguiente grafo.
1 1 2 3 8 1 5 4 1 7 2 2 6 2 3 3 8 4 1
Nodo

2 3 4 5 6 7

S F T F T F T F T F T F T

D 1 12 5 4 5 4 2

P 1 1 5 1 7 1 7 1 7 1 2

A partir de las tablas, cmo calcular cul es el camino mnimo para un nodo v?
A.E.D.

4.3.3.1. Caminos mnimos desde un origen.

Eficiencia del algoritmo de Dijkstra

Con matrices de adyacencia:
Inicializacin: O(n) Ejecutar n-1 veces: Buscar el nodo con mnimo D[v] y S[v] falso: O(n) Actualizar los valores de los candidatos: O(n) En total: O(n2)

Con listas de adyacencia:

Seguimos teniendo un O(n2) Podemos modificar la implementacin y conseguir un O(alog n). Ser adecuada cuando a << n2.

A.E.D.

4.3.3.2. Caminos mnimos entre todos los pares. Problema: Calcular los caminos mnimos entre todos los pares de nodos del grafo.

Posibilidades
Aplicar el algoritmo de Dijkstra n veces, una por cada posible nodo origen: Con matrices de adyacencia: O(n3) Con listas de adyacencia: O(anlog n) Aplicar el algoritmo de Floyd: Con listas o matrices: O(n3) Pero ms sencillo de programar...
A.E.D.

4.3.3.2. Caminos mnimos entre todos los pares. Entrada: C: array [1..n, 1..n] de real Matriz de costes Salida:
D: array [1..n, 1..n] de real Costes caminos mnimos

Algoritmo de Floyd
D:= C para k:= 1, ..., n hacer para i:= 1, ..., n hacer para j:= 1, ..., n hacer D[i, j]:= min ( D[i, j] , D[i, k] + D[k, j] )
A.E.D.

4.3.3.2. Caminos mnimos entre todos los pares. En qu se basa el algoritmo de Floyd? En cada paso k, la matriz D almacena los caminos mnimos entre todos los pares pudiendo pasar por los k primeros nodos. Inicializacin: D almacena los caminos directos. Paso 1: Caminos mnimos pudiendo pasar por el 1. ... Paso n: Caminos mnimos pudiendo pasar por cualquier nodo Lo que buscamos. En el paso k, el nodo k acta de pivote.
A.E.D.

4.3.3.2. Caminos mnimos entre todos los pares.

D[i, k]
i

D[k, j]
j

D[i, j]

Camino mnimo entre i y j, en el paso k:

Sin pasar por k: D[i, j] Pasando por k: D[i, k] + D[k, j] Nos quedamos con el menor.

Ojo: Falta indicar cules son los caminos mnimos. P: array [1..n, 1..n] de entero. P[i, j] indica un nodo intermedio en el camino de i a j. i ... P[i, j] ... j
A.E.D.

4.3.3.2. Caminos mnimos entre todos los pares.

Algoritmo de Floyd
D:= C P:= 0 para k:= 1, ..., n hacer para i:= 1, ..., n hacer para j:= 1, ..., n hacer si D[i, k] + D[k, j] < D[i, j] entonces D[i, j]:= D[i, k] + D[k, j] P[i, j]:= k finsi Cunto es el orden de complejidad del algoritmo?
A.E.D.

4.3.3.2. Caminos mnimos entre todos los pares. El algoritmo de Floyd se basa en una descomposicin recurrente del problema:
Dk(i, j):= C[i, j] min(Dk-1(i, j), Dk-1(i, k) + Dk-1(k, j)) Si k=0 Si k>0

Como la fila y columna k no cambian en el paso k, se usa una sola matriz D. Cmo recuperar el camino?
operacin camino (i, j: entero) k:= P[i, j] si k 0 entonces camino (i, k) escribe (k) camino (k, j) finsi A.E.D.

escribe (i) camino (i, j) escribe (j)

4.3.3.2. Caminos mnimos entre todos los pares. Ejemplo: Aplicar el algoritmo de Floyd al siguiente grafo dirigido.
8 3

2
2 2 5

D 1 2 3 P 1 2 3
A.E.D.

1 0 3 6 5 1 0 0 0 2 2 0 3 0 0

2 8 4 0 2 3 0 0 1 0

3 2 5 0

1
6

Calcular el camino mnimo entre 1 y 2.

4.3.3.3. Cierre transitivo de un grafo. Problema: Dada una matriz de adyacencia M (de boolenos) encontrar otra matriz A, tal que A[i, j] es cierto si y slo si existe un camino entre i y j.

Algoritmo de Warshall
Es una simple adaptacin del algoritmo de Floyd a valores booleanos. A:= M para k:= 1, ..., n hacer para i:= 1, ..., n hacer para j:= 1, ..., n hacer A[i, j]:= A[i, j] OR (A[i, k] AND A[k, j])
A.E.D.

4.3.3. Problemas de caminos mnimos.

Conclusiones
Caminos mnimos: Problema fundamental en grafos. Diferentes problemas, con diversas aplicaciones. Desde un origen hasta todos los dems nodos Algoritmo de Dijkstra. Idea: Nodos escogidos y candidatos. Entre todos los pares Algoritmo de Floyd. Idea: Pivotar sobre cada nodo. Ambos algoritmos pueden modificarse para resolver otros problemas relacionados.
A.E.D.

4.3.4. Algoritmos sobre grafos dirigidos.

4.3.4.1. Componentes fuertemente conexos 4.3.4.2. Grafos dirigidos acclicos

Definicin: Un componente conexo de un grafo G es un subgrafo maximal y conexo de G. En grafos dirigidos: Componente fuertemente conexo. Existen caminos entre todos los pares de nodos y en los dos sentidos. Problema: Dado un grafo, calcular sus componentes (fuertemente) conexos.
A.E.D.

4.3.4.1. Componentes fuertemente conexos. Componentes conexos en grafos no dirigidos.

1 8 6 2 9 10 4 5

Solucin trivial: Aplicar una BPP. Cada rbol es un componente conexo. Componentes fuertemente conexos en grafos dirigidos. Funciona una 1 4 2 3 simple BPP?
A.E.D.

4.3.4.1. Componentes fuertemente conexos. La BPP no funciona, pero... Y si hubiramos empezado la BPP de mayor a menor nmero...?
4 3 2 1

Idea: Hacer dos bsquedas en profundidad. En la primera se calcula un orden para la segunda. En la segunda se recorre el grafo (invertido), segn ese orden. Orden posterior de un grafo: npost[v] = orden de terminacin de la llamada recursiva de v en la BPP.
A.E.D.

4.3.4.1. Componentes fuertemente conexos. Algoritmo para calcular los Componentes Fuertemente Conexos de un grafo G = (V, A)
1. Realizar una BPP de G, numerando los vrtices en orden posterior. npost: array [1..n] de entero. 2. Construir el grafo invertido G = (V, A). Para toda arista <v, w> A, tenemos <w, v> A. 3. Realizar una BPP en G empezando en el nodo con mayor npost. Si no se visitan todos los nodos, continuar con el nodo no visitado con mayor npost. 4. Cada rbol del bosque resultante del paso 3 es un componente fuertemente conexo de G.

A.E.D.

4.3.4.1. Componentes fuertemente conexos. Ejemplo: Encontrar los componentes fuertemente conexos del siguiente grafo.
B A C E D

Cunto es el orden de complejidad del algoritmo?

A.E.D.

4.3.4.1. Componentes fuertemente conexos.

A partir de los componentes fuertemente conexos, podemos representar todos los caminos existentes mediante un grafo reducido. Grafo reducido de un grafo dirigido G: GR. Cada nodo de GR representa un componente fuertemente conexo de G. Existe una arista entre dos nodos de GR si existe una arista entre algunos de los nodos de los componentes conexos de G correspondientes.
A, B, C D, E

A.E.D.

4.3.4.2. Grafos dirigidos acclicos. Definicin: Un grafo dirigido acclico (GDA) es un grafo dirigido y sin ciclos.
Ejemplos: Grafo de planificacin de tareas, expresiones aritmticas (con subexpresiones comunes), grafo de prerrequisitos, etc. Licencia
* + A B D + *
Aplanar terreno de obras

Comprar piedras

Hacer camino

Cincelar piedras

(A+B)*(D+D*(A+B))

Pintar pirmide

Colocar piedras

A.E.D.

4.3.4.2. Grafos dirigidos acclicos.

Las propias caractersticas de la aplicacin implican que no pueden existir ciclos. Concepto matemtico subyacente: Representacin de rdenes parciales. Definicin: Un orden parcial en un conjunto C es una relacin binaria que cumple:
Para cualquier elemento a C, (a R a) es falso Para cualquier a, b, c C, (a R b) Y (b R c) (a R c)
{ 1, 2, 3 }

Ejemplo: La relacin de { 1, 2 } inclusin propia entre conjuntos, .

{1}

{ 1, 3 } {2} { }

{ 2, 3 } {3}

A.E.D.

4.3.4.2. Grafos dirigidos acclicos.

Recorrido en orden topolgico: Es un tipo de recorrido aplicable solamente a GDA. Idea: Un vrtice slo se visita despus de haber sido visitados todos sus predecesores en el grafo. Numeracin en orden topolgico: ntop[v]. Si existe una arista <v, w> entonces ntop[v] < ntop[w]. Puede existir ms de un orden vlido. Cul es el significado del orden topolgico? Grafo de tareas: Es un posible orden de ejecucin de las tareas, respetando las precedencias. Expresin aritmtica: Orden para evaluar el resultado total de la expresin (de mayor a menor ntop).
A.E.D.

4.3.4.2. Grafos dirigidos acclicos.

Ejemplo: Ordenacin topolgica de las tareas para construir una pirmide. Licencia
1
de obras

2 4 7

Aplanar terreno

Comprar piedras

Hacer camino

Cincelar piedras

Pintar pirmide

Colocar piedras

Existen otras ordenaciones topolgicas vlidas. Disear un algoritmo para calcular una ordenacin topolgica.

A.E.D.

4.3.4.2. Grafos dirigidos acclicos. Algoritmo de recorrido topolgico

1. Calcular los grados de entrada de todos los nodos. 2. Buscar un nodo v con grado de entrada 0 (es decir, sin predecesores). Numerarlo y marcarlo como visitado. Si no hay ninguno es porque existe un ciclo. 3. Para todos los nodos adyacentes a v, decrementar en 1 su grado de entrada. 4. Repetir los pasos 2 y 3 hasta haber visitado todos los nodos.

A.E.D.

4.3.4.2. Grafos dirigidos acclicos. Otra posibilidad: Usar la numeracin en orden posterior (orden de terminacin de las llamadas recursivas en el procedimiento BPP). Proposicin: Si npost[v] es una numeracin posterior de un GDA, entonces ntop[n]:= n-npost[v] es una numeracin topolgica vlida del GDA. Por qu? 1 2 Ejemplo: Aplicar los dos algoritmos 3 4 5 al siguiente grafo.
6 A.E.D. 7

4.3.5. Algoritmos sobre grafos no dirigidos.

4.3.5.1. Puntos de articulacin y componentes biconexos 4.3.5.2. Caminos y ciclos de Euler

Definicin: Un punto de articulacin de un grafo no dirigido, G, es un nodo v tal que cuando es eliminado de G (junto con las aristas incidentes en l) se divide un componente conexo de G en dos o ms componentes conexos. Definicin: Un grafo no dirigido se dice que es biconexo si no tiene puntos de articulacin. Definicin: Un componente biconexo de un grafo G es un subgrafo biconexo y maximal de G.
A.E.D.

4.3.5.1. Puntos de articulacin y componentes biconexos.

Ejemplo: Grafo de estrategias de pase del baln del Real Murcia.

2 6 8

5 7

11

10

Qu jugador, o jugadores, desconectan al equipo si los eliminamos? Escribir un algoritmo que lo calcule. +
A.E.D.

4.3.5.1. Puntos de articulacin y componentes biconexos.

Definicin: Un grafo G tiene conectividad k si la eliminacin de k-1 nodos cualesquiera (con sus aristas) no desconecta el grafo. Por lo tanto, un grafo es biconexo si y slo si tiene conectividad 2 o ms.
1 3 7 8 2 4 6

Posible algoritmo: Eliminar los nodos uno a uno. Para cada uno, comprobar si el grafo sigue siendo conexo.
A.E.D.

4.3.5.1. Puntos de articulacin y componentes biconexos.

Otro algoritmo mejor. Idea: Calcular los caminos alternativos que hay para cada nodo en una BPP.
1. Realizar una BPP, numerando los nodos en el orden de recorrido en profundidad: nbpp[1..N]. 2. Al terminar la llamada recursiva de un nodo v, calcular el valor bajo[v] (camino alternativo), segn la frmula: bajo[v]:= mnimo { nbpp[v], nbpp[z] | siendo (v, z) un arco de retroceso, bajo[y] | siendo y hijo de v en el rbol } 3. La raz es un punto de articulacin si y slo si tiene dos o ms hijos en el rbol. 4. Un nodo v es un punto de articulacin si y slo si tiene algn hijo w en el rbol tal que bajo[w] nbpp[v]. A.E.D.

4.3.5.1. Puntos de articulacin y componentes biconexos.

Ejemplo: Calcular los puntos de articulacin del siguiente grafo.

1 9 3 7 6 8 2 5

Cules son los puntos de articulacin? Y los componentes biconexos?

A.E.D.

4.3.5.1. Puntos de articulacin y componentes biconexos.

Ejemplo.
2, 1 3 3, 3 9

1 4, 1 7

nbpp[1]= 1, bajo[1]= 1

5, 1 8 7, 6 4

2 6, 6 6 9, 6

8, 8

Fundamento del algoritmo: bajo[v] indica el menor valor de nbpp alcanzable desde v hasta cualquier descendiente y luego hacia arriba a travs de un arco de retroceso. Si se cumple la condicin de 4 (bajo[w] nbpp[v]), al eliminar v entonces w y sus descendientes no pueden alcanzar los nodos antecesores de v. A.E.D.

4.3.5.2. Caminos y circuitos de Euler.

Aplicacin: Un grafo no dirigido se utiliza para representar un dibujo de lneas.

1 2 5 7 4

3 6

Pregunta: Es posible dibujar estas figuras con un bolgrafo, pintando cada lnea una sola vez, sin levantar el bolgrafo y acabando donde se empez? A.E.D.

4.3.5.2. Caminos y circuitos de Euler. El problema se transforma en un problema de grafos. Circuito de Euler: Es un ciclo (no necesariamente simple) que visita todas las aristas exactamente una vez. Si puede empezar y acabar en nodos distintos: Camino de Euler. 1
2 5 7 3 4 6

Condiciones necesarias y suficientes para que exista un circuito de Euler: El grafo debe ser conexo. Todos los nodos deben tener grado par, ya que el camino entra y sale de los nodos. Y para los caminos de Euler? A.E.D.

4.3.5.2. Caminos y circuitos de Euler.

Si existe un circuito de Euler, cmo calcularlo? Algoritmo para encontrar un circuito de Euler en un grafo G, partiendo de un nodo v.
1. Buscar un ciclo cualquiera en G empezando por v. 2. Si quedan aristas por visitar, seleccionar el primer nodo, w, del ciclo que tenga una arista sin visitar. Buscar otro ciclo partiendo de w que pase por aristas no visitadas. 3. Unir el ciclo del paso 1 con el obtenido en el paso 2. 4. Repetir sucesivamente los pasos 2 y 3 hasta que no queden aristas por visitar.

Cmo encontrar un ciclo en el grafo, que pase por aristas no visitadas (pasos 1 y 2)?
A.E.D.

4.3.5.2. Caminos y circuitos de Euler.

Ejemplo: Encontrar un circuito de Euler para el siguiente grafo.

1 2 4 5 7 6 3

Cmo modificar el algoritmo para el caso del camino de Euler?

A.E.D.

4.3.4. y 4.3.5. Algoritmos sobre grafos dirigidos y no dirigidos. Conclusiones Podemos utilizar grafos para modelar problemas de la vida real.
Problema de inters Problema con grafos Algoritmo genrico con grafos Algoritmo para el problema de inters

Importancia del estudio de problemas genricos sobre grafos. La bsqueda primero en profundidad es una herramienta bsica, subyacente en muchos de los algoritmos estudiados.
A.E.D.

4.3.6. Otros problemas con grafos.

Problemas genricos y clsicos sobre grafos: Problemas de flujo en redes: Los grafos representan canales de flujo de informacin, de lquidos, mercancas, coches, etc. Problema del viajante: Optimizacin de rutas en mapas de carreteras. Coloracin de grafos: Los grafos representan relaciones de incompatibilidad. Comparacin, isomorfismo y subisomorfismo: Representacin de informacin semntica, bsqueda de patrones, inteligencia artificial.
A.E.D.

4.3.6. Otros problemas con grafos.

Problemas de flujo en redes Supongamos un grafo dirigido G= (V, A) con pesos. Los nodos representan puntos de una red. Las aristas representan canales de comunicacin existentes entre dos puntos. Los pesos de cada arista C(v, w) representan el nmero mximo de unidades que pueden fluir desde el nodo v al w. Problema: Encontrar el mximo volumen que se puede enviar entre dos puntos.
A.E.D.

 Problema del flujo mximo:

4.3.6. Otros problemas con grafos.

Restricciones:

Dado un nodo origen s y un nodo destino t en un grafo dirigido con pesos, G, encontrar la cantidad mxima de flujo que puede pasar de s a t.
La suma de las entradas de cada nodo interior debe ser igual a la suma de sus salidas. Los valores de flujo en cada arista (v, w) no pueden superar los valores mximos, dados por C(v, w).

5 s 3

b 1 a 4

3 t

A.E.D.

4.3.6. Otros problemas con grafos.

Solucin. G: Grafo del problema. F: Grafo resultante.

G
s

b 1

2 4 2

3 t

F
s

b 0

2 1 2

3 t

El problema se puede resolver de forma eficiente. Posible algoritmo:

Encontrar un camino cualquiera desde s hasta t. El mximo flujo que puede ir por ese camino es el mnimo coste de las aristas que lo forman, m. Sumar m en el camino en F, y restarlo de G.

Ojo: este algoritmo no garantiza solucin ptima.

A.E.D.

4.3.6. Otros problemas con grafos.

Problema del ciclo hamiltoniano

Definicin: Dado un grafo no dirigido G, un ciclo de Hamilton (o hamiltoniano) es un ciclo simple que visita todos los vrtices. Es decir, pasa por todos los vrtices exactamente una vez. Problema del ciclo hamiltoniano. Determinar si un grafo no dirigido dado tiene un ciclo hamiltoniano o no.
1 3 5 6 A.E.D. 2 4 3 5 6 1 2 4

4.3.6. Otros problemas con grafos.

Aunque el problema es muy parecido al del circuito de Euler, no se conoce ningn algoritmo eficiente para resolverlo, en tiempo polinomial. El problema del ciclo hamiltoniano pertenece a un conjunto de problemas de difcil solucin, llamados problemas NP-completos. Las soluciones conocidas requieren bsicamente evaluar todas las posibilidades, dando lugar a rdenes de complejidad exponenciales o factoriales. Otra alternativa es usar mtodos heursticos: soluciones aproximadas que pueden funcionar en algunos casos y en otros no.
A.E.D.

4.3.6. Otros problemas con grafos.

Problema del viajante (o del agente viajero)

Dado un grafo no dirigido, completo y con pesos, G, encontrar el ciclo de menor coste que pase por todos los nodos.
1
45

10

2
55

20

25

40

25

5
50

30
15

Ejemplo: Un cartero tiene que repartir cartas por todo el pueblo. Qu ruta debe seguir para que el coste de desplazamiento sea mnimo? A.E.D.

4.3.6. Otros problemas con grafos.

1
45

10

2
55

TOTAL 140 2
0

1
45

10

TOTAL 135 2 2
55
0

25

40

25

40

25

25

5
50

30
15

5
50

30
15

El problema del viajante es un problema NP-completo, equivalente (reducible) al problema del ciclo hamiltoniano. No se conoce una solucin con tiempo polinmico. Las soluciones conocidas tienen complejidad exponencial. Podemos aplicar heursticas, tcnicas probabilistas, algoritmos genticos, computacin con ADN, etc., obteniendo aproximaciones.

A.E.D.

4.3.6. Otros problemas con grafos.

Coloracin de grafos
Un grafo no dirigido G representa ciertos elementos. Una arista (v, w) representa una incompatibilidad entre los elementos v y w. La coloracin de un grafo consiste en asignar un color (o etiqueta) a cada nodo, de forma que dos nodos incompatibles no tengan el mismo color. Problema de coloracin de grafos: Realizar una coloracin del grafo utilizando un nmero mnimo de colores.

A.E.D.

4.3.6. Otros problemas con grafos. Ejemplo: Con cuntos colores, como mnimo, se puede pintar un mapa? Dos regiones adyacentes no pueden tener el mismo color.

Modelamos el problema con una representacin de grafos.

A.E.D.

4.3.6. Otros problemas con grafos. Modelado del problema: Nodos del grafo: Regiones del mapa. Aristas del grafo: Hay una arista (v, w) si las regiones v y w tienen una frontera comn. Solucin: Encontrar la coloracin mnima del grafo.
ARNOR ERIADOR COMARCA GONDOR ROHAN MORDOR RHUN

La coloracin de grafos es un problema NP-completo.

A.E.D.

4.3.6. Otros problemas con grafos.

Comparacin e Isomorfismo de grafos Igualdad

Definicin: Dados dos grafos G= (VG, AG) y F= (VF, AF), se dicen que son iguales si VG = VF y AG = AF.

Isomorfismo
Definicin: Dos grafos G= (VG, AG) y F= (VF, AF) se dice que son isomorfos si existe una asignacin de los nodos de VG con los nodos de VF tal que se respetan las aristas. Isomorfismo entre grafos. El isomorfismo es una funcin:

a : VG VF, biyectiva tal que (v, w) AG (a(v), a(w)) AF

A.E.D.

4.3.6. Otros problemas con grafos.

Ejemplo: Reconocimiento de patrones. Identificar las figuras isomorfas y los puntos anlogos en ambas.
2 1 3 4 2 7 6 1 1 3 7 5 6 4 2 7 4 6 6

El isomorfismo de grafos es tambin un problema NPcompleto. La solucin consistira, bsicamente, en comprobar todas las posibles asignaciones. A.E.D.

Conclusiones

4. Grafos.

Los grafos son una herramienta fundamental en resolucin de problemas. Representacin:

Tamao reducido: matrices de adyacencia. Tamao grande y grafo escaso: listas de adyacencia.

Existen muchos algoritmos clsicos para resolver diferentes problemas sobre grafos. Nuestro trabajo: Saber modelar los problemas de inters usando grafos y encontrar el algoritmo adecuado para la aplicacin que se requiera. Problemas NP-completos sobre grafos: Disear un algoritmo ptimo con alto coste, o un algoritmo heurstico, aproximado pero rpido. Continuar...
A.E.D.

A.E.D.