INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE

Ecole Nationale Superieure d’Electricite et de Mecanique

Elements de Theorie des Graphes

Didier Maquin

Version provisoire du 3 mai 2003

Table des matieres

Avant propos 4

1 Un bref historique de la theorie des graphes 4

2 Introduction 6

2.1 Qu’est-ce qu’un graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Graphes et applications multivoques . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Principales definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Modes de representation d’un graphe 9

3.1 Listes de succession . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Etude de la connexite 11

4.1 Chaınes et cycles, elementaires et simples . . . . . . . . . . . . . . . . . . . . . . 114.2 Chemins et circuits, elementaires et simples . . . . . . . . . . . . . . . . . . . . . 124.3 Graphes et sous-graphes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.4 Graphes et sous-graphes fortement connexes . . . . . . . . . . . . . . . . . . . . . 134.5 Cycles et nombre cyclomatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

5 Parcours euleriens et hamiltoniens 15

5.1 Chaınes et cycles euleriens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155.2 Chaınes et cycles hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

6 Methode de recherche de chemins 18

6.1 Rappel sur les operations booleennes sur les matrices . . . . . . . . . . . . . . . . 186.2 Recherche de chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.3 Le probleme du plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7 Arbres et arborescences 23

7.1 Definitions et proprietes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237.2 Arbres couvrants de poids minimum . . . . . . . . . . . . . . . . . . . . . . . . . 24

8 Reseaux, reseaux de transport et problemes de flots 26

8.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268.2 Recherche d’un flot complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278.3 Amelioration du flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288.4 Recherche d’un flot maximal : algorithme de Ford et Fulkerson . . . . . . . . . . 298.5 Exemple traite manuellement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298.6 Recherche d’un flot maximal a cout minimal . . . . . . . . . . . . . . . . . . . . . 32

9 Couplages 32

9.1 Le probleme du couplage maximal . . . . . . . . . . . . . . . . . . . . . . . . . . 339.2 Couplage maximal et flot maximal . . . . . . . . . . . . . . . . . . . . . . . . . . 359.3 Couplage de poids maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369.4 Problemes d’affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3

10 Problemes d’ordonnancement 40

10.1 Le graphe potentiels-taches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4110.2 Le graphe potentiels-etapes ou graphe PERT . . . . . . . . . . . . . . . . . . . . 4210.3 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4310.4 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Annexe A - Implementation de l’algorithme de Moore-Dijkstra 46

Annexe B - Implementation de l’algorithme de Floyd 50

Annexe C - Implementation de l’algorithme de Prim 52

References 53

4

Avant propos

”Faut t’faire un dessin ?”. La representation d’un probleme par un dessin, un plan, uneesquisse contribue souvent a sa comprehension. Le langage des graphes est construit, a l’ori-gine, sur ce principe. Nombres de methodes, de proprietes, de procedures ont ete pensees outrouvees a partir d’un schema pour etre ensuite formalisees et developpees. Chacun d’entre nousa, au moins une fois, vu ou utilise un plan de metro, une carte de lignes ferroviaires, un planelectrique, un arbre genealogique ou un organigramme d’entreprise ; ainsi, tout le monde saitplus ou moins intuitivement ce qu’est un graphe. Toutefois, entre cette notion vague ou despoints, representant des individus, des objets, des lieux ou des situations, sont relies par desfleches, il y a une longue elaboration des concepts. La premiere difficulte a laquelle on peut etreconfronte concerne la terminologie (tres abondante en theorie des graphes). Nous avons doncchoisi d’isoler les principales definitions du reste du cours en utilisant une mise en page differente.

La theorie des graphes constitue aujourd’hui un corpus de connaissances tres important.Comme son nom l’indique, ce cours ne constituera donc qu’une introduction a cette theorie. Nousle preciserons ulterieurement, le developpement de cette theorie doit beaucoup a celui des calcu-lateurs. Il nous a donc semble incontournable d’exposer quelques algorithmes de base (recherchede chemin, d’arbre, de flots, etc.). Cependant, ceci ne constitue pas le corps de cet enseignementmeme si les problemes pratiques de mise en œuvre sont importants. Nous n’evoquerons pas, parexemple, l’optimalite de telle ou telle representation d’un graphe au regard du traitement quel’on souhaite effectuer, ni la complexite (au sens nombre d’operations elementaires) des algo-rithmes. De maniere a permettre au lecteur interesse de juger des difficultes de mise en œuvredes algorithmes “litteraux”, plus clairs pour la comprehension, decrits dans le corps du texte,quelques implementations a l’aide du langage Matlab r© sont donnes en annexe. Ces fonctions nepretendent nullement a etre efficaces ou efficientes sur des donnees quelconques ; elles ne sontdonnees qu’a titre d’illustration. De meme, nous nous sommes efforces ce citer, au moment del’introduction des methodes de base, les fonctions de la boıte a outils de manipulation de graphesMetanet du logiciel Scilab c© qui leur correspondent.

1 Un bref historique de la theorie des graphes

Tout le monde s’accorde a considerer que la theorie des graphes est nee en 1736 avec lacommunication d’Euler (1707-1783) dans laquelle il proposait une solution au celebre problemedes ponts de Konigsberg (Euler, 1736). Le probleme pose etait le suivant. Deux ıles A et Dsur la riviere Pregel a Konigsberg (alors capitale de la Prusse de l’Est, aujourd’hui rebaptiseeKaliningrad) etaient reliees entre elles ainsi qu’aux rivages B et C a l’aide de sept ponts (designespar des lettres minuscules) comme le montre la figure 1.

Fig. 1 – La riviere Pregel et l’ıle de Kneiphof

5

Le probleme pose consistait, a partir d’une terre quelconque A, B, C, ou D, a traverser chacundes ponts une fois et une seule et a revenir a son point de depart (sans traverser la riviere a lanage !). Euler representa cette situation a l’aide d’un “dessin” ou les sommets representent lesterres et les aretes, les ponts comme le montre la figure 2.

A

C

B

D

Fig. 2 – Graphe associe au probleme des ponts de Konigsberg

Comme nous le montrerons ulterieurement, Euler demontra que ce probleme n’a pas de so-lution. Le probleme des ponts de Konigsberg est identique a celui consistant a tracer une figuregeometrique sans lever le crayon et sans repasser plusieurs fois sur un meme trait.

Pendant les cent annees qui suivirent, rien ne fut fait dans ce domaine de recherche. En1847, Kirchhoff (1824-1887) developpa la theorie des arbres pour l’appliquer a l’analyse de cir-cuits electriques. Dix ans plus tard, Cayley (1821-1895) decouvrit la notion d’arbre alors qu’ilessayait d’enumerer les isomeres satures des hydrocarbures de type CnH2n+2. A cette epoque,deux autres problemes d’importance pour la theorie des graphes furent egalement proposes etpartiellement resolus.

Le premier est la conjecture des quatre couleurs qui affirme que quatre couleurs suffisentpour colorier n’importe quelle carte plane telle que les “pays” ayant une frontiere communesoient de couleurs differentes. C’est sans doute Mobius (1790-1868) qui presenta le premier ceprobleme dans l’un de ses cours en 1840. Environ dix ans apres, de Morgan (1806-1871) essaya deresoudre ce probleme. Les lettres de de Morgan a ces divers collegues mathematiciens constituentles premieres references a la conjecture des quatre couleurs. Le probleme devint celebre apres sapublication, par Cayley en 1879, dans le premier volume des Proceedings of the Royal Geographic

Society. Ce probleme est reste tres longtemps sans solution. Il fallut attendre jusqu’en 1976 pourque Appel et Haken prouvent ce theoreme en reduisant le probleme a un nombre fini de situa-tions particulieres et en trouvant une solution pour chacune d’entre elles a l’aide d’un ordinateur.

Le second probleme est du a Sir Hamilton (1805-1865). En 1859, il inventa un casse-tetequ’il vendit pour 25 guinees a un fabricant de jouet de Dublin. Ce jeu consiste en un dodecaedreregulier en bois (un polyedre a 12 faces et 20 sommets), chaque face etant un pentagone reguliercomme le montre la figure 3.

Trois aretes sont donc issues de chaque sommet. Un clou est fiche sur chaque sommet marquedu nom de vingt grandes villes mondiales. Le casse-tete consiste a enrouler une ficelle passantune fois et une seule fois par chacune des villes (sommets). Bien que la solution de ce problemesoit aisee a obtenir, personne n’a encore trouve de condition necessaire et suffisante de l’existenced’un tel chemin (appele chemin Hamiltonien) dans un graphe quelconque.

Cette periode fertile fut suivie d’un demi-siecle de relative inactivite. Les annees 1920 virent

6

Fig. 3 – Un dodecaedre regulier

la resurgence de l’interet pour les graphes. L’un des pionniers de cette periode fut Konig a quil’on doit le premier ouvrage consacre entierement a la theorie des graphes (Konig, 1936). Il estsans doute a l’origine de l’utilisation du terme “graphe” pour designer ce qui etait prealablementconsidere comme un ensemble de “points et de fleches”.

A partir de 1946, la theorie des graphes a connu un developpement intense sous l’impul-sion de chercheurs motives par la resolution de problemes concrets. Parmi ceux-ci, citons demaniere privilegiee Kuhn (1955), Ford et Fulkerson (1956) et Roy (1959). Parallelement, unimportant effort de synthese a ete opere en particulier par Claude Berge. Son ouvrage “Theorie

des graphes et ses applications” publie en 1958 (Berge, 1958) marque sans doute l’avenementde l’ere moderne de la theorie des graphes par l’introduction d’une theorie des graphes unifieeet abstraite rassemblant de nombreux resultats epars dans la litterature. Depuis, cette theoriea pris sa place, en subissant de tres nombreux developpement essentiellement dus a l’appari-tion des calculateurs, au sein d’un ensemble plus vaste d’outils et de methodes generalementregroupees sous l’appellation “recherche operationnelle” ou “mathematiques discretes”.

2 Introduction

2.1 Qu’est-ce qu’un graphe ?

Definition 1On appelle graphe G = (X,A) la donnee d’un ensemble X dont les elements sontappeles sommets et d’une partie de A symetrique ( (x, y) ∈ A ⇔ (y, x) ∈ A) dontles elements sont appeles aretes.

En presence d’une arete a = (x, y) qui peut etre notee simplement xy, on dit quex et y sont les extremites de a, que a est incidente en x et en y, et que y est unsuccesseur ou voisin de x (et vice versa).

On dit qu’un graphe est sans boucle si A ne contient pas d’arete de la forme (x, x),c’est-a-dire joignant un sommet a lui-meme.

Le nombre de sommets est appele ordre du graphe.

Un graphe ne possedant pas de boucle ni d’aretes paralleles (deux aretes distinctes joignantla meme paire de sommets) est appele graphe simple ou 1-graphe. En revanche un p-graphe ougraphe generalise est un graphe pour lequel il n’existe jamais plus de p aretes de la forme (x, x).

Graphiquement, les sommets peuvent etre representes par des points et l’arete a = (x, y)par un trait reliant x a y. On notera que la disposition des points et la longueur ou la forme

7

(rectiligne ou incurvee) des traits n’a aucune importance. Seule l’incidence des differentes areteset sommets compte. A titre d’exemple, les deux graphes de la figure 4 sont identiques.

1

2

3

4

1

2 4

3

Fig. 4 – Deux representations graphiques d’un meme graphe

Dans le trace graphique d’un graphe, deux aretes peuvent sembler avoir une intersection enun point qui n’est pas un sommet. C’est le cas, par exemple, des aretes e et f du graphe dela figure 5. De telles aretes peuvent etre vues comme etant placees dans des plans differents etn’ayant donc aucun point commun.

a

b

c

d

e

f

Fig. 5 – Les aretes e et f n’ont pas de point commun

Les graphes ainsi definis sont dits “graphes non orientes”. Dans certaines situations cepen-dant, l’orientation des aretes est importante.

Definition 2On appelle graphe oriente ou digraphe G = (X,A) la donnee d’un ensemble X dontles elements sont appeles sommets et d’une partie A de X × X dont les elementssont appeles arcs ou aretes.

En presence d’un arc a = (x, y) qui peut etre note simplement xy, on dit que x estl’origine (ou extremite initiale) et y l’extremite (terminale) de a, que a est sortant enx et incident en y, et que y est un successeur de x tandis que x est un predecesseur

de y. On dit aussi que x et y sont adjacents.

2.2 Graphes et applications multivoques

L’ensemble des successeurs d’un sommet x ∈ X est note Γ(x). L’application Γ qui, a toutelement de X, fait correspondre une partie de X (un element de P(X)) est appelee une applica-

tion multivoque. L’ensemble des predecesseurs d’un sommet x ∈ X peut alors etre note Γ−1(x)

8

ou Γ−1 est l’application (multivoque) reciproque de Γ.

Si le graphe G est un 1-graphe, on constate qu’il est parfaitement determine par la donneede l’ensemble X et de l’application multivoque Γ de X → P(X). Un tel graphe peut donc aussietre note : G = (X,Γ).

2.3 Principales definitions

Les definitions qui suivent sont enoncees dans le cadre des graphes orientes. Le lecteur trans-posera aisement ces definitions (si elles ont un sens) au cas des graphes non orientes.

Definition 3On appelle degre sortant ou demi-degre exterieur d’un sommet x le nombre d’arcsde la forme a = (x, y) avec y 6= x, c’est-a-dire le nombre d’elements de Γ(x)\ {x}.On note ds(x) ce degre.

On appelle degre entrant ou demi-degre interieur d’un sommet x le nombre d’arcsde la forme a = (y, x) avec y 6= x, c’est-a-dire le nombre d’elements de Γ−1(x)\ {x}.On note de(x) ce degre.

On appelle degre de x (ou valence) la somme du degre entrant et du degre sortant.

Un sommet de degre entrant non nul et de degre sortant nul est appele puits, tandis qu’unsommet de degre entrant nul et de degre sortant non nul est appele source.

Un sommet n’ayant pas d’arcs incidents est appele sommet isole ; ces sommets ont un degrenul. Deux arcs adjacents sont dits ”en serie” si leur sommet commun est de degre egal a deux.Dans la definition d’un graphe, l’ensemble des arcs A peut etre vide ; dans ce cas, on a affairea un graphe nul. Tous les sommets d’un graphe nul sont donc des sommets isoles. En revanche,l’ensemble des sommets X ne peut etre vide sinon le graphe correspondant n’existe pas. Celasignifie donc qu’un graphe comporte au moins un sommet.

Definition 4On appelle graphe reflexif un graphe possedant une boucle sur chaque sommet.

Un graphe est symetrique si, pour tout arc a1 = (x, y) appartenant a A, l’arca2 = (y, x) appartient egalement a A.

