7.3 Incremento del flujo de una red

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

Alberto Conejero y Cristina JordánDepto. Matemática Aplicada E.T.S. Ingeniería InformáticaUniversitat Politècnica de València

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

Semicaminos

Sea G un grafo dirigido.

Llamamos u1-up-semicamino en G a la

cadena u1, u2, …, up donde

(ui,ui+1) œ E(G) (arco propiamente orientado) ó

(ui+1,ui) œ E(G) (arco impropiamente orientado)

Podemos decir que G es débil conexo si

todo par de vértices u y v de G

están unidos por un semicamino

v

uw

s t

G

suwt es un semicamino(s,u) y (w,t) son arcos propiamente orientados(w,u) es un arco impropiamente orientado

7.3 Incremento del flujo de una red

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

f(N)=8

t

w

8,56,2

s

t

w

8,86,5

s D1=3

6, 23,1

6, 2

t

w

vu

s

6,67,5

5,3

8,5

6,2

6,2

3,1

6-2=48-5=3

min{3,4}=3

D1=3

Ejemplo

7.3 Incremento del flujo de una red

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

f(N)=8

t

w

8,56,2

s

t

w

8,86,5

s D1=3

f1(N)= f(N)+ D 1= 11

6, 23,1

6, 2

t

w

vu

s

6,67,5

5,3

8,8

6,2

6,5

3,1

Ejemplo

7.3 Incremento del flujo de una red

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

f(N)=8

f1(N)= f(N)+ D 1= 11

6, 23,1

6, 2

t

w

vu

s

6,67,5

5,3

8,8

6,2

6,5

3,1

Ejemplo

7.3 Incremento del flujo de una red

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

Ejemplo

6, 23,1

6,

6, 2

t

w

vu

s

6,67,5

5,3

8,8

6,2

6,5

3,1 f(N)=8

D2=1

f1(N)= f(N)+ D 1= 11

t

w

v

s

5,3

6,2

6,5

w

t

v

s

5,4

6,1

6,6

6-5=125-3=2

min{1, 2}=1

D2=1

7.3 Incremento del flujo de una red

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

Ejemplo

f(N)=8

D2=1

f1(N)= f(N)+ D 1= 11

t

w

v

s

5,3

6,2

6,5

w

t

v

s

5,4

6,1

6,6

6, 23,1

6,

6, 2

t

w

vu

s

6,67,5

5,4

8,8

6,1

6,6

3,1

f2(N)= f1(N)+ D 2= 12

7.3 Incremento del flujo de una red

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

f(N)=8

f1(N)= f(N)+ D 1= 11

f2(N)= f1(N)+ D 2= 12

6, 23,1

6,t

w

vu

s

6,67,5

5,4

8,8

6,1

6,6

3,1

Ejemplo

7.3 Incremento del flujo de una red

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

Semicaminos f-incrementables

Sea f un flujo en una red N

Llamamos s-t-camino f-incrementable a un semicamino de s a t en el que en los arcos

a) propiamente orientados la capacidad sea estrictamente mayor que el flujo

b) impropiamente orientados el flujo sea estrictamente positivo

7.3 Incremento del flujo de una red

Teorema del flujo máximo

Sea f un flujo en una red N

f es flujo máximo si y sólo si no existe ningún s-t-camino f-incrementable

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

¿Cómo se obtiene el flujo máximo?

El flujo máximo se obtiene buscando semicaminos f-incrementables de s a t e incrementando el flujo como se ha indicado en el ejemplo anterior.

7.3 Incremento del flujo de una red

El proceso se realiza de forma eficiente aplicando el algoritmo de Ford-Fulkerson

En el ejemplo anterior obtuvimos

6, 23,1

6,t

w

vu

s

6,67,5

5,4

8,8

6,1

6,6

3,1Se observa que no existen s-t-caminos f2-incrementables.Por tanto, f2 es flujo máximo en la red dada N