14 mars 2006Cours de graphes 4 - Intranet1 Cours de graphes Problèmes de flots. Théorème du Max-flow – Min-cut. Algos de Ford-Fulkerson et Edmonds-Karp

14 mars 2006 Cours de graphes 4 - Intranet 1

Cours de graphesCours de graphes

Problèmes de flots.Problèmes de flots.

Théorème du Max-flow – Min-cut.Théorème du Max-flow – Min-cut.

Algos de Ford-Fulkerson et Edmonds-Algos de Ford-Fulkerson et Edmonds-Karp.Karp.

Applications.Applications.


Les grandes lignes du coursLes grandes lignes du cours

•Définitions de baseDéfinitions de base•ConnexitéConnexité•Les plus courts cheminsLes plus courts chemins•Dijkstra et Bellmann-FordDijkstra et Bellmann-Ford•ArbresArbres•Arbres de recouvrement minimaux Arbres de recouvrement minimaux •Problèmes de flotsProblèmes de flots•Coloriage de graphesColoriage de graphes•CouplageCouplage•Chemins d’Euler et de HamiltonChemins d’Euler et de Hamilton•Problèmes NP-completsProblèmes NP-complets


Les graphes de flotsLes graphes de flots----------------------------------------------------------------------------------------------------------------------------------

• Un graphe de flot est :Un graphe de flot est :

– un graphe orienté; les arcs portent des capacités un graphe orienté; les arcs portent des capacités (poids),(poids),

– qui possède deux sommets particuliers qui sont la qui possède deux sommets particuliers qui sont la « source s » et le « puits p ».« source s » et le « puits p ».











• On a en plus :On a en plus :

– Le graphe est quasi-fortement connexe avec « s » Le graphe est quasi-fortement connexe avec « s » comme unique racine !comme unique racine !







– Le graphe est quasi-fortement connexe avec « s » comme Le graphe est quasi-fortement connexe avec « s » comme unique racine !unique racine !

– Si nous inversons tous les arcs, le graphe est quasi-Si nous inversons tous les arcs, le graphe est quasi-fortement connexe avec « p » comme unique racine !fortement connexe avec « p » comme unique racine !




– un graphe orienté; les arcs portent des capacités (poids),un graphe orienté; les arcs portent des capacités (poids),

– qui possède deux sommets particuliers qui sont la « source qui possède deux sommets particuliers qui sont la « source s » et le « puits p ».s » et le « puits p ».


– Le graphe est quasi-fortement connexe avec « s » comme unique Le graphe est quasi-fortement connexe avec « s » comme unique racine !racine !

– Si nous inversons tous les arcs, le graphe est quasi-fortement Si nous inversons tous les arcs, le graphe est quasi-fortement connexe avec « p » comme unique racine !connexe avec « p » comme unique racine !

– Donc, tout sommet « u » appartient à un chemin simple orienté qui Donc, tout sommet « u » appartient à un chemin simple orienté qui relie « s » à « p » en passant par « u » , ( s ; u ; p ) !relie « s » à « p » en passant par « u » , ( s ; u ; p ) !



Exemple :Exemple :



Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88

2020

Les capacités !Les capacités !



Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88

2020Source « s »Source « s »




Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88





Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88


UniquementUniquementdes arcsdes arcssortants !sortants !




Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88





Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88

2020Source « s »Source « s » Puits « p »Puits « p »



1010


Exemple :Exemple :

2020

1010

1010

1515

1717

55

1515

1010

88




1010


Exemple :Exemple :

2020

1010

1010

1515

1717

55

1515

1010

88


UniquementUniquementdes arcsdes arcs

entrants !entrants !




Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88


Tout sommet « u » appartient à unTout sommet « u » appartient à unchemin simple de « s » vers « p » !chemin simple de « s » vers « p » !




Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88


Tout sommet « u » appartient à unTout sommet « u » appartient à unchemin simple de « s » vers « p » !chemin simple de « s » vers « p » !

uu




• La dynamique :La dynamique :

– La source produit ( des m^3 d’eau, des La source produit ( des m^3 d’eau, des kWh ), elle est la seule à produire !kWh ), elle est la seule à produire !





– Le puits consomme, il est le seul à le faire !Le puits consomme, il est le seul à le faire !






– Les autres sommets transmettent, sans Les autres sommets transmettent, sans produire, ni consommer !produire, ni consommer !













• Un peu de discipline :Un peu de discipline :

– Sur chaque arc le flot est compris entre zéro et la Sur chaque arc le flot est compris entre zéro et la capacité de l’arc !capacité de l’arc !




– La source produit ( des m^3 d’eau, des kWh ), elle La source produit ( des m^3 d’eau, des kWh ), elle est la seule à produire !est la seule à produire !


