[PDF] Algorithmique de graphes - LIPN PDF Cours_Algo

Tri topologique dans un graphe orienté sans circuit Déterminer la fermeture transitive du graphe réduit Gr qui est sans circuit 3 Déduire la fermeture

Voici le graphe pour lequel on se propose de calculer la fermeture transitive en calculant les puissances successives des matrices 1 2 3 4 5 6 La matrice

[PDF] TP 6 Fermeture transitive dun graphe orienté

Le but de ce TP est de calculer la fermeture transitive d'un graphe orienté D, puis de l'utiliser afin de calculer les composantes fortement connexes de D Langage

[PDF] Graphes orientés - Université de Montréal

8 Graphes orientés Calculer la fermeture transitive d'un graphe On peut utiliser l'algorithme de parcours en profondeur à partir de chaque sommet: O(n(n+m))

[PDF] Théorie des graphes et optimisation dans les graphes Table - CNRS

peut modéliser ce problème par un graphe non orienté, dont les sommets matrice d'adjacence de la fermeture transitive Gf du graphe G de départ

[PDF] Fermeture transitive - Dimitri Watel

TD 2 : Fermeture transitive Théorie des Dessinez la fermeture transitive des graphes suivants : A B C D E A Soit G un graphe orienté sans circuit Montrer

[PDF] Parcours de graphes - IRIF

13 déc 2017 · Les graphes sans circuits Fermeture transitive Données: un graphe orienté G = (X,U), un sommet x0 ∈ X Résultat: une arborescence de

[PDF] Algorithmique de graphes - LIPN

Tri topologique dans un graphe orienté sans circuit Déterminer la fermeture transitive du graphe réduit Gr qui est sans circuit 3 Déduire la fermeture

[PDF] Graphes Orientés - uOttawa

