Graphes

Universit de Montpellier II : Sciences et Techniques du Languedoc Place Eugne Bataillon 34095 Montpellier CEDEX 2

GRAPHES ET ALGORITHMES DE TRAITEMENT

Bruno ROUZEYRELaboratoire d'Informatique, de Robotique et de Microlectronique de Montpellier

Dpartement ERII Polytech'MontpellierMaster EEA 2eme anne

Universit de Montpellier II : Sciences et Techniques du Languedoc Place Eugne Bataillon 34095 Montpellier CEDEX 2

BIBLIOGRAPHIE

Graphes et Algorithmes M. Gondran et M. Minoux. Coll. de la direction des tudes et recherche dlectricit de France. Editions Eyrolles.

Graph theory with applications to engineering and computer science N. Deo. Series in Automatic Computation. Editions Prentice Hall.

Graph theory : an algorithmic approach N. Christofides. Series in computer science and applied mathematics. Editions Academic Press.

Graphes et hypergraphes C. Berge. Editions Dunod.

Algbre moderne et thorie des graphes B. Roy. Editions Dunod.

Introduction

Page 1

INTRODUCTION ET TERMINOLOGIEI DEFINITIONS1- Notions orientesUn graphe G[X,U] est un ensemble dtermin par :

- X : ensemble des sommets (ou noeuds).N = Card(X) est appel lordre du graphe, G est dit graphe dordre N.- U : ensembles des arcs, ou un arc est un couple ordonn u=(i,j), i!X, j!X. i est appel lorigine de larc u, j lextrmit. On note M=Card(U)

Un graphe G[X,U] est appel p-graphe si p est le nombre maximum darcs joignant deuxsommets quelconques.Un arc de la forme u=(x,x) est appel une boucle.Un sommet j est dit successeur de i si il existe u=(i,j). i est alors appel prdcesseur de j.Lensemble des sommets successeurs de i est not " i, " application multivoque de X dans X.Lensemble des sommets prdcesseurs de i est not "-1i2- Notions non orientesSi lon ne considre plus lorientation les arcs sont appels artes.Un multigraphe est un graphe pour lequel il peut exister plusieurs artes entre paires desommets.Un graphe est dit simple si :

- il est sans boucle- il existe une arte au plus entre 2 sommets

3- Principales dfinitions- 2 arcs (artes) sont adjacents sils ont un sommet commun.- le demi-degr extrieur dun sommet i est le nombre darcs dorigine i (not d+i). Dans un1-graphe d+i=Card(" i).- le demi-degr intrieur dun sommet i est le nombre darcs dextrmit i (not d-i). Dansun 1-graphe : d- i=Card("-1i).- le degr de i not di = d+i + d- i- G[X,U] est symtrique pour tout u=(i,j), u=(j,i) ! U- G[X,U] est antisymtrique pour tout u=(i,j), u=(j,i) # U.- graphe partiel : soit G=[X,U], soit V $ U, le graphe partiel engendr par V est gal [X,V].- sous-graphe : soit G=[X,U], soit A $ X, le sous-graphe engendr par A est le graphe notGA dont les sommets sont ceux de A et dont les arcs sont ceux de G ayant leur origine et leurextrmit dans A.

Introduction

Page 2

- sous-graphe partiel : soient G=[X,U], V$U, A $X. Le sous-graphe partiel engendr par Aet V est le graphe partiel de GA engendr par V.- graphe complmentaire : G=[X,U] est dfini par :

si (i,j) ! U => (i,j) # Usi (i,j) # U => (i,j) ! U

- graphe complet - clique :G [X,U] est dit complet si pour toute paire de sommets (i,j), il existe au moins un arc (i,j) ou(j,i).Un 1-graphe complet non orient dordre n est not Kn.Un sous-graphe complet est appel une clique (c--d un sous-graphe dont tous les sommetssont connects 2 2).- graphe biparti : G [X,U] est biparti si X = X1 U X2 avec : X1 % X2 =

pour tout u=(i,j), i!X1 => j!X2 et i!X2 => j!X1- graphe contract :Soit Y $ X , le graphe contract de G par rapport Y est le graphe not G/Y = [X-Y+&y',V]o : V est dfini par :

(i,j) ! V si i ! X-Y, j ! X-Y(i,y) ! V si i ! X-Y, et sil existe j ! Y/ (i,j) ! U.

4- Chemins et connexita - non orient :Une chane de longueur q est une squence de q arcs: L = &u1, u2, ......, uq' telle que : ( r/ 1

Introduction

Page 3

- Cocycle :Soit A $ X, on note :

*+(A) = &u=(i,j)/ i!A, j!X-A' = ensemble des arcs incidents extrieurement A *-(A) = &u=(i,j)/ i!X-A, j!A' = ensemble des arcs incidents intrieurement A *(A) = *+(A) U *-(A) = ensemble des arcs incidents ATout ensemble darcs de la forme *(A) est appel un cocycle.Un cocycle est lementaire sil est form darcs reliant 2 sous-graphes connexes GA1 et GA2de G avec A1 non vide, A2 non vide, A1 % A2 = , et A1 U A2 est une composanteconnnexe de G.Un cocycle lmentaire peut tre dfini de faon quivalente comme un cocycle minimal pourlinclusion.b- orient :- Un chemin de longueur q est une chane de longueur q dont les arcs sont orients dans lesens de parcours.- Chemin lmentaire + chane lmentaire.- Circuit + cycle.- Circuit lmentaire + cycle lmentaire.- Fermeture transitive : on appelle fermeture transitive de lapplication ", lapplication "dfinie par :

"i = " i U "2i U "3i U ......U "N-1i o "ki reprsente lensemble des sommets quelon peut atteindre partir de i part un chemin de longueur k (N est lordre du graphe).

"i reprsente lensemble des sommets que lon peut atteindre partir de i."i = lensemble des descendants de i."i-1 = lensemble des ascendants de i.

- Forte connexit : Un graphe est dit fortement connexe si pour tout couple de sommets i,j ilexiste un chemin de i j et un chemin de j i.Soit R la relation binaire :i R j soit i=j

soit, il existe un chemin de i j et un chemin de j i.R est une relation dquivalence.

Les classes dquivalence sont appeles les composantes fortement connexes de G.Remarque : forte connexit => connexit.- Cocircuit : cest un cocycle dont tous les arcs sont orients dans le mme sens c--d uneensemble darcs de la forme *+(A) ou bien *-(A).

Introduction

Page 4

II Lemme de Minty - Nombre cyclomatique - Formule dEuler :1 Lemme de Minty :Soit un graphe dont les arcs sont colors soit en rouge, soit en noir, soit en vert, soit laisssincolores. Si lon suppose que larc u0 = (i0,j0) est color en noir, alors lune et une seule desdeux propositions suivantes est vraie :

1- il passe par larc u0 un cycle lmentaire dont tous les arcs sont noirs,rouges ou verts(pas dincolore) avec tous les noirs orients dans le mme sens (celui de u0), tous lesverts en sens inverses.2- il existe une partie A de X telle que j0 ! A, i0 # A et telle que le cocycle *(A) soitsans arc rouge avec tous les arcs noirs dans le mme sens (celui de u0 ) et tous les vertsdans lautre sens.

remarque :- *(A) peut contenir des arcs incolores.- u0 ! *,(A) => tous les noirs intervenant ! *,(A) et tous les verts ! *+(A) .

Dmonstration : elle consiste chercher un ensemble de chemins de j0 i0 vrifiant lesconditions du cas 1 par une procdure de marquage.On part de j0 marqu (extrmit de larc de dpart).Soit i un sommet marqu, on marque j non encore marqu uniquement dans lun des cassuivants :- il existe un arc (i,j) de couleur noire,- il existe un arc (j,i) de couleur verte,- il existe un arc (i,j) ou (j,i) de couleur rouge.et on ritre.A la fin, deux cas possibles :- on a russi marquer le sommet i0, => proposition 1.- on ne rencontre jamais i0. Soit A lensemble des sommets marqus (i0 # A, j0 ! A).A ne contient pas darc darc rouge (sinon les deux extrmits dun tel arc appartiendrait A.,tous les arcs noirs sont dans *,(A) , et tous les verts dans *+(A) . Donc A vrifie bien lesconditions de la proposition2. c.q.f.d.Consquence :tout arc appartient soit un circuit soit un cocircuit mais pas aux deux.dm : il suffit de colorier tous les arcs en noir et dappliquer le lemme de Minty.

2. Bases de cycles, de cocycles :

Soit un cycle quelconque, soit + lensemble des arcs orients dans le sens de parcours, ,lensemble des arcs orients dans le sens inverse.A on peut faire correspondre un vecteur M composantes =(1,2,.........,M) avec M =Card(U)avec u = 0 si u # + U ,

Introduction

Page 5

1 si u ! + ,1 si u ! ,

Proprit : Tout cycle est une somme (au sens vectoriel) de cycles lmentaires sans arcscommuns.Dm : Lorsque lon parcourt un cycle quelconque, on dfinit un nouveau cycle chaque foisque lon arrive un sommet dj rencontr.

Dfinitions : - dpendance linaire de cycles- indpendance linaire- base de cycles = ensemble minimal de cycles indpendants tel que tout cycle puisse semettre sous forme de combinaison linaire des cycles de la base.- nombre cyclomatique : ) (G) = dimension de la base de cycle.De faon identique, on dfinit des bases de cocycles, => - (G) = nombre cocyclomatique .rappel : On dit quun cocycle est lmentaire si et seulement si il est form dun ensembledarcs joignant deux sous-graphes connexes non vides A1 et A2 / A1 % A2 = , A1 U A2 estune composante connexe de G.

Proprits :-Tout cocycle est une somme (au sens vectoriel) de cocycles lmentaires disjoints (sans arcscommuns).-Un cocycle est lmentaire si et seulement si cest un cocycle minimal (i.e. si et seulement sion ne peut pas en dduire un autre cocycle par suppression darcs)Thorme :

Soit G un graphe avec n sommets, m arcs et p composantes connexes.Alors : ) (G) = m - n + p