– Les autres sommets transmettent, sans produire, ni Les autres sommets transmettent, sans produire, ni consommer !consommer !


– Sur chaque arc le flot est compris entre zéro et la capacité Sur chaque arc le flot est compris entre zéro et la capacité de l’arc !de l’arc !

– Représentation :Représentation :

flot / capacitéflot / capacité




– La source produit ( des m^3 d’eau, des kWh ), elle La source produit ( des m^3 d’eau, des kWh ), elle est la seule à produire !est la seule à produire !


– Les autres sommets transmettent, sans produire, ni Les autres sommets transmettent, sans produire, ni consommer !consommer !


– Sur chaque arc le flot est compris entre zéro et la capacité Sur chaque arc le flot est compris entre zéro et la capacité de l’arc !de l’arc !

– Représentation :Représentation :

flot / capacitéflot / capacité



Exemple :Exemple :

2020

10101010

1010

1515

1717

55

1515

1010

88




Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8

1313 / 20 / 20Source « s »Source « s » Puits « p »Puits « p »

flot flot / capacité/ capacité



Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8



Toutes contraintes sur lesToutes contraintes sur lescapacités sont respectées ! ! !capacités sont respectées ! ! !



Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8



Les intermédiaires redistribuentLes intermédiaires redistribuentexactement ce qu’ils reçoivent !exactement ce qu’ils reçoivent !



Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8




55 / 10 / 10



Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8



Il sort 17 unités de la source « s », il entre 17 unitésIl sort 17 unités de la source « s », il entre 17 unitésdans le puits « p », c’est ce que nous appellerons le flot !dans le puits « p », c’est ce que nous appellerons le flot !



Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8





Exemple :Exemple :

1010 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

55 / 10 / 10

88 / 8 / 8


flot flot / capacité/ capacité OUI : + 5OUI : + 5



Exemple :Exemple :

1515 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8



Le flot est de 22 unités !Le flot est de 22 unités !



Exemple :Exemple :

1515 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8





Exemple :Exemple :

1515 / 20 / 20

00 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

55 / 17 / 17

44 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8


flot flot / capacité/ capacité OUI : + 1OUI : + 1



Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8






Exemple :Exemple :

1515 / 20 / 20

11 / 10 / 1055 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8





• Pour un graphe de flot, nous voulons connaître :Pour un graphe de flot, nous voulons connaître :

– Le flot maximal :Le flot maximal :

• pour prévoir les investissements,pour prévoir les investissements,

• pour connaître la marge de sécurité, c’est-à-dire la pour connaître la marge de sécurité, c’est-à-dire la différence entre le flot normal et le flot maximal !différence entre le flot normal et le flot maximal !



• Pour un graphe de flot, nous voulons connaître :Pour un graphe de flot, nous voulons connaître :

– Le flot maximal :Le flot maximal :

• pour prévoir les investissements,pour prévoir les investissements,

• pour connaître la marge de sécurité, c’est-à-dire la pour connaître la marge de sécurité, c’est-à-dire la différence entre le flot normal et le flot maximal !différence entre le flot normal et le flot maximal !

– La coupe minimale :La coupe minimale :

• pour localiser le goulot d’étranglement,pour localiser le goulot d’étranglement,

• pour orienter les investissements !pour orienter les investissements !



ApplicationApplication----------------------------------------------------------------------------------------------------------------------------------

• La SNCF étudie son réseau ferré de la région La SNCF étudie son réseau ferré de la région parisienne :parisienne :

– Nous connaissons les capacités des gares de Nous connaissons les capacités des gares de Paris !Paris !

– Nous connaissons le réseau et ses capacités !Nous connaissons le réseau et ses capacités !

– Nous connaissons les capacités des gares de Nous connaissons les capacités des gares de banlieue !banlieue !



LyonLyon

AusterlitzAusterlitz

LazareLazare

EstEst

NordNord

VersaillesVersailles

EvryEvry

Marne la ValléeMarne la Vallée

Saint-DenisSaint-Denis



LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040

Les capacités d’accueilLes capacités d’accueildes différentes gares !des différentes gares !



LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525




LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323

Les lignesLes ligneset leurset leurs

capacités !capacités !



• La SNCF étudie son réseau ferré de la région La SNCF étudie son réseau ferré de la région parisienne :parisienne :

– Nous connaissons les capacités des gares de Nous connaissons les capacités des gares de Paris !Paris !


– Nous connaissons les capacités des gares de Nous connaissons les capacités des gares de banlieue !banlieue !

– Nous limitons les capacités des trains dans les Nous limitons les capacités des trains dans les gares !gares !



LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323





LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



2323

2525

Capacités de trains en gares !Capacités de trains en gares !



