Cours de Graphes et Flots

5 mars 20085 mars 2008 Cours de graphes 4 - IntraCours de graphes 4 - Intranetnet

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.

Définitions de baseDéfinitions de base ConnexitéConnexité Les plus courts cheminsLes plus courts chemins Floyd-Warshall, Dijkstra et Bellmann-Floyd-Warshall, Dijkstra et Bellmann-

FordFord ArbresArbres Arbres de recouvrement minimaux Arbres de recouvrement minimaux Problèmes de flots, Ford & FulkersonProblèmes de flots, Ford & Fulkerson 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 grandes lignes du coursLes grandes lignes du cours

I N T R O D U C T I O NI N T R O D U C T I O N

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

un graphe orienté,un graphe orienté,

les arcs portent des capacités (poids positifs),les arcs portent des capacités (poids positifs),

qui possède deux sommets particuliers :qui possède deux sommets particuliers :

• la source s et le puits p .la source s et le puits p .

On a en plus :On a en plus :

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 !relie s à p en passant par u !

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

Exemple :Exemple :

2020Source sSource s

Les capacités !Les capacités !

Tous les autres sommetsTous les autres sommetspeuvent être atteints !peuvent être atteints !

UniquementUniquementdes arcsdes arcssortants !sortants !

Exemple :Exemple :

Puits pPuits p

Depuis tout autre sommetDepuis tout autre sommetnous pouvons atteindre p !nous pouvons atteindre p !

UniquementUniquementdes arcsdes arcs

entrants !entrants !

Exemple :Exemple :

Puits pPuits p

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

L AL A

D Y N A M I Q U ED Y N A M I Q U E

La dynamique :La dynamique :

La source produit, elle est la seule à produire !La source produit, 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, ni stocker !produire, ni consommer, ni stocker !

Un peu de discipline :Un peu de discipline :

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

Représentation :Représentation :

flot / capacitéflot / capacité

I L L U S T R A T I O NI L L U S T R A T I O N

Exemple :Exemple :

Source sSource s

Puits pPuits p1010 / 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 / 20

flot flot / capacité/ capacité

Exemple :Exemple :

Source sSource s

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

1818 / 20 / 20

Exemple :Exemple :

Source sSource s

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

1818 / 20 / 20

55 / 10 / 10

Exemple :Exemple :

Source sSource s

11 / 10 / 10

77 / 10 / 10

77 / 15 / 15

66 / 17 / 17

55 / 5 / 5

00 / 15 / 15

1010 / 10 / 10

88 / 8 / 8

1818 / 20 / 20

En rouge les arcs quiEn rouge les arcs quigardent de la marge !gardent de la marge !

Voici une coupeVoici une coupequi est saturée !qui est saturée !

U N EU N E

A P P L I C A T I O NA P P L I C A T I O N

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 le réseau et ses capacités !Nous connaissons le réseau et ses capacités !

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 !

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

LyonLyon

AusterlitzAusterlitz

LazareLazare

EstEst

NordNord

VersaillesVersailles

EvryEvry

Marne la ValléeMarne la Vallée

Saint-DenisSaint-Denis

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

Les lignesLes ligneset leurset leurs

capacités !capacités !

Capacités de trains en gares, au départ !Capacités de trains en gares, au départ !

250250

LimitationLimitationglobaleglobaleen en trains !trains !

LyonLyon

AusterlitzAusterlitz

LazareLazare

EstEst

NordNord

VersaillesVersailles

EvryEvry

Marne la ValléeMarne la Vallée

Saint-DenisSaint-Denis

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

Les lignesLes ligneset leurset leurs

capacités !capacités !

Capacités de trains en gares, au départ !Capacités de trains en gares, au départ !

250250

LimitationLimitationglobaleglobaleen en trains !trains !

L E SL E S

D E F I N I T I O N SD E F I N I T I O N S

D ED E

B A S EB A S E