- (G) = n - p

Application : Formule dEuler :

Dans un graphe planaire, on a :

n- m + f = 2 o f est le nombre de faces.

Exercice : chercher tous les types de polydres convexes rguliers (il y en a 5).III Matrices associes un graphe :1 - Matrice dincidence sommets-arcs :La matrice dincidence sommets-arcs A dun graphe G[X,U] est une matrice N lignes etM colonnes telle que si u( i,j) est un arc de U la colonne u vaut 0 partout sauf en

a iu = +1a ju = -1.

Introduction

Page 6

On a : ( i ! X, *+ (i) = & u/ a iu = +1 '*- (i) = & u/ a iu = -1 '

Proprit : la matrice dincidence sommets-arcs est totalement unimodulaire (i.e. toute sous-matrice carre extraite de A est dterminant +1 ,-1 ou 0.

2- Matrice dincidence sommet-artes :La matrice dincidence sommets-artes A dun graphe G[X,U] est une matrice N lignes etM colonnes telle que si u( i,j) est un arc de U la colonne u vaut 0 partout sauf en

a iu = +1a ju = +1.

Proprit : la matrice dincidence sommets-artes est totalement unimodulaire ssi G[X,U] estun graphe biparti.

3- Matrice dadjacence :La matrice dadjacence dun graphe orient G [X,U] est une matrice carre dordre N telleque : a ij = +1 (i,j) !ULa matrice dadjacence dun graphe non orient est une matrice symtrique.

IV Reprsentations des graphes en mmoire dun calculateur :On peut toujours reprsenter un graphe soit laide de sa matrice dadjacence soit de samatrice dincidence, mais perte de place inutile puisque beaucoup de termes nuls.1 - A partir de la matrice dadjacence :

La matrice dadjacence ncessite N2 mots mmoire en orient, 1/2 N (N+1) en non orient.Si le graphe est peu dense M

Introduction

Page 7

b - Par le liste des cocycles *+ (i) ou *- (i) :On dcrit la liste des arcs dorigine un sommet i (et/ou dextrmit i) laide de deuxtableaux :LP [1..N+1] et LA [1..M+1] (et LS[1..M+1])O LP [i] donne ladresse de la liste des arcs dorigine i dans le tableau LA .

*+ (i) = lensemble des lments de LA compris entre LP[i] et LP[i+1] exclus.Remarque : le choix de la structure de donnes dpend du problme traiter.

DFS

Page 1

RECHERCHE EN PROFONDEUR DABORD DANS UNGRAPHE (DEPTH FIRST SEARCH - DFS)

I INTRODUCTIONIl sagit dune mthode de parcours des sommets du graphe. Elle permet de rsoudre les

problmes de connexit sur un graphe par des algorithmes efficaces (i.e. linaires). Parexemple :

- un sommet j est-il accessible partir dun sommet i donn ?- le graphe est-il connexe ?- le graphe est-il fortement connexe ?On suppose que G est un 1-graphe (sans perte de gnralit).

II PRINCIPEIl sagit dexplorer tous les sommets dun graphe, une fois et une seule, atteignables

partir dun sommet i0 donn et en cheminant le long des arcs en accord avec leur orientation.On avance tant quon peut avancer. A chaque embranchement possible, on prend unedirection au hasard. Lorsquon ne peut plus avanceer ou que lon retombe sur un sommet djrencontr, on repart du dernier embranchement en prenant une nouvelle direction.

Au cours de lexploration, tout sommet i se trouve dans lun des 2 tats suivants :S1 : i na pas encore t rencontrS2 : i a dj t rencontr. On note P(i) le sommet partir duquel on a rencontr i.Soient les 2 sous-tats :

E1 : tous les successeurs de i ont dj t examins.E2 : certains successeurs j de i (j appartient "i) nont pas t examins.

- Conditions initiales :P(i0) = i0;P(i) = 0, pour tout i / i0 , i.e. i non encore atteint.i dans ltat S1 P(i) = 0

Soit n(i), un compteur associ chaque sommet, donnant le nombre de successeurs de inon encore examins.initialement n(i) = d+i = Card ("i)i dans ltat E1 n(i)=0- A ltape courante :On considre le sommet i atteint(au dpart i=i0)

Cas 1 : n(i) > 0il existe j ! "i non encore examin.

- slectionner j dans "i non encore examin- et faire n(i)

DFS

Page 2

Cas 1a : cest la premire fois que lon rencontre le sommet j i.e. P(j)=0. On marque alors jcomme atteint partir de i i.e. P(j)

DFS

Page 3

Complexit : Chaque arc est parcouru au plus une fois et on neffectue jamais plus dun retour arrire

pour chaque sommet => le nombre doprations lmentaires est en O(N)+O(M). Dans un graphe connexe on a toujours M > N-1. Donc O(M).

III APPLICATIONS : III.1 : TEST DE CONNEXITE - DETERMINATION DES COMPOSANTES CONNEXES

Connexit notion non oriente => on remplace chaque arte (i,j) par deux arcs (i,j) et (j,i). Soit G[X,U] le graphe obtenu. Test de connexit :

Si G non connexe, il nexiste pas de chane entre 2 sommets i0 et j0 il nexiste pas de chemin entre i0 et j0 dans G. Donc, si en appliquant lalgorithme D.F.S. il existe un sommet j / P(j)=0, G nest pas connexe. Dtermination des composantes connexes :

Dans lalgorithme D.F.S., un sommet j est atteint dan G il appartient la mme composante connexe que i0 dans G.

=> on applique la procdure D.F.S. en marquant i0 et tous les sommets atteints 1. On ritre partir dun autre sommet non atteint en prenant une marque gale 2. etc.... En pratique il suffit dutiliser un tableau ncomp(), ncomp(i) donne le numro de

composante connexe du sommet i. Si nc est le numro de composante connexe en cours de construction, le cas 1a devient : Si (P(j)=0) alors P(j)

DFS

Page 4

Enonc formel de dtermination des composantes connexes :a- Initialisations :

pour i=1,2,...,N fairencomp(i)

DFS

Page 5

Soit ninf() un tableau / ninf(i) donne le j de (2), initialement ninf(i)=i.Calcul de inf(i) :

inf(i) peut tre calcul directement dans DFS :Si chaque fois que lon atteind un sommet i, on initialise inf(i)

DFS

Page 6

Enonc formel de lalgorithme DFS2 :a- initialisationPour i=1,2,....,N, faire :

P(i)

DFS

Page 7

Dmonstration :Soit un graphe comportant p composantes fortement connexes C1,C2,..Cp.

Soit Cq dont lun des sommets est atteint dans DFS2 (=> tous les sommets sont atteints).condition ncessaire :

Soit i0 le premier sommet de Cq atteint, on a : ( j ! Cq, num(j) > num(i0) (cf.lemme).Soit un circuit passant par i0 (il existe puisque Cq composante fortement connexe).De faon gnrale il est constitu de :- un chemin entre i0 et i1 ! D(i0) dont tous les sommets intermdiaires appartiennent D(i0)(ce nest pas forcment un chemin de larborescence),- dun arc entre i1 ! D(i0) et i2 # D(i0),- dun chemin de i2 i0.On a :num(i2) > num(i0) puisque i0 est le premier rencontr.num(i2) < num(i1) daprs le lemme

=> num(i0) < num(i2) < num(i1)Mais comme i1 ! D(i0), tous les sommets j / num(i0) < num(j) < num(i1) sont danslarborescence issue de i0 => contradiction sur i2.Donc i2 ! D(i0)=> tout les sommets dun circuit passant par i0 appartiennent D(i0).Ceci tant vrai pour tout circuit, il nexiste pas dans D(i0) de sommet i1 reli j ! A(i0) avecnum(j) < num(i0)Donc i0 est tel que inf(i0) = num(i0).condition suffisante :Soit i0 / inf(i0) = num(i0).Par labsurde :Soit j ! Cq / num(j) < num(i0).Comme il existe un chemin entre j et i0, j ! A(i0).Dautre part, par i0 et j il passe au moins un circuit => il existe au moins un arc allant dunsommet de D(i0) j.

On a alors inf(i0) < num(j) < num(i0). Do contradiction. c.q.f.d.Application : dtermination des composantes fortement connexes

Pour trouver toutes les c.f.c., on utilise une pile :Lorsque on explore un nouveau sommet, on empile son numro dordre.Lors dun retour arrire et lorsque num(i)=inf(i) les lments de la composantes fortementconnexe sont dans la pile entre i et le haut de la pile. Il suffit donc de dpiler les (haut-de-pile)-i lments.

DFS

Page 8

a- initialisationPour i=1,2,....,N, faire : P(i)

Chemins

Page 1

PROBLEMES DE CHEMIN DANS LES GRAPHESI EXISTENCE DE CHEMINS, FERMETURE TRANSITIVE :Dfinition : On appelle fermeture transitive dun graphe G(X,U) le graphe G(X,U) o U={(i,j) si il existe un chemin de i j }.

Calcul de G :I.1 Mthode matricielle :Elever la matrice dadjacence la puissance N-1 dans lalgbre ((0,1),max,min) algbre((0,1),ou,et) :M2 =(xij) o xij = . aik . akj.xij = 1 il existe k0 / aik0 . ak0j = 1

il existe un arc (i,k0) et un arc (k0,j) il existe un chemin de i j de longueur 2

Ml = Ml-1 . M o xij = yik . akj.xij = 1 il existe k0 / yik0 . ak0j = 1

il existe un chemin (i,k0) de longueur < l-1 et un arc (k0,j) il existe un chemin de i j de longueur < l.

Complexit : O(N4)

I.2- Deuxime mthode :1- Dterminer les composantes fortement connexes.2- Dterminer la fermeture transitive du graphe rduit G/R.3- En dduire la fermeture transitive du graphe.

point 1 : cf. chap. prcdent . complexit en O(M).point 3 : algorithme de reconstructiona- pour chaque c.f.c. Xi de cardinal Ni, tablir la liste des Ni(Ni-1) arcs du sous-graphecomplet sur Xi.b- si Xk et Xl sont deux sommets tels que arc (k,l) ! G/R, alors tablir la liste des Nk*Nlarcs de la forme (i,j) avec i ! Xk, j ! Xl.Complexit : O(M).

le problme se rduit au point 2 => fermeture transitive dun graphe sans circuit.I.3- Fermeture transitive dun graphe sans circuit :Soit G(X,U) dont les sommets sont numrots suivant un ordre topologique inverse i.e. (i,j)! U => j < i (cf. III ).Algorithme :

Chemins

Page 2

a- Pour tout i faire : Li C(i,j) = C(i,j) U Cir o C(i,j) est un chemin lmentaire de i j et Cir est un circuit.. si l(Cir) < 0, il nexiste pas de plus court chemin => pas de solution. si l(Cir) > 0 alors l(C) < l(C), on se restreint au chemin lmentaire.

Plusieurs algorithmes suivant que :- lu > 0 , pour tout u- lu = 1, pour tout u- G et lu quelconques- G sans circuit

et que lon sintresse au plus court chemin entre :- 1 sommet donn et un autre sommet donn- 1 sommet donn et tous les autres sommets- tous les couples de sommets

II.1 : Plus courts chemins dorigine fixe i0 :II.1.1 Longueurs quelconques : algorithme de Ford-Bellman

On utilise le principe doptimalit de Bellman :toute sous-politique dune politique optimale est une politique optimale.

En termes de longueurs de chemins : si L*(j) reprsente la longueur du plus court chemin entre i0 et j, on a :

L*(j) = MIN [ L*(i) + l(i,j) ] i ! Pred(j)

Chemins

Page 3

Principe de lalgorithme : procdure de marquage.

A chaque sommet i on associe une marque M(i). Les M(i) sont modifis itrativement de tellesorte qu la fin M(i) reprsente la longueur du plus court chemin de i0 i.

initialement : M(i0)=0 et M(i)=+0 pour i/i0.

Daprs le principe doptimalit :Les M(i) reprsentent les longueurs des plus courts chemins de i0 i pour tout (i,j) de U : M(j) < M(i) + lijLe principe de lalgorithme consiste balayer tous les arcs et vrifier la condition pourchaque arc :

- lorsque la condition est satisfaite pour chaque arc, le pb est rsolu.- lorsque on rencontre un arc (i,j) / M(j) > M(i)+lij, on met jour la valeur de M(j) par :M(j) = M(i)+lij.Au passage, on note dans un tableau P que le sommet j a pour prdcesseur i sur le +

court chemin en faisant P(j) O(MN).Enonc formel :a- Initialisations :

M(i0)

Chemins

Page 4

c - Si k=N+1 et Modif=vrai (i.e. il y a eu une modification la Nime itration) alors il existeun circuit de longueur ngative et donc il nexiste pas de solution au problme,FIN Sinon on a trouv la solution FIN

Chemins

Page 5

II.1.2 : Longueurs > 0 , algorithme de MOORE-DIJKSTRA :

Principe identique de marquage des sommets.A chaque itration lensemble des sommets est partag en deux : X = S U X/S = S U So S et S sont dfinis par :pour tout k ! S , M(k)=L*(k).pour tout k ! S, M(k)= MIN (M(i)+lik) (1)

i ! S%"-1k= la longueur minimale des chemins de i0 k condition que tous les sommets

S est lensemble des sommets dont la marque est dfinitive, et S est lensemble des sommetsdont la marque est provisoire.Lemme : Soit j ! S / M(j)= Min { M(i) } alors M(j)=L*(j)

i ! SDm :- il existe un chemin de i0 j de longueur M(j) par dfinition de M- soit Ch un chemin quelconque de i0 j .Ch peut tre dcompos en 2 sous-chemins :

Ch1: i0 -> k o k est le premier sommet de S rencontret Ch2 : k -> j.

on a : L(Ch1) = M(k) > M(j) par dfinition de j et L(Ch2) > 0donc L(Ch) = L(Ch1) + L(Ch2) > M(j) , et ceci pour tout chemin Ch de i0 j.Donc M(j)=L*(j).

Enonc formel de lalgorithme de MOORE-DIJKSTRA :a- Initialisations :S = {1,2,....N}M(i0)

Chemins

Page 6

O(d+(j)) oprations.Pour la slection du sommet j de S de marque minimale, il faut N oprations => O(N).Or 1 d+(j) = M donc au total la complexit est en O(M)+O(N2).Or, on a toujours M < N2, et donc on a une complexit en O(N2).

II.1.3 longueurs constantes longueurs en nombre darcs :Les informations stockes sont identiques (M(i) et P(i)), mais en plus on utilise une file(FIFO) contenant les sommets marqus avec le rgles suivantes :- chaque fois quun sommet i (prcdemment non marqu reoit une marque provisoire, ilentre dans la file ladresse top+1.- chaque itration, le sommet en tte de file est le sommet slectionn et il est extrait de lafile.Justification :Il faut donc que le sommet de tte de file soit le sommet de marque provisoire minimum :

- au dbut de la premire itration, lorsque i0 est slectionn la file est vide, puiscontient tous les successeurs j de i0 munis de la marque provisoire M(j)=1 qui sont stocks demanire conscutive dans la file.

-le sommet slectionn a donc une marque M(j)=1. Les seuls nouveaux sommets misdans la file sont les successeurs de j, non marqus, et ils reoivent la marque M(j)+1=2.Les sommets successeurs de j, qui taient dj marqus 1, sont dj dans la file avec lamarque 1

- etc....Donc tout sommet de marque provisoire k est examin aprs tout sommet de marqueprovisoire < k.Do le choix de llment de marque provisoire minimale se fait en O(1), ce qui conomisele terme en O(N2) de MOORE-DIJKSTRA.Do complexit en O(M).

Enonc formel de lalgorithme :a- Initialisations :M(i0)

Chemins

Page 7

si bottom < top faire : j 0 Moore-Dijkstra => O(N3)l 0 Ford-Bellman => O(MN2)l = 1 => O(MN)

Lalgorithme de Floyd a une complexit en O(N3) mme si les longueurs sont ngatives ounulles. Il sagit dune mthode matricielle.

Principe :Soit L=(lij) la matrice des longueurs darcs avec lij = +0 si (i,j) # U et lii=0.

On note L(k) = (lij(k)) la matrice dont le terme lij(k) reprsente la longueur minimale dunchemin de i j condition que tous les sommets intermdiaires appartiennent {1,2,....k} etL(0) = L. La matrice L(N) est donc la matrice des longueurs des plus courts chemins

Proprit : Pour tout i et tout j , lij (k) = Min { lij(k-1) , lik(k-1)+lkj(k-1) } (1)Dm : le plus court chemin de i j sommets intermdiaires dans { 1,2,...k } passe par k (cas1) ou ne passe pas par k (cas 2).- cas 1 : ce chemin est form dun sous-chemin Ch1 : i -> k et dun sous-chemin Ch2 : k -> jChacun deux a ses sommets intermdiaires dans {1,2,...k-1} et doit tre minimal (principedoptimalit de Bellman) et sont donc de longueur lik(k-1) et lkj(k-1). Donc lij(k) = lik(k-1) +lkj(k-1).- cas 2 : on a videmment lij(k) = lij(k-1)

Algorithme :La matrice des plus courts chemins L(N) va tre calcule en N itrations grce la formule(1).C--d litration 1, le sommet 1 est insr dans le chemin de i j si lij > li1+l1j, etc...=> complexit en O(N3).

Remarques :- cet algorithme permet de dtecter lexistence dun circuit de longueur ngative et donc pasde solution. Le circuit apparait ds quun lii(k) devient ngatif.- appliqu tel quel, lalgorithme de Floyd ne dtermine que les longueurs des plus courts

Chemins

Page 8

chemins. Si lon veut expliciter le chemin, on utilise une matrice P=(Pij) qui contient leprdcesseur sur le plus courts chemins avec :

- initialement : pij=i si lij < +0pij=0 sinon

- a la kime itration, si le sommet k est insr entre i et j, llment Pij est remplac parle Pkj courant, c--d Pij

Chemins

Page 9

Enonc formel de lalgorithme de Floyd :a- initialisationPour i=1,2,...,N

Pour j=1,2,...,NSi (i,j) ! U, alors faire

L(i,j)

Chemins

Page 10

Proprit : Pour tout k>0, lensemble Xk des sommets de niveaux k est gal lensemble dessommets de degr intrieur nul dans le graphe obtenu en liminant tous les sommets deniveau 0,1,...,k-1.Algorithme de dtermination dun ordre topologique si G est sans circuit, et de dtectiondun circuit dans le cas contraire :

a- Soit G(X,U) = G(X,U) k

Chemins

Page 11

rang(j)

Chemins

Page 12

Remarque : dans le cas dune maximisation, il suffit de remplacer Min par Max dans (1).

Application : le problme central de lordonnancement.

Un projet donn est compos de N tches ayant entre elles des contraintes dantriorit. Soitchaque tche i a un dure dtermine di ou le passage dune tche i une tche j a un dlaidij. Le problme est de trouver un ordonnancement des tches pour lequel le projet sera fini leplus tt possible et de dterminer pour chaque tche la date au plus tt laquelle elle peutcommencer et la date au plus tard laquelle on peut la faire commencer sans retarder la datede fin des travaux.Pour cela on cre un graphe dont chaque sommet est une tche et dont les arcs reprsentent lescontraintes dantriorit.Chaque arc (i,j) est valu soit par di soit par dij. Ce graphe est videmment sans circuit.On rajoute un sommet D de dbut des travaux relis par des arcs valus 0 aux sommets sansprdcesseurs et un sommet F de fin des travaux relis aux sommets sans successeurs par desarcs valus soit di soit 0.

- La date au plus tt de chaque tche est donc gale : ti = Max (tj+dji) et tD = 0 j ! "-1i

c--d la longueur du plus long chemin entre D et i.

- la dure totale du projet est tF.

- Si on fixe la dure du projet tF, la date au plus tard Ti de la tche i est :Ti = Min (Tj-dij) et TF=tF j ! "i

- la marge est mi = Ti - ti.Les tches de marge nulles sont appeles tches critiques. Ce sont celles qui ne peuventprendre aucun retard.

Donc pour dterminer les ti, on utilisera lalgorithme prcdent.Pour dterminer les Ti, on utilisera lalgorithme prcdent en prenant les sommets par ordredcroissant et en initialisant Tf tf.

Arbres et arborescences

Page 1

ARBRES ET ARBORESCENCESI DEFINITIONS- un arbre est un graphe connexe sans cycles (non orient)- une fort est un graphe sans cycles => k arbres- un fort maximale est une fort telle que si lon ajoute un arc on introduit un cycle.

Proprits :a) G(X,U) est un arbre entre 2 sommets quelconques il existe une chane unique.b) Si G a N sommets et P composantes connexes, une fort maximale de G comporteexactement N-P artes. Donc tout arbre extrait de G comporte N-1 arcs.c) Soit F(X,T) une fort maximale de G(X,U) Alors F et G ont mme nombre de connexit.d) G admet un graphe partiel qui est un arbre G est connexe.e) Soit F(X,T) une fort maximale de G(X,U). Pour tout u de U-T, il passe un cycle et un seulC dont toutes les artes, sauf u, appartiennent F (consquence de a- et dfinition de fortmaximale).

II- ARBRE DE POIDS MINIMUM (MINIMUM SPANNING TREE)Problme : Soit G(X,U) un graphe connexe. A chaque arte u de U est associ un nombrerel p(u) appel le poids de larte.Le problme est de trouver F*(X,T) tel que :

p(F*) = . p(u) soit minimal. u ! F*

Rappel : un cocycle CC est un ensemble darcs tel quil existe A $ X et tel que chacun desarcs de CC ait une extrmit dans A et lautre dans X-A.

Proprit : Soit F(X,T) un arbre de G(X,U) connexe. Soit u(x,y) une arte de F. Le cocycleCCu tel que CCu % T = {u} est compos dartes v(a,b) telles que il existe une chanedans F de a x et il existe une chane de y b dans F.

Thorme : F(X,T) est un arbre de poids minimum ssi pour toute arte u de T, le cocycleCCu ( tel que CCu % T = {u} ) vrifie :

p(u) < p(v) pour tout v de CCu ( v / u).

Autrement dit, une C.N.S. pour quun arbre soit de poids minimum est que pour toute arte ude larbre, toutes les artes de CCu soient de poids suprieur u.

Dm :Condition ncessaire :Soit u ! T et v ! CCu / p(u) > p(v). Le graphe partiel (X,T+{v}-{u}) est un arbre(cf.proprit) et de poids strictement infrieur F(X,T). Contradiction.


Page 2

Condition suffisante :Soit F(X,T) un arbre vrifiant la condition et soit F*(X,T*) un arbre de poids minimum avec F/ F*. Montrons que p(F)=p(F*).Soit u ! T et u # T*.Soit CCu le cocycle associ u.Soit Cu le cycle introduit par u dans F*.Soit v ! CCu % Cu (v / u), v # T et v ! T*.Par dfinition de T, on a : p(v) > p(u).On ne peut pas avoir p(v) > p(u), car en remplaant v par u dans F*, on obtiendrait un arbre depoids infrieur F* (qui est de poids minimum). Donc p(v)=p(u).En rsum, pour tout u de F, il existe v de F* / p(u)=p(v) et donc p(F)=p(F*). c.q.f.d.

Algorithme de PRIM : (cas gnral) issu directement du thorme.Principe : On construit progressivement partir dun sommet i0 arbitraire un sous-ensemblede sommets A de X contenant i0 et un sous-ensemble T de U tel que (A,T) soit un arbre depoids minimal du sous-graphe engendr par A.Pour cela on slectionne dans le cocycle CC(A)= { (k,l) / k ! A et l ! X-A } larte de poidsminimum. Soit u=(i,j) cette arte. On ajoute alors j et u A et T respectivement.

Mise en oeuvre :- chaque sommet i, on associe une marque m(i) telle qu une tape quelconque, pour i !X-A, m(i) reprsente le poids de larte de poids minimal joignant i un sommet de A.- Il suffit alors de prendre le sommet i ayant la marque m(i) minimale.- dans Lien(i) on conserve larte ayant permis dattribuer i la marque m(i).Lorsque le sous-ensemble A est augment dun sommet i, on met jour les artes u(i,j) avec j! X-A par : m(j) 0 ssi i ! ALien(i)


Page 3

m(j) cetalgorithme permet de tester la connexit.

Thorme : F(X,T) est un arbre de poids minimum ssi pour tout arc u de U-T, le cycle Cu (telque Cu $ T+{u}) vrifie :

p(u) > p(v), pour tout v de Cu (v / u).

Dm : consquence du thorme prcdent.Consquence : si les poids des arcs sont tous diffrents, larbre de poids minimum est unique.Do lalgorithme (dans le cas o tous les poids sont diffrents).

Algorithme de Kruskal:a- ranger les artes par ordre de poids croissant.b- en suivant cet ordre, on reconstruit larbre de la faon suivante :

- soit u larte de poids minimum restant.- on rajoute u larbre. Si u introduit un cycle, on le retire, sinon on le garde.

Enonc formel de lalgorithme de Kruskala)- ranger les artes par ordre de poids croissant dans U.b)- T