• La SNCF étudie son réseau ferré de la région parisienne :La SNCF étudie son réseau ferré de la région parisienne :

– Nous connaissons les capacités des gares de Paris !Nous connaissons les capacités des gares de Paris !


– Nous connaissons les capacités des gares de banlieue !Nous connaissons les capacités des gares de banlieue !

– Nous limitons les capacités des trains dans les gares !Nous limitons les capacités des trains dans les gares !

– Nous levons cette limitation pour certaines gares !Nous levons cette limitation pour certaines gares !

– Nous limitons la capacité globale de tous les trains !Nous limitons la capacité globale de tous les trains !



LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



2323

2525




LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



+ +

2525


250250

LimitationLimitationglobaleglobaleen en trains !trains !



LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



+ +

2525


250250




LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



+ +

2525


250250




LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



+ +

2525


250250




LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



+ +

2525


250250




LyonLyon


LazareLazare

EstEst

NordNord


EvryEvry



SS

5050

4040


PP

2020

2525


1717

2323



+ +

2525


250250




• La représentation :La représentation :

– Les capacités : c : V x V Les capacités : c : V x V --> R+> R+II




– Les capacités : c : V x V Les capacités : c : V x V --> R+> R+

– Si ( u , v ) n’existe pas, alors c ( u , v ) = 0 !Si ( u , v ) n’existe pas, alors c ( u , v ) = 0 !

II






– Les flots : Les flots : f : V x V f : V x V --> R> RII

II






– Les flots : Les flots : f : V x V f : V x V --> R> R

– f ( u , v ) >= 0 , si le flot va de « u » vers « v » ,f ( u , v ) >= 0 , si le flot va de « u » vers « v » ,– f ( u , v ) <= 0 , si le flot va de « v » vers « u » !f ( u , v ) <= 0 , si le flot va de « v » vers « u » !

II

II








• Les contraintes :Les contraintes :

– f ( u , v ) <= c ( u , v )f ( u , v ) <= c ( u , v )

II

II









– f ( u , v ) <= c ( u , v )f ( u , v ) <= c ( u , v )

– f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

II

II









– f ( u , v ) <= c ( u , v )f ( u , v ) <= c ( u , v )

– f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

– f ( u , v ) = 0 , si u est différent de s et de p .f ( u , v ) = 0 , si u est différent de s et de p .

II

v v V V

II









– f ( u , v ) <= c ( u , v )f ( u , v ) <= c ( u , v )

– f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

– f ( u , v ) = 0 , si u est différent de s et de p .f ( u , v ) = 0 , si u est différent de s et de p .

II

v v V V

II


Ford et FulkersonFord et Fulkerson----------------------------------------------------------------------------------------------------------------------------------

Initialiser le flot à 0Initialiser le flot à 0

Tantqu’il existe un chemin augmentantTantqu’il existe un chemin augmentant

Augmenter le flot le longAugmenter le flot le long du chemin en question !du chemin en question !



• Comment changer le flot ?Comment changer le flot ?

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




• D’abord :D’abord :

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

f ( u , v ) <= c ( u , v )f ( u , v ) <= c ( u , v )

-- f ( u , v ) = f ( v , u ) <= c ( v , u ) f ( u , v ) = f ( v , u ) <= c ( v , u )

-- c ( v , u ) <= f ( u , v ) <= c ( u , v ) c ( v , u ) <= f ( u , v ) <= c ( u , v )




• Ensuite :Ensuite :

– Le flot « f ( u , v ) » est le flot dans l’arc ( u , v ) Le flot « f ( u , v ) » est le flot dans l’arc ( u , v ) diminué du flot dans l’arc ( v , u ) !diminué du flot dans l’arc ( v , u ) !

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




• Ensuite :Ensuite :

– Le flot « f ( u , v ) » est le flot dans l’arc ( u , v ) Le flot « f ( u , v ) » est le flot dans l’arc ( u , v ) diminué du flot dans l’arc ( v , u ) !diminué du flot dans l’arc ( v , u ) !

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv+ 2+ 2

3 / 53 / 5

1 / 41 / 4uu vv-- 1 1

2 / 52 / 5

3 / 43 / 4




uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




– Le flot dans l’arc ( u , v ) est porté au maximum !Le flot dans l’arc ( u , v ) est porté au maximum !

– Le flot dans l’arc ( v , u ) est ramené à zéro !Le flot dans l’arc ( v , u ) est ramené à zéro !

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




– Le flot dans l’arc ( u , v ) est porté au maximum !Le flot dans l’arc ( u , v ) est porté au maximum !

– Le flot dans l’arc ( v , u ) est ramené à zéro !Le flot dans l’arc ( v , u ) est ramené à zéro !

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv+ 5+ 5

5 / 55 / 5

