s7 4 redes y modelizacion

8/18/2019 S7 4 Redes y Modelizacion

1/17

7.4 Redes (modelización)

Aplicaciones de laTeoría de Grafos

a la vida real

Alberto Conejero y Cristina Jordán

Depto. Matemática AplicadaE.T.S. Ingeniería Informática

Universitat Politècnica de València


2/17

7.4 Redes (modelización) Imágenes de GoogleEarth y Wikipedia


3/17

Aplicaciones de la Teoría de Grafos a la vida real

Viaje New York-Sidney

Definimos una red N=(G,s,t,c) en la que:

G=(V, E) siendo

V = {aeropuertos donde podemos hacer escalas, incluyendo NY y

Sidney}

E = { (u,v) / u, v œ V y hay plazas libres en un vuelo entre u y v}

G es un grafo dirigido, débil conexo

s= New York t= Sidney

c(u,v) = número de plazas libres entre u y v

Buscamos un flujo máximo en N

s a

c

b

d t

Modelización



4/17


5/17


s a

c

b

d t

Consideramos como flujo inicial el flujo 0.

Buscamos s-t caminos f-incrementables.

s ö a ö b ö t

3,0 2,0 1,0

D1=1




6/17



Buscamos s-t caminos f-incrementables

s ö a ö b ö t

3,0 2,0 1,0

D1=1

s a

c

b

d t




7/17




s ö a ö b ö t

3,0 2,0 1,0

D1=1

s a

c

b

d t




8/17




s ö a ö b ö t

3,0 2,0 1,0

D1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2




9/17




s ö a ö b ö t

3,0 2,0 1,0

D1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2




10/17


11/17




s ö a ö b ö t

3,0 2,0 1,0

D1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2

s ö d ö a ö cö t3,0 1,0 5,2

D3=16,2




12/17


13/17




sö

aö

bö

t

3,0 2,0 1,0D

1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2

s ö d ö a ö cö t3,0 1,0 5,2

D3=16,2




14/17




sö

aö

bö

t

3,0 2,0 1,0D

1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2

s ö d ö a ö cö t3,0 1,0 5,2

D3=16,2

s ö d ö b ô aö cö t3,1 3,0 2,1 5,3 6,3

D4=1




15/17




sö

aö

bö

t

3,0 2,0 1,0D

1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2

s ö d ö a ö cö t3,0 1,0 5,2

D3=16,2

s ö d ö b ô aö cö t3,1 3,0 2,1 5,3 6,3

D4=1




16/17




sö

aö

bö

t

3,0 2,0 1,0D

1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2

s ö d ö a ö cö t3,0 1,0 5,2

D3=16,2

s ö d ö b ôaö cö t3,1 3,0 2,1 5,3 6,3

D4=1




17/17




sö

aö

bö

t

3,0 2,0 1,0D

1=1

s a

c

b

d t

s ö a ö c ö t3,1 5,0 6,0

D2=2

s ö d ö a ö cö t3,0 1,0 5,2

D3=16,2

s ö d ö b ôaö cö t3,1 3,0 2,1 5,3 6,3

D4=1

No hay más caminos f-incrementables

El actual flujo f de la red es máximo

f(N)=0+D1 +D2 +D3 +D4 =5



s7 4 redes y modelizacion

Documents