Algor Ford Fulkerson [PDF]

Zitiervorschau

Application de l’algorithme de FORD-FULKERSON Soit le graphe orienté et valué suivant :

8

a

c

4

Valuation

b = 0  c = capacité d = coût (non pris en compte) 

3

8

7

2

S

b

10

d

3

4

e

()

7 [0]

S ()

8 [0]

8 [0] 4 [0]

b 10 [0]

()

3 [0]

7 [0]

P

()

4 [0]

()

7 [0]

S (+)

8 [0]

8 [0] 4 [0]

() Marquage

[] Flot

(+S )

c 4 [0]

Premier marquage :

b 10 [0]

Capacité

(+a )

3 [0]

2 [0]

d 3 [0] 3 [0]

7 [0]

P

(+a )

4 [0]

(+c )

6 [0]

e

a 7 [0]

S (+)

8 [0]

8 [0] 4 [0]

[] Flot

(+S )

c

Augmentation possible du flot dans la chaîne améliorante : 4 [0]

S

b 10 [0]

Capacité

(+a )

3 [0]

2 [0]

L’ordre dans lequel on traite les sommets marqués est une file : S, a, b, c, d, e, P

() Marquage (+b )

(+S )

Flot nul

6 [0]

()

a

Capacité

4 [0]

e

(+S )

6

()

d 3 [0]

P

c 3 [0]

2 [0]

7

3

Chercher le flot complet du réseau.

a

4

d 3 [0] 3 [0]

7 [0]

(+a )

4 [0]

(+b )

a

8

c

4

P

P (+c )

La capacité minimale de la chaîne : 4

6 [0] () Marquage

e

7

[] Flot Capacité

On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne.

a (+S )

7 [4]

8 [0]

S

b

(+)

(+S )

10 [0]

8 [4] 4 [0]

c (+a )

3 [0]

2 [0]

d 3 [0] 3 [0]

4 [4] 7 [0]

P

(+a )

4 [0]

6 [0] () Marquage

e

()

7 [4]

S ()

8 [0]

8 [4] 4 [0]

[] Flot

()

Capacité

()

4 [4]

Nouveau marquage :

b 10 [0]

d 3 [0] 3 [0]

7 [0]

P

()

4 [0]

()

6 [0] [] Flot

()

a 7 [4]

S (+)

8 [0]

8 [4] 4 [0]

(+S )

c

Augmentation possible du flot dans la chaîne améliorante : 4 [4]

S

b 10 [0]

Capacité

(+a )

3 [0]

2 [0]

d 3 [0] 3 [0]

7 [0]

4 [0]

(+d )

7 [4+3] 8 [0]

S (+)

8 [4] 4 [3]

() Marquage

b 10 [0]

(+S )

3 [0]

d

7

P

La capacité minimale de la chaîne : 3

[] Flot

On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne.

Capacité

c

d 3 [0]

4

(+a )

3 [0]

2 [0]

a

6 [0]

(+b )

a

3

P

(+a )

e

(+S )

L’ordre dans lequel on traite les sommets marqués est une file : S, a, b, c, d, e, P

() Marquage

e

(+S )

On remarque que le flot est complet dans c → P , cet arc est saturé.

c 3 [0]

2 [0]

f1 / v1 = 4

(+c )

(+b )

a

Le flot sur cette chaîne est maintenant :

4 [4] 7 [3]

(+a )

4 [0]

Le flot sur cette chaîne est maintenant : P (+d )

6 [0] () Marquage

e (+b )

[] Flot Capacité

f 2 / v2 = 3 On remarque que le flot est complet dans S → a , cet arc est saturé.

a ()

7 [7]

S (+)

8 [0]

8 [4] 4 [3]

(+S )

()

3 [0]

2 [0]

b 10 [0]

c

d 3 [0] 3 [0]

4 [4] 7 [3]

P

()

4 [0]

()

Le sommet a n’est pas marquable depuis S car il est saturé.

6 [0] () Marquage

e

[] Flot

()

a (-c)

7 [7]

S (+)

8 [0]

8 [4] 4 [3]

b 10 [0]

(+S )

3 [0]

On continue le marquage :

c

d 3 [0]

Capacité

(+b )

3 [0]

2 [0]

4 [4] 7 [3]

(+b )

4 [0]

7 [7]

8 [0]

S

b

(+)

(+S )

10 [0]

8 [4] 4 [3]

Ensuite on a c → P saturé, on ne peut donc pas encore marquer P.

6 [0] () Marquage

[] Flot

3 [0]

4 [4] 7 [3]

4 [0]

(+d )

6 [0] () Marquage

e

a 7 [7]

S (+)

8 [0]

8 [4] 4 [3]

(+S )

on a f (d , P) < c(d , P) , on note donc le sommet P par (+ d ) .

Capacité

c

Augmentation possible du flot dans la chaîne améliorante : 4 [4]

S

b 10 [0]

On traite d.

[] Flot

(+b )

3 [0]

2 [0]

On continue le marquage : P

(+b )

(+b )

(-c)

Les autres sommets encadrants c sont déjà marqués (b et d), on passe donc au suivant.

c

d 3 [0]

Capacité

(+b )

3 [0]

2 [0]

a Or on a f (a, c) > 0 , on note donc le sommet par (−c) .

