Embed Size (px)
DESCRIPTION
Théorie de graphe et flots
Citation preview
Cours sur les graphesFlots
Florent Madelaine([email protected])
Universite d’Auvergne
8 Octobre 2007
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 1 / 11
Plan du cours
1 IntroductionExemplesReseau, flot et loi des noeudsFlot realisable et valeur d’un flot
2 Flot maximalProbleme du calcul d’un flot maximalAlgorithme de Ford-Fulkerson
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 2 / 11
De l’ubiquite des flots
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 3 / 11
Reseau, flot et loi des noeuds
Definition (reseau)
(−→G , c, s, t) est un reseau ssi−→G est un graphe oriente connexe sansboucle;ce graphe est value: chaque arc (u, v)du graphe a une capacite c(u, v);la source s de degre entrant nul; et,le puit t de degre sortant nul.
Definition (flot a travers un reseau)
Un flot est une fonction f : E (V )→ R quiverifie la loi des noeuds:(( ce qui rentre egal ce qui sort )).
Conservation du fluxLoi de Kirchhoff (1847, circuits electriques)
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 4 / 11
Definitions
Definition (Flot realisable)
Si pour tout arc la valeur du flot estinferieure ou egale a la capacite del’arc alors on dit que le flot estrealisable.
Definition (valeur du flot)
On ajoute un arc de retour (fictif)depuis t vers s. On definit alors lavaleur du flot comme celle du fluxqui passe par cet arc fictif.
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 5 / 11
Une combinaison lineaire de flots est un flot
Proposition
La somme d’un flot est un flot.
Un multiple d’un flot est un flot.
exercice
Demontrer la proposition
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 6 / 11
Flot maximal
Probleme
donnee: un reseauquestion: trouver un flotrealisable maximal (dont lavaleur est maximale)
Solution
Algorithme de Ford-Fulkerson(1956)
Idee
Proceder par marquagesuccessifs des sommetsdepuis la source vers le puit.On traite chaque sommet umarque successivement.On marque tout successeurpositivement si l’arc n’est pasa pleine capacite et toutpredecesseur negativement sul’arc a un flux non nul.Ceci permet de trouver deschemins augmentant.
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 7 / 11
Algorithme 1 : Algorithme de Ford-Fulkerson
Donnees (−→G , c, s, t) un reseau
debutinitialisation marquer + le sommet entree stant que le flot n’est pas maximal faire
tant que on marque des sommets fairepour chaque sommet marque u non encore traite faire
pour chaque arc (u, v) fairesi v n’est pas marque et (u, v) n’est pas sature alors
marquer v par (+, u)finsi
finprchpour chaque arc (v , u) faire
si v n’est pas marque et (u, v) a un flot non nul alorsmarquer v par (−, u)
finsi
finprch
finprchsi le puits t n’est pas marque alors
le flot est maximal (on s’arrete)sinon
augmenter le flot et continuerfinsi
fintq
fintq
fin
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 8 / 11
Exemple
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 9 / 11
Exemple
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 10 / 11
Informations importantes
Examen
Se prepare.Cours interdit.Mais Pompe Officiellede 1 recto A4autorisee.
Sujet
Algorithme de Bellman-Ford(simple, ameliorations et variantes)Parcours en largeurParcours en profondeurPreuves simples sur des graphes.
Finalement
Bonne semaine de vacanceBonne revisionJe suis disponible pour toute question (prenez rendez-vous par email auprealable svp)
Florent Madelaine (Universite d’Auvergne) Graphes 8 Octobre 2007 11 / 11