Un graphe est antisymetrique si, pour tout arc a1 = (x, y) appartenant a A, l’arca2 = (y, x) n’appartient pas a A.

Enfin, un graphe est transitif si, quelque soit deux arcs adjacents a1 = (x, y) eta2 = (y, z) appartenant a A, alors l’arc a3 = (x, z) appartient egalement a A.

Le concept de graphe symetrique est tres proche de celui des graphes non orientes. Enfait, a tout graphe symetrique, on peut associer un graphe non oriente en substituant aux arcsa1 = (x, y) et a2 = (y, x), une arete a = (y, x).

9

Definition 5Un graphe G = (X,A) est dit complet si, pour toute paire de sommets (x, y), il existeau moins un arc de la forme (x, y) ou (y, x).

Un graphe simple complet d’ordre n est note Kn. Un sous-ensemble de sommetsC ⊂ X tel que deux sommets quelconques de C sont relies par une arete est appeleune clique.

Definition 6Soit un graphe G = (X,A) et X ′ ⊂ X. Le sous-graphe engendre par X ′ est G′ = (X ′, A′),A′ etant forme des aretes dont les deux extremites sont dans X ′.

Si l’on se donne un sous-ensemble A1 de A, le graphe partiel engendre par A1 estG1 = (X,A1).

Dans certaines situations, les sommets de G1 ayant un degre nul (sommets isoles n’ayantaucune arete incidente appartenant a A1) peuvent etre supprimes du graphe partiel.

D’apres la definition precedente, une clique d’un graphe G est donc un sous-graphe completde G.

3 Modes de representation d’un graphe

Comme nous l’avons mentionne precedemment, l’essor de la theorie des graphes est essen-tiellement du a l’avenement de puissants calculateurs. Il est donc legitime de s’interesser a lamaniere de representer les graphes au sein d’un ordinateur. Plusieurs modes de representationpeuvent etre envisages selon la nature des traitements que l’on souhaite appliquer au grapheconsidere.

3.1 Listes de succession

Un graphe peut etre represente a l’aide d’un dictionnaire ; il s’agit d’une table a simple entreeou chaque ligne correspond a un sommet et comporte la liste des successeurs ou des predecesseursde ce sommet. Considerons le graphe de la figure 6.

1

4

1

2

35 8

6

7

2

3

4

5

Fig. 6 – Un graphe elementaire

Celui-ci peut etre represente par les deux tables suivantes :

10

1 2, 3, 4, 5

2 3

3 4

4 -

5 1, 4

1 5

2 1

3 1, 2

4 1,3,5

5 1

Dans la mesure ou, pour une table donnee, le nombre de successeurs ou de predecesseurs n’estpas le meme pour chaque sommet, il est preferable de representer le dictionnaire sous forme dedeux tableaux : le premier comprenant autant d’elements que de sommets, ces elements pointant,dans un second tableau, les debuts de listes de successeurs (ou de predecesseurs). La figure 7montre cette organisation en ce qui concerne la table des successeurs.

1

0

56

7

1 42 3 4 5 3 4

Fig. 7 – Codage d’une liste de successeurs

Cette representation est un peu redondante dans le cas des graphes non orientes ; elle estcependant assez commode pour parcourir le graphe. L’encombrement de cette representation estminimal puisqu’il correspond exactement a la quantite d’information fournie par le graphe.

3.2 Matrice d’adjacence

Les outils classiques d’algebre lineaire peuvent egalement etre utilises pour coder les graphes.La premiere idee consiste a considerer chaque arc comme un lien entre deux sommets.

Definition 7Considerons un graphe G = (X,A) comportant n sommets. La matrice d’adjacence

de G est egale a la matrice U = (uij) de dimension n× n telle que

uij =