Page 4

- F est une arbre de G- Pour tout j / i0, il existe un chemin de i0 j.

Un graphe est dit quasi fortement connexe si pour tout couple de sommet (i,j) il existe unsommet k reli i et j par deux chemins, lun entre k et i, lautre entre k et j.

forte connexit => quasi forte connexit => connexit

Proprits : les proprits suivantes sont quivalentes.Soit F(X,T) un graphe dordre N>1.a) F est un arbre admettant une racine i0.b) Il existe un sommet i0 qui est reli chacun des autres sommets par un chemin uniquedorigine i0.c) F est quasi fortement connexe et est minimal pour cette proprit.d) f est connexe et il existe i0 / d-(i0)=0 et pour tout j/i0, d-(j)=1.e) F est sans cycle et il existe i0 / d-(i0)=0 et pour tout j/i0, d-(j)=1.f) F est quasi fortement connexe et sans cycle.g) F est quasi fortement connexe et comporte N-1 arcs.IV - ARBORESCENCE DE POIDS MINIMUM :Problme : On associe chaque arc u un poids p(u), on veut chercher larborescence F* deracine i0 telle que :


Le principe de lalgorithme est bas sur la proprit e).Pour chaque sommet j / i0, on choisit larc incident j de poids minimum. Si le grapheobtenu est sans circuit (ou de faon quivalente sil est connexe) alors il sagit delarborescence de poids minimum. Sinon il contient un circuit C.Thorme : Si F*(X,T*) est une arborescence de poids minimal de racine i0 alors F* contient

