Tpicos I
Unidad I
Arboles, Montculos y Grafos
Semana 5
Grafos II
Objetivos Generales
Entender el manejo, uso de algoritmos y
estructuras de datos avanzados, haciendo
nfasis en los algoritmos de internet,
seguridad y redes.
Objetivo Especfico
Implementar
algoritmos
utilizando
estructura de datos avanzadas.
Objetivo Instruccional
Implementar algoritmos sobre estructuras
de datos complejas: grafos
Contenidos
Grafos dirigidos
Clausura transitiva
Todos los caminos mas cortos
Flujo de red
Grafos dirigidos
Definicin
Son aquellos en los que las aristas que conectan
los nodos son de sentido nico. Tambin se les
denomina como DIGRAFOS.
A menudo, la direccin de las aristas reflejan
algn tipo de relacin de precedencia en la
aplicacin que se esta modelando.
Por ejemplo, un grafo dirigido puede utilizarse
como modelo para una cadena de fabricacin,
los nodos corresponden a las tareas a realizar.
El orden en el que aparecen los vrtices al especificar
las aristas tiene mucha importancia: la notacin V1V2
describe una arista que apunta de V1 hacia V2, pero
no de V2 hacia V1.
Grafos dirigidos
Bsqueda en profundidad
Los algoritmos de bsqueda en profundidad
estudiados
anteriormente
pueden
ser
utilizados exactamente de igual forma con los
grafos dirigidos.
De hecho, opera de una manera un poco
mas directa que con los grafos no dirigidos
dado que no se necesita tener en cuenta las
dobles aristas entre nodos, a menos que estn
incluidas explcitamente en el grafo.
Bsqueda en profundidad
1 2
3 4
5 6
9 10 11 12
1
2
Grafos dirigidos
3
4
5
6
7
8
9
10
11
12
12
10
11
Grafos dirigidos
Bsqueda en profundidad
Como en el caso de los grafos no dirigidos,
existe
gran
inters
en
conocer
las
propiedades de conectividad de los grafos
dirigidos. Debera ser posible responder a
preguntas tales como:
Existe un camino dirigido desde el vrtice x al
vrtice y?,
Qu vrtices son accesibles desde el vrtice x
por medio de un camino dirigido? y
Existe un camino dirigido desde el vrtice x al
vrtice y y un camino dirigido desde y a x?
Bsqueda en Amplitud
1 2
3 4
5 6
9 10 11 12
1
2
Grafos dirigidos
3
4
5
6
7
8
9
10
11
12
10
11
12
Clausura transitiva
Definicin
El concepto de transitividad es el mismo que
se utiliza en la teora matemtica , el cual
postula que si:
a<b<c a<c
En el caso de la clausura
transitiva, el
concepto se refiere a que existe un camino
que une el vrtice x con el vrtice y, no
importando que para llegar desde x a y
tengamos que visitar otros vrtices del grafo
(camino mas corto).
Clausura transitiva
En que consiste?
Consiste en completar el grafo con todas las aristas
que "acortan" el camino entre dos nodos x y y, si es
que se puede llegar de x a y.
En dgrafos muy grandes, el problema de encontrar caminos entre pares
de vrtices es demasiado complicado, slo siguiendo el trazado del
dibujo del mismo, de ah la importancia de este algoritmo y el inters
que gener su estudio.
Clausura transitiva
Mtodo de Warshall
Ejemplo
Clausura transitiva
Mtodo de Warshall
Clausura transitiva
Mtodo de Warshall
Clausura transitiva
Mtodo de Warshall
Se continua analizando hasta el vrtice 9, obteniendo las
siguientes etapas finales
Todos los caminos mas cortos
La clausura transitiva de un grafo no ponderado
(dirigido o no) responde a la pregunta Existe un
camino desde x a y? para todos los pares de
vrtices x, y.
Para los grafos ponderados (dirigidos o no) se puede
desear construir una tabla que permita encontrar el
camino mas corto desde x a y para todos los pares
de vrtices.
Este es el problema de todos los pares de caminos
cortos.
Todos los caminos mas cortos
En que consiste?
El algoritmo del camino mas corto
(warshall) encuentra el camino mas
corto desde el vrtice de partida a
cada uno de los otros vrtices, por lo
que para hallar todos los caminos mas
cortos, se necesita solamente ejecutar
este
procedimiento
V
veces,
comenzando una vez en cada
vrtice.
Todos los caminos mas cortos
Mtodo de Floyd
El algoritmo representa una red de n nodos como una matriz cuadrada de orden n, la llamaremos matriz C.
De esta forma, el valor Cij representa el coste de ir desde el nodo i al nodo j, inicialmente en caso de no
existir un arco entre ambos, el valor Cij ser infinito.
Definiremos otra matriz D, tambin cuadrada de orden n, cuyos elementos van a ser los nodos
predecesores en el camino hacia el nodo origen, es decir, el valor Dij representar el nodo predecesor a j
en el camino mnimo desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por lo que Dij = i.
Las diagonales de ambas matrices representan el coste y el nodo predecesor para ir de un nodo a si
mismo, por lo que no sirven para nada, estarn bloqueadas.
Los pasos a dar en la aplicacin del algoritmo de Floyd son los siguientes:
Formar las matrices iniciales C y D.
Se toma k=1.
Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i<>k, j<>k e i<>j, hacemos:
Si (Cik + Ckj) < Cij Dij = Dkj y Cij = Cik + Ckj
En caso contrario, dejamos las matrices como estn.
Si k <= n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las
iteraciones.
La matriz final C contiene los costes ptimos para ir de un vrtice a otro, mientras que la matriz D contiene los
penltimos vrtices de los caminos ptimos que unen dos vrtices, lo cual permite reconstruir cualquier
camino ptimo para ir de un vrtice a otro.
Todos los caminos mas cortos
Mtodo de Floyd
Aplicar el algoritmo de
Floyd sobre el siguiente
grafo para obtener las
rutas ms cortas entre
cada dos nodos.
Todos los caminos mas cortos
Mtodo de Floyd
10
10
15
Se inicializan las matrices C y D
Todos los caminos mas cortos
Mtodo de Floyd
Iteracin: k = 1 2 3 4 5
C
10
10
15
Si (Cik + Ckj) < Cij Cij = Cik + Ckj y Dij = Dkj = k
Para i=2, j=3 se tiene calcular C[2,3]:
C[2,1]+C[1,3] = 3 + 10 = 13
(Cik + Ckj) < Cij 13 < Cij = 13 y Dij = 1
Todos los caminos mas cortos
Mtodo de Floyd
Iteracin: k = 1 2 3 4 5
C
10
13
10
15
10
13
10
13
15
De forma anloga se
analiza
los
dems
elementos de la matriz,
obtenindose al final
de la iteracin 1 los
siguientes resultados:
Todos los caminos mas cortos
Mtodo de Floyd
Iteracin: k = 1 2 3 4 5
C
10
13
10 13
15
10
10
4
5
De forma anloga se
analiza
los
dems
elementos de la matriz,
obtenindose al final
de la iteracin 2 los
siguientes resultados:
13
13
15
Todos los caminos mas cortos
Mtodo de Floyd
Iteracin: k = 1 2 3 4 5
C
10
13
10
13
15
10
10
4
5
De forma anloga se
analiza
los
dems
elementos de la matriz,
obtenindose al final
de la iteracin 3 los
siguientes resultados:
25
13
28
13
15
Todos los caminos mas cortos
Mtodo de Floyd
Iteracin: k = 1 2 3 4 5
C
10
25
13
28
10
13
15
10
10
4
5
D
De forma anloga se
analiza
los
dems
elementos de la matriz,
obtenindose al final
de la iteracin 4 los
siguientes resultados:
12
11
11
10
12
10
Todos los caminos mas cortos
Mtodo de Floyd
Iteracin: k = 1 2 3 4 5
C
10
12
11
10
11
10
12
10
10
10
4
5
De forma anloga se
analiza
los
dems
elementos de la matriz,
obtenindose al final
de la iteracin 5 los
siguientes resultados:
12
11
11
10
12
10
Todos los caminos mas cortos
Mtodo de Floyd
5
12
11
11
10
12
10
10
10
4
5
Matrices
finales
Las matrices finales C y D contienen toda la informacin necesaria para determinar
la ruta ms corta entre dos nodos cualquiera de la red.
Por ejemplo, la distancia ms corta del nodo 1 al nodo 5 es C[1,5] = 12.
Para determinar la ruta asociada del camino mnimo entre el nodo 1 y el nodo 5
haremos lo siguiente:
Consultamos D[1,5]=4, el nodo predecesor al 5 es el 4, es decir, 4 5.
Consultamos D[1,4]=2, el nodo predecesor al 4 es el 2, es decir, 2 4 5.
Consultamos D[1,2]=1, el nodo predecesor al 2 es el 1, es decir, 1 2 4 5.
Entonces as ya tenemos la ruta completa.
Flujo de red
Problemtica
Los grafos dirigidos ponderados son modelos muy
tiles en ciertos tipos de aplicaciones que implican
flujo de productos a travs de una red de
interconexin. Considrese, por ejemplo, una red de
oleoductos de distintos tamaos, interconectados
de forma compleja, con vlvulas que controlen la
direccin del flujo en las derivaciones. Supngase
adems que la red tiene una fuente nica (como un
campo de petrleo) y un nico destino (como una gran
refinera) al que convergen finalmente todos los
conductos. Qu ajuste de vlvula har mxima la
cantidad de petrleo que fluye de la fuente hacia el
destino?
El problema del flujo de red
A
Flujo de red
Flujo mximo en una red simple
Flujo de red
El problema del flujo de red
En la grafica idealizada anterior de la pequea red
de oleoducto, las canalizaciones tienen una
capacidad fija proporcional a su tamao y el
petrleo
solamente
puede
fluir
en
forma
descendente. Adems las vlvulas de cada
derivacin controlan la capacidad de petrleo que
va en cada direccin.
Sin importar la forma en la que estn puestas las
vlvulas, el sistema alcanza un estado de equilibrio
cuando la capacidad de petrleo que fluye al
sistema por arriba es igual a la cantidad que fluye
hacia afuera por la parte inferior y cuando la
cantidad de petrleo que fluye hacia cada
derivacin es igual a la que sale de ella.
El problema del flujo de red
A
Flujo de red
El objetivo es desarrollar un algoritmo que pueda
encontrar el reglaje de las vlvulas adecuado para
cualquier
red
y
de
esta
manera
evitar
embotellamientos. Adems, se desea estar seguros
de que ningn otro reglaje dar un flujo mayor.
Flujo de red
El problema del flujo de red
Red: Se define como un grafo dirigido ponderado con dos
vrtices principales: uno, que no tiene aristas que apunte a el (la
fuente), y otro que no tiene aristas que apunten afuera de el (el
pozo). Los pesos de las aristas, que se supone que no son
negativos, se denominan capacidades de las aristas.
Flujo: Se define como un conjunto de pesos en las aristas tal que
el flujo en cada una de ellas es igual o menor que la
capacidad, y el flujo que entra en cada vrtice es igual al que
sale de el. El valor del flujo es el que entra en la fuente (o sale del
pozo).
El problema del flujo de red consiste en
encontrar un FLUJO DE VALOR MXIMO para
una red dada .
Flujo de red
Mtodo de Ford-Fulkerson
El algoritmo de Ford-Fulkerson propone buscar
caminos en los que se pueda aumentar el flujo, hasta
que se alcance el flujo mximo. La idea es encontrar
una ruta de penetracin con un flujo positivo neto
que una los nodos origen y destino.
Consideraremos las capacidades iniciales del arco que une el
nodo i y el nodo j como Cij y Cji. Estas capacidades iniciales irn
variando a medida que avanza el algoritmo, denominaremos
capacidades residuales a las capacidades restantes del arco
una vez pasa algn flujo por l, las representaremos como cij y
cji.
Para un nodo j que recibe el flujo del nodo i, definimos una
clasificacin [aj,i] donde aj es el flujo del nodo i al nodo j.
Mtodo de Ford-Fulkerson
Flujo de red
PASOS:
1. Identificar los nodos origen y destino
2. Identificar la capacidad mas alta que sale del nodo origen
3. Identificar el nodo intermediario con [af,i] (af es el flujo mximo
de ingreso y i el nodo de donde proviene dicho flujo mximo)
4. Repetir paso 3, como si el nodo intermediario fuera el nodo
origen
5. Actualizar los flujos: (Cij , Cji) = (Ci k, Cj + k) donde:
C = Capacidad
i , j = ndices de los nodos
K = flujo mnimo del camino seleccionado
6. Retornar al paso 2 si al menos hay una salida de flujo del
nodo fuente
7. La suma de los K corresponde al Flujo Mximo.
Mtodo de Ford-Fulkerson
Del nodo 4 al
nodo 1 no hay
flujo
Capacidad de
flujo mximo del
nodo 1 al nodo 4
20
Flujo de red
10
Fuente
[ ,-]
Por ser la fuente
se considera la
cantidad de flujo
mximo de
ingreso ()
[ ,-]
30
Sumidero
20
30
0
40
10
20
Por no tener
nodo conocido
como inicio se
considera (-)
PASO 1
Mtodo de Ford-Fulkerson
0
20
Flujo de red
10
[ ,-]
0
30
Iteracin 1
[ 20,3]
Paso 2
Paso 3
20
30
0
40
10
20
[ 30,1]
0
20
10
[ ,-]
0
30
Actualizando las capacidades
10
[ 20,3]
0
20
20
20
30
0
40
10
20
[ 30,1]
K = min (,30,20) = 20
i=1,j=3
(Cij , Cji) = (30 20, 0 + 20) = (10,20)
i=3,j=5
(Cij , Cji) = (20 20, 0 + 20) = (0,20)
Mtodo de Ford-Fulkerson
[ 10,3]
0
20
Flujo de red
10
[ ,-]
Iteracin 2
10
[ 20,4]
K = min (,20,40,10,20) = 10
20
20
30
0
40
20
10
(C12
(C23
(C34
(C45
[ 40,2]
[ 20,1]
, C21) = (20
, C32) = (40
, C43) = (10
, C54) = (20
10
10
10
10
[ ,-]
10, 0 + 10) = (10,10)
10, 0 + 10) = (30,10)
10, 0 + 10) = ( 0,10)
10, 0 + 10) = (10,10)
0
10
5
20
10
20
30
10
30
10
Mtodo de Ford-Fulkerson
0
10
10
Flujo de red
10
[ ,-]
Iteracin 3
10
10
[ 30,2]
K = min (,10,30) = 10
20
10
20
30
10
10
30
(C12 , C21) = (10 10, 10 + 10) = (0,20)
(C25 , C52) = (30 10, 0 + 10) = (20,10)
0
0
[ 10,1]
10
10
10
10
[ ,-]
10
10
5
20
20
20
20
30
10
Mtodo de Ford-Fulkerson
0
10
10
Flujo de red
10
[ ,-]
Iteracin 4
10
10
[ 20,2]
10
K = min (,10,10,20) = 10
20
20
20
20
10
30
(C13 , C31) = (10 10, 20 + 10) = (0,30)
(C32 , C23) = (10 10, 30 + 10) = (0,40)
(C25 , C52) = (20 10, 10 + 10) = (10,20)
[ 10,3]
[ 10,1]
10
10
10
10
[ ,-]
20
0
5
20
10
20
40
30
Mtodo de Ford-Fulkerson
[ 10,1]
0
10
10
Flujo de red
10
[ ,-]
Iteracin 5
10
[ 10,4]
20
K = min (,10,10) = 10
20
10
20
30
40
(C14 , C41) = (10 10, 0 + 10) = (0,10)
(C45 , C54) = (10 10, 10 + 10) = (0,20)
10
10
20
[ ,-]
20
0
5
20
10
20
40
30
Mtodo de Ford-Fulkerson
10
10
20
Flujo de red
[ ,-]
20
0
5
20
10
20
40
30
Flujo Mximo = k
= 20+10+10+10+10
= 60
Mtodo de Ford-Fulkerson
0
Propuesta
20
Flujo de red
10
30
5
0
20
30
0
40
10
20
10
4
10
20
20
Flujo Mximo = 60
5
20
30
20
Tpicos I
Unidad I
Arboles, Montculos y Grafos
Semana 5
Grafos II
