Chapitre 5 : Flot maximal dans un graphe

Description

Graphes et Recherche Operationnelle – ESIAL 2A Chapitre 5 : Flot maximal dans un graphe J.-F. Scheid 2011–2012 1

• reseau informatique


• recherche operationnelle


• probleme de flot optimal


• graphes consideres


• aretes


• lien hypertexte


• ji remarque

Sujets

• Hyperlien
• Aretes
• Recherche opérationnelle
• Réseau informatique

Informations

• Publié par: pefav
• Nombre de lectures: 211
• Langue: Français

Extrait

Chapitre

GraphesetRechercheOp´erationnelle– ESIAL

5

:

Flot maximal

J.-F. Scheid

2011–2012

dans

un

graphe

2A

1

Plan du chapitre

I.

II.

III.

D´efinitions 1 Graphe 2 ule´ehavrGpa 3 tionentar´esRepirtam(ehpargnu’de,ncdeciind’ce successeurs/pred´ecesseurs) ´ 4 Flot dans un graphe

Probl`emedeflotoptimaldansungraphe

Algorithme de Ford-Fulkerson

matrice

d adjacence, ’

2

1) Graphe

GrapheG= (E,Γ) E: ensemble fini dessommets Γ : ensemble fini de couples o d ´ (i,j) aveci,j∈E. r onnes Lese´le´mentsdeΓsontappele´slesraeˆetsdu graphe

Notation:

Remarque(seteˆrasessnoree´is´dcsnoes:lent´sorittouL:rgseehpai,j) et (j,i) sont distinctes.

3

Exemple

de

graphe

:

E Γ

= =

{1,2,3,4} {(1,2),(3,

4),

(4,

2),

(4,

3)}

4