Parte de Algoritmos
de la asignatura de Programacin
Master de Bioinformtica
Grafos
Web asignatura: http://dis.um.es/~domingo/algbio.html
E-mail profesor:
[email protected]Transparencias preparadas a partir de las Gins GarcEstructuras de Datos I,
del Grado de Ingeniera Informtica y
An Introduction to Bioinformatics Algorithms
1
Ejemplos de grafos
Ejemplo: Grafo de carreteras entre ciudades.
C o ru a O v ie d o 304
B ilb a o
45
171
5
32
0
V ig o 356 G e ro n a
28
Z a ra g o z a
4
00
395
296 1
V a lla d o lid 32
5 B a r c e lo n a
19
3
9
M a d rid
34
3 25
40 1
191 V a le n c ia
335
B a d a jo z
241
Jan
15
2 0
24 M u r c ia
99
S e v illa 256 278
5
G ra n a d a
12
C d iz
2
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?
3
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
Grafo no dirigido. v w
Las aristas no estn ordenadas:
(v, w) = (w, v)
Grafos dirigidos (o digrafos).
v w
Las aristas son pares ordenados:
<v, w> <w, v>
<v, w> w = cabeza de la arista, v = cola.
4
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
5
Terminologa de grafos
Camino de un vrtice w a w : es una secuencia w , w , ...,
1 q 1 2
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.
6
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.
7
Terminologa de grafos
Un grafo es completo si existe una arista entre cualquier
par de vrtices.
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>
8
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
Mucho menos frecuente
9
Representacin de grafos
Representacin de grafos:
Representacin del conjunto de nodos, V.
Representacin del conjunto de aristas, A.
1 2
4 5
10
Representacin de grafos
Representacin del conjunto de aristas, A.
Mediante matrices de adyacencia.
M 1 2 3 4 5
1 2
1 T T
2 T T 3
3 T T T
4 5
4
Mediante listas
5 T
de adyacencia.
1 2 3
2 3 5
3 1 4 5
4
4
5
11
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 2 3 4 5
1 2
1 T T T
3 2 T T T T
3 T T
4 5
4 T T T
5 T M[i, j]T = M[j, i].
Grafo no dirigido Matriz simtrica:
Resultado: se desperdicia la mitad de la memoria.
12
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 1 2 3 4
M
3
0 1 3
2 2
2 4 2
4 2 3 3 0 4 2
4
13
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.
14
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
15
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
16
Problemas de caminos mnimos
Definicin: Dado un grafo ponderado G= (V, A) (dirigido o no) y
un camino w1, w2, ..., wq en G, el costo del camino ser la suma de
los costos asociados a las aristas (w1, w2), ..., (wq-1, wq).
Si el grafo es no ponderado, normalmente el costo se asocia con la
longitud del camino.
Problema de los caminos ms cortos por un origen:
Encontrar los caminos ms cortos entre un nodo origen dado a
todos los dems nodos.
17
Algoritmo de Dijkstra
Supongamos un grafo ponderado G (con pesos 0) y un nodo
origen v.
El algoritmo trabaja con dos conjuntos:
S: conjunto de nodos escogidos, para los cuales se conoce el
camino de distancia mnima al origen.
C: conjunto de nodos candidatos, pendientes de calcular el
camino mnimo. Conocemos los caminos mnimos al origen
pasando por nodos de S.
En cada paso coger del conjunto de candidatos el nodo con distancia
mnima al origen. Recalcular los caminos de los dems candidatos
pasando por el nodo cogido.
Un camino especial del origen a otro nodo cualquiera es un camino
que slo pasa por nodos ya escogidos.
Supongamos que el nodo origen es el 1.
18
Algoritmo de Dijkstra
En un array D[2, ..., N] se guarda la longitud del camino especial
ms corto a cada vrtice. Cuando todos los nodos estn en S, todos
los caminos son especiales y D contiene las distancias mnimas al
origen.
En otro array P[2, ..., N] se almacena el camino por el que pasa
cada nodo v. El camino de 1 a v pasa por P[v].
Inicialmente D contendr los caminos directos de 1 a los restantes
nodos, es decir d[1, x]. Si no existe la arista (1, x) el costo ser .
P contendr el valor 1 (el camino es directo). S contendr slo el
nodo 1.
Buscar el nodo v de C=V-S con mnimo valor de D. Aadir v a S.
Para el resto de nodos comprobar si el camino al origen es ms
corto pasando por el nodo v:
si D[v]+d[v, w] < D[w]
D[w]:= D[v] + d[v, w]
P[w]:= v
19
Algoritmo de Dijkstra
para i:= 2, ..., N
S[i]:= FALSO
D[i]:= d[1, i]
P[i]:= 1
para i:= 1, ..., N-1
v:= vrtice con D[v] mnimo y
S[v]=FALSO
S[v]:= VERDADERO
para cada nodo w adyacente a v
si S[w]=FALSO
si D[v]+d[v, w]<D[w]
D[w]:= D[v]+C[v, w]
Operacin ImprimeCamino
P[w]:= v
(v:entero)
si v != 1
ImprimeCamino(P[v])
escribir v
20
Algoritmo de Dijkstra
Ejemplo:
2
1 2
4 1
3 10
2
3 4 2
5
5 8 4
6
6 7
1
Nodo S D P S D P S D P S D P S D P
2 F 2 1 F 2 1 T 2 1 T 2 1 T 2 1
3 F 1 F 3 4 F 3 4 T 3 4 T 3 4
4 F 1 1 T 1 1 T 1 1 T 1 1 ..... T 1 1
5 F 1 F 3 4 F 3 4 F 3 4 T 3 4
6 F 1 F 9 4 F 9 4 F 8 3 T 6 7
7 F 1 F 5 4 F 5 4 F 5 4 T 5 4
Inicializ. v=4 v=2 v=3 5, 7 v=6
21
Problema del ciclo hamiltoniano
Dado un grafo no dirigido G, un ciclo hamiltoniano es un ciclo
simple que visita todos los vrtices.
Problema del ciclo hamiltoniano.
Determinar si un grafo no dirigido dado tiene un ciclo hamiltoniano.
1 2 1 2
3 4 3 4
5 6 5 6
No se conoce ningn algoritmo para resolverlo en tiempo
polinomial.
22
Problema del viajante
Dado un grafo no dirigido, completo y ponderado G = (V, A),
encontrar un ciclo simple de costo mnimo.
10
1 2
45 20
55
40 25
5 30 3
25
50 4 15
Ejemplos: Un repartidor de determinadas mercancas tiene encargos
en varias ciudades. Qu ruta debe seguir para que el costo de
desplazamiento sea mnimo?
El problema del viajante es un problema NP-completo, con un orden
de complejidad exponencial. No existe una solucin polinmica.
Podemos aplicar heursticas, obteniendo soluciones aproximadas, no
necesariamente ptimas.
23
Problema de la Supercadena ms Corta
Dado un conjunto de cadenas, encontrar la cadena ms corta que
contiene a todas las cadenas.
Entrada: Cadenas s1, s2,., sn
Salida: Una cadena s que contiene a todas las cadenas
s1, s2,., sn como subcadenas y tal que la longitud de s es
mnima
Complejidad: NP completo (no hay algoritmos eficientes
para este problema)
24
Problema de la Supercadena ms Corta
25
Problema de la Supercadena ms Corta
Se puede reducir al Problema del Viajante de Comercio
(TSP)
Se define overlap ( si, sj ) como la longitud del prefijo ms
largo de sj que coincide con un sufijo de si.
Se construye un grafo con n vrtices que representan las n
cadenas s1, s2,., sn.
Con aristas con peso overlap ( s , s ) del vrtice s al s .
i j i j
Se trata de encontrar el camino ms largo que visita cada
vrtice una vez: variante del Problema del Viajante de
Comercio (TSP)
26
Problema de la Supercadena ms Corta
27
Problema de la Supercadena ms Corta
S = { ATC, CCA, CAG, TCC, AGT }
SSP TSP ATC
AGT
0 2 1
CCA 1
ATC AGT 1 CCA
1
ATCCAGT 2 2 2
TCC
CAG CAG 1 TCC
ATCCAGT
28