()

e

a

Le sommet b traité, on traite c. P

(+b )

(-c)

Nouveau marquage :

d 3 [0] 3 [0]

7 [3]

(+b )

4 [0]

(+b )

b

3

d

4

P

P (+d )

La capacité minimale de la chaîne : 3

6 [0] () Marquage

e

10

[] Flot Capacité

On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne.

a (-c)

7 [7]

8 [0]

S

b

(+)

(+S )

10 [3]

8 [4] 4 [3]

c (+b )

3 [0]

2 [0]

d 3 [3] 3 [0]

4 [4] 7 [3+3]

(+b )

4 [0]

6 [0] () Marquage

e

a 7 [7]

S (+ )

8 [0]

8 [4] 4 [3]

(+S)

[] Flot Capacité

c

d 3 [3] 3 [0]

4 [4] 7 [6]

P

(+b)

4 [0]

(+e)

6 [0] [] Flot

(+b)

a 7 [7]

S (+ )

8 [0]

8 [4] 4 [3]

(+S)

c

Augmentation possible du flot dans la chaîne améliorante : 4 [4]

S

b 10 [3]

Capacité

(+b)

3 [0]

2 [0]

d 3 [3] 3 [0]

7 [6]

4 [0]

(+e)

7 [7]

S (+ )

8 [0]

8 [4] 4 [3]

() Marquage

b 10 [3+3]

(+S)

3 [3]

e

6

P

La capacité minimale de la chaîne : 3

[] Flot

On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne.

Capacité

c

d 3 [3]

3

(+b)

3 [0]

2 [0]

b

6 [0]

(+b)

a

7

P

(+b)

e

(-c)

L’ordre dans lequel on traite les sommets marqués est une file : S, b, c, e, a, d, P

() Marquage

e

(-c)

On remarque que le flot est complet dans b → d , cet arc est saturé.

Nouveau marquage

b 10 [3]

f 3 / v3 = 3

(+b)

3 [0]

2 [0]

P (+d )

(+b )

(-c)

Le flot sur cette chaîne est maintenant :

4 [4] 7 [6]

(+b)

4 [0]

Le flot sur cette chaîne est maintenant : P (+e)

6 [3] () Marquage

e (+b)

[] Flot Capacité

f 4 / v4 = 3 On remarque que le flot est complet dans b → e , cet arc est saturé.

a (-c)

7 [7]

8 [0]

S

b

(+ )

(+S)

10 [6]

8 [4] 4 [3]

c 4 [4]

3 [0]

2 [0]

d 3 [3] 3 [3]

7 [6]

P

(+c)

4 [0]

(+d)

6 [3]

S

e

a 7 [7]

S (+ )

8 [0]

8 [4] 4 [3]

[] Flot

b 10 [6+1]

(+S)

Capacité

3 [3]

4 [4]

(+c)

7 [7]

8 [0]

S

b

(+ )

(+S)

10 [7]

8 [4] 4 [3]

4 [0]

() Marquage

3 [3]

c

7 [7]

S (+ )

8 [0]

8 [4] 4 [3] 2 [1+1]

b 10 [7+1]

(+S)

7 [7]

P

(+c)

4 [0]

3 [3]

La capacité minimale de la chaîne : 1

f 5 / v5 = 1 On remarque que le flot est complet dans d → P , cet arc est saturé.

(+e)

6 [3]

Augmentation possible du flot dans la chaîne améliorante : S

3

b

1

c

2

d

4

e

3

P

() Marquage

[] Flot Capacité

La capacité minimale de la chaîne : 1

c (+b)

3 [1+1]

d 3 [3]

P

Nouveau marquage : L’ordre dans lequel on traite les sommets marqués est une file : S, b, c, d, a, e, P

4 [4]

e

a

1

Capacité

(+d)

(-c)

d

[] Flot

(+b)

d 3 [3]

3

P

6 [3]

3 [1]

2 [1]

c

(+d)

e

a

2

Le flot sur cette chaîne est maintenant :

7 [6+1]

(+d)

(-c)

b

c

d 3 [3]

4

(+b)

3 [1]

2 [1]

Augmentation possible du flot dans la chaîne améliorante :

() Marquage (+d)

(-c)

Nouveau marquage : L’ordre dans lequel on traite les sommets marqués est une file : S, b, c, d, a, P, e

(+b)

4 [4]

Le flot sur cette chaîne est maintenant :

7 [7]

P

(+c)

4 [1]

(+e)

6 [3+1] () Marquage

e (+d)

[] Flot Capacité

f 6 / v6 = 1 On remarque que le flot est complet dans b → c , cet arc est saturé.

Nouveau marquage : capacité minimale

a ()

7 [7]

S (+ )

8 [0]

8 [4]

(+S)

3 [2]

2 [2]

d 3 [3] 3 [3]

A

4 [4] 7 [7]

()

4 [1]

On n’a plus aucun sommet à traiter. P ()

6 [4]

On constate que P n’est pas marqué, donc on a atteint le flot complet du graphe.

() Marquage

e

A

On traite S, on marque b. On traite b : aucun sommet n’est marquable.

()

4 [3]

b 10 [8]

c

()

[] Flot

f ( S → P ) / v = 15

Capacité

On note : A = {S , b} et A = X − A