0 / 40 / 4




uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




– Le flot dans l’arc ( v , u ) est porté au maximum !Le flot dans l’arc ( v , u ) est porté au maximum !

– Le flot dans l’arc ( u , v ) est ramené à zéro !Le flot dans l’arc ( u , v ) est ramené à zéro !

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )






uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv-- 4 4

0 / 50 / 5

4 / 44 / 4






uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv-- 4 4

0 / 50 / 5

4 / 44 / 4vv uu++ 4 4

0 / 50 / 5

4 / 44 / 4




uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )




r ( u , v ) = c ( u , v ) r ( u , v ) = c ( u , v ) -- f ( u , v ) f ( u , v )

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )





le flot maximal le flot maximal le flot déjà le flot déjà acquisacquis

uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )





uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv+ 2+ 2

3 / 53 / 5

1 / 41 / 4





uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv+ 2+ 2

3 / 53 / 5

1 / 41 / 4

r ( u , v ) = 5 – 2 = 3r ( u , v ) = 5 – 2 = 3





uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv+ 2+ 2

3 / 53 / 5

1 / 41 / 4

r ( u , v ) = 5 – 2 = 3r ( u , v ) = 5 – 2 = 35 X5 X

0 X0 X

+ 3+ 3





uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv+ 2+ 2

3 / 53 / 5

1 / 41 / 4

r ( u , v ) = 5 – 2 = 3r ( u , v ) = 5 – 2 = 3

r ( v , u ) = 4 – (– 2) = 6r ( v , u ) = 4 – (– 2) = 6





uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv-- 2 2

3 / 53 / 5

1 / 41 / 4

r ( u , v ) = 5 – 2 = 3r ( u , v ) = 5 – 2 = 3

r ( v , u ) = 4 – (– 2) = 6r ( v , u ) = 4 – (– 2) = 6





uu vvf ( u , v )f ( u , v )

c ( u , v )c ( u , v )

c ( v , u )c ( v , u )

f ( u , v ) = f ( u , v ) = -- f ( v , u ) f ( v , u )

uu vv-- 2 2

3 / 53 / 5

1 / 41 / 4

r ( u , v ) = 5 – 2 = 3r ( u , v ) = 5 – 2 = 3

r ( v , u ) = 4 – (– 2) = 6r ( v , u ) = 4 – (– 2) = 6

0 X0 X

4 X4 X

+ 6+ 6



• Le graphe résiduel R :Le graphe résiduel R :

– Il a les mêmes sommets que le graphe de flot G !Il a les mêmes sommets que le graphe de flot G !

– Il possède un arc ( u , v ) si la capacité résiduelle r ( u Il possède un arc ( u , v ) si la capacité résiduelle r ( u , v ) dans le graphe G est strictement positive !, v ) dans le graphe G est strictement positive !

– L’arc en question est pondéré par la capacité résiduelle L’arc en question est pondéré par la capacité résiduelle !!





– Il possède un arc ( u , v ) si la capacité résiduelle r ( u Il possède un arc ( u , v ) si la capacité résiduelle r ( u , v ) dans le graphe G est strictement positive !, v ) dans le graphe G est strictement positive !

– L’arc en question est pondéré par la capacité résiduelle L’arc en question est pondéré par la capacité résiduelle !!

• Un chemin augmentant est un chemin de « s » vers Un chemin augmentant est un chemin de « s » vers « p » dans le graphe résiduel R !« p » dans le graphe résiduel R !





– Il possède un arc ( u , v ) si la capacité résiduelle r ( u , Il possède un arc ( u , v ) si la capacité résiduelle r ( u , v ) dans le graphe G est strictement positive !v ) dans le graphe G est strictement positive !

– L’arc en question est pondéré par la capacité résiduelle !L’arc en question est pondéré par la capacité résiduelle !

• Un chemin augmentant est un chemin de « s » vers Un chemin augmentant est un chemin de « s » vers « p » dans le graphe résiduel R !« p » dans le graphe résiduel R !

• Le poids du chemin augmentant est le poids de l’arc le Le poids du chemin augmentant est le poids de l’arc le plus léger du chemin !plus léger du chemin !



• Un exemple :Un exemple :

ss pp

uu

vv

Le graphe G !Le graphe G !

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv

ConstructionConstructiondu graphe R !du graphe R !




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11

r ( s , u ) =r ( s , u ) =c ( s , u ) c ( s , u ) -- f ( s , u ) f ( s , u )= 4 – 1 = 3= 4 – 1 = 3

r ( u , s ) =r ( u , s ) =c ( u , s ) c ( u , s ) -- f ( u , s ) f ( u , s )= c ( u , s ) + f ( s , u )= c ( u , s ) + f ( s , u )= 0 + 1 = 1= 0 + 1 = 1




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11