Utiliser l'Algorithme 5 16 (Algorithme 5 17) afin de trouver la fermeture transitive des graphes de l'Probl`eme 5 13 Montrer chaque matrice W(k) et graphe orienté

[PDF] Les graphes BTS SIO2

longueur p, la fermeture transitive, les niveaux et chemin de valeur minimale 1 Graphes simples orientés a) Graphe – représentation sagittal b) Sommets – arcs

[PDF] le temps de la révolution et de l'empire cycle 3

[PDF] fermeture transitive matrice

[PDF] décomposition d'un graphe en niveaux

[PDF] chemin hamiltonien

[PDF] de l'année 1789 ? l'exécution du roi cm1

[PDF] graphe d'ordonnancement

[PDF] sujet algorithme bts sio corrigé

[PDF] calcul matrice booléenne

[PDF] calcul matriciel bts

[PDF] prise de note rapide tableau abréviations

[PDF] sauzay programme

[PDF] programme voltaire

[PDF] un petit paragraphe sur l'environnement

[PDF] exemple de texte argumentatif sur l'environnement

[PDF] texte sur l'environnement

Algorithmique de graphes

Lucas Letocart

LIPN - UMR CNRS 7030

Institut Galilee, Universite Paris 13

99 av. Jean-Baptiste Clement

93430 Villetaneuse - FRANCE

lucas.letocart@lipn.univ-paris13.fr

Algorithmique de graphes

Chapitre Contenu du document.

1. Introduction4

2. Notions elementaires 4

2.1. Quelques problemes modelisables par des graphes . . . . . . . . . . . . . . . . . . . .

2.1.1. Choix d'un trajet en train . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2. Planication d'une session d'examens . . . . . . . . . . . . . . . . . . . . . .

2.1.3. Ordonnancement de t^aches . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4. Routage dans les reseaux de telecommunications . . . . . . . . . . . . . . . .

2.2. Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3. Connexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1. Cha^nes et chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2. Graphes et composantes connexes et fortement connexes . . . . . . . . . . . .

3. Representation des graphes 9

3.1. Matrices d'adjacence et d'incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1. Matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.2. Matrice d'incidence sommets-arcs . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.3. Matrice d'incidence sommets-ar^etes . . . . . . . . . . . . . . . . . . . . . . . .

3.2. Representation des graphes en machine . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1.

A partir de la matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . . .9

3.2.2.

A partir de la matrice d'incidence sommets-arcs ou sommets-ar^etes . . . . . .10

4. Parcours des graphes 10

4.1. Parcours en profondeur d'abord : DFS (Depth First Search) . . . . . . . . . . . . . .

4.2. Determination des composantes connexes . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1. Cas non oriente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2. Cas oriente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3. Determination des composantes fortement connexes . . . . . . . . . . . . . . . . . .

4.4. Tri topologique dans un graphe oriente sans circuit . . . . . . . . . . . . . . . . . . .

4.5. Fermeture transitive d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5.1. Algorithme de parcours de graphes . . . . . . . . . . . . . . . . . . . . . . . .

4.5.2. Puissances de la matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . .

4.5.3. Algorithmes par multiplications matricielles . . . . . . . . . . . . . . . . . . .

5. Problemes de meilleurs chemins 21

5.1. Plus courts chemins d'origine xee dans un graphe avec longueurs non negatives :

algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2

Algorithmique de graphes

5.2. Mise en oeuvre de l'algorithme de Dijkstra pour les graphes peu denses : algorithme

de Johnson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.2.1. Presentation de la structure de donnees de tas (heap) . . . . . . . . . . . . .

5.2.2. Algorithme de Johnson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3. Plus court chemin d'origine xee dans un graphe sans circuit avec longueurs quel-

conques : algorithme de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.4. Determination de plus courts chemins d'origine xee dans un graphe avec longueurs

quelconques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.4.1. Algorithme de Ford (1956) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4.2. Algorithme de Ford-Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5. Plus courts chemins entre toutes les paires de sommets : algorithme de Floyd . . . .

6. Arbres couvrants 28

6.1. Arbre et arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2. Arbre couvrant de poids minimal d'un graphe simple . . . . . . . . . . . . . . . . . .

6.2.1. Formulation du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.2. Algorithme de Prim-Dijsktra . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.3. Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7. Flots dans les graphes 32

7.1. Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2. Proprietes fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.1. Flot maximal et coupe minimale . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.2. Graphe d'ecart et chemin augmentant . . . . . . . . . . . . . . . . . . . . . .

7.3. Recherche d'un

ot maximal : algorithme de Ford-Fulkerson . . . . . . . . . . . . . . 34

7.3.1. Algorithme generique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3.2. Algorithme de marquage de Ford-Fulkerson . . . . . . . . . . . . . . . . . . .

7.3.3. Une application du probleme de

ot maximal : le couplage dans un graphe biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.4. Recherche d'un

ot maximal a co^ut minimal . . . . . . . . . . . . . . . . . . . . . . . 37

7.4.1. Condition d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.4.2. Algorithmes de determination du

ot maximal a co^ut minimal . . . . . . . . 38

8. Ordonnancement et graphes 39

8.1. Methode des potentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.1.1. Calendrier au plus t^ot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.1.2. Calendrier au plus tard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40
3

Algorithmique de graphes

Chapitre 1. Introduction

La theorie des graphes et l'algorithmique qui lui est liee est un des outils privilegies de modelisation

et de resolution de problemes dans un grand nombre de domaines allant de la science fondamentale aux applications technologiques concretes. Par exemple, les graphes deterministes et/ou aleatoires

sont utilises en physique, en sciences sociales (pour representer des relations entre groupes d'indi-

vidus), en mathematique combinatoire, en informatique (structures de donnees et algorithmique). Concernant les tres nombreuses applications, on peut citer : les reseaux electriques et transport d'energie, le routage du trac dans les reseaux de telecommunications et les reseaux d'ordinateurs,

le routage de vehicules et l'organisation des tournees ou rotations, les problemes de localisation (d'en-

trep^ots, d'antennes,:::) et de placement, les problemes d'ordonnancement de t^aches et d'aectation de ressources,:::

Chapitre 2. Notions elementaires

2.1. Quelques problemes modelisables par des graphes

2.1.1. Choix d'un trajet en train

Comment faire pour aller en train le plus rapidement possible de Bordeaux a Grenoble sachant que la SNCF donne les temps de parcours suivants et que l'on suppose que toutes les correspondances sont possibles sans attente :Bordeaux!Nantes4h

Bordeaux!Marseille6h

Bordeaux!Lyon6h

Nantes!Paris-Montparnasse2h

Nantes!Lyon4h30

Paris-Montparnasse!Paris-Lyon0h30

Paris-Lyon!Grenoble3h

Marseille!Lyon1h30

Marseille!Grenoble3h

Lyon!Grenoble1h15

Ce probleme peut facilement ^etre represente par un graphe dont les ar^etes sont valuees par les durees des trajets. Il s'agit alors de determiner un plus court chemin entre Bordeaux et Grenoble.

2.1.2. Planication d'une session d'examens

8 groupes d'etudiants (numerotes de G1 a G8) doivent passer des examens dans dierents ensei-

gnements, chaque examen occupant une demi-journee :ChimieG1 et G2

ElectroniqueG3 et G4

InformatiqueG3, G5, G6 et G7

MathematiquesG1, G5, G6 et G8

PhysiqueG2, G6, G7 et G8

Algorithmique de graphes

On cherche a organiser la session d'examens la plus courte possible. On peut representer chaque enseignement par un sommet et relier par des ar^etes les sommets qui correspondent aux examens ne pouvant se derouler simultanement. Le probleme est alors de colorier tous les sommets du graphe en utilisant le moins de couleurs possible sachant que deux sommets relies par une ar^ete doivent ^etre de couleurs dierentes.

2.1.3. Ordonnancement de t^aches

La mise en exploitation d'un nouveau gisement minier demande l'execution d'un certain nombre de t^aches :CodesT^achesDureesT^aches anterieures

1Obtention d'un permis d'exploitation120-

Etablissement d'une piste de 6km1801

3Transport et installation de 2 sondeuses32

4Creation de b^atiments provisoires pour le bureau des

plans et le logement des ouvriers302

5Goudronnage de la piste602

6Adduction d'eau904

7Campagne de sondage2403 et 4

8Forage et equipement de 3 puits1805, 6 et 7

9Construction de bureaux et de logements denitifs2405, 6 et 7

10Transport et installation du materiel d'exploitation308 et 9

11Tracage et amenagement du fond3608 et 9

Cela revient a resoudre un probleme d'ordonnancement qui consiste a determiner les dates de debut

au plus t^ot et au plus tard de chaque t^ache ainsi que le temps minimum de realisation de l'ensemble.

Pour cela, on doit rechercher un plus long chemin dans un graphe, appele graphe potentiels-t^aches,

dont les sommets representent les t^aches a realiser et les arcs les contraintes d'anteriorite entre les

t^aches : un arc (i;j) represente la necessite de realiser la t^acheiavant la t^achejet l'arc (i;j) est

value par la duree d'execution dei.

2.1.4. Routage dans les reseaux de telecommunications

Le probleme de savoir s'il est possible d'acheminer un ensemble d'informations entre deux centres relies par un reseau de telecommunications revient a chercher un ot de valeur maximale dans un

graphe representant ce reseau, les sommets representant les centres et les ar^etes les liaisons entre ces

centres.

2.2. Denitions

Ungraphe orienteG= (X;U) est deni par :

Un ensem bleX=fx1;x2;:::;xngdont les elements sont appeles dessommetsou desnuds.

L'ordre du grapheGest le nombre de sommetsn.

Algorithmique de graphes

Un ensem bleU=fu1;u2;:::;umgdont les elements, appeles desarcs, sont des couples or- donnes deXX=f(x;y)jx2X;y2Xg. Pour un arcu= (x;y) avec (x;y)2X2, on dit que xest l'extremite initialeetyl'extremite terminaledeu,yestsuccesseurdexetxest predecesseurdey. On notejUj=m. Uneboucleest un arc ayant le m^eme sommet comme extremite initiale et terminale :u= (x;x) est appele une boucle,8x2X. Unp-grapheest un graphe dans lequel il n'existe jamais plus deparcs de la forme (x;y) entrex ety:p= max(x;y)2X2jfu2Uju= (x;y)gj. +(x),l'ensemble des successeursdex,8x2X, est une application multivoque deXdans une partie deXtelle que : +(x) =fy2Xj(x;y)2Ug. De m^eme, (x),l'ensemble des predecesseursdex,8x2X, est une application multivoque (reciproque) deXdans une partie deXtelle que : (x) =fy2Xj(y;x)2Ug.8x2X, (x) = +(x)S(x) estl'ensemble des voisinsdex. Un sommetxest ditisolesi (x) =fxg. Un sommetxestadjacentaYsix =2Yet x2(Y)S+(Y) ou (Y) =S(y)8y2Yet +(Y) =S+(y)8y2Y. SiGest un 1-graphe, il est parfaitement deni par l'ensembleXet l'application multivoque +ou . On peut alors le noterG= (X;+) ouG= (X;). Ledemi-degre exterieur (resp. interieur)du sommetx, noted+(x) (resp.d(x)) designe le nombre d'arcs ayantxcomme extremite initiale (resp. terminale),d+(x) =j+(x)jetd(x) = j(x)j.

SoitYXun sous-ensemble de sommets :

{!+(Y) est l'ensemble des arcs ayant leur extremite initiale dansYet leur extremite terminale dansXnY. {!(Y) est l'ensemble des arcs ayant leur extremite terminale dansYet leur extremite initiale dansXnY. {!(Y) =!+(Y)S!(Y) est appeleco-cycledu graphe.!(Y) est ditco-circuitsi!+(Y) =; ou!(Y) =;. Un grapheGest ditcompletsi pour toute paire (x;y) de sommets (avecx6=y) il existe au moins un arc (x;y) ou (y;x). Un 1-graphe est complet si et seulement si : (x;y)=2U)(y;x)2U.

Un grapheGest ditsymetriquesi (x;y)2U)(y;x)2U.

Un grapheGest ditanti-symetriquesi (x;y)2U)(y;x)=2U. Un grapheGest ditbipartisiX1SX2=X,X1TX2=;etX1T+(X1) =;(i.e. +(X1)X2), X

2T+(X2) =;(i.e. +(X2)X1).

Ungraphe non orienteG= (X;E) est deni par :

Un ensem bleX=fx1;x2;:::;xngdont les elements sont appeles dessommetsou desnuds.

L'ordre du grapheGest le nombre de sommetsn.

Un ensem bleE=fe1;e2;:::;emgdont les elements, appeles desar^etes, sont des couples non ordonnes deXX=f(x;y)jx2X;y2Xg. On notejEj=m. Unmultigrapheest un graphe non oriente pour lequel il peut exister plusieurs ar^etes entre deux sommetsxetydonnes. Un graphe non oriente est ditsimples'il est sans boucle et s'il n'existe pas plus d'une ar^ete entre toute paire de sommets. Deux arcs (ar^etes) sont dit(e)sadjacent(e)ss'ils ont au moins une extremite commune. 6

Algorithmique de graphes

Ledegredu sommetx, noted(x), est le nombre d'arcs ou d'ar^etes ayantxcomme extremite. On ad(x) =d+(x) +d(x) dans le cas d'un graphe oriente (attention :xest comptabilise deux fois en cas de boucle). Unecliqueest un graphe simple pour lequel il existe exactement une ar^ete entre toute paire de sommets. On la noteKnsinest son nombre de sommets. Lesous-grapheSG(Y) deG= (X;U) engendre par le sous-ensemble de sommetsYXest le graphe dont les sommets sont les elements deYet les arcs les elements deUayant leurs deux extremites dansY:SG(Y) = (Y;UY) avecUY=fu2Uju= (x;y);x;y2Y2g. Legraphe partielGP(V) deG= (X;U) engendre par le sous-ensemble d'arcsVUest le graphe dont les sommets sont ceux deXet les arcs ceux deV:GP(V) = (X;V). Lesous-graphe partielSGPdeG= (X;U) engendre par le sous-ensemble de sommetsYXet le sous-ensemble d'arcsVUest le graphe partielGP(V) du sous-grapheSG(Y) ou le sous-graphe SG(Y) du graphe partielGP(V) :SGP= (Y;V) avecYXetVU. Deux graphesG= (X;U) etG0= (X0;U0) sont ditsisomorphess'il existe deux bijections : g:X!X0eth:U!U0telles que8u= (x;y)2U,h(u) = (g(x);g(y))2U0.

2.3. Connexite

2.3.1. Cha^nes et chemins

Cha^nes et cyclesUnecha^nede longueurlallant du sommetxau sommetyest une suite d'ar^etes(x;y) = (u1;u2;:::;ul) tels que8i2 f1;:::;l1g,uietui+1sont adjacents. Le sommet x(resp.y) est appele l'extremite initiale (resp. terminale) de la cha^ne. Une cha^ne est diteelementairesi elle ne passe jamais deux fois par le m^eme sommet. Une cha^ne est ditesimplesi elle ne passe jamais deux fois par la m^eme ar^ete.

Remarques :

Dans un graph esimple, si un ec ha^neest elementaire,alors elle est simple. Dans le cas d'un graphe simple, une c ha^neest parfaitemen tcaract eriseepar la suite des sommets qu'elle rencontre ou par l'extremite initiale de la cha^ne et la suite d'ar^etes. Une cha^ne simple de longueurm(i.e. maximale) est unecha^ne eulerienne. Uncycleest une cha^ne dont les extremites initiale et terminale concident. Un cycle elementaire est un cycle minimal, au sens de l'inclusion, i.e. ne contenant strictement aucun cycle. Chemins et circuitsUncheminde longueurlallant du sommetxau sommetyest une suite d'arcs[x;y] = (u1;u2;:::;ul) tels que8i2 f1;:::;l1g,uietui+1sont adjacents et l'extremite terminale deuiest l'extremite initiale deui+1. Le sommetx(resp.y) est appele l'extremite initiale (resp. terminale) du chemin. Un chemin est ditelementairesi il ne passe jamais deux fois par le m^eme sommet. Un chemin est ditsimplesi il ne passe jamais deux fois par le m^eme arc.

Remarques :

Dans un graph esimple, si un c heminest elementaire,alors il est simple. Dans le cas d'un graphe simple, un c heminest parfaitemen tcaract erisepar la suite des sommets qu'il rencontre ou par l'extremite initiale du chemin et la suite d'arcs. 7

Algorithmique de graphes

Un chemin elementaire de longueurn1 (i.e. maximale) est unchemin hamiltonien. Uncircuitest un chemin dont les extremites initiale et terminale concident. Un circuit elementaire est un circuit minimal, au sens de l'inclusion, i.e. ne contenant strictement aucun circuit. Uncircuit hamiltonienest un chemin hamiltonien[xi1;xin] = (xi1;xi2;:::;xin) complete par (xin;xi1).

2.3.2. Graphes et composantes connexes et fortement connexes

Connexite simpleUn grapheGest ditconnexesi8(x;y)2X2x6=y,9(x;y). Proposition: La relationRdenie parxRy,x=you9(x;y) est une relation d'equivalence.

Preuve:

Elle est r e

exive: xRx. Elle est sym etrique: xRy)yRxcar il sut d'inverser la cha^ne. Elle est transitiv e: xRyetyRz)xRzcar il sut de concatener les deux cha^nes. Les classes d'equivalence induites surXparRconstituent une partition deXenX1;X2;:::;Xp. Le nombrepde classes d'equivalence est appele lenombre de connexitedu graphe. Un graphe est dit connexe si et seulement si son nombre de connexite est egal a 1. Les sous-graphesG1;G2;:::;Gp engendres par les sous-ensemblesX1;X2;:::;Xpsont appeles lescomposantes connexesdeG.

Chaque composante connexe est un graphe connexe.

Connexite forteUn grapheGest ditfortement connexesi8(x;y)2X2x6=y,9[x;y]. Proposition: La relationR'denie parxR'y,x=you9[x;y] et9[y;x] est une relation d'equivalence.

Preuve:

Elle est r e

exive: xR'x.

Elle est sym etrique: xR'y)yR'x.

Elle est transitiv e: xR'yetyR'z)xR'z.

Les classes d'equivalence induites surXparR'constituent une partition deXenX1;X2;:::;Xq. Le nombreqde classes d'equivalence est appele lenombre de connexite fortedu graphe. Un graphe est dit fortement connexe si et seulement si son nombre de connexite forte est egal a 1. Les sous-graphesG1;G2;:::;Gqengendres par les sous-ensemblesX1;X2;:::;Xqsont appeles les composantes fortement connexesdeG. On appelle legraphe reduit, noteGr, le graphe deni comme suit : les sommets deGrrepresentent les composantes fortement connexes et il existe un arc entre deux sommetsxetysi et seulement s'il existe au moins un arc entre un sommet deXxet un sommet deXydans le grapheG. Remarque : Un graphe reduit est necessairement sans circuit. 8

Algorithmique de graphes

Chapitre 3. Representation des graphes

3.1. Matrices d'adjacence et d'incidence

3.1.1. Matrice d'adjacence

SoitG= (X;U) un 1-graphe d'ordren, lamatrice d'adjacenceA= (aij(nn)) a coecients 0 ou 1 est denie comme suit :

âaxy= 1()(x;y)2U

âaxy= 0 sinon.

3.1.2. Matrice d'incidence sommets-arcs

SoitG= (X;U) un graphe oriente sans boucle d'ordren, lamatrice d'incidence sommets- arcsest une matriceA= (aij(nm)) a coecients entiers 0, +1 ou1 telle que chaque colonne correspond a un arc et chaque ligne a un sommet. Siu= (x;y) est un arc du grapheGalors la colonneua tous ses termes nuls sauf :

âaxu= +1

âayu=1

3.1.3. Matrice d'incidence sommets-ar^etes

SoitG= (X;U) un graphe non oriente sans boucle d'ordren, lamatrice d'incidence sommets- ar^etesest une matriceA= (aij(nm)) a coecients entiers 0 ou 1 telle que chaque colonne correspond a un arc et chaque ligne a un sommet. Siu= (x;y) est une ar^ete du grapheGalors la colonneua tous ses termes nuls sauf :

âaxu= 1

âayu= 1

3.2. Representation des graphes en machine

3.2.1.

A partir de la matrice d'adjacence

L'occupation memoire d'une matrice d'adjacence estO(n2). Dans le cas de graphes peu denses, mn2pour les graphes orientes etmn(n+ 1)=2 pour les graphes non orientes, il est plus avantageux d'ecrire uniquement que les termes non nuls de la matrice d'adjacence. Representation par liste d'adjacenceOn memorise pour chaque sommet la liste de ses predecesseurs

ou de ses successeurs en utilisant des listes cha^nees. Dans le cas oriente, cette representation revient

a decrire le graphe par son application multivoque ou +.

Remarques :

Algorithmique de graphes

Les deux representations seront dierentes si le graphe n'est pas symetrique. Le desavantage d'une telle representation est que le test d'appartenance d'un arc entrexety peut atteindreO(n) puisque l'on peut trouverO(n) sommets sur la liste des successeurs dei.

3.2.2.

A partir de la matrice d'incidence sommets-arcs ou sommets-ar^etes La matrice d'incidence permet de representer un p-graphe ou un multigraphe (sans boucle). Comme il n'existe que deux termes non nuls par colonne dans cette matrice, on a toujours inter^et a representer l'information sous une forme plus condensee. Par liste des arcsOn decrit la matrice d'incidence ligne par ligne : pour chaque sommetx2X, on decrit la liste!+(x) des arcs ayantxcomme extremite initiale (ou comme extremite dans le cas non oriente). Par liste des cocyclesOn decrit la matrice d'incidence colonne par colonne.

Chapitre 4. Parcours des graphes

De nombreux problemes fondamentaux en theorie des graphes concernent la connexite. On peut citer par exemple : ÔUn sommetyest-il accessible par un chemin a partir d'un autre sommet? ÔQuel est l'ensemble de tous les sommets accessibles par un chemin a partir d'un sommet x? ÔLe graphe est-il connexe, c'est-a-dire tous les sommets sont-ils accessibles par une cha^ne a partir d'un sommet donnex? ÔLe graphe est-il fortement connexe, c'est-a-dire existe-t-il un chemin joignant toute paire ordonnee (x;y) de sommets dans le graphe? Pour repondre a toutes ces questions, Tarjan a propose en 1972 un ensemble d'algorithmes ecaces (de complexite lineaire en fonction du nombre d'arcs ou d'ar^etes du graphe) qui sont fondes sur une methode d'exploration systhematique des sommets d'un graphe connue sous le nom de parcours en profondeur d'abord.

4.1. Parcours en profondeur d'abord : DFS (Depth First Search)

Il s'agit d'une generalisation du parcours prexe des arbres. On exploreGa partir d'un sommetx0quelconque. Au cours de l'exploration, chaque sommet peut se trouver dans l'un des deux etats suivants :

âE1: non explore;

âE2: explore.

Algorithmique de graphes

Remarque: Si un sommet est dans l'etatE2alors au moins un predecesseur de ce sommet a deja ete explore. Un sommetxexplore peut ^etre dans l'un deux etats suivants : âS1: ferme. C'est le cas quand tous les successeursydexont ete explores; âS2: ouvert. C'est le cas quand certains successeursydexn'ont pas encore ete explores; Pour chaque sommetx, on dispose d'un compteurc(x) indiquant a chaque instant le nombre de successeurs dexnon encore explores. Initialementc(x) =d+(x)8x. Un sommetxest donc ouvert tant quec(x)>0.A l'iteration courante, on part du sommet explorex(explore a partir d'un sommets). Sixest ouvert, on selectionne lec(x)ieme successeur non exploreydex(il faut alors decrementerc(x) de 1), pour passerya l'etat explore et commencer une nouvelle iteration a partir dey. Sixest ferme, il faut remonter au sommetspour commencer une nouvelle iteration a partir des. L'exploration a partir dex0se termine lorsque l'on est remonte en ce sommet et qu'il est ferme. On a donc pu atteindre tous les sommets pouvant ^etre atteints par un chemin a partir de x

0dans le graphe. Rappelons qu'un sommetxrelie par un chemin a tous les autres sommets d'un

graphe est appeleracine. Voici l'algorithme en pseudo-langage de cette exploration par un parcours en profondeur d'abord :ProcedureDFSx0(grapheG, sommetx0)k 1;Pouride1anfairec(i) d+(i)

Fin Pour;Pouride1anfairenum(i) 0

Fin Pour;num(x0) k;explore(G,x0);

FinAlgorithme 1: Parcours en profondeur d'abord a partir du sommetx0Procedureexplore(grapheG, sommetx)Tant que(c(x)>0)faireSelectionnerylec(x)ieme successeur dex;c(x) c(x)1;Si(num(y) = 0)Alorsk k+ 1num(y) kexplore(G,y)

Fin Si

Fait FinAlgorithme 2: Exploration en profondeur d'abord 11

Algorithmique de graphes

DFSx0(G,x0) permet d'explorer tous les sommets deGs'il est possible de les atteindre a partir dex0. Si ce n'est pas le cas, il reste des sommets non explores. Pour continuer l'exploration et couvrir tous les sommets deG, on choisit un sommetx1parmi les sommets non explores (tels que num(x1) = 0) et on applique DFS a partir dex1; et ainsi de suite tant qu'il existe des sommets non

explores. L'algorithme prend n lorsque tous les sommets ont ete explores.ProcedureDFS(grapheG)k 0;Pouride1anfairec(i) d+(i)

Fin Pour;Pouride1anfairenum(i) 0

Fin Pour;Pouride1anfaireSi(num(i) = 0)Alorsk k+ 1;num(i) k;explore(G,i);

Fin Si

Fin Pour

FinAlgorithme 3: Parcours en profondeur d'abord

La complexite de cet algorithme est enO(m)+O(n) car chaque arc est examine au plus une fois et chaque sommet est explore au plus une fois. Or siGest connexe,mn1 et le termeO(n) est absorbe. On obtient alors une for^et decrivant l'exporation deGpar DFS, maisegalement une caracterisation des arcs du graphe. On distingue 4 types d'arc : ÔArc d'arbre: arc ayant permis de visiter de nouveaux sommets lors de l'exploration par DFS. ÔArc avant: (x;y) est un arc avant si et seulement si (x;y) n'est pas un arc d'arbre etyest un descendant dexdans l'un des arbres de la for^et decrivant l'exploration par DFS (i.e. qu'il existe un chemin dexaydans l'un des arbres). ÔArc arriere: (x;y) est un arc arriere si et seulement si (x;y) n'est pas un arc d'arbre etxest un descendant deydans l'un des arbres de la for^et decrivant l'exploration par DFS. ÔArc croise: (x;y) est un arc croise si et seulement siyn'est un descendant dexetx n'est un descendant deydans la for^et decrivant l'exploration par DFS. 12

Algorithmique de graphes

4.2. Determination des composantes connexes

4.2.1. Cas non oriente

Pour determiner les composantes connexes d'un grapheG= (X;U) non oriente, il sut d'ap- pliquer l'algorithme de parcours du graphe en profondeur d'abord en modiant la procedure DFS en initialisant les compteursc(x) par les degresd(x) et en explorant, non pas les successeurs des sommets, mais les voisins. Chaque arbre de la for^et obtenue couvre des sommets appartenant a une m^eme composante connexe et le nombre d'arbres de la for^et est donc le nombre de connexite deG.

Ce nouvel algorithme, appele DFSno, est presente ci-dessous :ProcedureDFSno(grapheG)k 0;l 0;Pouride1anfairec(i) d(i)

Fin Pour;Pouride1anfairenum(i) 0

quotesdbs_dbs44.pdfusesText_44

[PDF] [PDF] Algorithmique de graphes - LIPN

Algorithmique de graphes

Lucas Letocart

LIPN - UMR CNRS 7030

Institut Galilee, Universite Paris 13

99 av. Jean-Baptiste Clement

93430 Villetaneuse - FRANCE

Algorithmique de graphes

Chapitre Contenu du document.

1. Introduction4

2. Notions elementaires 4

2.1. Quelques problemes modelisables par des graphes . . . . . . . . . . . . . . . . . . . .

2.1.1. Choix d'un trajet en train . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2. Planication d'une session d'examens . . . . . . . . . . . . . . . . . . . . . .

2.1.3. Ordonnancement de t^aches . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4. Routage dans les reseaux de telecommunications . . . . . . . . . . . . . . . .

2.2. Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3. Connexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1. Cha^nes et chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2. Graphes et composantes connexes et fortement connexes . . . . . . . . . . . .

3. Representation des graphes 9

3.1. Matrices d'adjacence et d'incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1. Matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.2. Matrice d'incidence sommets-arcs . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.3. Matrice d'incidence sommets-ar^etes . . . . . . . . . . . . . . . . . . . . . . . .

3.2. Representation des graphes en machine . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1.

3.2.2.

4. Parcours des graphes 10

4.1. Parcours en profondeur d'abord : DFS (Depth First Search) . . . . . . . . . . . . . .

4.2. Determination des composantes connexes . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1. Cas non oriente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2. Cas oriente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3. Determination des composantes fortement connexes . . . . . . . . . . . . . . . . . .

4.4. Tri topologique dans un graphe oriente sans circuit . . . . . . . . . . . . . . . . . . .

4.5. Fermeture transitive d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5.1. Algorithme de parcours de graphes . . . . . . . . . . . . . . . . . . . . . . . .

4.5.2. Puissances de la matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . .

4.5.3. Algorithmes par multiplications matricielles . . . . . . . . . . . . . . . . . . .

5. Problemes de meilleurs chemins 21

5.1. Plus courts chemins d'origine xee dans un graphe avec longueurs non negatives :

Algorithmique de graphes

5.2. Mise en oeuvre de l'algorithme de Dijkstra pour les graphes peu denses : algorithme

5.2.1. Presentation de la structure de donnees de tas (heap) . . . . . . . . . . . . .

5.2.2. Algorithme de Johnson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3. Plus court chemin d'origine xee dans un graphe sans circuit avec longueurs quel-

5.4. Determination de plus courts chemins d'origine xee dans un graphe avec longueurs

5.4.1. Algorithme de Ford (1956) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4.2. Algorithme de Ford-Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5. Plus courts chemins entre toutes les paires de sommets : algorithme de Floyd . . . .

6. Arbres couvrants 28

6.1. Arbre et arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2. Arbre couvrant de poids minimal d'un graphe simple . . . . . . . . . . . . . . . . . .

6.2.1. Formulation du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.2. Algorithme de Prim-Dijsktra . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.3. Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7. Flots dans les graphes 32

7.1. Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2. Proprietes fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.1. Flot maximal et coupe minimale . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.2. Graphe d'ecart et chemin augmentant . . . . . . . . . . . . . . . . . . . . . .

7.3. Recherche d'un

7.3.1. Algorithme generique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3.2. Algorithme de marquage de Ford-Fulkerson . . . . . . . . . . . . . . . . . . .

7.3.3. Une application du probleme de

7.4. Recherche d'un

7.4.1. Condition d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.4.2. Algorithmes de determination du

8. Ordonnancement et graphes 39

8.1. Methode des potentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.1.1. Calendrier au plus t^ot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.1.2. Calendrier au plus tard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Algorithmique de graphes

Chapitre 1. Introduction

Chapitre 2. Notions elementaires

2.1. Quelques problemes modelisables par des graphes

2.1.1. Choix d'un trajet en train

Bordeaux!Marseille6h

Bordeaux!Lyon6h

Nantes!Paris-Montparnasse2h