La représentation :La représentation :

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 ( flots négatifs ! )> R ( flots négatifs ! )

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

DéfinitionsDéfinitions------------------------------------------------------------------------------------------------------------------------------

v v V V

F O R D & F U L K E R S O NF O R D & F U L K E R S O N

U NU N

A L G O R I T H M EA L G O R I T H M E

G E N E R I Q U EG E N E R I Q U E

Initialiser le flot à 0Initialiser le flot à 0

Tantqu’il existe Tantqu’il existe un chemin augmentantun chemin augmentant

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

Ford & FulkersonFord & Fulkerson------------------------------------------------------------------------------------------------------------------------------

C’est quoi ?C’est quoi ?

Comment le trouver ?Comment le trouver ?

Lequel choisir ?Lequel choisir ?

L E SL E S

F L O T SF L O T S

Comment changer le flot ?Comment changer le flot ?

D’abord :D’abord :

Donc :Donc :

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 )

Attention :Attention :

+/- c ( u , v )+/- c ( u , v )==

+/- c ( v , u )+/- c ( 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 )

---- Comment changer le flot ?Comment changer le flot ?

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

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

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 )

---- Comment changer le flot ?Comment changer le flot ?

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 vv-- 4 4

0 / 50 / 5

4 / 44 / 4vv uu++ 4 4

0 / 50 / 5

4 / 44 / 4

L E SL E S

C A P A C I T E SC A P A C I T E S

R E S I D U E L L E SR E S I D U E L L E S

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

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

r ( u , v ) = +/- r ( v , u )r ( u , v ) = +/- r ( 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 )

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 )

uu vv22

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

00 X X

44 X X

- 6- 6

L EL E

G R A P H EG R A P H E

R E S I D U E LR E S I D U E L

Le graphe résiduel donne pour toute paire de Le graphe résiduel donne pour toute paire de sommets u et v la marge de flot qui est encore sommets u et v la marge de flot qui est encore disponible !disponible !

uu vv-- 2 2

3 / 53 / 5

1 / 41 / 4

Le graphe résiduel donne pour toute paire de sommets u et v la Le graphe résiduel donne pour toute paire de sommets u et v la marge de flot qui est encore disponible !marge de flot qui est encore disponible !

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 , v ) Il possède un arc ( u , v ) si la capacité résiduelle r ( u , v ) dans le graphe G est strictement positive !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 p dans le graphe Un chemin augmentant est un chemin de s vers p dans le graphe résiduel R !résiduel R !

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

I L L U S T R A T I O NI L L U S T R A T I O N

Un exemple :Un exemple :

Le graphe G !Le graphe G !

1/41/4

2/62/6

2/32/3 1/21/2

3/33/3

0/30/3

ConstructionConstructiondu graphe R !du graphe R !

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

Le graphe G !Le graphe G !

1/41/4

2/62/6

2/32/3 1/21/2

3/33/3

0/30/3

r ( s , v ) =r ( s , v ) =c ( s , v ) c ( s , v ) -- f ( s , v ) f ( s , v )= 6 – 2 = 4= 6 – 2 = 4

r ( v , s ) =r ( v , s ) =c ( v , s ) c ( v , s ) -- f ( v , s ) f ( v , s )= c ( v , s ) + f ( s , v )= c ( v , s ) + f ( s , v )= 0 + 2 = 2= 0 + 2 = 2

Le nouveauLe nouveaugraphe G !graphe G !

Le grapheLe grapherésiduel R !résiduel R !

Un cheminUn cheminaugmentantaugmentantde poids 3 !de poids 3 !

1/41/4

2/62/6

2/32/3 1/21/2

3/33/3

0/30/3

+1+1--22

Pour changer le flot :Pour changer le flot :

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

Suite . . .Suite . . .

1/41/4

5/65/6

0/30/3 2/22/2

3/33/3

331155