4422




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11

4422

33




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11

4422

33

33




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv

Le graphe R !Le graphe R !

33

11

4422

33

33

11 33




ss pp

uu

vv


1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11

4422

33

33

11 33Un cheminUn cheminaugmentantaugmentantde poids 3 !de poids 3 !




ss pp

uu

vv

Le nouveauLe nouveaugraphe G !graphe G !

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ss pp

uu

vv


33

11

4422

33

33


+3+3

+3+3

+2+2--11




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

4422

33

33





• Pour changer le flot :Pour changer le flot :

4 / 74 / 7

+2+2devientdevient

6 / 76 / 7




4 / 74 / 7

+2+2devientdevient

6 / 76 / 7

4 / 74 / 7

+2+2devientdevient

2 / 72 / 7




4 / 74 / 7

+2+2devientdevient

6 / 76 / 7

4 / 74 / 7

+2+2devientdevient

2 / 72 / 7

4 / 74 / 7

+2+2

devientdevient

2 / 52 / 5

5 / 75 / 7

1 / 51 / 5

ouou4 / 74 / 7

0 / 50 / 5

ouou . . .. . .




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3





ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


Ceci estCeci estconservé !conservé !




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44

33




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44

33




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44

33




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44

33




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44

33




ss pp

uu

vv

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

3/33/3

ss pp

uu

vv


33

11

33


1155

44

33


Théorème du Max-flow – Min-CutThéorème du Max-flow – Min-Cut----------------------------------------------------------------------------------------------------------------------------------



• Une coupe ( S , P ) ( cut en anglais ) :Une coupe ( S , P ) ( cut en anglais ) :

ss pp. . .. . . . . .. . .

SS PP



• Une coupe ( S , P ) ( cut en anglais ) :Une coupe ( S , P ) ( cut en anglais ) :

• Nous partitionnons les sommets du graphe pourNous partitionnons les sommets du graphe pour

– obtenir une partie S quasi-fortement connexe de racine s ,obtenir une partie S quasi-fortement connexe de racine s ,

– et une partie P quasi-fortement connexe de racine p , si et une partie P quasi-fortement connexe de racine p , si

nous inversons les arcs.nous inversons les arcs.

ss pp. . .. . . . . .. . .

SS PP



• Le flot à travers une coupe ( S , P ) : f ( S , P )Le flot à travers une coupe ( S , P ) : f ( S , P )

f ( S , P ) = f ( S , P ) = f ( u , v ) f ( u , v )u u S Sv v P P




f ( S , P ) = f ( S , P ) = f ( u , v ) f ( u , v )

ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P44 / … / …

22 / … / …

33 / … / …




f ( S , P ) = f ( S , P ) = f ( u , v ) f ( u , v )

• Dans le sens S vers P , nous comptons en positif !Dans le sens S vers P , nous comptons en positif !

• Dans le sens P vers S , nous comptons en négatif !Dans le sens P vers S , nous comptons en négatif !

ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P44 / … / …

22 / … / …

33 / … / …



f ( S , P ) = f ( S , P ) = f ( u , v ) f ( u , v )




ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P44 / … / …

22 / … / …

-- 3 3 / … / …




f ( S , P ) = f ( S , P ) = f ( u , v ) = f ( u , v ) = 4 + 2 4 + 2 -- 3 3



ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P44 / … / …

22 / … / …

-- 3 3 / … / …




f ( S , P ) = f ( S , P ) = f ( u , v ) = f ( u , v ) = 4 + 2 4 + 2 -- 3 3



ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P

S’’S’’ P’’P’’S’S’ P’P’

44 / … / …

22 / … / …

-- 3 3 / … / …



• La capacité d’une coupe ( S , P ) : c ( S , P )La capacité d’une coupe ( S , P ) : c ( S , P )

c ( S , P ) = c ( S , P ) = c ( u , v ) c ( u , v )u u S Sv v P P




c ( S , P ) = c ( S , P ) = c ( u , v ) c ( u , v )

ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P… … / / 44

… … / / 22

… … / / 33




c ( S , P ) = c ( S , P ) = c ( u , v ) c ( u , v )

• Dans le sens S vers P , nous considérons l’arc !Dans le sens S vers P , nous considérons l’arc !

• Dans le sens P vers S , nous ignorons l’arc !Dans le sens P vers S , nous ignorons l’arc !

ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P… … / / 44

… … / / 22

… … / / 33




c ( S , P ) = c ( S , P ) = c ( u , v ) = c ( u , v ) = 4 + 24 + 2



ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P… … / / 44

… … / / 22

… … / / 33




c ( S , P ) = c ( S , P ) = c ( u , v ) = c ( u , v ) = 4 + 24 + 2