tous les arcs du circuit C sauf un. (C est le circuit obtenu par la mthode prcdente).Dm :F* ne peut contenir tous les arcs de C (vident).Supposons que F* contienne C sauf 2 arcs (a,b) et (c,d).Comme F est une arborescence, il existe un chemin de i0 b et un chemin de i0 c.Soit a le prdcesseur de b sur ce chemin, a / a par hyp.Soit c le prdcesseur de d sur ce chemin, c / c par hyp.Par construction de C, on a : p((a,b)) > p((a,b))En remplaant (a,b) par (a,b) on obtiendrait une arborescence de poids infrieur. c.q.f.d.

Le principe de lalgorithme est, lorsque un circuit C est cr, de contracter G(X,U) suivant C,c--d remplacer C par un pseudo-sommet => G(X1,U1) = G/C.Soit F1*=(X1,T1*) la trace de F sur G1.F* et F1* sont lis par la relation :

p(F*)=p(F1*)+p(C)-p(u) o u est larc de C qui nappartient pas F.


Page 5

Lors de la contraction on modifie les poids de la faon suivante :p1(u) = p(u)-p(u) si u=(i,j) avec i # C, j ! C et u=(k,j), u! C.p1(u) = p(u) sinon.

On a alors p(F*)=p1(F1*)+p(C).Donc F1* est une arborescence de poids minimal par rapport aux poids p1 dans G1. On peutalors reconstruire F en prenant F1 plus C moins larc u intrieur C correspondant larcincident C.On a ramen le problme un problme de taille plus petite, etc...