Pour calculer plus rapidement . . .Pour calculer plus rapidement . . .

Si le graphe résiduel comporte la situation suivante Si le graphe résiduel comporte la situation suivante ( l’arc ( v , u ) peut être absent si y = 0 ) ,( l’arc ( v , u ) peut être absent si y = 0 ) ,

et que le chemin augmentant passe par l’arc ( u , v ) et que le chemin augmentant passe par l’arc ( u , v ) avec un poids p , avec un poids p ,

alors dans le nouveau graphe nous avons la alors dans le nouveau graphe nous avons la situation suivante ( l’arc ( u , v ) peut être absent si situation suivante ( l’arc ( u , v ) peut être absent si x – p = 0 ) : x – p = 0 ) :

yyuu vv

x - px - p

y + py + puu vv

Illustration :Illustration :

L’ancienL’anciengraphe R !graphe R !

Le nouveauLe nouveaugraphe R !graphe R !

331155

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

Illustration :Illustration :

L’ancienL’anciengraphe R !graphe R !

331155

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

Suite . . .Suite . . .

1/41/4

5/65/6

0/30/3 2/22/2

3/33/3

331155

Les arcs quiLes arcs quigardent unegardent unemarge ! ! !marge ! ! !

L EL ET H E O R E M ET H E O R E M E

D UD UF L O T M A X I M A LF L O T M A X I M A L

E T D EE T D EL A C O U P EL A C O U P EM I N I M A L EM I N I M A L E

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

Théorème du Max-Flow Min-CutThéorème du Max-Flow Min-Cut------------------------------------------------------------------------------------------------------------------------------

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 ) = 4 + 2 4 + 2 -- 3 3

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 P

44 / …/ …

22 / …/ …

33 / …/ …

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

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 ) = 4 + 24 + 2

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

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 ) = 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 ) !

