//img.uscri.be/pth/0ddc3eaa061be4c9b9af03b2b5a489e40f4bbb94
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Chapitre 5 : Flot maximal dans un graphe

40 pages
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


Voir plus Voir moins
Chapitre
GraphesetRechercheOp´erationnelle– ESIAL
5
:
Flot maximal
J.-F. Scheid
2011–2012
dans
un
graphe
2A
1
Plan du chapitre
I.
II.
III.
D´enitions 1Graphe 2ule´ehavrGpa 3tionentar´esRepirtam(ehpargnude,ncdeciindce successeurs/pred´ecesseurs) ´ 4Flot dans un graphe
Probl`emedeotoptimaldansungraphe
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,jE. 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