ss pp. . .. . . . . .. . .

SS PP

u u S Sv v P P… … / / 44

… … / / 22

… … / / 33



• Pour toute coupe ( S , P ) , nous avons :Pour toute coupe ( S , P ) , nous avons :

f ( S , P ) <= c ( S , P )f ( S , P ) <= c ( S , P )




f ( S , P ) <= c ( S , P )f ( S , P ) <= c ( S , P )

ss pp. . .. . . . . .. . .

SS PP

4 / 4 / 77

2 / 2 / 55

3 / 43 / 4




f ( S , P ) <= c ( S , P )f ( S , P ) <= c ( S , P )

f ( S , P ) = f ( S , P ) = 4 + 2 4 + 2 – 3 – 3 <= <= 4 + 2 4 + 2 <= <= 7 + 57 + 5 = c ( S , = c ( S , P )P )

ss pp. . .. . . . . .. . .

SS PP

4 / 4 / 77

2 / 2 / 55

3 / 43 / 4




f ( S , P ) <= c ( S , P )f ( S , P ) <= c ( S , P )

f ( S , P ) = f ( S , P ) = 4 + 2 4 + 2 – 3 – 3 <= <= 4 + 2 4 + 2 <= <= 7 + 57 + 5 = c ( S , P )= c ( S , P )

f ( S , P ) = f ( S , P ) = f ( u , v ) f ( u , v ) <= <= f ( u , v ) f ( u , v ) <= <= c ( u , v ) c ( u , v ) = c ( S , P ) = c ( S , P ) u u S , v S , v PP u u S , v S , v PP u u S , v S , v PP f ( u , v ) >= 0f ( u , v ) >= 0

ss pp. . .. . . . . .. . .

SS PP

4 / 4 / 77

2 / 2 / 55

3 / 43 / 4



• Pour le flot f à travers un graphe G, nous avons :Pour le flot f à travers un graphe G, nous avons :

– f = f ( S , P ) , quelque soit la coupe ( S , P ) !f = f ( S , P ) , quelque soit la coupe ( S , P ) !





– Or, pour toute coupe ( S , P ) , nous avons f ( S , P ) <= c Or, pour toute coupe ( S , P ) , nous avons f ( S , P ) <= c ( S , P ) !( S , P ) !






– Donc, 0 <= f <= min c ( S , P )Donc, 0 <= f <= min c ( S , P ) coupes ( S , P )coupes ( S , P )







ss pp

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8







ss pp

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8

f <= 10f <= 10







ss pp

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8

f <= 10f <= 10

f <= 6f <= 6







ss pp

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8

f <= 10f <= 10

f <= 6f <= 6



• Les trois conditions suivantes sont équivalentes :Les trois conditions suivantes sont équivalentes :

– ( 1 ) Le flot f est maximal !( 1 ) Le flot f est maximal !

– ( 2 ) Le graphe résiduel ne contient pas de chemin ( 2 ) Le graphe résiduel ne contient pas de chemin augmentant !augmentant !

– ( 3 ) Il existe une coupe ( S , P ) telle que f = c ( S , P ) ! ( 3 ) Il existe une coupe ( S , P ) telle que f = c ( S , P ) ! Cette coupe est minimale et saturée !Cette coupe est minimale et saturée !













• ( 1 ) => ( 2 )( 1 ) => ( 2 )

– Par absurde ! S’il y avait un chemin augmentant, le flot ne Par absurde ! S’il y avait un chemin augmentant, le flot ne serait pas maximal.serait pas maximal.





– ( 2 ) Le graphe résiduel ne contient pas de chemin augmentant !( 2 ) Le graphe résiduel ne contient pas de chemin augmentant !

– ( 3 ) Il existe une coupe ( S , P ) telle que f = c ( S , P ) ! Cette coupe est ( 3 ) Il existe une coupe ( S , P ) telle que f = c ( S , P ) ! Cette coupe est minimale et saturée !minimale et saturée !

• ( 1 ) => ( 2 )( 1 ) => ( 2 )

– Par absurde ! S’il y avait un chemin augmentant, le flot ne serait pas maximal.Par absurde ! S’il y avait un chemin augmentant, le flot ne serait pas maximal.

• ( 3 ) => ( 1 )( 3 ) => ( 1 )

– Comme il existe ( S , P ) telle que f = c ( S , P ) , nous avons c ( S , P ) = Comme il existe ( S , P ) telle que f = c ( S , P ) , nous avons c ( S , P ) = f <= min c ( S , P ) ! f est donc maximal et égal une coupe. f <= min c ( S , P ) ! f est donc maximal et égal une coupe. coupes coupes ( S , P )( S , P )