Enonc formel de lalgorithme de recherche dune arborescence de poidsminimal

a- initialisationst


Page 1

ARBRES ET ARBORESCENCESI DEFINITIONS- un arbre est un graphe connexe sans cycles (non orient)- une fort est un graphe sans cycles => k arbres- un fort maximale est une fort telle que si lon ajoute un arc on introduit un cycle.

Proprits :a) G(X,U) est un arbre entre 2 sommets quelconques il existe une chane unique.b) Si G a N sommets et P composantes connexes, une fort maximale de G comporteexactement N-P artes. Donc tout arbre extrait de G comporte N-1 arcs.c) Soit F(X,T) une fort maximale de G(X,U) Alors F et G ont mme nombre de connexit.d) G admet un graphe partiel qui est un arbre G est connexe.e) Soit F(X,T) une fort maximale de G(X,U). Pour tout u de U-T, il passe un cycle et un seulC dont toutes les artes, sauf u, appartiennent F (consquence de a- et dfinition de fortmaximale).

II- ARBRE DE POIDS MINIMUM (MINIMUM SPANNING TREE)Problme : Soit G(X,U) un graphe connexe. A chaque arte u de U est associ un nombrerel p(u) appel le poids de larte.Le problme est de trouver F*(X,T) tel que :


Rappel : un cocycle CC est un ensemble darcs tel quil existe A $ X et tel que chacun desarcs de CC ait une extrmit dans A et lautre dans X-A.

