14 mars 2006Cours de graphes 4 - Intranet1 Cours de graphes Problèmes de flots. Théorème du...

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 :

10101010

Les capacités !Les capacités !

Exemple :Exemple :

10101010

2020Source « s »Source « s »

Exemple :Exemple :

10101010

Exemple :Exemple :

10101010

UniquementUniquementdes arcsdes arcssortants !sortants !

Exemple :Exemple :

10101010

Exemple :Exemple :

10101010

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

Exemple :Exemple :

UniquementUniquementdes arcsdes arcs

entrants !entrants !

Exemple :Exemple :

10101010

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

Exemple :Exemple :

10101010

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

• 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 :

10101010

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

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

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

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

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

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

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

250250

LimitationLimitationglobaleglobaleen en trains !trains !

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

250250

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

250250

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

250250

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

250250

LyonLyon

LazareLazare

EstEst

NordNord

EvryEvry

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 !

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

– 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 » !

• Les contraintes :Les contraintes :

– 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 ) <= 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 .

v v V V

– 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 .

v v V V

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 :

Le graphe G !Le graphe G !

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

ConstructionConstructiondu graphe R !du graphe R !

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

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

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

Le graphe R !Le graphe R !

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

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

Le nouveauLe nouveaugraphe G !graphe G !

1/41/4

2/62/6

1/21/2 0/20/2

3/33/3

0/30/3

+2+2--11

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

• 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

devientdevient

2 / 52 / 5

5 / 75 / 7

1 / 51 / 5

ouou4 / 74 / 7

0 / 50 / 5

ouou . . .. . .

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

Ceci estCeci estconservé !conservé !

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

1/41/4

5/65/6

0/20/2 2/22/2

3/33/3

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. . .. . . . . .. . .

• 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. . .. . . . . .. . .

• 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. . .. . . . . .. . .

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. . .. . . . . .. . .

u u S Sv v P P44 / … / …

22 / … / …

33 / … / …

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

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. . .. . . . . .. . .

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. . .. . . . . .. . .

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. . .. . . . . .. . .

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. . .. . . . . .. . .

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. . .. . . . . .. . .

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. . .. . . . . .. . .

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 )

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. . .. . . . . .. . .

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. . .. . . . . .. . .

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 )

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8

f <= 10f <= 10

……/7/7

……/3/3

……/7/7

……/5/5

……/1/1

……/8/8

f <= 10f <= 10

f <= 6f <= 6

……/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. . .. . . . . .. . .

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

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

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

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

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

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. . .. . . . . .. . .

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

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

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

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

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

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

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

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. . .. . . . . .. . .

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

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

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/10/1

Graphe !Graphe !

0/10000/1000 0/10000/1000

0/10/1

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

10001000 999999

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

1/10001/1000 1/10001/1000

0/10/1

Re-nouveau graphe !Re-nouveau graphe !

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. . .. . .. . .

Le cheminLe cheminaugmentant !augmentant !

. . .. . .

Certains arcsCertains arcsde retour !de retour !

. . .. . .

NouveauNouveaugraphegrapherésiduel :résiduel :

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 » !

. . .. . .

– 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 » !

. . .. . .

– 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 !

. . .. . .

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

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

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

les arcs rouges !les arcs rouges !

• 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 ! !

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.

‘‘

14 mars 2006Cours de graphes 4 - Intranet1 Cours de graphes Problèmes de flots. Théorème du...

Documents

Algorithmes de Bloch et Ford Fulkerson Florent DELAHAYE Christophe DE BATZ Thibault LE BRAS Groupe B

Les graphes 2-intervallaires - Philippe GAMBETTEphilippe.gambette.free.fr/LIAFA/Gambette - Les graphes 2... · Mots-clés : théorie des graphes, bioinformatique, ordonnancement,

Théorie des graphes et MuPad1 Stage Graphes et Mupad Première journée

28 février 2006Cours de graphes 3 - Intranet1 Cours de graphes Les arbres et arborescences. Les arbres de recouvrement. Les arbres de recouvrement minimaux

Graphes, Théorie des

23 février 2007Cours 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

Graphes - univ-brest.fr

Les graphes

Cours de graphes

HEFF (Bruxelles) Graphes Jeux sur les graphes

Théorie des Graphes - Brainternet · Théorie des Graphes - Graphe Définition Degré Sous-graphe Clique et Stable Les graphes modélisent de nombreuses situations concrêtes où

30 mars 2007Cours de graphes 9 - Intranet1 Cours de graphes Quelques applications

Graphes de Terrain

Théorie des Graphes

Cours Graphes IREM

Graphes - Département Informatique et Interactionsgcolas/algo-licence/slides/graphes...Graphes Plan du cours : déﬁnitions, exemples, parcours en profondeur, algorithme de Dijkstra

Graphes Conceptuels

Graphes et MuPad (C.Boulinier)1 Stage Graphes et Mupad Première journée

St Valentin 2006Cours de graphes 1 - Intranet2 Marc Gengler Marc.Gengler@esil.univ-mrs.fr Cours de graphes Alexandra Bac - Sébastien Fournier 12h de cours

theorie des graphes