• ( 2 ) => ( 3 )( 2 ) => ( 3 )

– Il existe une coupe ( S , P ) avec des arcs retour seulement !Il existe une coupe ( S , P ) avec des arcs retour seulement !



• ( 2 ) => ( 3 )( 2 ) => ( 3 )


ss pp. . .. . . . . .. . .

SS PP



• ( 2 ) => ( 3 )( 2 ) => ( 3 )


– Dans le graphe G, il y a trois cas :Dans le graphe G, il y a trois cas :

ss pp. . .. . . . . .. . .

SS PP



• ( 2 ) => ( 3 )( 2 ) => ( 3 )



ss pp. . .. . . . . .. . .

SS PP

ss pp. . .. . . . . .. . .

SS PP

uu vv

uu vv

r ( u , v ) = 0r ( u , v ) = 0et doncet donc

f ( u , v ) = c ( u , v )f ( u , v ) = c ( u , v )



• ( 2 ) => ( 3 )( 2 ) => ( 3 )



ss pp. . .. . . . . .. . .

SS PP

ss pp. . .. . . . . .. . .

SS PP

uu vv

uu vv


f ( u , v ) = c ( u , v )f ( u , v ) = c ( u , v )

xx yy

xx yy

r ( x , y ) = 0r ( x , y ) = 0et doncet donc

f ( y , x ) = 0f ( y , x ) = 0



• ( 2 ) => ( 3 )( 2 ) => ( 3 )



ss pp. . .. . . . . .. . .

SS PP

ss pp. . .. . . . . .. . .

SS PP

uu vv

uu vv


f ( u , v ) = c ( u , v )f ( u , v ) = c ( u , v )

xx yy

xx yy


f ( y , x ) = 0f ( y , x ) = 0

aa bb

aa bb

r ( a , b ) = 0r ( a , b ) = 0et doncet donc

f ( a , b ) = c ( a , b )f ( a , b ) = c ( a , b )



• ( 2 ) => ( 3 )( 2 ) => ( 3 )



ss pp. . .. . . . . .. . .

SS PP

ss pp. . .. . . . . .. . .

SS PP

uu vv

uu vv


f ( u , v ) = c ( u , v )f ( u , v ) = c ( u , v )

xx yy

xx yy


f ( y , x ) = 0f ( y , x ) = 0

aa bb

aa bb

r ( a , b ) = 0r ( a , b ) = 0et doncet donc

f ( a , b ) = c ( a , b )f ( a , b ) = c ( a , b )








ComplexitéComplexité----------------------------------------------------------------------------------------------------------------------------------

• Le calcul du graphe résiduel R et du chemin Le calcul du graphe résiduel R et du chemin augmentant est en augmentant est en ( | E | ) ! ( | E | ) !

• Le nombre d’itérations peut être aussi élevé que la Le nombre d’itérations peut être aussi élevé que la valeur du flot optimal f* !valeur du flot optimal f* !





0/10000/1000 0/10000/1000

0/10000/1000 0/10000/1000

0/10/1

Graphe !Graphe !





0/10000/1000 0/10000/1000

0/10000/1000 0/10000/1000

0/10/1

10001000 10001000

11

10001000 10001000

Graphe !Graphe ! Graphe résiduel !Graphe résiduel !





1/10001/1000 0/10000/1000

0/10000/1000 1/10001/1000

1/11/1

Nouveau graphe !Nouveau graphe !





1/10001/1000 0/10000/1000

0/10000/1000 1/10001/1000

1/11/1

Nouveau graphe !Nouveau graphe !

999999 10001000

11

10001000 999999

Nouveau graphe résiduel !Nouveau graphe résiduel !

1111





1/10001/1000 1/10001/1000

1/10001/1000 1/10001/1000

0/10/1

Re-nouveau graphe !Re-nouveau graphe !





1/10001/1000 1/10001/1000

1/10001/1000 1/10001/1000

0/10/1

Re-nouveau graphe !Re-nouveau graphe !



• Nous améliorons l’algorithme en choisissant le Nous améliorons l’algorithme en choisissant le chemin augmentant le plus lourdchemin augmentant le plus lourd à chaque fois ! à chaque fois !




– C’est celui dont l’arc le plus léger est le plus lourd C’est celui dont l’arc le plus léger est le plus lourd possible !possible !





– Il est difficile d’établir une borne sur le nombre Il est difficile d’établir une borne sur le nombre d’itérations !d’itérations !






• L’algorithme d’Edmonds et Karp :L’algorithme d’Edmonds et Karp :

– choisit le chemin augmentant le plus court (nombre choisit le chemin augmentant le plus court (nombre d’arcs),d’arcs),