Proprit : Soit F(X,T) un arbre de G(X,U) connexe. Soit u(x,y) une arte de F. Le cocycleCCu tel que CCu % T = {u} est compos dartes v(a,b) telles que il existe une chanedans F de a x et il existe une chane de y b dans F.

Thorme : F(X,T) est un arbre de poids minimum ssi pour toute arte u de T, le cocycleCCu ( tel que CCu % T = {u} ) vrifie :

p(u) < p(v) pour tout v de CCu ( v / u).

Autrement dit, une C.N.S. pour quun arbre soit de poids minimum est que pour toute arte ude larbre, toutes les artes de CCu soient de poids suprieur u.

Dm :Condition ncessaire :Soit u ! T et v ! CCu / p(u) > p(v). Le graphe partiel (X,T+{v}-{u}) est un arbre(cf.proprit) et de poids strictement infrieur F(X,T). Contradiction.


Page 2

Condition suffisante :Soit F(X,T) un arbre vrifiant la condition et soit F*(X,T*) un arbre de poids minimum avec F/ F*. Montrons que p(F)=p(F*).Soit u ! T et u # T*.Soit CCu le cocycle associ u.Soit Cu le cycle introduit par u dans F*.Soit v ! CCu % Cu (v / u), v # T et v ! T*.Par dfinition de T, on a : p(v) > p(u).On ne peut pas avoir p(v) > p(u), car en remplaant v par u dans F*, on obtiendrait un arbre depoids infrieur F* (qui est de poids minimum). Donc p(v)=p(u).En rsum, pour tout u de F, il existe v de F* / p(u)=p(v) et donc p(F)=p(F*). c.q.f.d.

Algorithme de PRIM : (cas gnral) issu directement du thorme.Principe : On construit progressivement partir dun sommet i0 arbitraire un sous-ensemblede sommets A de X contenant i0 et un sous-ensemble T de U tel que (A,T) soit un arbre depoids minimal du sous-graphe engendr par A.Pour cela on slectionne dans le cocycle CC(A)= { (k,l) / k ! A et l ! X-A } larte de poidsminimum. Soit u=(i,j) cette arte. On ajoute alors j et u A et T respectivement.

Mise en oeuvre :- chaque sommet i, on associe une marque m(i) telle qu une tape quelconque, pour i !X-A, m(i) reprsente le poids de larte de poids minimal joignant i un sommet de A.- Il suffit alors de prendre le sommet i ayant la marque m(i) minimale.- dans Lien(i) on conserve larte ayant permis dattribuer i la marque m(i).Lorsque le sous-ensemble A est augment dun sommet i, on met jour les artes u(i,j) avec j! X-A par : m(j) 0 ssi i ! ALien(i)


Page 3

m(j) cetalgorithme permet de tester la connexit.

Thorme : F(X,T) est un arbre de poids minimum ssi pour tout arc u de U-T, le cycle Cu (telque Cu $ T+{u}) vrifie :

p(u) > p(v), pour tout v de Cu (v / u).

Dm : consquence du thorme prcdent.Consquence : si les poids des arcs sont tous diffrents, larbre de poids minimum est unique.Do lalgorithme (dans le cas o tous les poids sont diffrents).

Algorithme de Kruskal:a- ranger les artes par ordre de poids croissant.b- en suivant cet ordre, on reconstruit larbre de la faon suivante :

- soit u larte de poids minimum restant.- on rajoute u larbre. Si u introduit un cycle, on le retire, sinon on le garde.

Enonc formel de lalgorithme de Kruskala)- ranger les artes par ordre de poids croissant dans U.b)- T


Page 4

- F est une arbre de G- Pour tout j / i0, il existe un chemin de i0 j.

Un graphe est dit quasi fortement connexe si pour tout couple de sommet (i,j) il existe unsommet k reli i et j par deux chemins, lun entre k et i, lautre entre k et j.

forte connexit => quasi forte connexit => connexit

Proprits : les proprits suivantes sont quivalentes.Soit F(X,T) un graphe dordre N>1.a) F est un arbre admettant une racine i0.b) Il existe un sommet i0 qui est reli chacun des autres sommets par un chemin uniquedorigine i0.c) F est quasi fortement connexe et est minimal pour cette proprit.d) f est connexe et il existe i0 / d-(i0)=0 et pour tout j/i0, d-(j)=1.e) F est sans cycle et il existe i0 / d-(i0)=0 et pour tout j/i0, d-(j)=1.f) F est quasi fortement connexe et sans cycle.g) F est quasi fortement connexe et comporte N-1 arcs.IV - ARBORESCENCE DE POIDS MINIMUM :Problme : On associe chaque arc u un poids p(u), on veut chercher larborescence F* deracine i0 telle que :


Le principe de lalgorithme est bas sur la proprit e).Pour chaque sommet j / i0, on choisit larc incident j de poids minimum. Si le grapheobtenu est sans circuit (ou de faon quivalente sil est connexe) alors il sagit delarborescence de poids minimum. Sinon il contient un circuit C.Thorme : Si F*(X,T*) est une arborescence de poids minimal de racine i0 alors F* contient

tous les arcs du circuit C sauf un. (C est le circuit obtenu par la mthode prcdente).Dm :F* ne peut contenir tous les arcs de C (vident).Supposons que F* contienne C sauf 2 arcs (a,b) et (c,d).Comme F est une arborescence, il existe un chemin de i0 b et un chemin de i0 c.Soit a le prdcesseur de b sur ce chemin, a / a par hyp.Soit c le prdcesseur de d sur ce chemin, c / c par hyp.Par construction de C, on a : p((a,b)) > p((a,b))En remplaant (a,b) par (a,b) on obtiendrait une arborescence de poids infrieur. c.q.f.d.