Pour toute coupe ( S , P ) , on a f ( S , P ) <= c ( S , Pour toute coupe ( S , P ) , on a f ( S , P ) <= c ( S , P ) !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

f <= 10f <= 10f <= 6f <= 6

L EL E

T H E O R E M ET H E O R E M E

M A X - F L O WM A X - F L O W

M I N - C U TM I N - C U T

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 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 ( 3 ) Il existe une coupe ( S , P ) telle que f = c ( S , P ) ! Cette coupe est minimale et saturée !coupe est minimale et saturée !

( 1 ) => ( 2 ) , par absurde !( 1 ) => ( 2 ) , par absurde !

S’il y a un chemin augmentant, f n’est pas maximal.S’il y a un chemin augmentant, f n’est pas maximal.

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

Si il existe ( S , P ) telle que f = c ( S , P ) , nous avonsSi il existe ( S , P ) telle que f = c ( S , P ) , nous avons c ( S , P ) = f <= min c ( S , P ) ! f est donc maximal !c ( S , P ) = f <= min c ( S , P ) ! f est donc maximal ! coupes ( S , P )coupes ( S , P )

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

Il y a une coupe ( S , P ) avec des arcs retour Il y a une coupe ( S , P ) avec des arcs retour seulement !seulement !

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

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

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

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

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

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

C O M P L E X I T EC O M P L E X I T E

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

1/10001/1000 1/10001/1000

0/10/1

Re-nouveau graphe !Re-nouveau graphe !

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

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 C’est celui dont l’arc le plus léger est le plus lourd possible !lourd 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 !

C’est une variante de Dijkstra :C’est une variante de Dijkstra :

Les arcs inexistants sont initialisés à - Les arcs inexistants sont initialisés à - , ,

avec extrait_max_D à la place de extrait_min_D avec extrait_max_D à la place de extrait_min_D et et

relax ( x , v )relax ( x , v ) si si min ( D ( x ) , M ( x , v ) ) > D ( v )min ( D ( x ) , M ( x , v ) ) > D ( v ) D ( v ) <- min ( D ( x ) , M ( x , v ) )D ( v ) <- min ( D ( x ) , M ( x , v ) ) P ( v ) <- xP ( v ) <- x

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

choisit le chemin augmentant le plus court en choisit le chemin augmentant le plus court en nombre d’arcsnombre d’arcs

et utilise le classique algorithme de la vague et utilise le classique algorithme de la vague pour le trouver.pour le trouver.

Cet algorithme nécessite au plus O ( | V | * | E | ) Cet algorithme nécessite au plus O ( | V | * | E | ) itérations,itérations,

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

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

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 !

GrapheGrapherésiduel :résiduel :

NouveauNouveaugraphegrapherésiduel :résiduel :

Le cheminLe cheminaugmentant !augmentant !

Certains arcsCertains arcsde retour !de retour !

Certains arcsCertains arcsaller !aller !

Tous les arcsTous les arcsde retour !de retour !

. . .. . .

V A R I A N T E SV A R I A N T E S

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

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

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

les arcs rouges !les arcs rouges !

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

Les arcs transportentLes arcs transportentdes flots de couleursdes flots de couleurs

mais rien ne garantit lamais rien ne garantit labonne destination !bonne destination !

Nous pouvons aussi faire dépendre la capacité de la Nous pouvons aussi faire dépendre la capacité de la couleur ( encore appelé multi-capacités ) !couleur ( encore appelé multi-capacités ) !

La plupart des variantes de problèmes de flots La plupart des variantes de problèmes de flots deviennent vite compliquées et difficiles à deviennent vite compliquées et difficiles à résoudre ! ! !résoudre ! ! !

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

… … / 5/ 5… … / 7/ 7

Cours de Graphes et Flots

Documents

Théorie des graphes - Mathématiques Discrètes · Plan du cours premières notions, graphes orientés/non orientés chemins, graphes eulériens recherche du plus court chemin

Recherche Opérationnelle Théorie des graphes: Flots dans les réseaux Recherche OpérationnelleFlots

21 mars 2006Cours de graphes 5 - Intranet1 Cours de graphes Coloriage de graphes. Problème des 4 couleurs, graphes planaires. Théorème de Vizing. Applications

9 mars 2007Cours de graphes 6 - Intranet1 Cours de graphes Chemins dEuler. Chemins de Hamilton. Couplages

Cours - Théorie des graphes (Pierre Bornsztein)

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

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

Algorithmique des graphes - Cours 7 - LaBRI

Graphes, multi-graphes et recherche d’information

Optimisation dans les réseaux GC-SIE. Graphes et flots

Graphes et algorithmique des graphes - Serveur de …perso.ens-lyon.fr/eric.thierry/Graphes2009/bouchitte.pdf · Graphes et algorithmique des graphes cours: Vincent Bouchitt´e r´edaction:

Bassins à flots

Traverse et Calculs dans Arbres Exemple: Graphes de Réseauxvernier.frederic.free.fr/Teaching/PimpA/cours/5/slidesCours5.fred.pdf · Résumé Graphes sont une structure de donnée

Cours d'algorithmique des graphes du MPRIphilippe.gambette.free.fr/SCOL/Graphes.pdf · sur les graphes dans les ouvrages classiques d'algorithmique (cf. par exemple l'excellent Algo-

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

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

1 Licence d’informatique Algorithmique des graphes Cours 3 deuxième partie : Opérations et relations entre graphes. Composition, puissances. Utilisation

Théoriedes Flots maximum graphes - LIP6blin/Enseignement_files/ALGR/... · 2014. 2. 7. · graphes Cours de Lélia Blin! 3eme année de Licence "1. Lélia Blin Algorithmique des

5eme Cours : Parcours de graphes MPRI 2012 2013habib/Documents/cours5-2012.pdf5eme Cours : Parcours de graphes MPRI 2012{2013 Introduction Graph searches are very well known and used

Graphes Chap8 Flots Pres