• Nous améliorons l’algorithme en choisissant le Nous améliorons l’algorithme en choisissant le chemin chemin augmentant le plus lourdaugmentant le plus lourd à chaque fois ! à chaque fois !




– choisit le chemin augmentant le plus court (nombre choisit le chemin augmentant le plus court (nombre d’arcs),d’arcs),

– il utilise l’algorithme de la vague pour le trouver,il utilise l’algorithme de la vague pour le trouver,




– C’est celui dont l’arc le plus léger est le plus lourd possible !C’est celui dont l’arc le plus léger est le plus lourd possible !

– Il est difficile d’établir une borne sur le nombre d’itérations !Il est difficile d’établir une borne sur le nombre d’itérations !


– choisit le chemin augmentant le plus court (nombre d’arcs),choisit le chemin augmentant le plus court (nombre d’arcs),


– et nécessite au plus O ( | V | * | E | ) itérations,et nécessite au plus O ( | V | * | E | ) itérations,




– C’est celui dont l’arc le plus léger est le plus lourd possible !C’est celui dont l’arc le plus léger est le plus lourd possible !

– Il est difficile d’établir une borne sur le nombre d’itérations !Il est difficile d’établir une borne sur le nombre d’itérations !


– choisit le chemin augmentant le plus court (nombre d’arcs),choisit le chemin augmentant le plus court (nombre d’arcs),


– et nécessite au plus O ( | V | * | E | ) itérations,et nécessite au plus O ( | V | * | E | ) itérations,

– d’où une complexité globale de O ( | V | * | E |^2 ) = O ( | V |^5 ) .d’où une complexité globale de O ( | V | * | E |^2 ) = O ( | V |^5 ) .



• L’idée derrière Edmonds-Karp :L’idée derrière Edmonds-Karp :

GrapheGrapherésiduel :résiduel :

ss pp. . .. . .. . .





ss pp

Le cheminLe cheminaugmentant !augmentant !

. . .. . .





ss pp


Certains arcsCertains arcsde retour !de retour !

. . .. . .





NouveauNouveaugraphegrapherésiduel :résiduel :

ss pp



ss pp

Certains arcsCertains arcsaller !aller !

Tous les arcsTous les arcsde retour !de retour !

. . .. . .

. . .. . .




– Il y a de plus en plus de chemins de retour de « p » vers « s » !Il y a de plus en plus de chemins de retour de « p » vers « s » !



ss pp



ss pp



. . .. . .

. . .. . .




– Il y a de plus en plus de chemins de retour de « p » vers « s » !Il y a de plus en plus de chemins de retour de « p » vers « s » !– Il y a de moins en moins de chemins de « s » vers « p » !Il y a de moins en moins de chemins de « s » vers « p » !



ss pp



ss pp



. . .. . .

. . .. . .




– Il y a de plus en plus de chemins de retour de « p » vers « s » !Il y a de plus en plus de chemins de retour de « p » vers « s » !– Il y a de moins en moins de chemins de « s » vers « p » !Il y a de moins en moins de chemins de « s » vers « p » !– Les chemins augmentants deviennent de plus en plus long !Les chemins augmentants deviennent de plus en plus long !– Commençons donc par nous intéresser à ceux qui sont courts !Commençons donc par nous intéresser à ceux qui sont courts !



ss pp



ss pp



. . .. . .

. . .. . .


mm

11

VariantesVariantes----------------------------------------------------------------------------------------------------------------------------------

• Réseau de flot multi-sources, multi-puits :Réseau de flot multi-sources, multi-puits :

ss11

ssnn

pp

pp


mm

11



ss11

ssnn

pp

pp

SS PP Avec des capacitésAvec des capacitésassez grandes pourassez grandes pour

les arcs rouges !les arcs rouges !


mm

11



• Ce n’est plus le même problème, si s doit envoyer à p Ce n’est plus le même problème, si s doit envoyer à p ! !

ss11

ssnn

pp

pp



ii ii


mm

11



• Ce n’est plus le même problème, si s doit envoyer à p Ce n’est plus le même problème, si s doit envoyer à p ! !

ss11

ssnn

pp

pp



ii ii

nn

ss11

ssnn

pp

pp

11


SynthèseSynthèse----------------------------------------------------------------------------------------------------------------------------------

• Problèmes de flots.Problèmes de flots.

• Théorème du Max-flow – Min-cut.Théorème du Max-flow – Min-cut.

• Algos de Ford-Fulkerson et Edmonds-Algos de Ford-Fulkerson et Edmonds-Karp.Karp.

• Applications.Applications.


‘‘

Documents

14 mars 2006Cours de graphes 4 - Intranet1 Cours de graphes Problèmes de flots. Théorème du Max-flow – Min-cut. Algos de Ford-Fulkerson et Edmonds-Karp