Le principe de lalgorithme est, lorsque un circuit C est cr, de contracter G(X,U) suivant C,c--d remplacer C par un pseudo-sommet => G(X1,U1) = G/C.Soit F1*=(X1,T1*) la trace de F sur G1.F* et F1* sont lis par la relation :

p(F*)=p(F1*)+p(C)-p(u) o u est larc de C qui nappartient pas F.


Page 5

Lors de la contraction on modifie les poids de la faon suivante :p1(u) = p(u)-p(u) si u=(i,j) avec i # C, j ! C et u=(k,j), u! C.p1(u) = p(u) sinon.

On a alors p(F*)=p1(F1*)+p(C).Donc F1* est une arborescence de poids minimal par rapport aux poids p1 dans G1. On peutalors reconstruire F en prenant F1 plus C moins larc u intrieur C correspondant larcincident C.On a ramen le problme un problme de taille plus petite, etc...

Enonc formel de lalgorithme de recherche dune arborescence de poidsminimal

a- initialisationst

Flots

Page 1

PROBLEMES DE FLOTSI DEFINITIONS ET PROBLEME DE FLOT MAXIMUM :Dfinition : Soit G(X,U) avec Card(X)=N et Card(U)=M. Un flot dans G est un vecteur M

composantes f=(f1,...,fM) tel que :. fu = . fu , pour tout i de X (premire loi de Kirchoff).

u ! *+(i) u ! * -(i)

A chaque arc u, on associe : cu > 0 borne suprieure de flux ou capacit de u bu > 0 borne infrieure de flux.Un flot f est dit compatible avec les bornes bu et cu si bu < fu < cu pour tout u

Soit G(X,U) dans lequel chaque arc u est associe une capacit cu > 0 et deux sommetsparticuliers s (source) et t (puits).Soit G0(X,U0) obtenu en rajoutant larc (t,s) (arc de retour) de numro 0 et de capacitinfinie.On dit que le vecteur f=(f1,...,fM) est un flot de s t et de valeur f0 si et seulement sif=(f0,f1,...,fM) est un flot de G0.Pour f=(f1,f2,..,fm) les lois de conservation aux noeuds sont vrifies sauf en s et t o lon a :

. fu = . fu = f0 , pour tout i de X. u ! *+(i) u ! * -(i)

En gnral, on se limite G 1-graphe.

Le problme de flot maximum de s t dans G muni des capacits cu et bu revient dterminer f=(f0,f1,...,fM) tel que bu < fu < cu et que f0 soit maximum.

Dfinition : On appelle graphe dcart associ un flot f vrifiant les contraintes aux bornes legraphe G(f) = (X,U(f)) o U(f) est construit de la faon suivante : chaque arc u=(i,j) on fait correspondre au plus deux arcs:u+ = (i,j) si fu < cu de capacit (rsiduelle) cu-fu > 0u- = (j,i) si fu > bu de capacit (rsiduelle) fu-bu > 0.

Rappel : LEMME DE MINTY .

II CAS DES BORNES INFERIEURES NULLES :

Remarque : dans le cas des bornes infrieures nulles, le flot f=(0,0,...,0) est un flot compatible.Thorme : Soit f un flot de s t, compatible avec les cu. Soit G(f) le graphe dcart associ

f. Alors f est un flot maximum si et seulement si il nexiste pas de chemin de s t dansG(f).

Flots

Page 2

Dm : consquence du lemme de Minty (cf. Gondran et Minoux).

Le graphe dcart permet dune part de vrifier une solution mais aussi damliorer unesolution :Soit f de s t ne vrifiant pas la condition du thorme. Il existe donc un chemin de s t dansG(f). Ce chemin correspond sur G une chane L joignant s t.Par dfinition de G(f), si la chane L, parcourue de s t, c--d dans le sens direct, emprunteun arc u( i,j) de G dans le sens direct alors on a ncessairement fu < cu. Inversement, si elleemprunte u(i,j) dans le sens inverse alors fu > 0 .Soit L+ = ensemble des arcs parcourus dans le sens direct. L- = ensemble des arcs parcourus dans le sens inverse.Pour 2 >0 petit, soit la transformation :

fu = fu + 2 pour u ! L+.fu = fu - 2 pour u ! L-.

Cette transformation prserve les conditions de conservation du flot.De plus pour les sommets s et t, on a :

. fu = ( . fu ) + 2 = f0 + 2 = . fu . u ! *+(s) u ! * -(s) u ! * -(t)

Donc la valeur de f0 a t augment de 2.

Remarque : la valeur maximale possible pour 2 est la capacit du chemin L du graphe dcartc--d :2 = MIN (2+ , 2-) o 2+ = MIN (cu- fu) , 2- = MIN (fu)

u ! L+ u ! L-

ALGORITHME DU FLOT MAXIMUM (FORD ET FULKERSON) .a) Initialisations :k

Flots

Page 3

fuk+1 = fuk - 2k si u- ! Lkf0k+1 = f0k + 2k.

Faire k algorithme non polynomial.- si Pk est le plus court chemin en nombre darcs => O(M.N2).

Flots

Page 4

III - PROBLEME DU FLOT MAXIMUM AVEC BORNESINFERIEURES NON NULLES

On peut gnraliser la mthode prcdente avec des bu quelconques et utiliserlalgorithme prcdent en prenant : 2 = valeur maximale telle que 2 < cu- fu et 2 < fu.

Toutefois il reste le problme de la dtermination du flot compatible initial. f=(0,0,..,0)nest pas forcment compatible.

Thorme dHoffman et recherche dun flot compatible :Il existe un flot compatible ( bu < fu < cu pour tout u) si et seulement si pour toutcocycle * (A) = *+(A) U * -(A) :

. cu - . bu > 0. u ! *+(A) u ! * -(A)

Dm :condition ncessaire :si f compatible existe, on a , pour tout A

0 = . fu - . fu < . cu - . bu . u ! *+(A) u ! * -(A) u ! *+(A) u ! * -(A)

condition suffisante et construction dun flot compatible :Si f est un flot quelconque, on dfinit :du (fu) = 0 si fu ! [bu,cu]

bu - fu si fu < bu fu - cu si fu > cu

Donc en gnral d(f) = . du(fu) > 0 u!U

Lide est de minimiser de proche en proche la quantit d(f) jusqu trouver d(f)=0. Alors fsera un flot compatible.Si une tape quelconque, f vrifie d(f) > 0, il existe u0 tel que d(fu0)>0 c--d par exemplefu0 < bu0. soit u0= (y,x).Soit la coloration du graphe suivante :- larc u0 est colori en noir.- tous les arcs / fu < bu sont noirs- tous les arcs / bu < fu < cu sont rouges- tous les arcs / fu > cu sont verts.Daprs le lemme de Minty, on a les cas suivants :a)- Il existe un cycle noir, rouge et vert, avec tous les arcs noirs orients dans le mme sens,tous les verts orients dans le sens contraire.Soit le vecteur associ ce cycle avec ()u0 = +1.Soit 2=Min(21,22) avec :

Flots

Page 5

21 = Min {cu-fu}, + ={u / u =+1} c--d les arcs noirs du cycle et certains rouges u ! +22 = Min {fu-bu}, - = {u / u =-1} c--d les arcs verts du cycle et les autres arcs rouges u ! -

Soit alors f = f + 2.. On a d(f) cu), les arcs de *-(A) sont noirs (c--d fu < bu) avec fu0 < bu0.Or . fu - . fu = 0. u ! *+(A) u ! * -(A)