{

1 si (i, j) ∈ A (c’est-a-dire (i, j) est une arete)0 sinon

Une telle matrice, ne contenant que des ”0” et des ”1” est appelee, de manieregenerale, une matrice booleenne.

Un graphe oriente quelconque a une matrice d’adjacence quelconque, alors qu’un graphe nonoriente possede une matrice d’adjacence symetrique. L’absence de boucle se traduit par unediagonale nulle. La matrice d’adjacence du graphe de la figure 6 est la suivante :

U =

0 1 1 1 10 0 1 0 00 0 0 1 00 0 0 0 01 0 0 1 0

11

Ce mode de representation engendre des matrices tres creuses (i.e. comprenant beaucoupde zeros). Cependant la recherche de chemins ou de chaınes s’effectue aisement avec une tellerepresentation (cf § 6.2). De plus, la matrice d’adjacence possede quelques proprietes qui peuventetre exploitees. Considerons un graphe G et sa matrice d’adjacence associee U :

– la somme des elements de la ieme ligne de U est egale au degre sortant ds(xi) du sommetxi de G.

– la somme des elements de la jeme colonne de U est egale au degre entrant de(xj) du sommetxj de G.

– U est symetrique si, et seulement si, le graphe G est symetrique.

3.3 Matrice d’incidence

La seconde idee permettant une representation matricielle d’un graphe exploite la relationd’incidence entre aretes et sommets.

Definition 8Considerons un graphe oriente sans boucle G = (X,A) comportant n sommetsx1, . . . , xn et m aretes a1, . . . , am. On appelle matrice d’incidence (aux arcs) deG la matrice M = (mij) de dimension n×m telle que :

mij =

1 si xi est l’extremite initiale de aj

−1 si xi est l’extremite terminale de aj

0 si xi n’est pas une extremite de aj

Pour un graphe non oriente sans boucle, la matrice d’incidence (aux aretes) estdefinie par :

mij =

{

1 si xi est une extremite de aj

0 sinon

La matrice d’incidence du graphe de la figure 6 s’ecrit sous la forme suivante :

M =

1 0 1 0 1 1 −1 0−1 1 0 0 0 0 0 0

0 −1 −1 1 0 0 0 00 0 0 −1 −1 0 0 −10 0 0 0 0 −1 1 1

4 Etude de la connexite

4.1 Chaınes et cycles, elementaires et simples

Definition 9Une chaıne est une sequence finie et alternee de sommets et d’aretes, debutant etfinissant par des sommets, telle que chaque arete est incidente avec les sommets quil’encadre dans la sequence. Une arete ne doit pas intervenir plusieurs fois dans lasequence contrairement a un sommet.

Le premier et le dernier sommet sont appeles (sommets) extremites de la chaıne.

12

La longueur de la chaıne est egale au nombre d’aretes qui la composent.

Si aucun des sommets composant la sequence n’apparaıt plus d’une fois, la chaıneest dite chaıne elementaire.

Si aucune des aretes composant la sequence n’apparaıt plus d’une fois, la chaıne estdite chaıne simple.

Un cycle est une chaıne dont les extremites coıncident.

Un cycle elementaire (tel que l’on ne rencontre pas deux fois le meme sommet en leparcourant) est un cycle minimal pour l’inclusion, c’est-a-dire ne contenant stricte-ment aucun autre cycle.

4.2 Chemins et circuits, elementaires et simples

Toutes les definitions precedentes, s’appliquant au cas des graphes non orientes, peuvent etretransposees au cas des graphes orientes.

Definition 10Un chemin est une sequence finie et alternee de sommets et d’arcs, debutant etfinissant par des sommets, telle que chaque arc est sortant d’un sommet et incident ausommet suivant dans la sequence (cela correspond a la notion de chaıne ”orientee”).

Si aucun des sommets composant la sequence n’apparaıt plus d’une fois, le cheminest dit chemin elementaire.

Si aucune des aretes composant la sequence n’apparaıt plus d’une fois, le chemin estdit chemin simple.

Un circuit est un chemin dont les extremites coıncident.

En parcourant un circuit elementaire, on ne rencontre pas deux fois le meme sommet.

4.3 Graphes et sous-graphes connexes

De maniere intuitive, la notion de connexite est triviale. Un graphe est connexe si l’on peutatteindre n’importe quel sommet a partir d’un sommet quelconque en parcourant differentesaretes. De maniere plus formelle, on a :

Definition 11Un graphe G est connexe s’il existe au moins une chaıne entre une paire quelconquede sommets de G.

La relation :

xi R xj ⇔

{

soit xi = xj

soit il existe une chaıne joignant xi a xj

est une relation d’equivalence (reflexivite, symetrie, transitivite). Les classes d’equivalence in-duites sur X par cette relation forment une partition de X en X1, X2, . . . , Xp.

13

Le nombre p de classes d’equivalence distinctes est appele nombre de connexite du graphe.

On peut alors donner une autre definition concernant la connexite d’un graphe. Un grapheest dit connexe si et seulement si son nombre de connexite est egal a 1.

Les sous-graphes G1, G2, . . . , Gp engendres par les sous-ensembles X1, X2, . . . , Xp sont ap-peles les composantes connexes du graphe. Chaque composante connexe est un graphe connexe.

La verification de la connexite d’un graphe est un des premiers problemes de la theorie desgraphes. Nous decrirons ulterieurement des algorithmes permettant d’etablir cette connexite.

Definition 12Un point d’articulation d’un graphe est un sommet dont la suppression augmente lenombre de composantes connexes.

Un isthme est une arete dont la suppression a le meme effet.

Un ensemble d’articulation E ⊂ X d’un graphe connexe G est un ensemble desommets tel que le sous-graphe G′ deduit de G par suppression des sommets de E,ne soit plus connexe.

4.4 Graphes et sous-graphes fortement connexes

Definition 13Un graphe oriente est dit fortement connexe s’il existe un chemin joignant deux som-mets quelconques.

La relation :

xi R xj ⇔

soit xi = xj

soit il existe a la fois un chemin joignant xi a xj

et un chemin joignant xj a xi

est une relation d’equivalence et les classes d’equivalence induites sur X par cette relation formentune partition de X en X1, X2, . . . , Xq. Les sous-graphes G1, G2, . . . , Gq engendres par les sous-ensembles X1, X2, . . . , Xq sont appeles les composantes fortement connexes du graphe.

Pour le graphe de la figure 8, les differentes composantes fortement connexes sont :

C1 = {1, 2, 3, 4, 5} C2 = {6, 7} C3 = {8}

Definition 14On appelle graphe reduit Gr le quotient du graphe G par la relation de forte connexiteGr = G/R ; les sommets de Gr sont donc les composantes fortement connexes et ilexiste un arc entre Ci et Cj si et seulement s’il existe au moins un arc entre unsommet de Ci et un sommet de Cj dans le graphe G. On verifie que le graphe Gr estsans circuit.

Le graphe reduit correspondant au graphe de la figure 8 est donne figure 9. La recherchedes composantes fortement connexes et la determination du graphe reduit revetent une grandeimportance pour l’analyse structurale d’un systeme.

14

1 3 5

2

8

4 7 6

Fig. 8 – Graphe oriente

C1

C2

C3

Fig. 9 – Graphe reduit du graphe de la figure 8

4.5 Cycles et nombre cyclomatique

Les notions de cycle et de cycle elementaire ont deja ete definies au paragraphe 4.1. Pour uncycle µ donne, on designe par µ+ l’ensemble des arcs du cycle orientes dans le sens de parcourset par µ− l’ensemble des arcs orientes en sens contraire. Si le graphe possede m arcs designespar a1, . . . , am, on peut faire correspondre a tout cycle µ un vecteur µ = (µ1, µ2, . . . , µm) telque :

µi =

1 si ai ∈ µ+

−1 si ai ∈ µ−

0 si ai /∈ µ+ ∪ µ−

On remarque que −µ est aussi un vecteur associe au cycle µ (obtenu en choisissant l’autresens de parcours). Au signe pres, on pourra donc identifier le cycle µ au vecteur µ.

Definition 15On dit que p cycles µ1, µ2, . . . , µp sont dependants s’il existe, entre leurs vecteursassocies, une relation vectorielle de la forme :

λ1µ1 + λ2µ2 + . . . + λpµp = 0

avec les λi non tous nuls.

Si la satisfaction de la relation precedente implique λi = 0, ∀i = 1, . . . , p, les p cyclessont dits independants.

15

Une base de cycles est un ensemble minimal de cycles independants tel que toutvecteur representatif d’un cycle puisse s’exprimer comme combinaison lineaire descycles de la base.

On appelle nombre cyclomatique d’un graphe G, la dimension de la base de cycles.

On peut noter que le nombre cyclomatique v(G) d’un graphe a n sommets, m arcs et pcomposantes connexes est egal a v(G) = m− n + p.

5 Parcours euleriens et hamiltoniens

L’etude des problemes euleriens – ou hamiltoniens – (recherche d’une chaıne ou d’un cyclepassant exactement une fois par chaque arete – ou par chaque sommet –) remonte aux originesde la theorie des graphes.

L’interet porte aujourd’hui a ces problemes s’explique par leurs nombreuses applications :tournees de distribution, trace automatique sur ordinateur, problemes d’ordonnancement d’ate-lier, etc.

5.1 Chaınes et cycles euleriens

Il s’agit la d’une generalisation du jeu bien connu consistant a dessiner toutes les aretes d’ungraphe avec un crayon sans jamais le soulever, ni passer deux fois sur la meme arete.

Definition 16Soit G = (X,A) un graphe oriente.

Une chaıne eulerienne est une chaıne empruntant une fois et une fois seulementchaque arete de G.

Un cycle eulerien est une chaıne eulerienne dont les extremites coıncident.

Un graphe possedant un cycle eulerien est appele graphe eulerien.

Le probleme de l’existence et de la determination d’un cycle eulerien (d’une chaıne eulerienne)dans un graphe non oriente a ete pose la premiere fois et resolu par Euler en 1736 a propos ducelebre probleme des ponts de Konigsberg evoque au premier paragraphe. Euler prouva l’impos-sibilite de l’obtention d’une solution en demontrant le theoreme suivant :

Theoreme 1Un graphe non oriente connexe possede une chaıne eulerienne si et seulement si lenombre de sommets de degre impair est egal a 0 ou 2.

Il admet un cycle eulerien si et seulement si tous ses sommets ont un degre pair.

Montrons que la condition est necessaire. Si le cycle eulerien existe, on peut l’orienter demaniere arbitraire. En chaque sommet, le nombre d’arcs incidents doit etre egal au nombred’arcs sortants, les sommets doivent donc etre de degre pair. Dans le cas d’une chaıne, les deuxextremites font exception ; on part ou l’on arrive une fois de plus, d’ou un degre impair pour ces

16

deux sommets extremites.

Montrons maintenant que la condition est suffisante. Raisonnons par recurrence en supposantque le theoreme est verifie pour des graphes connexes ayant moins de m aretes. Soit G = (X,A)un graphe de m aretes verifiant la condition du theoreme. Si G possede deux sommets de degreimpair, soient a et b ces sommets (si tous les sommets de G sont de degre pair, on choisit a quel-conque et b confondu avec a). Soit L la chaıne parcourue par un “voyageur” partant de a dansune direction quelconque et seulement soumis a l’interdiction d’emprunter deux fois la memearete. Si, a un instant donne, il arrive en un sommet x 6= b, il aura utilise un nombre impaird’aretes incidentes a x et il pourra donc repartir par une arete non deja utilisee. Quand il nepeut plus bouger, c’est donc qu’il est en b. Si toutes les aretes ont ete utilisees, L est une chaıneeulerienne et le theoreme est vrai. Dans le cas contraire, le graphe partiel, defini par les aretesnon utilisees, a tous ses sommets de degre pair (de part la nature des suppressions effectuees).Soient G′

1, G′2, ..., G′

p les composantes connexes de G qui comportent au moins une arete. Chacundes sous graphes G′

i possede moins de m aretes et d’apres l’hypothese de recurrence, il admetun cycle eulerien µi. Comme G est connexe, L rencontre successivement G′

1, G′2, ..., G′

p en lessommets x1, x2, . . . , xp. Le parcours alors constitue par :

– la chaıne L entre a et x1,– le cycle µ1 entre x1 et x1,– la chaıne L entre x1 et x2,– le cycle µ2 entre x2 et x2,– ...– la chaıne L entre xp et b.

constitue bien une chaıne eulerienne entre a et b dans G. Le theoreme est donc vrai a l’ordre m.Comme il est vrai a l’ordre 1, il est demontre pour tout m.

Le probleme d’Euler peut aussi etre considere avec des “sens uniques”.

Definition 17Un chemin dans un graphe oriente est dit eulerien s’il passe exactement une fois parchaque arete.

Un graphe oriente est dit eulerien s’il admet un circuit eulerien.

La demonstration precedente peut aisement etre adaptee a cette nouvelle situation.

Theoreme 2Un graphe oriente connexe admet un chemin eulerien (mais pas de circuit eulerien)si, et seulement si, pour tout sommet sauf deux (a et b), le degre entrant est egal audegre sortant et

de(a) = ds(a)− 1 et de(b) = ds(b) + 1

Un graphe oriente connexe admet un circuit eulerien si, et seulement si, pour toutsommet, le degre entrant est egal au degre sortant.

Parmi les problemes “prototypes” classiques des formulations precedentes, citons le problemedu “postier chinois” (non oriente) qui consiste a parcourir les rues d’une ville en passant au moins

17

une fois dans chaque rue, le graphe n’etant pas necessairement eulerien ; on cherche bien sur aminimiser la longueur totale du parcours.

On rencontre ce genre de probleme dans les organisations de tournees de distribution decourrier, de ramassage d’ordures, d’inspection de reseaux de distribution. Dans le cas orienteou chaque arc doit etre emprunte dans un sens privilegie, le probleme se ramene a la recherched’un flot a cout minimum (cf. § 8.4).

Il s’agit d’abord de savoir si le “parcours chinois” a au moins une solution. Nous enonconsici sans demonstration les resultats suivants.

Theoreme 3Un graphe non oriente admet un cycle chinois si, et seulement si, il est connexe.

Un graphe oriente admet un circuit chinois si, et seulement si, il est fortementconnexe.

La resolution du probleme du postier chinois peut s’inspirer des methodes de recherche dechaınes ou cycles euleriens. Cependant, on preferera formuler le probleme en termes de couplage

parfait de poids minimum (cf. § 9.3)

5.2 Chaınes et cycles hamiltoniens

Soit G = (X,A) un graphe connexe d’ordre n.

Definition 18On appelle chemin hamiltonien (chaıne hamiltonienne) un chemin (une chaıne) pas-sant une fois, et une fois seulement, par chacun des sommets de G.

Un chemin hamiltonien (une chaıne hamiltonienne) est donc un chemin (une chaıne)elementaire de longueur n− 1.

Un circuit hamiltonien (un cycle hamiltonien) est un circuit (un cycle) qui passe unefois, et une seule fois, par chacun des sommets de G.

On dit qu’un graphe G est hamiltonien s’il contient un cycle hamiltonien (cas nonoriente) ou un circuit hamiltonien (cas oriente).

La notion de cycle hamiltonien trouve son origine dans le jeu invente par Hamilton que nousavons evoque au premier paragraphe. De nombreux problemes concrets peuvent etre formulesen termes de recherche de parcours hamiltoniens.

On peut en particulier citer le probleme du voyageur de commerce. Un representant de com-merce doit rendre visite a n clients x1, x2, . . . , xn en partant d’une ville x0 et revenir a sonpoint de depart. Il connaıt les distances d0j qui separent le depot x0 de chacun de ses clients xj ,ainsi que la distance dij entre deux clients quelconques xi et xj .

Dans quel ordre doit-il rendre visiste a ses clients pour que la distance totale parcourue soitminimale ? Ce probleme revient a chercher un cycle hamiltonien de longueur totale minimaledans le graphe complet G construit sur l’ensemble des sommets X = {x0, x1, . . . , xn}, les

18

aretes etant munies des longueurs dij .

Lorsque le point d’arrivee est different du point de depart, le probleme revient a rechercherune chaıne hamiltonienne de longueur totale minimale.

Un autre probleme classique concerne l’ordonancement de taches. On cherche un ordre danslequel on peut effectuer n taches donnees (deux taches quelconques ne pouvant etre effectuees si-multanement) tout en respectant un certain nombre de contraintes d’anteriorite. Si l’on construitle graphe G dont l’ensemble des sommets correspond a l’ensemble des taches, et ou il existe unarc (i, j) si la tache i peut etre effectuee avant la tache j, le probleme revient a determiner unchemin hamiltonien de G.

D’autres problemes concrets peuvent se ramener egalement a la problematique precedente.On appelle cycle (circuit) prehamiltonien d’un graphe G, un cycle (un circuit) passant au moinsune fois par chaque sommet de G. Un graphe G qui admet un tel cycle (ou circuit) est appelegraphe prehamiltonien et une condition necessaire et suffisante pour qu’il en soit ainsi est queG soit connexe (fortement connexe).

La recherche d’un cycle (circuit) prehamiltonien de longueur minimale dans un graphe Gou les aretes (arcs) ont des longueurs donnees se ramene a un probleme de recherche de cycle(circuit) hamiltonien dans le graphe complet G′ construit sur le meme ensemble de sommets, lalongueur d’une arete (arc) (i, j) de G′ etant egale a la longueur de la plus courte chaıne (chemin)entre i et j.

De nombreux problemes du type “voyageur de commerce” sont en realite des problemesprehamiltoniens et, pour les resoudre, on commencera par calculer la matrice des plus courtschemins (des plus courtes chaınes).

Notons que l’on ne connaıt pas de condition necessaire et suffisante d’existence de cycles oude circuits hamiltoniens.

6 Methode de recherche de chemins

6.1 Rappel sur les operations booleennes sur les matrices

Rappelons brievement les deux operations d’addition et de multiplication booleenne notees⊕ et ⊗. Les variables A et B sont booleennes et prennent donc leur valeur dans {0, 1}

A B A⊕B A⊗B

0 0 0 00 1 1 01 0 1 01 1 1 1

Avant de proceder a la recherche systematique de chemins, examinons, de facon generale, lasignification des operations sur les matrices d’adjacence en termes de graphes.

19

Addition booleenne des matrices

Soient deux graphes G1 et G2, possedant les memes sommets, et leurs matrices d’adjacenceassociees U1 et U2 de dimension n× n. Calculons U3 = U1 ⊕ U2 telle que :

(U3)ij = (U1)ij ⊕ (U2)ij

Chaque element non nul de U3 represente, par definition, un arc de G3 decrit par la matriceU3. Pour qu’un element de U3 soit non nul, il faut que l’un au moins des elements correspondantsde U1 ou U2 soit non nul. On conclut donc que cette operation revient a construire un grapheG3 comportant a la fois les arcs de G1 et ceux de G2.

Multiplication booleenne des matrices

Considerons de nouveau les deux graphes G1 et G2 precedents et calculons U4 = U1 ⊗ U2

telle que :(U4)ij = (U1)i1 ⊗ (U2)1j ⊕ (U1)i2 ⊗ (U2)2j ⊕ . . . (U1)in ⊗ (U2)nj

Pour que (U4)ij soit egal a 1, il faut qu’il existe au moins un indice k tel que simultanementles elements (U1)ik et (U2)kj soit egaux a 1.

Cela revient a construire un graphe G4 dans lequel un arc (i, j) existe si et seulement s’ilexiste un sommet k tel que (i, k) soit un arc de G1 et (k, j) un arc de G2.

6.2 Recherche de chemins

Soit U la matrice d’adjacence associee au graphe G. Par definition, Uij = 1 indique l’exis-tence d’un chemin de longueur 1 entre les sommets i et j. Multiplions U par elle-meme, soitU2 = U ⊗ U et considerons le graphe G′ associe a U 2. Chaque arc (i, j) de G′ exprime l’exis-tence d’un chemin de longueur 2 du sommet i au sommet j. En effet, d’apres l’interpretationprecedente, (i, j) existe si et seulement s’il existe un sommet k tel que (i, k) et (k, j) sont desarcs de G.

Demontrons par recurrence que, plus generalement, U p donne l’existence des chemins de lon-gueur p. Soit un graphe possedant n sommets et U sa matrice d’adjacence associee. Admettonsla propriete pour p− 1 et demontrons la pour p.

Un chemin de longueur p entre les sommets i et j peut se decomposer en un chemin delongueur p−1 entre les sommets i et k auquel on ajoute l’arc (k, j). L’existence du chemin entreles sommets i et k est donnee, par hypothese, par l’element (U p−1)ik, celle de l’arc (k, j) par Ukj.

L’existence d’un chemin joignant les sommets i et j et passant par le sommet k est doncdonnee par (U p−1)ik ⊗Ukj. Or, le sommet k est quelconque et peut etre l’un des n sommets dugraphe. L’existence d’un chemin entre les sommets i et j s’ecrit donc :

Cij =(

Up−1)

i1⊗ U1j ⊕

(

Up−1)

i2⊗ U2j ⊕ . . .

(

Up−1)

in⊗ Unj

L’expression de Cij est, par definition, celle donnee pour calculer l’element (U p)ij . Commenous l’avons verifiee pour p = 2, la propriete est vraie quel que soit p.

Remarquons que pour un graphe a n sommets, un chemin elementaire comprend au plusn − 1 arcs. Il suffit donc, pour avoir l’existence de tous les chemins, d’elever successivementla matrice U jusqu’a la puissance n. De plus, si deux matrices successives ainsi calculees sontidentiques, il est inutile de poursuivre le calcul jusqu’a la puissance n.

20

6.3 Le probleme du plus court chemin

Le probleme de la recherche du plus court chemin dans un graphe se rencontre dans denombreuses applications. On peut citer entre autres :

– les problemes de tournees,– certains problemes d’investissement et de gestion de stocks,– les problemes de programmation dynamique a etats discrets et temps discret,– les problemes d’optimisation de reseaux (routiers, telecommunications),– certaines methodes de traitement numerique du signal, de codage et de decodage de l’in-

formation,– les problemes de labyrinthe et de recreations mathematiques.

Le probleme considere se formule ainsi. Etant donne un graphe oriente G = (X,A), on asso-cie a chaque arc a ∈ A un nombre l(a) ∈ R appele “longueur” de l’arc. On dit alors que G estvalue par les longueurs l(a). Si a = (i, j), on utilisera egalement la notation lij pour la longueurde l’arc a.

Le probleme du plus court chemin entre deux sommets i et j sera de trouver un cheminµ(i, j) de i et j dont la longueur totale l(µ) =

∑

a∈µ(i,j) l(a) soit minimum.

Ce probleme a de nombreuses applications pratiques car la “longueur” l(a) peut s’interpreteraussi bien comme un cout de transport sur l’arc a, comme les depenses de construction de l’arca, comme le temps necessaire pour parcourir l’arc a, etc.

Selon les proprietes du graphe traite (les longueurs sont quelconques, positives ou toutesegales, le graphe est quelconque ou sans circuit) et selon le probleme considere (recherche duplus court chemin d’un sommet a un autre, ou d’un sommet a tous les autres, ou entre tousles couples de sommets) il existe de nombreux algorithmes permettant l’obtention d’une solution.

Nous nous contenterons simplement ici de decrire les algorithmes les plus classiques, sansexplorer toutes les situations.

Dans beaucoup de situations, les longueurs sont positives. On utilisera alors l’algorithmede Moore-Dijkstra pour calculer le plus court chemin d’un sommet (arbitrairement le sommetnumero 1) a tous les autres.

Posons X = {1, 2, . . . , n}. Soit lij la longueur de l’arc (i, j) si (i, j) ∈ A. Definissons π∗(i)comme la longueur minimum des chemins du sommet 1 au sommet i ; en particulier π∗(1) = 0.

L’algorithme procede en n− 1 iterations. Au debut de chacune des iterations, l’ensemble dessommets est partitionne en deux sous-ensembles S et S = X\S. Le sous-ensemble S (initialisea {1}) contient les sommets definitivement marques, c’est-a-dire les sommets pour lesquels lamarque π(i) represente effectivement la longueur du plus court chemin entre le sommet 1 et lesommet i. Le complementaire S contient tous les sommets ayant une marque provisoire definiepar :

∀k ∈ S : π(k) = mini∈S∩Γ−1

k

(π(i) + lik)

On demontre alors aisement qu’a une etape quelconque si j est le sommet de marque provi-soire π(j) minimale c’est-a-dire :

π(j) = mink∈S

(π(k))

21

alors π(j) = π∗(j), c’est-a-dire que le sommet j peut etre inclus dans l’ensemble S des sommetsdefinitivement marques (et, bien sur, enleve de S).

On mettra donc a jour l’ensemble S en incluant j (S ← S∪{j}) ainsi que les marques provi-soires des sommets k de S relies par un arc (j, k). Ceci se fera en considerant successivement tousles sommets k ∈ Γ(j)∩ S et en remplacant π(k) par π(j)+ ljk chaque fois que π(j)+ ljk < π(k).Si l’on souhaite determiner explicitement le plus court chemin, et non pas seulement sa longueur,on conservera, dans un tableau de predecesseurs, l’information selon laquelle le predecesseur dek est j.

Algorithme 1 (Moore-Dijkstra)Recherche du plus court chemin entre deux sommets dans un graphe a longueurs positives.

(a) - Initialisations

S = {2, 3, . . . , n}

π(1) = 0

π(i) =

{

l1i si i ∈ Γ(1)+∞ sinon

(b) - Selectionner j tel que

π(j) = mink∈S

(π(k))

Faire S ← S\{j}

Si S = ∅ alors FIN

(c) - Faire pour tout i ∈ S ∩ Γ(j)

π(i)← min (π(i), π(j) + lji)

Retourner en (b)

On trouvera en annexe A, un programme Matlab r© implementant cet algorithme. SousScilab c©, la commande relative a la recherche du plus court chemin entre deux sommets senomme shortest path.

Considerons, a titre d’exemple, le graphe de la figure 10. Les iterations de l’algorithmeprecedent sont les suivantes :

(a) S = {2, 3, 4, 5, 6}, π(1) = 0, π(2) = 7, π(3) = 1, π(4) = π(5) = π(6) =∞(b) j = 3, S = {2, 4, 5, 6}(c) S ∩ Γ(3) = {2, 5, 6}, π(2) = min(7, 1 + 5) = 6, π(5) = min(∞, 1 + 2) = 3,

π(6) = min(∞, 1 + 7) = 8(b) j = 5, S = {2, 4, 6}(c) S ∩ Γ(5) = {2, 4}, π(2) = min(6, 3 + 2) = 5, π(5) = min(∞, 3 + 5) = 8(b) j = 2, S = {4, 6}(c) S ∩ Γ(2) = {4, 6}, π(4) = min(8, 5 + 4) = 8, π(6) = min(8, 5 + 1) = 6(b) j = 6, S = {4}(c) S ∩ Γ(2) = ∅(b) j = 4, S = ∅

22

3

4

6

52

1

7

4 5

1

25

1

3

7

2

Fig. 10 – Graphe oriente

Les longueurs des plus courts chemins seront donc :

π(1) = 0, π(2) = 5, π(3) = 1, π(4) = 8, π(5) = 3 et π(6) = 6

On peut egalement s’interesser a la determination des plus courts chemins entre toutes lespaires de sommets (on se place toujours dans la situation ou les longueurs sont toutes positives).On peut, bien sur, utiliser l’algorithme precedent, mais son efficacite est faible devant ce typede probleme. On preferera un algorithme se rattachant aux methodes matricielles. L’algorithmede Floyd que nous allons presenter est particulierement simple dans sa mise en œuvre.

Notons L = (lij) la matrice n× n dont le terme (i, j) est egal a la longueur de l’arc (i, j) si(i, j) ∈ A et +∞ sinon (pour les termes diagonaux, on pose lii = 0).

Pour 1 ≤ k ≤ n, notons L(k) = (l(k)ij ) la matrice dont le terme (i, j) represente la longueur

minimale d’un chemin d’origine i et d’extremite j, et astreint a la condition que tous les sommetsintermediaires appartiennent au sous-ensemble {1, 2, . . . , k}.

Pour k = 0, on a L(0) = L, puisque lij est la longueur du chemin direct (unique) entre i et j(sans sommet intermediaire). On remarque alors que les matrices L(k) sont liees par la relationde recurrence :

l(k)ij = min

(

l(k−1)ij , l

(k−1)ik + l

(k−1)kj

)

En effet, deux situations peuvent se produire suivant que le plus court chemin de i a j asommets intermediaires dans {1, 2, . . . , k} emprunte le sommet k ou non.

Dans le premier cas, ce chemin est forme d’un sous-chemin entre i et k, suivi d’un sous-cheminentre k et j, chacun ne pouvant utiliser comme sommets intermediaires que des sommets de

{1, 2, . . . , k − 1} et devant etre de longueur minimale. On doit donc avoir l(k)ij = l

(k−1)ik + l

(k−1)kj .

Dans le second cas, on doit evidemment avoir l(k)ij = l

(k−1)ij .

La matrice L(n), donnant l’ensemble des valeurs des plus courts chemins dans le graphe,pourra donc etre determinee en n etapes de recurrence a partir de la relation precedente.

23

Algorithme 2 (Floyd)Recherche de la matrice des plus courts chemins dans un graphe a longueurs positives.

Pour k de 1 a nPour tout i et j de 1 a n faire

lij = min (lij , lik + lkj)

Comme pour l’algorithme precedent, si l’on souhaite, en plus de la longueur des chemins,exhiber explicitement le chemin, on mettra a jour, au fur et a mesure de l’introduction d’unnouveau sommet k, une matrice de predecesseurs.

Un programme Matlab r© implementant cet algorithme est donne en annexe B.

7 Arbres et arborescences

7.1 Definitions et proprietes

Definition 19Un arbre est un graphe connexe sans cycles.

Un graphe sans cycle qui n’est pas connexe est appele une foret (chaque composanteconnexe est un arbre).

Par definition meme, un arbre est donc un graphe simple. On constate egalement queT = (X,T ) est un arbre si et seulement s’il existe une chaıne et une seule entre deux som-mets quelconques.

Etant donne un graphe quelconque G = (X,A) un arbre de G est un graphe partiel connexeet sans cycles. Si ce graphe partiel inclut tous les sommets du graphe G, l’arbre est appelearbre maximum ou arbre couvrant. Une foret de G est un graphe partiel sans cycle de G (nonnecessairement connexe). Une foret maximale de G est une foret de G maximale pour l’inclusion(l’ajout d’une seule arete supplementaire du graphe a cette foret cree un cycle).

Considerons un graphe G = (X,A) comportant n sommets, m arcs et p composantesconnexes ; l’algorithme suivant permet de construire une foret maximale de G.

Initialement, tous les arcs du graphe sont “incolores”. La methode consiste a examiner suc-cessivement tous les arcs du graphe (dans n’importe quel ordre) et a les colorer soit en “rouge”soit en “vert”.

A une etape quelconque, Gc est le graphe partiel engendre par les arcs colores (rouges ouverts) et Gr le graphe partiel engendre par les arcs rouges.

Chaque fois qu’un nouvel arc a incolore est examine :

– soit il passe par a un cycle elementaire µ dont tous les arcs (autres que a) sont rouges ; oncolore alors l’arc en vert, le nombre de connexite de Gc et de Gr reste constant,

– soit un tel cycle n’existe pas, auquel cas l’arc a permet de connecter deux sommets quin’etaient pas encore connectes dans Gc ; on colore l’arc a en rouge, le nombre de connexitede Gc et de Gr decroıt de 1.

24

Pour montrer que le graphe partiel Gr obtenu est bien une foret maximale de G, il suffitd’observer qu’a tout instant, le graphe Gr est sans cycle (c’est donc bien une foret de G) ; a la finde la procedure, elle est bien maximale pour l’inclusion car, en ajoutant un arc vert quelconquea Gr, on cree un cycle.

On peut egalement facilement demontrer les proprietes suivantes :

Si G possede n sommets et p composantes connexes, une foret maximale de G comporteexactement n− p arcs.

Soit T = (X,T ) une foret maximale de G = (X,A). Alors T et G ont le meme nombre deconnexite.

Soit T = (X,T ) une foret maximale de G = (X,A). Alors, par tout arc a ∈ T = A − T , ilpasse un cycle et un seul µa dont tous les arcs (autres que a) appartiennent a T .

Cette derniere propriete est importante car elle permet de construire une base de cycles d’ungraphe G (voir § 4.5).

Soit un graphe G = (X,A) comportant n sommets, m arcs et p composantes connexes. SoitT = (X,T ) une foret maximale de G = (X,A) et pour a ∈ T = A − T , notons µa le cycle(unique) contenu dans T + {a}. Les cycles {µa} forment une base de cycles du graphe G, dontla dimension est le nombre cyclomatique de G.

La notion d’arborescense est l’adaptation de la structure d’arbre aux 1-graphes orientes.

Definition 20Un graphe G est une arborescence s’il existe un sommet R appele racine de G telque, pour tout sommet S de G, il existe un chemin et un seul de R vers S.

La notion d’arborescence couvrante se definit comme celle d’arbre couvrant, mais elle estplus delicate car il faut trouver une racine (qui n’existe pas toujours).

7.2 Arbres couvrants de poids minimum

Considerons le probleme qui consiste a relier n villes par un reseau cable de la maniere la pluseconomique possible. On suppose connue la longueur lij = l(aij) la longueur de cable necessairepour relier les villes i et j. Le reseau doit evidemment etre connexe et il ne doit pas admettre decycles pour etre de cout minimal ; c’est donc un arbre et ce doit etre l’arbre maximum le pluseconomique.

Le probleme a resoudre se pose donc dans les termes suivants :

Definition 21Soit un graphe non oriente G, connexe, pondere par une fonction positive l attacheeaux aretes. Soit un arbre couvrant T = (X,B) defini comme graphe partiel de Gavec un ensemble d’aretes B. Son poids (ou cout) total est :

25

l(T ) =∑

a∈B

l(a)

On dit que T est un arbre couvrant de poids minimal de G si l(T ) est minimal parmiles poids de tous les arbres couvrants possibles de G.

On peut montrer que si toutes les aretes sont de “poids” differents, l’arbre couvrant de poidsminimal est unique. Plusieurs algorithmes ont ete proposes pour resoudre ce probleme. Les plussimples sont les algorithmes de Prim et de Kruskal.

L’algorithme de Prim consiste a batir progressivement un arbre a partir d’un sommet quel-conque (arbitrairement le sommet numero 1) et en y greffant, a chaque etape, l’arete de poidsminimal parmi celles qui permettent de maintenir un graphe partiel qui soit un arbre. Si legraphe est connexe, le processus s’arrete avec un arbre couvrant. Sinon, il aboutit a un arbrecouvrant pour une composante connexe ; on poursuit avec les autres composantes connexes pourobtenir une foret couvrante.

Plus precisement, on construit progressivement, a partir du sommet numero 1, un sous-ensemble de sommet S ⊂ X contenant {1} et un sous-ensemble T ⊂ A tel que le graphe partiel(S, T ) soit un arbre de poids minimal du sous-graphe engendre par S. Pour cela, a chaque etape,on selectionne dans le cocycle :

ω(S) = {(k, l) | (k, l) ∈ A, k ∈ S, l ∈ X\S}

l’arete de poids minimal, soit a = (i, j). Les sous-ensembles S et T sont alors augmentes en leurajoutant le sommet j et l’arete a respectivement : S ← S ∪ {j}, T ← T ∪ {a}.

La mise en œuvre de cet algorithme peut se faire aisement a l’aide d’une procedure de mar-quage de la facon suivante. On associe, a chaque sommet i, un nombre reel π(i) appele marque dusommet i. A une etape quelconque, la marque π(i) d’un sommet i ∈ X\S represente le poids del’arete de poids minimal dans l’ensemble des aretes joignant i a S. D’autre part, on conserve dansun tableau α l’indice α(i) de l’arete ayant permis d’attribuer au sommet i, la marque π(i). Cesinformations permettent aisement d’obtenir, a l’etape courante, l’arete de poids minimal dans lecocycle ω(S) : il suffit en effet de determiner le sommet i ∈ X\S ayant une marque minimale etl’arete cherchee est α(i). Par ailleurs, lorsque le sous-ensemble S est augmente du sommet i, lesmarques sont mises a jour en examinant toutes les aretes issues de i et dont l’autre extremite j nefait pas encore partie de l’arbre (j ∈ X\S) et en effectuant la substitution π(j)← min(π(j), lij).Chaque fois qu’une marque est amelioree, le tableau α est mis a jour. Si le graphe est connexe,l’algorithme s’arrete lorsque S = X (tous les sommets ont ete integres a l’arbre). Les elements dutableau α representent alors les indices des aretes constituant l’arbre couvrant de poids minimal.

Algorithme 3 (Prim)Recherche d’un arbre couvrant de poids minimal.

(a) - Initialisations

π(1) = 0

π(i) =∞, ∀i ∈ {2, 3, . . . , n}

α(i) =∞, ∀i ∈ {1, 2, . . . , n}

S = ∅

26

(b) - Selectionner i tel que π(i) = minj∈X\S

(π(j))

Si π(i) =∞ ou S = X alors FIN

S ← S ∪ {i}

(c) - Pour toutes les aretes a = (i, j) telles que j ∈ X\S faire

Si lij < π(j) alors π(j) = lij , α(j) = a

Retourner en (b)

L’annexe C presente une implementation Matlab r© de cet algorithme et les resultats obtenussur un exemple.

Le probleme de l’optimisation du choix d’une arborescence couvrante est plus difficile quepour les arbres couvrants parce qu’il faut verifier que le sommet choisi au depart est bien racinede l’arbre. Plusieurs algorithmes ont ete developpes pour resoudre ce probleme ; nous ne lesdecrirons pas ici.

8 Reseaux, reseaux de transport et problemes de flots

8.1 Definitions

Definition 22Un graphe fortement connexe, sans boucle et ayant plus d’un sommet, est appele unreseau.

On appelle nœud d’un reseau un sommet qui a plus de deux arcs incidents. Les autressommets sont appeles antinœuds.

On appelle branche tout chemin pour lequel seuls les premiers et derniers sommetssont des nœuds.

Dans un graphe oriente G, un flot est l’affectation d’une valeur reelle a chaque arc de G,representant une quantite transportee sur cet arc, de telle sorte que, en chaque sommet, lasomme des flots entrants soit egale a la somme des flots sortants (loi de Kirchhoff : conservationdes flux en chaque sommet).

Parmi les problemes les plus classiques, on peut citer celui de la recherche d’un flot maxi-mal. On se donne une capacite maximale sur chaque arc qui sera une borne superieure du flotautorise sur cet arc. Le probleme du flot maximal consiste a determiner un flot dont la valeuren un certain lieu est maximale. On peut, de plus, se donner un cout de transport d’une unitede flot sur chaque arc et chercher le flot maximal de cout minimal.

Definition 23On appelle reseau de transport un graphe oriente antisymetrique value G = (X,A,C),sans boucle et dans lequel il existe :

– un sommet x1 sans predecesseur (c’est-a-dire Γ−1(x1) = ∅) nomme entree ousource du reseau,

– un sommet xn sans successeur (c’est-a-dire Γ(xn) = ∅) nomme sortie ou puits dureseau,

27

et tel qu’au moins un chemin unisse x1 a xn dans G.

La fonction de ponderation C est supposee positive et l’on nomme capacite de l’arca le nombre C(a).

Definition 24Si l’on designe par A−

x l’ensemble des arcs sortants du sommet x et A+x l’ensemble

des arcs entrants de ce meme sommet x, on dit qu’une fonction ϕ(a) definie sur Aet a valeurs reelles est un flot pour le reseau de transport si :

– il est positif : ϕ(a) > 0, ∀a ∈ A,

– il verifie la loi des nœuds de Kirchhoff :

∑

a∈A−

x

ϕ(a)−∑

a∈A+x

ϕ(a) = 0, ∀x 6= x1 et x 6= xn

– il ne depasse pas la capacite des arcs : ϕ(a) ≤ C(a), ∀a ∈ A.

Si x n’est ni x1 ni xn, la quantite entrante en x doit etre egale a la quantite sortante quenous designons par ϕx :

ϕx =∑

a∈A−

x

ϕ(a) =∑

a∈A+x

ϕ(a)

Si ϕ est un flot sur un reseau de transport G, alors on a ϕx1= ϕxn ; cette quantite s’appelle

la valeur du flot.

La principale question qui se pose pour un reseau de transport donne est de determiner unflot de valeur maximale ainsi que les flots le long de chaque arc. Il arrive frequemment egalementque l’on doive considerer des reseaux avec des capacites localisees non seulement sur les aretesmais egalement sur les sommets. C’est notamment le cas pour les reseaux telephoniques pour les-quels la limite de capacite est autant due aux lignes qu’aux centraux. On peut ramener aisementce probleme au precedent ; il suffit de dedoubler chaque sommet en une entree et une sortie lieespar un arc ayant pour capacite celle qu’on attribuait precedemment au sommet.

Dans ce qui suit, les valeurs des flots et des capacites sont considerees comme entieres. Sil’on ne peut pas se ramener directement a cette situation, on approche les valeurs reelles pardes rationnels, on reduit ces nombres au meme denominateur commun d et l’on choisit commeunite de reference 1/d.

8.2 Recherche d’un flot complet

Definition 25Pour un flot ϕ dans un reseau de transport G = (X,A,C), on dit qu’un arc estsature si on a ϕ(a) = C(a).

Le flot est dit complet si tout chemin allant de x1 a xn contient au moins un arc sature.

Si l’on considere le graphe partiel engendre par les arcs non satures par le flot et si le flot n’estpas complet, il existe necessairement un chemin µ allant de l’entree a la sortie. On peut alorsdefinir un nouveau flot pour le reseau en augmentant de 1 le flot de chacun des arcs constituant lechemin µ ; la valeur du flot est alors egalement augmentee de 1. On peut donc progressivement

28

augmenter la valeur d’un flot incomplet jusqu’a ce qu’il soit complet. En tenant compte desdifferences entre les capacites et la valeur du flot sur les arcs de µ, on peut connaıtre d’avancel’augmentation possible du flot. Cependant, le flot complet ainsi obtenu n’est pas, en general, leflot maximal.

8.3 Amelioration du flot

Soit ϕ un flot complet. On va utiliser une procedure iterative pour identifier et marquer tousles sommets du graphe ou il est possible de faire transiter une unite de flot supplementaire.

On definit un processus d’etiquetage de certains sommets du graphe. En x1, on place uneetiquette + . Soit x un sommet deja marque :

– on marque avec une etiquette +x tout successeur y non marque de x pour lequel le flotn’est pas a son maximum ((x, y) ∈ A et ϕ(x, y) < C(x, y)).

– on marque avec une etiquette −x tout predecesseur y non marque de x pour lequel leflot n’est pas nul ((x, y) ∈ A et ϕ(y, x) > 0).

L’etiquette a pour role de donner le nom d’un predecesseur ou d’un successeur d’un sommetdonne en indiquant si le flot peut etre augmente dans le sens de parcours (etiquette +x ) ou

diminue s’il est dans le sens contraire (etiquette −x ).

Si l’on parvient jusqu’au marquage du sommet xn avec cette procedure, c’est qu’il existe unechaıne µ de x1 a xn dont tous les sommets sont marques avec l’indice du sommet precedent ausigne pres. Notons que l’on est pas oblige de marquer tous les sommets (tous les successeurs oupredecesseurs d’un sommet donne) ; l’objectif etant simplement d’elaborer une chaıne marqueede x1 a xn.

Soit alors :

ϕ′(a) = ϕ(a) si a /∈ µϕ′(a) = ϕ(a) + 1 si a ∈ µ et si a est orientee dans le sens de µϕ′(a) = ϕ(a) − 1 si a ∈ µ et si a est orientee dans le sens contraire de µ

On verifie aisement que ϕ′ est encore un flot. Comme ϕ′

xn= ϕxn + 1, la valeur du flot ϕ est

superieure, donc meilleure que celle de ϕ.

On peut alors systematiser l’idee precedente en introduisant la notion de graphe d’ecart oureseau residuel.

Definition 26Soit un reseau de transport G = (X,A,C) possedant un flot complet ϕ. On appellegraphe d’ecart ou reseau residuel, le reseau G(ϕ) = (X,A,C) tel que :

– si a ∈ A et ϕ(a) < C(a) alors a ∈ A et C(a) = C(a)− ϕ(a)

– si a = (x, y) ∈ A et ϕ(a) > 0 alors a−1 = (y, x) ∈ A et C(a−1) = ϕ(a)

Le reseau residuel indique le long de quels arcs on peut augmenter ou diminuer le flot.L’interet du graphe d’ecart apparaıt dans le theoreme suivant.

29

Theoreme 4Soit ϕ un flot de G (de x1 a xn) et G(ϕ) le reseau residuel associe a ϕ. Une condi-tion necessaire et suffisante pour que le flot ϕ soit maximal est qu’il n’existe pas dechemin de x1 a xn dans G(ϕ).

La demonstration de ce theoreme s’appuie sur le lemme des arcs colores de Minty que nousne detaillerons pas ici.

8.4 Recherche d’un flot maximal : algorithme de Ford et Fulkerson

A partir des resultats precedents, on peut maintenant proposer une methode constructive derecherche d’un flot maximal.

Algorithme 4 (Ford et Fulkerson)Recherche d’un flot maximum.

(a) - Iteration k = 0

Partir d’un flot initial ϕ0 (compatible avec les contraintes de capacite),

par exemple ϕ0 = (0, 0, . . . , 0).

(b) - A l’iteration k, soit ϕk le flot courant.

Rechercher un chemin µk de x1 a xn dans le graphe d’ecart G(ϕk).

S’il n’en existe pas, FIN : le flot ϕk est maximal.

(c) - Soit εk la capacite residuelle du chemin µk

(minimum des capacites residuelles des arcs du chemin).

Definir le flot ϕk+1 par :{

ϕk+1a = ϕk

a + εk si a ∈ µ et si a est orientee dans le sens de µϕk+1

a = ϕka − εk si a ∈ µ et si a est orientee dans le sens contraire de µ

Faire k ← k + 1 et retourner en (b).

Par definition du graphe d’ecart, les flots ϕk sont tous compatibles avec les capacites. Parailleurs, εk est positif a chaque iteration et, par suite, l’algorithme produit une sequence de flotscompatibles de valeurs strictement croissantes.

A chaque etape, la methode consiste donc a rechercher une chaıne joignant x1 a xn. Ilest evident que le choix d’une telle chaıne n’est pas unique. Plusieurs travaux ont tente desystematiser ce choix afin d’ameliorer les performances moyennes de l’algorithme.

8.5 Exemple traite manuellement

On considere le graphe de la figure 11 (les nombres associes aux arcs representent les capa-cites), pour lequel on cherche a determiner un flot maximal entre le sommet 1 et le sommet 7.

Toutes les composantes du flot initial sont considerees nulles ϕ0 = (0, 0, . . . , 0) (figure12a) ; le graphe d’ecart G(ϕ0) est represente figure 12b.

Le chemin choisi est trace en pointilles, sa capacite residuelle vaut ε1 = min(5, 4, 7) = 4.On augmente donc de quatre le flot sur les arcs composant le chemin (ils sont tous orientes

30

1

3

4

6

75

2

2

2

8 5

3

7

3

5

4

Fig. 11 – Graphe oriente elementaire

1

3

4

6

75

0

0

2

0 0

0

0

0

0

0

1

3

4

6

75

2

2

2

8 5

3

7

3

5

4

Fig. 12 – Flot initial et graphe d’ecart

positivement). On obtient un nouveau flot ϕ1, ainsi que son graphe d’ecart G(ϕ1), tous deuxrepresentes aux figures 13a et 13b.

1

3

4

6

75

0

0

2

0 0

0

4

0

4

4

1

3

4

6

75

2

2

2

8 5

33

3

1

4

4

4

Fig. 13 – Flot a l’iteration numero 1 et graphe d’ecart

Le nouveau chemin est toujours represente en traits pointilles. Cette fois, sa capacite residuellevaut ε2 = min(1, 2, 3) = 1. Le nouveau flot ϕ2 et le graphe d’ecart correspondant sont donnes ala figure 14.

En poursuivant ainsi l’algorithme, on obtient les situations decrites aux figures 15 et 16.Apres l’iteration numero 4, on constate qu’il n’existe plus de chemin joignant le sommet 1 ausommet 7 dans le graphe d’ecart. L’algorithme s’acheve donc et le flot maximal est celui obtenulors de cette derniere etape ϕ1 = ϕ7 = 9.

31

1

3

4

6

75

1

0

2

0 0

1

4

0

5

4

1

3

4

6

751

2

2

8 5

23

3

5

4

41

1

Fig. 14 – Flot a l’iteration numero 2 et graphe d’ecart

1

3

4

6

75

1

0

2

2 23

4

0

5

4

1

3

4

6

751

2

2

6 3

3

3

5

4

41

3

2 2

Fig. 15 – Flot a l’iteration numero 3 et graphe d’ecart

1

3

4

6

75

1

2

2

4 2

3

4

2

5

4

1

3

4

6

751

2

4 3

3

1

5

4

41

3

2 22 2

Fig. 16 – Flot a l’iteration numero 4 et graphe d’ecart

Notons egalement que l’algorithme peut etre adapte au cas ou les capacites des arcs ontdes bornes inferieures non nulles (positives, voire meme negatives). En pratique, on associe a laplupart des reseaux de transport, une notion de cout unitaire du transport qui se traduit parl’association, a chaque arc a du reseau, d’un nombre reel w(a) representant ce cout unitaire. Lecout total d’un flot ϕ est defini comme la somme des couts associes aux flots elementaires :

W (ϕ) =∑

a∈A

w(a)ϕ(a)

On peut alors se poser le probleme consistant a rechercher, parmi les flots a valeur maximale,celui qui est a cout minimal. L’algorithme de Ford et Fulkerson peut egalement etre adapte acette situation.

32

8.6 Recherche d’un flot maximal a cout minimal

La recherche d’un flot maximal a cout minimal peut etre resolue a l’aide de l’algorithme deBusacker-Gowen qui permet de determiner la famille complete de tous les flots de cout minimald’un sommet x1 a un sommet xn et de valeur ϕ = 1, 2, ..., v. Nous enoncons ici cet algorithmeiteratif sous forme litterale et laissons le soin au lecteur d’en effectuer une description plus “in-formatique”.

A l’iteration numero k, le flot courant ϕk est suppose etre un flot de valeur ϕk0 et de cout

minimal parmi l’ensemble de tous les flots de valeur ϕk0 .

Soit G(ϕk) le graphe d’ecart relatif a ϕk ; on attribue aux arcs de G(ϕk) les couts w et lescapacites c suivantes :

– si a = (xi, xj) ∈ A et ϕ(a) < c(a), l’arc a+ = (xi, xj) a un cout w(a) = w(a) et unecapacite c(a) = c(a)− ϕ(a) > 0,

– si a = (xi, xj) ∈ A et ϕ(a) > 0, l’arc a− = (xj , xi) a un cout w(a) = −w(a) et une capacitec(a) = ϕ(a).

Soit alors µk un chemin de cout minimal relativement aux couts w entre x1 et xn sur legraphe d’ecart G(ϕk) ; on note εk la capacite residuelle de ce chemin. On definit alors le flotϕk+1 comme dans l’algorithme de Ford-Kulkerson. Si µ est le vecteur associe au chemin µk

(c’est-a-dire tel que µa = 1 si a+ ∈ µk et µa = −1 si a− ∈ µk), on a ϕk+1 = ϕk + εkµ et le flot

ϕk+1 est un flot de cout minimal de valeur ϕk0 + εk.

On notera qu’a chaque iteration, on doit rechercher le plus court chemin (au sens du cheminde cout minimal) de x1 a xn dans un graphe ou la longueur (le cout) des arcs peut etre negative ;il conviendra donc d’employer un algorithme adapte a cette situation (l’algorithme de Dijkstrane convient pas). Il existe cependant une amelioration de cet algorithme proposee par Edmondset Karp et basee sur une technique de modification des couts permettant de les rendre touspositifs en conservant cependant la meme hierarchie de chemin sur le graphe d’ecart ; dans cettesituation l’algorithme de Dijkstra peut etre utilise.

9 Couplages

Les problemes de couplage dans les graphes quelconques (ou dans les graphes bipartis) ontun double interet. Le premier, le plus evident, vient de leurs applications : ils generalisent di-rectement les problemes d’affectation et ils interviennent dans certains problemes importantsde la theorie de graphes : problemes de tournees, determination de plus courtes chaınes dansun graphe non oriente, etc. Le second, d’ordre theorique, vient de ce qu’ils se rattachent a uneclasse de problemes de programmation lineaire en nombres entiers.

Definition 27Etant donne un graphe simple non oriente G = (X,A), un couplage est un sous-ensemble d’aretes K ⊂ A tel que deux aretes quelconques de K ne sont pas adja-centes.

Un sommet i ∈ X est dit sature par le couplage K ⊂ A s’il existe une arete de Kincidente a i.

Un couplage K qui sature tous les sommets du graphe est appele couplage parfait.

Un couplage maximal est un couplage de cardinalite maximale.

33

9.1 Le probleme du couplage maximal

Definition 28Si K ⊂ A est un couplage de G = (X,A), on appelle chaıne alternee (relativement aK) une chaıne elementaire de G dont les aretes appartiennent alternativement a Ket K = A−K.

Une chaıne alternee augmentante ou chaıne ameliorante est une chaıne alternee joi-gnant deux sommets insatures.

En convenant de dessiner les aretes d’un couplage par des traits epais, les aretes de K = A−Krestant en traits fins, une chaıne alternee est une chaıne elementaire dont les aretes sont alter-nativement fines et epaisses.

Definition 29Etant donne un couplage K ⊂ A, considerons une chaıne alternee L dont chaqueextremite est un sommet insature ou est telle que l’unique arete de K qui lui estincidente soit dans L. Alors le couplage K ′ obtenu en echangeant le role des aretesfines et epaisses le long de la chaıne L est encore un couplage de G. Cette operationqui fait passer du couplage K au couplage K ′ est appelee transfert le long de lachaıne alternee L.

Une operation de transfert le long d’une chaıne alternee augmentante, augmente la cardina-lite du couplage d’une unite.

Par exemple, sur le graphe de la figure 17, les aretes (2, 3) et (5, 6), dessinees en traits epais,forment un couplage K de cardinalite egale a 2. La chaıne L = {1, 2, 3, 4} est une chaıne alterneedont les extremites sont des sommets insatures. C’est donc une chaıne alternee augmentante.Un transfert le long de cette chaıne produit le nouveau couplage K ′ = {(1, 2), (3, 4), (5, 6)} decardinalite egale a 3.

3

4

6

52

1

3

4

6

52

1

Fig. 17 – Couplages initial et final

Pour cet exemple particulier, ce couplage est maximal, car, pour un graphe d’ordre n, lacardinalite d’un couplage maximal est egale a la partie entiere de n/2.

Le theoreme suivant permet de caracteriser un couplage maximal.

Theoreme 5Un couplage K est maximal si et seulement s’il n’existe pas de chaıne alternee aug-mentante relativement a K.

34

Ce theoreme montre que pour rechercher un couplage maximal, il suffit donc de savoir trouverune chaıne alternee augmentante (s’il en existe) relativement a un couplage K ⊂ A quelconque.La procedure pour construire un couplage maximal K pour G = (X,A) est la suivante :

1. Initialiser K = ∅

2. Trouver un chaıne ameliorante Ka de K, effectuer le transfert le long de cette chaıneet remplacer le couplage K par celui ainsi obtenu (dont la cardinalite a necessairementaugmente de un).

3. Repeter l’etape 2 jusqu’a ce qu’il ne soit plus possible de creer une nouvelle chaıneameliorante ; K est alors un couplage maximal.

Le probleme qui se pose alors est de savoir construire, pour un couplage donne, une chaınealternee augmentante. Pour rechercher des chaınes alternees d’origine fixee i0, on construit unarbre alterne T de racine i0 tel que :

– T = (Y, T ) est un sous-graphe partiel connexe et sans cycle de G,– pour tout j ∈ Y , la chaıne (unique) LT (j) de l’arbre entre i0 et j est une chaıne alternee,– les chaınes reliant i0 aux sommets pendants ont un nombre pair d’aretes.

Nous ne detaillerons pas ici les multiples situations particulieres auxquelles on peut etreconfrontes dans la construction de cet arbre. Nous nous contenterons de decrire la situation laplus courante.

On choisit tout d’abord comme racine de l’arbre (niveau 0) un sommet insature relativementau couplage courant. Au niveau i impair, on insere dans l’arbre un sommet adjacent a l’un dessommets inseres au niveau i−1 par le biais d’une arete n’appartenant pas au couplage cou-rant, ainsi que cette arete. Au niveau i pair, on insere dans l’arbre alterne, un sommet adjacent al’un des sommets inseres au niveau i−1 par le biais d’une arete appartenant au couplage, ainsique cette arete. On continue a construire progressivement cet arbre jusqu’a l’insertion, a un ni-veau impair, d’un sommet insature, ou bien jusqu’a ce que l’on ne puisse plus inserer de sommet.

S’il existe une chaıne alternee augmentante du couplage courant, on finit necessairement parinserer un sommet insature s. La chaıne reliant s a la racine de l’arbre est alors une chaınealternee augmentante.

Considerons le graphe biparti de la figure 18 ou l’on a materialise, a l’aide d’aretes “epaisses”,le couplage obtenu apres une etape determinee de l’algorithme precedent.

x5 x4 x3 x2 x1

f5 f4 f3 f2 f1f

x

Fig. 18 – Couplage courant

35

Choisissons de construire un arbre alterne dont la racine est le sommet x1 insature par cecouplage.

x5

x3

x2

x1 f5

f4

f3

f2

f1

Fig. 19 – Arbre alterne de racine x1

Au niveau 1 de l’arbre, la seule possibilite est d’inserer l’arete (x1, f5) et le sommet f5. Auniveau 2, on insere l’arete (f5, x5) appartenant au couplage (c’est encore la seule possibilite). Auniveau 3, les deux aretes (x5, f3) et (x5, f4) n’appartenant pas au couplage peuvent etre inserees.On insere ensuite les aretes (f4, x3) et (f3, x2), ainsi que les sommets (satures) correspondants.Le sommet x3 est alors un sommet pendant de l’arbre, en revanche, on peut inserer, au niveau5, les aretes (x2, f1) et (x2, f2) conduisant a l’arbre alterne de la figure 19.

Comme les sommets f1 et f2 sont tous deux insatures, on a ainsi cree deux chaınes ameliorantesqui permettent d’augmenter, en effectuant un transfert, la cardinalite du couplage. Si l’on choisitpar exemple, la chaıne f1, x2, f3, x5, f5, x1), le nouveau couplage est represente figure 20.

x5 x4 x3 x2 x1

f5 f4 f3 f2 f1f

x

Fig. 20 – Couplage “augmente”

Pour cet exemple particulier, on observe qu’il suffit d’ajouter a ce dernier couplage l’arete(x4, f2), reliant les deux seuls sommets insatures, pour obtenir un couplage parfait qui est, biensur, un couplage maximal du graphe.

9.2 Couplage maximal et flot maximal

Pour determiner un couplage maximal sur un graphe biparti G = (X,Y,Γ), on peut recou-rir a l’artifice suivant. On construit un reseau de transport (voir definition 23) en ajoutant augraphe une origine S liee a tous les sommets de X et une destination P liee a tous les sommetsde Y (voir figure 21). On fixe a 1 les capacites de tous les arcs de ce reseau.

Un couplage permet de selectionner un certain nombre d’aretes du graphe biparti. Si l’on faitpasser une unite de flot par ces aretes et sur les aretes correspondantes vers S et P (en faisantpasser un flot nul sur les autres aretes), on obtient bien un flot sur le reseau. En effet, la loi de

36

Kirchhoff en un sommet quelconque de X ou de Y exprime ici qu’il y a au plus une arete ducouplage y parvenant. Reciproquement, un flot sur ce reseau ne peut transporter au plus qu’uneunite de flot sur chaque arete et l’ensemble des aretes transportant une unite de flot entre X etY determine un couplage sur G. En effet, si deux aretes retenues etaient adjacentes en x ∈ X,la loi de Kirchhoff en x imposerait un flot de deux unites au moins sur l’arc entre S et x, ce quidepasse la capacite imposee. La valeur du flot est donc egale au nombre d’aretes constituant lecouplage.

Le probleme du couplage maximal se ramene ainsi a un probleme de flot maximal dans unreseau de transport, qui peut etre resolu a l’aide de l’algorithme de Ford-Fulkerson. La figure21 (partie gauche) montre un flot complet et non maximal qui peut etre ameliore en un flotmaximal (partie droite).

x1

x2

x3

x4

x5

y1

y2

y3

y4

y5

S P

x1

x2

x3

x4

x5

y1

y2

y3

y4

y5

S P

Fig. 21 – Flot complet et maximal

9.3 Couplage de poids maximal

A chaque arete a ∈ A du graphe G(X,A), on associe maintenant un nombre reel w(a) ap-pele poids de l’arete a. Le poids d’un couplage K ⊂ A est la somme des poids des aretes quile constituent, soit w(K) =

∑

a∈K w(a). Le probleme du couplage de poids maximal est la re-cherche d’un couplage tel que son poids soit maximal sur l’ensemble de tous les couplages de G.On remarquera qu’un couplage de poids maximal n’est pas necessairement un couplage maximal(couplage de cardinalite maximale).

Definition 30Soit K ⊂ A un couplage de G = (X,A), on rappelle qu’une chaıne alternee augmen-

tante est une chaıne alternee joignant deux sommets insatures.

Une chaıne alternee reductrice est une chaıne alternee impaire dont les aretes extremessont dans K.

Une chaıne alternee conservative est une chaıne alternee paire dont une extremiteest un sommet isole.

On remarquera de maniere evidente que le transfert le long d’une chaıne alternee augmen-tante augmente la cardinalite du couplage d’une unite ; le long d’une chaıne reductrice, il lareduit d’une unite et le long d’une chaıne conservative, il ne la change pas.

37

Definition 31Le cout reduit d’une chaıne alternee L (augmentante, reductrice ou conservative)relative au couplage K vaut :

δ(L) = w(L ∩ K)− w(L ∩K)

Un cycle alterne pair est une chaıne alternee paire dont les extremites coıncident.Un transfert le long d’un cycle alterne pair conserve la cardinalite du couplage.

Le cout reduit du cycle µ est :

δ(L) = w(µ ∩ K)− w(µ ∩K)

Le resultat suivant caracterise un couplage de poids maximal en termes d’existence de chaınesalternees.

Theoreme 6Un couplage K est de poids maximal si et seulement s’il n’existe pas de chaıne al-ternee, ni de cycle alterne pair de cout reduit strictement positif relativement a K.

Le theoreme ci-dessous montre que l’on peut construire, de proche en proche, des couplagesK1, K2, ..., Kp de cardinalite 1, 2, ..., p et de poids maximal, par des transferts successifs le longde chaınes alternees augmentantes et de cout reduit maximal. On generalise ainsi le resultat deBusacker-Gowen sur la recherche de flot maximal de cout minimal.

Theoreme 7Soit K un couplage de cardinalite p de poids maximal (sur l’ensemble des couplagesde cardinalite p) et soit L une chaıne alternee augmentante (relativement a K) decout reduit maximal. Le couplage K ′ obtenu a partir de K par transfert le long deL est de poids maximal parmi tous les couplages de cardinalite p + 1.

9.4 Problemes d’affectation

La formulation generale d’un probleme d’affectation est la suivante. Etant donne n taches arealiser et n machines pour les realiser et sachant que l’on connaıt le cout de realisation C ij dela tache ti par la machine mj (pour tous les couples (ti,mj) possibles, si la tache ti ne peut etreeffectuee par la machine mj, on pose Cij = ∞), on cherche une permutation σ de {1, 2, . . . , n}conduisant a un cout total :

n∑

i=1

Ci,σ(i)

minimum (sur l’ensemble de toutes les n! permutations σ possibles).

Le probleme d’affectation est un cas particulier du probleme de transport (sans capacite).Il peut egalement etre vu comme un probleme de couplage parfait de poids minimum dans ungraphe biparti.

Cependant, compte-tenu de l’importance de ce type de probleme, un algorithme specifiquea ete propose par Kuhn ; il s’agit de l’algorithme Hongrois.

38

Cet algorithme repose essentiellement sur la constatation suivante. On ne change pas la oules solutions optimales en augmentant ou en diminuant d’une meme quantite λ tous les elementsd’une meme ligne (ou d’une meme colonne) de la matrice des Cij (les valeurs infinies restantinfinies). Apres une telle operation, la valeur totale est augmentee ou diminuee de λ.

Par consequent, si l’on fait apparaıtre, par des transformations de ce type, suffisamment dezeros dans le tableau, mais pas de couts negatifs, et qu’il existe n zeros “independants” (c’est-a-dire un seul zero dans chaque ligne et dans chaque colonne), on aura alors trouve l’affectationoptimale.

L’algorithme procede en trois phases successives. Afin d’expliquer la demarche suivie, conside-rons l’exemple decrit par la matrice des couts suivante :

ABCDE

7 3 5 7 106 8 76 5 1 5∞ ∞

∞∞

∞11 4 11 154 5 2 10

1 2 3 4 5

Premiere phase : obtention de valeurs nulles

A tous les elements de chacune des colonnes, on enleve le plus petit element de cette colonne,puis, dans la matrice ainsi obtenue, on enleve, a tous les elements d’une meme ligne, le plus petitelement de la ligne. On obtient de la sorte une matrice (C1,ij) ayant au moins un zero par ligneet par colonne.

Pour l’exemple precedent, on obtient, apres traitement des colonnes puis des lignes, les deuxmatrices suivantes :

ABCDE

1 0 4 5 30 6 00 2 0 3∞ ∞

∞∞

∞5 1 9 81 4 0 3

1 2 3 4 5ABCDE

1 0 4 5 30 6 00 2 0 3∞ ∞

∞∞

∞4 0 8 71 4 0 3

1 2 3 4 5

Deuxieme phase : recherche du maximum d’affectations possibles

A partir de la matrice (C1,ij), on cherche a former une solution de cout nul (un seul zero danschaque ligne et dans chaque colonne). Si c’est le cas, on a la solution optimale, sinon on chercheun ensemble maximum de zeros “independants” : ceci revient a chercher un flot maximal sur legraphe G′ constitue par les arcs de cout (reduit) nul. Sur la matrice C1,ij, cela correspond autraitement suivant. On considere la ligne ayant un nombre minimal de zeros (pour l’exemple,cela peut etre la premiere). On encadre l’un des zeros de cette ligne (ici, C1,A2), puis on barre leszeros qui se trouvent sur la meme ligne ou la meme colonne que le zeros encadre (ici, C1,D2). Onprocede de meme pour toutes les lignes, en tenant compte des etapes precedentes. On obtient,pour l’exemple, la matrice suivante :

39

ABCDE

1 0 4 5 30 6 00 2 0 3∞ ∞

∞∞

∞4 0 8 71 4 0 3

1 2 3 4 5

Troisieme phase : determination des affectations “interessantes”

Pour determiner ces affectations, on procede la maniere suivante :

– On marque (d’une asterisque) toutes les lignes qui ne contiennent aucun zero encadre –sommet non affecte – (ligne D de l’exemple) ;

– On marque les lignes qui ont un zero encadre dans une colonne marquee (ligne A del’exemple) ;

– On marque les colonnes qui ont un ou plusieurs zeros barres dans une ligne marquee –possibilite non exploitee – (colonne 2 de l’exemple).

On repete ces trois marquages successifs jusqu’a ce que l’on ne puisse plus effectuer de nou-veaux marquages (pour l’exemple, une seule “passe” suffit).

Les affectations interessantes a considerer sont celles issues des sommets correspondant auxlignes marquees ; on barre donc les lignes non marquees. Les sommets correspondant aux colonnesmarquees ne sont pas interessants car ils ne peuvent etre reaffectes ; on barre donc les colonnesmarquees.

ABCDE

1 0 4 5 30 6 00 2 0 3∞ ∞

∞∞

∞4 0 8 71 4 0 3

1 2 3 4 5*

*

*

Dans le tableau reduit ainsi obtenu (cases non barrees), on recherche ensuite l’element le pluspetit, necessairement non nul par construction (pour l’exemple, il s’agit de l’element C1,A1) ; onretranche sa valeur aux colonnes non barrees et on l’ajoute aux lignes barrees. On obtient lestableaux successifs suivants :

ABCDE

0 0 3 4 2-1 5 -1-1 2 -1 2∞ ∞

∞∞

∞3 0 7 61 3 -1 2

1 2 3 4 5ABCDE

0 0 3 4 20 6 00 3 0 3∞ ∞

∞∞

∞3 0 7 62 4 0 3

1 2 3 4 5

40

On note (C2,ij) la matrice ainsi obtenue et l’on poursuit la procedure de traitement en re-prenant a la seconde phase. Lorsqu’une solution optimale est obtenue (un zero par ligne etpar colonne), on arrete ; sinon on recommence et on definit successivement les matrices (C3,ij),(C4,ij), . . . , (Cn,ij).

Sur le tableau (C2,ij) de l’exemple, on est amene a encadrer C2,D2 et barrer C2,A2, encadrerC2,E4, encadrer C2,A1 et barrer C2,B1 et C2,C1, encadrer C2,B5 et enfin encadrer C2,C3 :

ABCDE

0 0 3 4 20 6 00 3 0 3∞ ∞

∞∞

∞3 0 7 62 4 0 3

1 2 3 4 5

La solution optimale est alors obtenue grace aux elements :

C2,A1 = C2,B5 = C2,C3 = C2,D2 = C2,E4 = 0

et a la permutation σ =

(

A B C D E1 5 3 2 4

)

.

Si l’on revient aux donnees initiales, on obtient :

CA1 = CB5 = CC3 = CD2 = CE4 = 7 + 7 + 1 + 4 + 2 = 21

La figure 22 visualise en trait fort le couplage optimal obtenu.

A

C

D

E

1

2

3

4

5

B

Fig. 22 – Affectation optimale

10 Problemes d’ordonnancement

L’objet d’un probleme d’ordonnancement est de faciliter la mise en œuvre et de guiderl’execution d’un ensemble complexe de taches (programme de recherche ou de production, lan-cement d’un produit, construction d’un edifice ...). La technique d’analyse la plus connue, appeleemethode PERT (Program Evaluation and Review Technique) a ete introduite aux Etats-Unis en1958 pour la conduite du programme de recherche et de construction des fusees Polaris. Cette

41

methode tient une place dominante par sa simplicite, son efficacite et la variete d’extensions quiont pu etre developpees.

En toute generalite, les problemes d’ordonnancement se posent sous la forme suivante. Etantdonne un objectif qu’on se propose d’atteindre et dont la realisation suppose l’execution prealablede multiples taches, soumises a de nombreuses contraintes, determiner l’ordre et le calendrierd’execution des diverses taches.

Le critere d’optimalite peut porter sur la minimisation de la duree et/ou du cout de larealisation du projet. Nous supposerons que le projet est decomposable en un nombre fini detaches, caracterisees par leur duree d’execution (generalement fixe, parfois aleatoire), eventuel-lement aussi par leur cout d’execution, et soumises a des contraintes de posteriorite stricte (unetache ne peut commencer que si certaines autres taches sont completement terminees). Ce typede probleme se nomme probleme central de l’ordonnancement. Des cas plus complexes peuventegalement etre envisages comme par exemple le cas des contraintes disjonctives, c’est-a-dire lecas ou, en plus des contraintes de succession, on impose la realisation non simultanee de certainespaires de taches.

La representation par un graphe d’un probleme d’ordonnancement permet une bonne appre-hension globale du probleme. L’etude de ce graphe conduit a l’identification des taches priori-taires et la detection des retards ou des depassements de moyens afin de prendre les mesurescorrectives necessaires.

Le probleme central de l’ordonnancement s’enonce comme suit : etant donne un projetconstitue de n taches de durees d’execution fixes et soumises a des contraintes de posterioritestricte, determiner un “calendrier d’execution” ou ordonnancement qui minimise la duree derealisation totale du projet.

En pratique, le travail preliminaire a accomplir sera donc de dresser une liste des differentesoperations a mener que l’on decomposera plus ou moins finement selon la precision souhaitee.Generalement, les taches sont definies pour que leurs durees d’execution soient du meme ordrede grandeur ; de plus, les contraintes de posteriorite entre les taches doivent pouvoir etre etabliesavec precision. Ce travail important est souvent long et necessite une collaboration etroite entreles differents acteurs du projet.

10.1 Le graphe potentiels-taches

A partir de la description des taches du projet, on construit le graphe suivant :

– A chaque tache i (i de 1 a n), on associe un sommet i du graphe,– On definit un arc entre i et j de longueur di (la duree de la tache i) si la tache i doit

preceder la tache j.– On introduit deux sommets correspondant a deux taches fictives de duree nulle, la tache

de debut des travaux α, anterieure a toutes les taches (il suffit de relier le sommet α auxsommets sans predecesseurs du graphe) et la tache de fin des travaux ω, posterieure atoutes les autres taches (tous les sommets sans successeur du graphe seront relies au som-met ω).

Le graphe ainsi defini doit etre sans circuit ; en effet, dans le cas contraire, une operationdevrait se succeder a elle-meme. Le travail commencant a la date 0, on cherche un ordonnance-ment qui minimise la duree totale du projet, donc la date de fin des travaux. Pour qu’une tache

42

puisse commencer, il est necessaire que toutes les taches qui la relient a la tache debut du projetsoient realisees.

Definition 32La date au plus tot, ti de debut de la tache i est egale a ti = max

j∈Γ−1

i(tj + dj),

c’est-a-dire que ti est egale a la longueur du plus long chemin l(α, i) de α a i.

La duree minimale du projet tω est donc la longueur du plus long chemin de α a ω.

Si la duree minimale du projet est egale a tω, la date au plus tard pour commencerla tache i est egale a Ti = minj∈Γi

(Tj − di) avec Tω = tω, ce qui montre que Ti =tω − l(i, ω) ou l(i, ω) est la longueur du plus long chemin de i a ω.

La marge totale Mi de la tache i est definie comme la difference entre la date au plustot et au plus tard (Mi = Ti − ti).

Les taches dont la marge est nulle sont appelees taches critiques. Si un quelconqueretard est pris sur la realisation de l’une de ces taches, la duree minimale du projetsera augmentee d’autant.

La marge libre mi de la tache i est le delai dont on peut retarder cette tache sans affec-ter les dates de debut au plus tot des taches posterieures, mi = minj∈Γi

(tj− ti−di)).

On observe donc qu’a chaque tache i est associe un nombre ti qui peut etre considere commeun potentiel d’ou la denomination de graphe potentiels-taches.

10.2 Le graphe potentiels-etapes ou graphe PERT

Dans cette representation, les taches sont materialisees par les arcs du graphe. La longueurde chaque arc est egale a la duree di de la tache correspondante. Le debut et la fin d’une tacheconstituent les etapes du projet. Comme precedemment, on introduit les deux etapes de debut(α) et de fin (ω) du projet.

Chaque etape est donc definie par un ensemble de taches deja effectuees. Si une tache j doitsucceder a une tache i, on confondra l’extremite initiale de l’arc aj (correspondant a la tachej) et l’extremite terminale de l’arc ai (correspondant a la tache i), via eventuellement un arc fictif.

Le graphe ainsi defini doit etre sans circuit. Dans cette formulation, les sommets s’interpretentcomme des etapes, c’est pourquoi l’on utilise l’appellation graphe potentiels-etapes (connu pluscommunement sous le nom de graphe PERT).

La construction d’un tel graphe est un peu plus complexe que celle du graphe potentiels-taches car elle demande la definition des etapes qui peuvent correspondre au debut ou a la finde plusieurs taches. Si l’on se donne, pour chaque tache i, l’ensemble Γ−1

i des taches qui doiventla preceder, les differentes etapes du projet correspondent aux differents ensembles Γ−1

i .

Soulignons aussi que pour pouvoir exprimer certaines contraintes de posteriorite stricte, ilest parfois necessaire d’introduire des taches fictives et donc des arcs fictifs de duree nulle. Atitre d’exemple, considerons le sous-graphe partiel de la figure 23.

Ce graphe indique que les taches 3 et 4 doivent succeder aux taches 1 et 2. Supposons quesuite a une modification de conditions techniques, l’execution de la tache 4 puisse commencer

43

Tâche 1 Tâche 3

Tâche 2 Tâche 4

Fig. 23 – Element de graphe PERT

avant que ne soit achevee la tache 1. Pour adapter le graphe a ce changement, on ajoute un arcfictif comme sur la figure 24.

Tâche 1 Tâche 3

Tâche 2 Tâche 4

Tâche fictive

Fig. 24 – Element de graphe PERT

10.3 Resolution

Un ordonnancement est un programme d’execution qui fixe la date ti de debut d’executionde chacune des taches (dans la methode du potentiel) ou de debut de realisation de chacune desetapes (dans la methode PERT). Un ordonnancement est optimal s’il est realisable c’est-a-diresi tj − ti ≥ di et s’il minimise la duree de realisation tω du projet.

La duree minimale du projet est egale a la longueur du plus long chemin de α a ω. Eneffet, pour qu’une tache puisse commencer, il faut que toutes les taches precedentes aient eteexecutees, de sorte que la duree du projet ne peut etre inferieure a la somme des durees destaches composant le chemin le plus long de α a ω. Ce chemin, appele chemin critique, n’est pasnecessairement unique. Comme le graphe est sans circuit,on a :

tj = maxi∈Γ−1

j

(ti + di), 1 ≤ j ≤ n

Chaque ti ainsi obtenu est la longueur du chemin le plus long du sommet α au sommet i etrepresente la date au plus tot de debut d’execution de la tache ou de l’etape i.

La duree minimum tω du projet ayant ete determinee, il est bien sur possible de retarderl’execution de certaines taches ou etapes sans pour autant accroıtre tω. Il est des lors interessantde determiner les dates au plus tard Ti de debut d’execution des differentes taches ou etapes isous la condition que la duree minimale du projet ne soit pas modifiee. Ces dates se calculent dememe maniere que pour les dates au plus tot mais a partir du graphe inverse obtenu en inversantle sens de tous les arcs. Il vient Tω = tω et :

Tj = mini∈Γj

(Ti − di), 0 ≤ j ≤ n− 1

44

Chaque quantite Tω − Ti ainsi obtenue est la longueur du chemin le plus long du sommet iau sommet ω.

10.4 Complements

Pour comparer l’interet des deux graphes precedemment decrits, il faut se placer dans uncadre plus general que le probleme central de l’ordonnancement et examiner un ensemble decontraintes que l’on doit pratiquement prendre en compte dans les problemes d’ordonnancement.Ces contraintes sont essentiellement de trois types :

Type potentiel : la tache j doit commencer apres la fin de i ou bien apres la moitie de larealisation de i, ou bien un certain temps apres la fin de i, etc.

Type disjonctif : les taches i et j ne peuvent etre realisees en meme temps (car c’est le memeouvrier qui les realise par exemple).

Type cumulatif : les moyens necessaires a l’execution d’un certain nombre de taches sont,a chaque instant, limites ; par exemple, le nombre de camions utilisables ou la sommedepensee pour les travaux realises a l’instant t ne doit pas depasser un certain seuil, etc.

Les contraintes de type potentiel autres que les contraintes d’anteriorite du probleme centralsont difficiles a prendre en compte dans le graphe potentiels-etapes. On est en effet amenea ajouter des sommets et des arcs fictifs en tres grand nombre dans le graphe. En revanche,dans le graphe potentiels-taches, chaque contrainte supplementaire de type potentiel s’introduitsimplement par l’adjonction d’un arc dans le graphe. Par exemple :

– la contrainte : j ne doit pas commencer avant la moitie de la realisation de la tache i serepresente par un arc (i, j) de longueur di/2.

– la contrainte : j ne peut commencer qu’un temps t apres la fin de i se represente par unarc (i, j) de longueur di + t.

– la contrainte : j ne peut commencer qu’apres la date bj se represente par un arc (α, j) delongueur bj.

– la contrainte : j doit commencer avant la date cj se represente par un arc (j, α) de longueur−cj.

– enfin la contrainte : j doit suivre immediatement la tache i s’ecrit ti + di = tj et serepresente par un arc (i, j) de longueur di et un arc (j, i) de longueur −di.

Les deux derniers cas introduisent des circuits et des arcs de longueurs negatives. La condi-tion d’existence d’un ordonnancement devient alors : “il n’existe pas de circuit de longueurstrictement positive”. Comme l’on peut introduire des arcs de longueur differentes partant d’unsommet i quelconque, il est preferable de noter dij la longueur de l’arc allant de i a j. Lesformules de determination des dates au plus tot et au plus tard deviennent alors :

tj = maxi∈Γ−1

j

(ti + dij) au lieu de tj = maxi∈Γ−1

j

(ti + di)

Tj = mini∈Γj

(Ti − dij) au lieu de Tj = mini∈Γj

(Ti − di)

Les contraintes de type disjonctif ou cumulatif sont impossibles a prendre en compte dansle graphe PERT. Certains amenagements permettent leur prise en compte dans le graphepotentiels-taches. On preferera donc la representation potentiels-taches des que le problemene se reduit pas au probleme central.

45

Pour terminer cette presentation succincte des problemes d’ordonnancement, examinonsquelques exemples pouvant se formuler en termes du “probleme du voyageur de commerce”ou de ses nombreuses variantes.

Exemple 1 : Dans un systeme d’exploitation automatise, une machine doit regulierement effec-tuer n types de taches differentes x1, x2, . . . , xn. On connaıt de plus des durees de commutationsentre deux taches xi et xj quelconques. Le probleme est de trouver une sequence de xi qui mini-mise le temps total des commutations. Si l’on considere le graphe de sommets {xi}i=1,...,n dontl’arc (xi, xj) a une longueur egale au temps de commutation entre xi et xj, le probleme revienta determiner un circuit hamiltonien de longueur minimum.

Dans beaucoup de situations, on cherche un chemin hamiltonien dans un graphe qui mini-mise une autre fonction economique que la longueur totale du chemin.

Exemple 2 : Etant donnees n taches i = 1, . . . , n de duree ai, soit di la date ou la tache idoit etre terminee (date souhaitee). Determiner la sequence de taches sur une machine uniquede facon a minimiser le retard maximum, c’est-a-dire minimiser maxi=1,...,n(ti − di) ou ti est ladate ou la tache i est effectivement terminee. La solution optimale est obtenue en ordonnant les

taches i selon l’ordre croissant des dates souhaitees di.

Exemple 3 : Etant donne un graphe oriente G = (X,A) et des poids Ca = Ci,j sur chaque arca = (i, j), determiner une chaıne hamiltonienne qui minimise :

f(σ) =∑

i=1,...,n

∑

j>i

Cσ(i)σ(j)

ou σ(i) represente le iieme sommet de la chaıne hamiltonienne.

Cela revient a determiner, sur une matrice carree d’ordre n, C = (Cij), une permutationσ des lignes et des colonnes (la meme pour les lignes et les colonnes) telle que la somme deselements de la matrice triangulaire superieure soit minimale.

Ce probleme a de nombreuses applications. La plus classique correspond a l’analyse despreferences : etant donne N objets, on demande a k personnes de les comparer par paires (onpose Cij , le nombre de personnes ayant preferees i a j). L’optimum de f(σ) est obtenu si lachaıne hamiltonienne est constituee de la succession des sommets pris dans un ordre minimisantle nombre de desaccords.

46

Annexe A - Implementation de l’algorithme de Moore-Dijkstra

Le programme Matlab r© ci-dessous est une implementation de l’algorithme de Moore-Dijkstradecrit au paragraphe 6.3 et permettant l’obtention du plus court chemin entre deux sommets.Les trois parametres d’appel de la fonction moore sont les suivants :

L : matrice des longueurs (s’il n’y a pas d’arc entre le sommet i et le sommet j, alorslij =∞ et conventionnellement lii = 0).

dep : numero du sommet de depart du chemin recherche.

arv : numero du sommet d’arrivee du chemin recherche.

En sortie, on recupere :

s : la longueur du plus court chemin (s =∞ s’il n’existe pas de chemin).

m : le vecteur des longueurs des plus courts chemins entre dep et tous les autressommets.

function [s,mark]=moore(L,dep,arv)

%MOORE Recherche du plus court chemin entre deux sommets d’un graphe

%

% S=MOORE(L,DEP,ARV) calcule la longueur du plus court chemin entre

% les sommets de numero DEP et ARV.

%

% [S,M]=MOORE(L,DEP,ARV) renvoie egalement le vecteur des longueurs

% des plus courts chemins entre le sommet DEP et tous les autres sommets.

%

% Voir aussi MOORE1

% Copyright (c) 2003 by Didier MAQUIN

% $Revision: 0.1 $Date: 05/01/03 $

n=size(L,1);

% Initialisation

Sb=1:n;

Sb(dep)=[];

mark=L(dep,:);

while 1

[v,indj]=min(mark(Sb));

j=Sb(indj); % j sommet de marque provisoire minimale

Sb(indj)=[]; % on retire j de Sb

if isempty(Sb),break,end % si Sb est vide on arete

succ=find(L(j,:)~=inf & L(j,:)~=0); % liste des successeurs de j

A=intersect(succ,Sb); % intersection entre cette liste et Sb

if ~isempty(A) % si cette liste n’est pas vide

mark(A)=min(mark(A),mark(j)+L(j,A)); % on remet a jour les marques

end

end

s=mark(arv);

47

Considerons le graphe de la figure 25 :

3

4

6

52

1

7

4 5

1

25

1

3

7

2

Fig. 25 – Graphe oriente

Voila ci-dessous un exemple de programme d’appel pour calculer les longueurs des plus courtschemins joignant le sommet 1 a tous les autres :

clear

% Matrice de distance

D=[ 0 7 1 inf inf inf

inf 0 inf 4 inf 1

inf 5 0 inf 2 7

inf inf inf 0 inf inf

inf 2 inf 5 0 inf

inf inf inf inf 3 0 ];

%

dep=input(’Sommet de depart : ’);

arv=input(’Sommet d’’arrivee : ’);

[s,m]=moore(D,dep,arv)

Pour dep = 1 et arv = 6, on obtient :

Sommet de depart : 1

Sommet d’arrivee : 6

s =

6

m =

0 5 1 8 3 6

La fonction precedente peut etre modifiee de maniere a memoriser, en plus de la longueurdu chemin, la succession des sommets par lesquels il passe. Il suffit pour cela de maintenir a jourune table de predecesseurs. Celle-ci peut ensuite etre exploitee pour reconstituer le chemin suivi.

Le programme Matlab r© ci-dessous realise cette fonction. Les trois parametres d’appel de lafonction moore1 sont identiques a ceux de la fonction precedente. En sortie, on obtient :

s : la longueur du plus court chemin (s =∞ s’il n’existe pas de chemin).

chemin : le vecteur des numeros de sommets decrivant le chemin.

48

function [s,chemin]=moore1(L,dep,arv)

%MOORE1 Recherche du plus court chemin entre deux sommets d’un graphe

%

% S=MOORE1(L,DEP,ARV) calcule la longueur du plus court chemin entre

% les sommets de numero DEP et ARV.

%

% [S,CHEMIN]=MOORE1(L,DEP,ARV) renvoie egalement le chemin emprunte

% (sequence de numero de sommets).

%

% Voir aussi MOORE

% Copyright (c) 2003 by Didier MAQUIN

% $Revision: 0.1 $Date: 05/01/03 $

n=size(L,1);

% Initialisation

Sb=1:n;

Sb(dep)=[];

mark=L(dep,:);

p=ones(1,n)*inf;

succ=find(L(dep,:)~=inf & L(dep,:)~=0);

p(succ)=dep;

while 1

[v,indj]=min(mark(Sb));

j=Sb(indj); % j sommet de marque provisoire minimale.

Sb(indj)=[]; % on retire j de Sb.

if isempty(Sb),break,end % si Sb est vide on arete.

succ=find(L(j,:)~=inf & L(j,:)~=0);% on cherche la liste des successeurs de j.

A=intersect(succ,Sb); % intersection entre cette liste et Sb.

if ~isempty(A) % si cette liste n’est pas vide

oldmark=mark(A); % on memorise l’ancienne marque

mark(A)=min(mark(A),mark(j)+L(j,A)); % et on remet a jour les marques.

id=find(oldmark~=mark(A)); % pour les sommets dont les marques ont

p(A(id))=j; % change on memorise le predecesseur.

end

end

s=mark(arv);

chemin=[];

if isfinite(p(arv))

chemin=[arv]; % on construit le chemin

while chemin(end)~=dep % a l’aide de la table des predecesseurs

k=chemin(end); % a partir de la fin.

chemin=[p(k) chemin];

end

end

Ci-dessous un exemple de programme d’appel correspondant au graphe de la figure 25 :

clear

% Matrice de distance

D=[ 0 7 1 inf inf inf

49

inf 0 inf 4 inf 1

inf 5 0 inf 2 7

inf inf inf 0 inf inf

inf 2 inf 5 0 inf

inf inf inf inf 3 0 ];

%

dep=input(’Sommet de depart : ’);

arv=input(’Sommet d’’arrivee : ’);

[s,chemin]=moore1(D,dep,arv);

if isfinite(s)

fprintf(’Le chemin ’)

fprintf(’%i ’,chemin)

fprintf(’de longueur %f ’,s)

fprintf(’est le chemin de longueur minimale\n’)

else

fprintf(’Il n’’existe pas de chemin !\n’)

end

Pour dep = 1 et arv = 6, on obtient :

Sommet de depart : 1

Sommet d’arrivee : 6

Le chemin 1 3 5 2 6 de longueur 6.000000 est le chemin de longueur minimale

Pour dep = 4 et arv = 3, on obtient :

Sommet de depart : 4

Sommet d’arrivee : 3

Il n’existe pas de chemin !

50

Annexe B - Implementation de l’algorithme de Floyd

Le programme Matlab r© ci-apres est une implementation de l’algorithme de Floyd decrit auparagraphe 6.3 et permettant l’obtention de la matrice des plus courts chemins dans un graphedont les arcs sont valuees positivement. Le seul parametre d’appel de la fonction floyd est lesuivant :

L : matrice des longueurs (s’il n’y a pas d’arc entre le sommet i et le sommet j, alorslij =∞ et conventionnellement lii = 0).

En sortie, on recupere :

A : la matrice des plus courts chemins entre tous les sommets.

P : la matrice des predecesseurs (pij represente le numero du sommet predecesseurimmediat de j sur le plus court chemin entre i et j).

function [A,P]=floyd(L)

%FLOYD Recherche de la matrice des plus courts chemins entre sommets

%

% [A]=FLOYD(L) calcule a matrice des plus courts chemins entre sommets

%

% [A,P]=FLOYD(L) renvoie egalement la matrice des predecesseurs

%

% Copyright (c) 2003 by Didier MAQUIN

% $Revision: 0.1 $Date: 05/04/03 $

[n,m]=size(L);

if n ~= m error(’La matrice des distance n’’est pas carree’);end

A=L;

for i=1:n

P(i,:)=i*ones(1,m);

end

for k=1:n

for i=1:n

for j=1:n

if A(i,k) + A(k,j) < A(i,j)

A(i,j) = A(i,k) + A(k,j);

P(i,j) = P(k,j);

end

end

end

end

Considerons de nouveau le graphe de la figure 25. Le programme ci-apres permet de calculerla matrice des plus courts chemins et d’editer, en exploitant la matrice des predecesseurs, lechemin reliant un sommet initial a un sommet terminal quelconques sous la forme d’une liste desommets.

51

clear;

% Matrice de distance

C=[ 0 7 1 inf inf inf

inf 0 inf 4 inf 1

inf 5 0 inf 2 7

inf inf inf 0 inf inf

inf 2 inf 5 0 inf

inf inf inf inf 3 0 ];

%

[A,P]=floyd(C)

initial=input(’Sommet initial : ’);

terminal=input(’Sommet terminal : ’);

%

if ~isfinite(A(initial,terminal))

fprintf(’Il n’’existe pas de chemin entre les sommets %d et %d\n\n’,initial,terminal);

else

j=terminal;

chemin=[j];

while j ~= initial

j=P(initial,j);

chemin=[j chemin];

end

fprintf(’Plus court chemin entre les sommets %d et %d\n\n’,initial,terminal)

fprintf(’%d ’,chemin);

fprintf(’\n\n’)

end

Pour initial = 1 et terminal = 6, on obtient :

Plus court chemin entre 1 et 6

1 3 5 2 6

Alors que pour initial = 6 et terminal = 1, le resultat est le suivant :

Il n’existe pas de chemin entre 6 et 1

52

Annexe C - Implementation de l’algorithme de Prim

Le programme Matlab r© ci-apres est une implementation de l’algorithme de Prim decrit auparagraphe 7.2 et permettant l’obtention d’un arbre couvrant de poids minimal. Les deux pa-rametres d’appel de la fonction prim sont les suivants :

L : matrice des longueurs (s’il n’y a pas d’arc entre le sommet i et le sommet j, alorslij =∞ et conventionnellement lii = 0).

dep : numero du sommet de depart pour la construction de l’arbre recherche.

En sortie, on recupere :

alpha : un tableau de chaınes de caracteres designant les aretes constituant l’arbre.

function [alpha]=prim(L)

%PRIM Recherche d’un arbre couvrant de poids minimal

%

% ALPHA=PRIM(L) determine un arbre couvrant de poids minimal

% ALPHA est un tableau de chaınes de caracteres designant les

% aretes de l’arbre.

% Copyright (c) 2003 by Didier MAQUIN

% $Revision: 0.1 $Date: 05/01/03 $

n=size(L,1);

mark=ones(1,n)*inf;

alpha=ones(n,3)*abs(’-’); % liste des aretes de l’arbre

dep=1; % sommet de depart (fixe a 1)

mark(dep)=0;

A=[];

S=1:n;

while 1

S=setdiff(S,A); % ensemble X\A

[val,l]=min(mark(S)); % recherche du sommet ayant la plus petite marque

i=S(l); % numero du sommet

if isempty(setxor(A,1:n)),break, end % si A=X alors FIN

A=[A i]; % ajout du sommet a l’arbre

succ=find(L(i,:)~=inf & L(i,:)~=0); % successeurs du sommet i

E=setdiff(succ,A); % liste des successeurs moins les sommets deja dans S

for k=1:length(E) % mise a jour des marques

if L(i,E(k))<mark(E(k))

mark(E(k))=L(i,E(k));

alpha(E(k),:)=[num2str(i) ’-’ num2str(E(k))]; % memorisation aretes

end

end

end

Considerons le graphe de la figure 26. Le programme ci-apres permet de determiner un arbrecouvrant de ce graphe.

53

3

5

1 4

6

72

7

3

1 4

1

43

2

2

7

2

210

Fig. 26 – Graphe simple

clear

% 1 2 3 4 5 6 7

D=[ 0 7 3 2 2 inf inf

7 0 1 inf inf inf inf

3 1 0 inf 4 3 inf

2 inf inf 0 1 10 2

2 inf 4 1 0 4 2

inf inf 3 10 4 0 7

inf inf inf 2 2 7 0 ]

%

alpha=prim(D);

setstr(alpha)

Le resultat obtenu est :

ans =

---

3-2

1-3

1-4

4-5

3-6

4-7

Cela correspond a l’arbre suivant :

3

5

1 4

6

72 3

1

1

3

2

2

Fig. 27 – Arbre couvrant de poids minimal

54

References

[1] A.V. Aho, J.E. Hopcroft et J.D. Ullman, The design and analysis of computer algorithms,ISBN 0-201-00029-6, Addison Wesley, Reading (Mass.), 1974.

[2] M.L. Assas, Analyse de la tolerance aux fautes : approches fonctionnelle et structurelle.These de doctorat de l’Universite des Sciences et Technologies de Lille, 2002.

[3] K. Appel et W. Haken, Every planar map is 4-colorable, Bulletin of the AMS, Volume 82,711-712, 1976.

[4] C. Berge, Graphes, ISBN 2-04-15555-4, Gauthiers-Villars, Bordas, Paris, 1983.

[5] H. Bestougeff, C. Guilpin et M. Jacques, La technique informatique, Tome 2 : algorithmes

numeriques et non numeriques, ISBN 2-225-40337-6, Masson, Paris, 1975.

[6] N. Biggs, E. Lloyd et R. Wilson, Graph Theory 1736-1936, ISBN 0-19-853901-0, ClarendonPress Oxford, 1976.

[7] R. Cabane, Theorie des graphes, Techniques de l’Ingenieur, Traite Sciences fondamentales,document AF205.

[8] H. Coilland, Polycopie d’exercices de recherche operationnelle, IUT Informatique Nancy 2et Ecole des Mines de Nancy, juillet 1999.

[9] R. Diestel, Graph theory, Graduate Texts in Mathematics Series, vol. 173, electronicedition, http ://www.math.uni-hambourg.de/home/diestel/books/graph.theory, Springer-Verlag, New York 1997, 2000,

[10] F. Droesbeke, M. Hallin et C. Lefevre, Les graphes par l’exemple, ISBN 2-7298-8730-X,Ellipses, 1987.

[11] N. Deo, Graph theory with applications to engineering and computer science, Prentice-Hall,Englewood cliffs (N.J.),1975.

[12] L. Euler, Solutio Problematis Ad geometriam Situs Pertinentis, Commenrarii Academiae

Scientiarum Imperialis Petropolitanae, 8, pp. 128-140, 1736.

[13] M. Gondran et M. Minoux,Graphes et algorithmes, 2eme ed., Collection de la Direction desEtudes et Recherches d’Electricite de France, Eyrolles 1985.

[14] M. Minoux et G. Bartnik, Graphes, algorithmes, logiciels, Dunod Informatique, ISBN 2-04-016470-7, Bordas Paris, 1986.

[15] Roseaux, Exercices et problemes resolus de recherche operationnelle. Tome 1. Graphes :

leurs usages, leurs algorithmes, ISBN 2-10-003935-0, Dunod, Paris, 1998.

55