7.2 ¿Qué

Aplicaciones de la A

pTeoría de Grafos a la vida real

es una red?

Alberto Conejero y Cristina JordánD t M t áti A li dDepto. Matemática Aplicada E.T.S. Ingeniería InformáticaUniversitat Politècnica de València

Imagen de GoogleEarth 7.2 ¿Qué es una red?

Imagen de GoogleEarth 7.2 ¿Qué es una red?

RedRed

sFuente

Se llama red a una cuate

G es un grafo débil conexo, con do

ds(s) ∫ 0 y

y c es una función

c : E(G)c : E(G)

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

Sumiderot

Sumidero

rna, N=(G,s,t,c), donde:

os vértices s y t

y de(t) ∫ 0

(función capacidad)) ö N (función capacidad)) ö N

7.2 ¿Qué es una red?

Flujo en la redFlujo en la red

Se llama flujo en la red a la funciónSe llama flujo en la red a la función

f: E(G) ö N« {0} tal qu

a) "e œ E(G) 0 b f(e) b c(e)

︵E︶︵

f ︵u,v ︶︸t,s︷︶G︵Vu︶b vE︶v,u

ss

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

e verifica

(Limitación por capacidad)

E︶u

︶f ︵v,u (Ecuación de conservación)E︶u,

tu

t

7.2 ¿Qué es una red?

Flujo de la redFlujo de la red

Se llama flujo de la red al valorSe llama flujo de la red al valor

E︶suE︶us

︶s,u︵fu ︶,s︵f︶N︵f E︶s,uE︶u,s

s s

Objetivo

Obtener el valor máximObtener el valor máxim

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

t

mo de f(N)mo de f(N)

7.2 ¿Qué es una red?

PropiedadPropiedad

Sea N una red, f un flujo definidoSe verifica

E︶t,u︵

t,u︵f︶N︵f

ss

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

o en N.

E︶u,t ︵

︶u,t︵f︶

t

7.2 ¿Qué es una red?