Modelo de Redes
Matemticas
Discretas
Modelo de Redes
Consideremos la grfica mostrada, que representa una red
de tuberas de petrleo:
El petrleo se descarga en el muelle a y se bombea a travs
de la red hasta la refinera z.
Los vrtices b, c, d y e representan estaciones de bombeo
intermedias.
Las aristas dirigidas representan las subtuberas del sistema y
muestran la direccin en que el petrleo puede fluir.
Las etiquetas sobre las aristas indican la capacidad de cada
subtubera.
Captulo 7:
Modelo de Redes
y Redes de Petri
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Red de Transporte
c
4
3
2
a)
Un vrtice fijo, la fuente denotada por a, no tiene aristas
de entrada
b)
Un vrtice fijo, el sumidero (o destino) denotada por z, no
tiene aristas de salida
c)
El peso Cij de la arista dirigida (i, j), llamado la capacidad
de (i, j), es un nmero no negativo
5
Muelle
Una red de transporte (o ms simple, una red) es una
grfica dirigida, simple, con pesos que satisface:
Refinera
Modelo de Redes
Modelo de Redes
Cont...
Cont
Ejemplo:
Flujo en una Red
La grfica es una red de transporte. La fuente es el
vrtice a y el sumidero es el vrtice z. La capacidad de la
arista (a,b), Cab es 3, y la capacidad de la arista (b,c), Cbc
es 2.
Definicin:
b)
4
4
2
Fij <= Cij
Para cada vrtice j, que no sea la fuente ni el sumidero,
Fij = Fji (Propiedad de la conservacin del Flujo)
Z = refinera
Sea G una red de transporte. Sea Cij la capacidad de la arista dirigida (i,j).
Un flujo F en G asigna a cada arista dirigida (i,j) un nmero no negativo Fij
tal que:
a)
a = muelle
Un Flujo en una red asigna un flujo de una arista dirigida que no excede
la capacidad de dicha arista.
En esta suma a menos que se indique lo contrario, se supone que la suma
se realiza sobre todos los vrtices i. Adems si (i,j) no es una arista,
hacemos Fij = 0
Fij es el flujo de la arista (i,j). Para cualquier vrtice j,
fij es el flujo de entrada a j, y
Fji es el flujo de salida de j
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Ejemplo 1:
Las asignaciones:
Fab = 2, Fbc = 2, Fcz = 3, Fad = 3, Fdc = 1, Fde = 2, Fez = 2
definen un flujo para la red de la figura.
Cont...
Por ejemplo, el flujo de entrada del vrtice d, es Fad = 3, es igual al flujo
de salida del vrtice d,
Fdc + Fde = 1 + 2 = 3
Una arista e se etiqueta x, y si la capacidad de e es x y el flujo
en e es y.
En este ejemplo, el flujo de salida de la fuente a
Fab + Fad
es igual al flujo de entrada del sumidero z
Fcz + Fez
b
2,2 c
ambos iguales suman 5 .
3,2
4,3
a = muelle
2,1
Z = refinera
5
d
4,2
5,3
e
7
2,2
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Teorema:
Dado un flujo F en una red, el flujo de salida de la fuente a
es igual al flujo de entrada del sumidero z, es decir:
Ejemplo 2:
Una red de Bombeo
La figura representa una red
de bombeo por medio de la
cual se enva agua a 2
ciudades, A y B, desde 3
pozos, W1, W2, W3.
Las capacidades de los
sistemas
intermedios
aparecen sobre las aristas.
Los vrtices b, c y d
representan estaciones de
bombeo intermedias.
Modelar este sistema como
una red de transporte
Fai = Fiz
Valor del Flujo
Sea F un flujo en una red G. El valor
Fai = Fiz
es el valor del flujo F
En el ejemplo anterior el valor del flujo en la red es 5.
Modelo de Redes
2 c
W2
3
W3
4
B
10
Cont...
Cont...
Modelo de Redes
Cont...
6
W1
Para obtener una fuente y un sumidero fijos, podemos
obtener una red de transporte equivalente, uniendo las
fuentes en una superfuente y los sumideros en un
supersumidero.
representa una capacidad ilimitada
W1
4
2 c
W2
Una red de Flujo de Trfico
Es posible ir de la ciudad A a la ciudad C directamente o
pasar por la ciudad B. Durante el periodo de 6:00 a 7:00
PM, los tiempos promedios son:
B
11
A a B (15 minutos)
B a C (30 minutos)
A a C (30 minutos)
Las capacidades mximas de las carreteras son:
W3
Ejemplo 3:
A a B (3000 carros)
B a C (2000 carros)
A a C (4000 carros)
Representar el flujo de trfico de A a C, de 6:00 a 7:00 PM
como una red.
12
Modelo de Redes
Modelo de Redes
Cont...
Un Algoritmo de Flujo Mximo
Cont...
Qu es el Flujo Mximo?
4000
A, 6:00
C, 6:30
3000
B, 6:15
2000
4000
A, 6:15
C, 6:45
3000
B, 6:30
A, 6:30
2000
C, 7:00
4000
Siendo G una red de trasporte, un flujo mximo es un
flujo con valor mximo.
En general, habr varias flujos con el mismo valor
mximo.
La idea es sencilla: comenzar con cierto flujo inicial e
incrementar de forma iterativa hasta que no pueda
mejorarse ms. El flujo resultante ser el mximo.
Para aumentar el valor de un flujo dado, debemos
determinar un camino de la fuente al sumidero e
incrementar el flujo a lo largo de ese camino.
13
14
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Terminologa
Se denotar a G como una red con fuente a, sumidero z y capacidad C.
Las aristas se tomarn como no dirigidas, por el momento, y sea:
P = (vo , v1 ,..., vn ),
v0 = a
Aumento de Flujo en Orientacin Propia
vn = z
Slo se podr hacer si al determinar un camino P de la fuente al
sumidero, todas las aristas estn orientadas en forma propia, y el
flujo en cada arista es menor que la capacidad de sta.
un camino de a a z de esta grfica.
a = v0
v1
vi-1
v2
vi+1
vn-1
4, 1
2, 1
Si una arista e en P est dirigida de vi-1 a vi , decimos que e est
orientada en forma propia (con respecto a P), caso contrario, se dice
que e est orientada en forma impropia (con respecto a P).
3, 1
Vn= z
3, 2
vi
15
4, 2
2, 2
Al aumentar el flujo en
1 para todas las aristas,
se tiene el flujo mximo
a
16
Modelo de Redes
Modelo de Redes
Cont...
Aumento
Cont...
de Flujo en Orientacin Impropia
Sea P un camino de a a z, y x un vrtice intermedio (que no sea si
a ni z) en P. Existen tres posibilidades para las orientaciones de
las aristas e1 y e2 incidentes en x:
e1
e2
La arista e2 est de forma impropia y e1 no. Si incrementamos en el flujo
en e1, debemos disminuir en el flujo en e2, de modo que el flujo de entrada
siga siendo igual al flujo de salida.
Caso A
La arista e1 est de forma impropia y e2 no. Si incrementamos en el
flujo en e2, debemos disminuir en el flujo en e1, de modo que el flujo
de entrada siga siendo igual al flujo de salida.
Caso B
e1
e2
Caso C
Las dos aristas estn en forma impropia. Ahora debemos disminuir el flujo
en ambas aristas en .
e1
e2
17
18
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Caso D
Las dos aristas estn en forma propia. Si incremento el flujo en ambas aristas
en , el flujo de entrada en x seguir siendo igual al flujo de salida de x.
Ejemplo
b
3, 1
e1
e2
19
4, 1
3, 2
5, 1
Las aristas (a,b), (c,d) y (d,z) estn
en forma propia. La arista (c,b) est
orientada en forma impropia.
d
Disminuimos el flujo en 1 en la
arista impropia (c,b) y aumentamos
el flujo en 1 en las aristas orientadas
3, 2
en forma propia (a,b), (c,d) y (d,z).
El valor del nuevo flujo es 1 ms
que el original.
a
4, 0
c
3, 3
5, 2
d
20
Modelo de Redes
Modelo de Redes
Cont...
Cont
Teorema:
Sea P un camino de a a z en una red G tal que:
1)
2)
Para cada arista (i,j) de P, orientada en forma propia, Fi j < Ci j
Para cada arista (i,j) de P, orientada en forma impropia, Fi j > 0
Sea
Algoritmo de Flujo Mximo
Si no existen caminos que satisfagan las condiciones del teorema recin
mencionado, entonces el flujo es mximo. As, es posible construir un
algoritmo con base a dicho teorema.
La idea se centra en:
= mn X
donde X consta de los nmeros Ci j Fi j para las aristas (i,j) de P orientadas
en forma propia, y Fi j para las aristas (i,j) de P orientadas en forma impropia.
Definimos
Fi j
si (i,j) no est en P
F*i j =
Fi j + si (i,j) est orientada en forma propia en P
Fi j - si (i,j) est orientada en forma impropia en P
Iniciar con un flujo (por ejemplo, uno tal que el flujo en cada arista sea 0).
Buscar un camino que satisfaga las condiciones del teorema del flujo
mximo. Si no existe tal camino, se habr terminado y el flujo es mximo.
Se incrementa el flujo en , donde se define como en el teorema, y se
regresa al paso 2.
En el algoritmo formal, se busca un camino que satisfaga las condiciones
del teorema, a la vez que se lleva un registro de las cantidades:
Entonces F* es un flujo cuyo valor es unidades mayor que el valor de F.
Ci j Fi j , Fi j
21
22
Modelo de Redes
Modelo de Redes
Cont
Cont
Algoritmo
Entrada: Una red de fuente a, sumidero z, capacidad C,
vrtices a = v0 ,....., vn = z y n
Salida: Un flujo mximo F
6.
7.
8.
9.
procedure max_flow(a, z, C, v, n)
// la etiqueta de v es (predecessor (v), val (v))
// se inicia con un flujo nulo
1.
2.
3.
4.
1.
10.
11.
for cada arista (i,j) do
Fi j :=0
while true do
begin
// se eliminan todas las etiquetas
for i :=0 to n do
12.
13.
14.
23
begin
predecesor(vi) := null
val(vi) := null
end
// se etiqueta a
predecessor(a) := val (a) :=
// U es el conjunto de vrtices etiquetados no examinados
U ;= {a}
// se contina hasta que z es etiquetado
while val(z) = null do
begin
24
Modelo de Redes
Modelo de Redes
Cont
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
Cont
if U = then // el flujo es mximo
return (F)
se elige v en U
U : = U {v}
: = val (v)
for cada arista (v,w) con val (w) = null do
if Fvw < Cvw then
begin
predecessor(w) : = v
val(w) : = min {, Cvw Fvw}
U := U U {w}
end
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
for cada arista (v,w) con val (w) = null do
if Fwv > 0 then
begin
predecessor(w) : = v
val(w): = min{, Fwv}
U : = U U {w}
end
end
// se determina un camino P de a a z para el cual se
// revisa el flujo
w0 : = z
k:=0
25
26
Modelo de Redes
Modelo de Redes
Cont
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
Cont
while wk a do
begin
wk+1 : = predecessor(wk)
k:=k+1
end
P : = (wk , wk + 1 , .... , w1 , w0)
: = val(z)
for i = 1 to k do
begin
e : = (wi , wi 1)
47.
48.
49.
50.
51.
52.
if e esta orientado en forma propia en P then
Fe : = Fe +
else
Fe : = Fe +
else
end
end max_flow
A este algoritmo se lo conoce tambin como
ALGORITMO DE ETIQUETADO
27
28
Modelo de Redes
Modelo de Redes
Cont
Cont
Ejemplo:
Maximizar el flujo en la red de transporte dada a
continuacin:
b
c
4,2
4,2
3,2
Variantes del modelo de redes mostrado se utilizan hoy en, por ejemplo, el
diseo de redes de computadoras eficientes. Al modelar una de estas redes,
un vrtice representa un centro de intercambio, una arista es un canal de
transmisin de datos, un flujo es el nmero promedio de bits por segundo
que se transmiten en el canal, y la capacidad de la arista representa la
capacidad de transmisin del canal, o sea, el ancho de banda.
El algoritmo de flujo mximo, obviamente tiene una aplicacin importante,
pues se puede con l hallar la manera ms eficiente de transmitir datos por
una red de computadoras, usando los canales con mayor capacidad
disponible.
5,3
2,1
Conclusin:
d
z
3,1
5,2
4,3
4,2
f
29
30
Modelo de Redes
Modelo de Redes
Redes de Petri
Cont
Redes de Petri o grficas modelo del
procesamiento concurrente, es un mtodo para
modelar y estudiar el procesamiento concurrente.
Definicin:
Una red de Petri es una grfica dirigida, bipartita, en la
cual las dos clases de vertices se llaman lugares y
transiciones.
En una red de Petri se permite la existencia de aristas
paralelas.
Una red de Petri es una grafica dirigida G=(V,E) ,
donde V = P U T y P T .
Cualquier arista e en E es incidente en un
miembro de P y un miembro de T.
P es el conjunto de lugares:.
T es el conjunto de transiciones:.
E es el conjunto de aristas:.
31
32
Modelo de Redes
Modelo de Redes
Cont
Cont
Ejemplo:
Marcado de una red de Petri
La figura muestra un ejemplo de red de Petri, en
general, los lugares se dibujan como crculos y las
transiciones como barras o rectngulos.
Un marcado de una red de Petri asigna a cada
lugar un entero no negativo.
Una red de Petri con un marcado es una red de
Petri marcada.
Si un marcado asigna el entero no negativo n al
lugar p, decimos que existen n elementos en p.
Los elementos se representan mediante puntos.
33
34
Modelo de Redes
Modelo de Redes
Cont
Cont
Ejemplo de red de Petri Marcada:
Ejemplo:
Los lugares representan condiciones, las transiciones
representan eventos, y la presencia de al menos un
elemento en un lugar indica que tal condicin se cumple.
Modelo de red de Petri para un programa de computadora
En este caso los eventos (transiciones) son las instrucciones, y
los lugares representan las condiciones bajo las cuales se puede
ejecutar una instruccin.
A=1
P1
A=A+1
P1
t1
P2
p4
B=A+C
B=2
p7
C=B+C
P2
t3
p9
p5
C=3
p8
P3
P3
t2
P4
35
p6
36
Modelo de Redes
Modelo de Redes
Cont
Cont
Definicin:
En una red de Petri, si una arista va del lugar p a la
transicin t, decimos que p es un lugar de entrada para la
transicin t.
Un lugar de salida se define de manera anloga.
Si cada lugar de entrada de una transicin t tiene al
menos un elemento, decimos que t esta activada .
La descarga de una transicin elimina un elemento de
cada lugar de entrada y agrega un elemento a cada lugar
de salida.
Ejemplo:
t1
p1
p2
t3
t2
p3
p4
37
38
Modelo de Redes
Modelo de Redes
Cont
Cont
Las transiciones t1 y t2 estn activadas
Se descarga solo t1.
t3 est activada.
t1
t1
p1
p1
p2
t3
t3
t2
t2
p3
p2
p3
p4
39
p4
40
10
Modelo de Redes
Modelo de Redes
Cont
Cont
Marcados Alcanzables
Si una serie de descargas transforma un
marcado M en un marcado M, decimos que M
es alcanzable desde M.
t3
t1
t3
t1
t2
Descarga de t1
t2
Ejemplo:
En la siguiente figura nos muestra que haciendo
la descarga de la transicin t1 y luego de t2. M
es alcanzable desde M.
Descarga de t3
Descarga de t2
t2
t3
t1
41
42
Modelo de Redes
Modelo de Redes
Cont
Cont
Propiedades importantes de las redes de Petri.
La Supervivencia
Se refiere a la ausencia de estancamientos.
Ejemplo:
Modelo de petri para un sistema de computo
compartido
Dos personas comparten un sistema de computo
que contiene una unidad de disco d y una impresora
P.
La figura nos muestra un posible modelo de red de
petri para el sistema compartido.
La primera figura nos indica que las 2 unidades
estn disponibles.
La Seguridad
Se relaciona a la capacidad de memoria.
43
44
11
Modelo de Redes
Modelo de Redes
Cont
Cont
Despus de descargar solicitar D y luego solicitar P para
la persona 1.
45
46
Modelo de Redes
Modelo de Redes
Cont
Cont
Despus de descargar solicitar D para la persona 1 y
solicitar P para la persona 2.
47
La figura 2 indica que tanto D como P ya han sido
solicitados por la persona 1.
La figura 3 indica que la persona 1 ha solicitado a D
y la persona 2 ha solicitado a P.
Formalmente podemos decir que la red esta
estancada si ninguna transicin se puede descargar.
48
12
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Ejemplo:
El marcado M no es seguro. Despus de descargar t1 , p2
tiene dos elementos.
t2
t2
p3
p1
p3
p1
Descarga de t1
p4
p2
p4
p2
t3
t1
t3
t1
p6
Definicin:
Un marcado M de una red de Petri est vivo
si, partiendo de M sin importar la serie de
descargas realizadas, es posible descargar
cualquier transicin dada mediante alguna
secuencia de descargas adicionales.
Si esto se cumple decimos que P nunca se
estancar.
p6
p5
p5
49
50
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Ejemplo:
t2
Descarga de t1
t3
t1
t3
t1
t2
Este marcado no est vivo, se considera que tiene capacidad
limitada. El hecho de que una red sea acotada nos garantiza que no
habr un desbordamiento de los lugares.
p1
A= 1
A= A+ 1
p4
Descarga de t3
B= A+ C
p2
Descarga de t2
t2
p7
B= 2
p5
C= B+ C
p9
C= 3
t3
t1
p8
p3
p6
M
51
52
13
Modelo de Redes
Modelo de Redes
Cont...
Cont...
Definicin:
Un marcado M para una red de Petri est acotado
si existe algn entero positivo n con la propiedad
de que, en cualquier secuencia de descarga ,
ningn lugar recibe ms de n elementos.
Es un marcado seguro, si un marcado M est
acotado y en cualquier secuencia de descarga
ningn lugar recibe ms de un elemento.
Ejemplo 1:
Los marcados son seguros.
t2
t3
t1
t3
t1
t2
Descarga de t1
Descarga de t3
Descarga de t2
t2
t3
t1
53
54
Modelo de Redes
Cont...
Ejemplo 2:
EL marcado no es seguro.
t2
t2
p3
p1
p3
p1
Descarga de t1
p4
p2
p2
t3
t1
p6
p5
p4
t3
t1
p6
p5
M
55
14