. cu - . bu < 0. u ! *+(A) u ! * -(A)

Ce qui montre que la condition ncessaire nest pas vrifie; et donc il nexiste pas de flotcompatible et lalgorithme sarrte.

remarque : si fu0 > cu0 (au lieu de fu0 < bu0), on procde de faon analogue en inversant lesrles de vert et noir.

Pour obtenir un cycle faisant intervenir le cas a) du lemme de Minty, on utilise uneprocdure de marquage, ou de faon quivalente, on recherche un chemin de x y dans legraphe dcart.

La condition du thorme est suffisante : si on suppose quelle est vrifie , chaque tape de lalgorithme prcdent, on a toujours lacondition a) du lemme de Minty, et on obtient toujours un flot f / d(f)=0

Parcours eulriens

Page 1

PARCOURS EULERIENSDfinitions : G[X,U] non orient connexe. Card(U)=M

- Une chane eulrienne est une chane empruntant une fois et une seule chaque arte.- Un cycle eulrien est une chane dont les extrmits concident.

Thorme : G connexe. G admet une chane eulrienne si et seulement si le nombre desommets de degr impairs est 0 ou 2 (0 pour un cycle,2 dans lautre cas).

Dm :condition ncessaire : Seules les deux extrmits sont de degr impair. Pour les autressommets i, il y a le mme nombre dartes avec lesquelles on arrive sur i que dartes aveclesquelles on repart de i (donc i de degr pair).condition suffisante : (par rcurrence sur le nombre dartes M).- vident pour M =0- on suppose la condition vraie pour tout graphe ayant moins de M artes.

- Soit G[X,U] / Card(U)=M et vrifiant la condition.Soit a et b les 2 sommets de degr impairs (dans lautre cas il suffit de diviser un sommet a en2 sommets a et b ayant chacun la moiti des artes).Soit L une chane parcourue en partant de a, en prenant nimporte quelle direction sansemprunter 2 fois la mme arte.A un instant donn soit x le sommet atteint. On aura donc utilis un nombre impair dartesincidentes a x => on peut donc en repartir.On ne sera donc bloqu que pour le sommet b. On a dfini ainsi une chane de a b.Soit G le graphe partiel engendr par les artes non parcourues. Tous les sommets de G sontde degr pair.Soit G1,G2,...,Gp les composantes connexes de G.Dans Gi il existe un cycle eulrien ci (par hypothse de rcurrence).L rencontre Gi aux sommets i1,i2,....,ip .Soit la chane L compose de ( lordre de rencontre prs des sommets ik) :L entre a et i1,du cycle c1 entre i1 et i1,L entre entre i1 et i2,.... , L entre ip et b.La chane L est donc une chane eulrienne entre a et b. c.q.f.d

Lalgorithme de dtermination dune chane eulrienne dcoule directement de ladmonstration.On part de a et on suit un chemin quelconque sans emprunter la mme arte. On arriveforcement en b. Si toutes les artes ont t rencontres fin. Sinon. Soit x un sommet par lequelon est pass et de degr restant non nul. On recherche un circuit eulrien dans le grapherestant de x x que lon recolle la premire chane. On ritre.

Parcours eulriens

Page 2

Enonc formel de lalgorithme :a - Initialisations :S(u)

Parcours eulriens

Page 3

PARCOURS HAMILTONIENSDfinitions : G[X,U] non orient connexe. Card(U)=M

- Une chane hamiltonienne est une chane passant une fois et une seule par chaquesommet.- Un cycle hamiltonien est une chane dont les extrmits concident.

Problmes : - trouver un chemin hamiltonien dans un graphe quelconque - on attribue chaque arte un longueur, trouver un chemin hamiltonien de

longueur minimale.

A lheure actuelle, on ne connait pas dalgorithme polynomial permettant de trouverune solution aux problmes ci-dessus. (et selon toute vraisemblance il nen existe pas)

=> pour rsoudre ces 2 problmes on donc explorer tout larbre des possibilits => algorithmede croissance exponentielle (dit NP-difficile).

Couplages

Page 1

PROBLEMES DE COUPLAGEDfinitions : Soit G(X,U) un graphe non orient, un couplage est un ensemble dartes K $

U, tels que deux artes quelconques de K ne sont pas adjacentes.On appelle couplage maximal un couplage de cardinalit maximale.

Un couplage correspond donc un appariement possible dobjets,tant donn des contraintesdappariement (du type tel objet ne peut tre appari quavec tels autres, etc...).Problme : Trouver un couplage maximal.Remarque : Dans le cas des graphes biparti, ce problme peut tre rsolu par un algorithme deflots.Dfinitions : Si K $ U est un couplage de G, un sommet i de X est dit satur par le couplage

K sil existe une arte de K incidente i. Dans le cas contraire i est dit insatur.Lensemble des sommets saturs pour K est not S(K).On appelle chane alterne (relativement K) une chane lmentaire de G dont lesartes sont alternativement dans K et U-K.

Lemme 1 : Soient K et K deux couplages distincts de G. Alors les composantes connexes dugraphe partiel H(X,V) o V=K 3 K sont de trois types :type 1 : point isoltype 2 : cycle lmentaire pair dont les artes sont alternativement dans K et Ktype 3 : chane lmentaire dont les artes sont alternativement dans K et K.

Dm : Le degr maximum dun sommet de H est 2 puisquil ne peut y avoir plus dune artede K et plus dune arte de K incidente ce sommet.a- Soit x # S(K-K) et x # S(K-K) => x est isol.b- Soit x ! S(K-K) et x # S(K-K). x est extrmit dune unique arte de K et daucunearte de K.c- Soit x ! S(K-K) et x ! S(K-K). x est extrmit dune unique arte de K et dune arteunique de K.Do les composantes connexes.Consquence : Soit K $U est un couplage et soit L une chane alterne telle que chaque

extrmit est soit un sommet insatur, soit telle que lunique arte de K qui lui estincidente soit dans L. Alors le sous-ensemble K=K 3 L est encore un couplage de G(cf. lemme 1).

K est obtenu en changeant les rles des artes de L de appartient K en nappartient pas K et inversement. Une telle opration est appele transfert le long de L.Dfinitions : Une chane alterne augmentante est une chane alterne joignant 2 sommets

insaturs. Le transfert le long dune telle chane augmente le couplage dune unit.Une chane alterne rductrice est une chane alterne lmentaire impaire dont lesextrmits sont dans K (rduction dune unit de couplage).Une chane alterne conservatrice est une chane alterne lmentaire dont une desextrmits est un sommet isol (un transfert ne change rien la cardinalit du couplage).

Thorme : un couplage K est maximum si et seulement si il nexiste pas de chane alterneaugmentante relativement K.

=> vident

Couplages

Page 2

Daprs le lemme 1, le graphe le graphe (X, K 3 K) nadmet pas de composante connexe detype 3 augmentante => Card(K-K) = Card (K-K) => Card (K) = Card(K).Corollaire 1 : Un couplage qui ne laisse pas plus dun sommet insatur est maximum.Corollaire 2 : Soit K un couplage maximum de G. Tout couplage maximum K de G peut

sobtenir partir de K par une suite de transferts le long des chanes alternes deux deux disjointes et qui sont :soit des cycles lmentaires pairs,soit des chanes alternes impaires.

Algorithme de recherche dun couplage maximum :Daprs le thorme 1, il suffit de trouver une chane alterne augmentante (et donc qui joint 2sommets insaturs) relativement un couplage K $ U quelconque. Il suffit ensuite deffectuerun transfert le long de ce chemin.

Documents

Graphes