Embed Size (px)
Citation preview
Théorie des graphes : le problème du pluscourt chemin.
Mathieu KLIMCZAK , Paul Marius NKENG BAKOUYAC
4 mai 2008
Table des matières
1 Les graphes et l’algorithmique : généralités. 31.1 Les graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.2 Le degré d’un sommet. . . . . . . . . . . . . . . . . . . . 41.1.3 Parcours et chaînes. . . . . . . . . . . . . . . . . . . . . . 5
1.2 L’algorithmique. . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.1 Actions de base. . . . . . . . . . . . . . . . . . . . . . . 71.2.2 Convergence et compléxité d’un algorithme. . . . . . . . 9
2 Calculs de distances. 112.1 De la verdure : arbres et forêts. . . . . . . . . . . . . . . . . . . . 112.2 Calcul des distances et plus court chemin. . . . . . . . . . . . .. 13
2.2.1 Calcul des distances. . . . . . . . . . . . . . . . . . . . . 132.2.2 Le plus court chemin : l’algorithme de Dijkstra. . . . . .. 15
2.3 Le pourquoi du comment, les matroïdes. . . . . . . . . . . . . . . 18
3 Annexe : trace des algorithmes. 213.1 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 213.2 Trace de l’algorithme de Dijsktra. . . . . . . . . . . . . . . . . . 26
1
Introduction.
Commentn travaux peuvent-ils être donnés àn personnes afin d’être le plusefficace possible ? Dans quel ordre un vrp doit-il visiter lesvilles pour minimi-ser le temps de trajet ? Pouvons-nous colorier chaque pays d’une carte de façon àce que deux pays voisins ne reçoivent pas la même couleur ? Tout ces problèmespeuvent être modélisés par la théorie des graphes. La théorie des graphes est unepartie des mathématiques qui a connue une très grande activité depuis environ unecinquantaine d’années. De nouveaux et profonds théorèmes ont été démontrés etde nombreuses conjectures résistent encore. Ce TIPE traited’une partie en parti-culier, le problème du plus court chemin : dans un graphe, quel est le plus courtchemin pour relier deux points ? Quelle définition donner à "plus court" ? Dansune première partie, nous traiterons des généralités sur les graphes et l’algorith-mique, une composante de la théorie des graphes. La deuxièmeparite sera desti-née au problème du plus court chemin et en particulier à l’algorithme de Dijkstra.Nous expliquerons aussi pourquoi cet algorithme marche avec l’introduction de lanotion de matroïde.
2
Chapitre 1
Les graphes et l’algorithmique :généralités.
Nous allons détailler ici la plus grande partie des définitions et théorèmes utilespar la suite. Cette partie pourrait ressembler à une liste delemmes et théorèmes,mais chacun aura son utilité.
1.1 Les graphes.
1.1.1 Définition.
Commençons directement par une définition.
Définition 1.1.0.1 (Graphe) Un graphe est un coupleG = (S, A) avecS unensemble non vide et fini etA ⊆ S × S. Les éléments deS sont appelés lessommets deG et ceux deA les arêtes deG. On dit que les sommetsx et y, quisont les extrémités de l’arêtee sont adjacents ou voisins dans le grapheG, et quee est incidente aux sommetsx ety.
Notation : L’ensemble des sommets (respectivement arêtes) deG est notéS(G) (respectivementA(G)).
On dira qu’un grapheG est fini si les ensembles de sommets et d’arêtes sontdes ensembles finis. Dans ce TIPE, on ne s’interessera qu’à ces ensembles.
La façon la plus naturelle de représenter un graphe est de dessiner des pointspour chaque sommet et de joindre deux de ces points par une ligne si ces deuxsommets forment une arête.
3
Au plan formel, un graphe est aussi un ensemble sur lequel on adéfini unerelation binaire, antiréflexive et symétrique. La structure graphe est donc particu-lèrement pauvre au premier abord. Mais on peut aussi associer à un grapheG desommetsx1, . . . , xn une matrice carréeM de dimensionn × n appelée matriced’adjacences du graphe dont les éléments valent 0 ou 1. La matriceM peut doncêtre définie par :
mij = 1 ssixi etxj sont voisins.
Exemple :
x2 x3
x1 x4
FIG. 1.1 – Matrice d’adjacence.
0 1 1 11 0 1 01 1 0 01 0 0 0
1.1.2 Le degré d’un sommet.
SoitG = (S, A) un graphe (non vide), l’ensemble des voisins d’un sommetv
deG est notéNG(v) ou N(v) s’il n’y a pas d’ambiguïté. En reprenant l’exemplede la figure 1.1 , on aN(x1) = {x2, x3, x4}.
Définition 1.1.0.2 (Degré d’un sommet)Le degréD(v) d’un sommetv est lenombre d’arêtes surv, il est égal au nombre de voisins dev.
4
Si tous les sommets d’un graphe ont le même degrék, alorsG estk-régulier.Concernant les degrés, nous possédons deux propriétés.
Propriété 1.1.0.1 (Propriétés de la somme des sommets)Pour tout grapheG =(S, A) :
1. la somme des degrés des sommets est égale au double du nombre d’arêtes.
2. le nombre de sommets de degré impair est pair.
Preuve : Montrons le point1) : Déterminer le degré d’un sommet revientà compter le nombre d’arêtes dont il est l’une des extrémités. Lorsqu’on fait lasomme des degrés d’un graphe, le comptage revient à compter exactement deuxfois chaque arête, d’où le résultat. Montrons maintenant lepoint 2) : D’après lapropriété1, un grapheG possède1
2
∑
v∈S D(v) arêtes, donc∑
v∈S D(v) est unnombre pair.�
1.1.3 Parcours et chaînes.
Définition 1.1.0.3 (Chaîne)Une chaînePn = (S, A) est un graphe dont on peutranger les sommets en une suite telle que tout sommet est adjacent à son prédé-cesseur et à son successeur, et uniquement à ceux-là, sauf lepremier et le dernierqui n’ont qu’un seul voisin.
Exemple :
b
b
b
b
b
x1
x2
x3
x4
x5
FIG. 1.2 – La chaîneP5.
Propriété 1.1.0.2 Pour une chaînePn on a :
1. |S| = n
2. |A| = n− 1
Lemme 1.1.0.1 (Lemme de la chaîne extraite.)S’il existe dans G un parcoursreliant deux sommetsx et y alorsx et y sont reliés par une chaîne de G dont lessommets et les arêtes sont des sommets et des arêtes du parcours.
5
bb bb
b
b
b
b
b
1
2
3 4 5
6
7
8
9
FIG. 1.3 – Parcours et chaîne
Remarque : il est tout à fait possible que la chaîne et le parcours soient égaux.Exemple :Un parcours possible pour aller de1 à5 est :
P (1, 5) = (1, 2, 7, 8, 9, 3, 6, 2, 3, 4, 5)
et de ce parcourt on peut en extraire une chaîneP ′ :
P ′(1, 5) = (1, 2, 3, 4, 5)
Preuve : Soit G un graphe etx et y deux sommets deG. Supposons un par-coursP dex à y, alors il existe un parcoursP ′ de longueur minimumh dont lessommets et les arêtes sont des sommets et des arêtes deP (on peut avoirP = P ′).Soit P ′ = (x0, x1, . . . , xh−1, xh) et deux indicesi et j tels que0 ≤ i ≤ j ≤ h ettels quexi etxj soient le même sommet de G.
Alors le parcoursP ′′ = (x0, x1, . . . , xi−1, xi, xj+1, . . . , xh−1, xh) obtenu à par-tir deP ′ en supprimant le parcours fermé entrexi etxj est encore un parcours dansG entrex ety dont les sommets et les arêtes sont des sommets et des arêtes deP ,strictement plus court queP ′, ce qui contredit le choix deP ′
Par conséquent lesxi avec1 ≤ i ≤ h sont tous différents et la suireP ′ définitune chaîne deG répondant aux conditions éxigées par l’énnoncé.�
Lemme 1.1.0.2 (Lemme des deux chaînes)S’il existe deux chaînes distinctes re-liant deux sommetsx ety d’un grapheG, alors ce graphe admet un cycle.
Définition 1.1.0.4 (Parcours)Un parcours dans un graphe est une liste ordonnéede sommets telle que deux sommets consécutifs soient adjacents. Un parcours dusommetx0 au sommetxf se noteP (x0, xf). Six0 = xf on parle alors de cycle.
Exemple :
6
bb bb
b
b
b
b
b
1
2
3 4 5
6
7
8
9
FIG. 1.4 – Parcours.Un parcours possible du sommet 1 à 9 estP (1, 9) = {1, 2, 6, 3, 9}.
La notion de parcours présente l’avantage de permettre de formaliser l’idéedynamique d’un déplacement à travers le graphe vu comme un réseau de com-munication : on parcourt des arêtes dans un ordre spécifié parla liste ordonnéedes sommets. Aucune contrainte n’est imposée sur les répétitions de sommets oud’arêtes (y compris sur les allers-retours :(a, b, a, b, a, b) est bien un parcours dansG si ab est une arête).
Une dernière définition, qui nous sera utile pour le 2e chapitre.
Définition 1.1.0.5 (Connexité)Un grapheG = (S, A) est connexe lorsque pourtoute paire{x, y} de ses sommets, il existe une chaîne reliantx ety.
1.2 L’algorithmique.
1.2.1 Actions de base.
L’algorithmique et le mot algorithmique dérivent du nom du mathématicienarabe AL KHAWARIZMI (Bagdad, IXe siècle). Un algorithme guide un proces-seur (exécutant) dans l’exécution d’une suite d’actions debase. Il existe plusieursaction de base dans un algorithme.
Comme action de base nous avons :
1. l’action affectation :
〈variable〉 ←− 〈expression〉
On évalue l’expression (membre droit) en fonction de la valeur des variablesqui y ont une occurrence, puis on affecte à la variable désignée la valeurrésultant de l’evaluation de l’expression.
7
2. l’action retourner :
retourner 〈expression〉
Retourner renvoie comme résultat d’une exécution de l’algorithme ou d’unefonction de l’algorithme la valeur de l’expression mentionnée après.
3. l’action conditionnelle :
si 〈condition〉 alors 〈instruction〉
L’instruction ne sera exécutée que si la condition demandéeest vérifiée.
4. l’instruction alternative :
si 〈condition〉 alors 〈instruction1〉 sinon 〈instruction2〉
Si la condition est vérifiée alors c’est intruction1 qui seraexécutée, dans lecas contraire, ce sera instruction2.
5. l’instruction répétitive :
tant que 〈condition〉 faire 〈instruction〉
L’instruction sera exécutée aussi longtemps que la condition sera vérifiée,l’instruction répétitive est aussi appelée plus communément une boucle. Lapartie instruction est le corps de la répétitive.
6. la séquence :
〈 instruction1, instruction2, instruction3, . . . 〉
Toutes ces actions de base sont ce que l’on appelle des mots réservés, c’est àdire qu’ils ne peuvent pas être utilisés dans un algorithme avec une autre significa-tion que celle déjà appliquée. Par exemple, on ne pourra pas nommer une variable"sinon".
Grâce à ces actions de base on peut définir des fonctions.
Définition 1.2.0.6 (Fonction.) Une fonction est une suite d’actions de base àl’intérieur même de l’algorithme. Elle se termine le plus souvent par l’actionretourner.
8
1.2.2 Convergence et compléxité d’un algorithme.
Lorsqu’un algorithme possède plusieurs répétitives, il convient de montrer quecelles ci convergent, c’est à dire que pour toutes valeurs autorisées de données,leur exécution ne réclamera qu’un nombre fini d’exécutions d’actions de base.La suite de Syracuse, par exemple, est un bon exemple des problèmes de conver-gences. On peut la définir comme tel : on choisit un nombreN ∈ N et l’on poseN = u0, on lui applique alors de façon récursive :
un+1 =
{
un
2si un pair
3un + 1 si un impair
Une conjecture (la conjecture de Collatz) affirme que pour toutN > 0 il existeun rangn pour lequelun = 1. On dit alors que la suite de Syracuse a convergé.Mais, actuellement, aucun mathématicien n’est en mesure deprouver cette conjec-ture pour toutu0 dansN. Paul Erdös a même affirmé : "les mathématiques ne sontpas encore faites pour de tels problèmes".
Il est donc nécéssaire que pour chaque répétitive, une expressions qui, comptetenue de l’évolution des valeurs des variables qui y ont une occurence, ne puisseprendre au cours de l’exécution qu’une suite de valeurs nécéssairement finie (même0 valeurs).
On en arrive alors au problème de la production effective d’une solution à unproblème : pour qu’un algorithme converge, il faut que les calculs qu’il doit effec-tuer soient en nombre fini. Une estimation de ce nombre de calcul est obligatoirepour savoir combien de temps va durer l’exécution de l’algorithme : 1 minute ?1 mois ? 1 an ? Le nombre fini de calculs élémentaires est en général une fonc-tion croissante de la taille des données. On parle alors d’analyse au sens du plusmauvais cas, et on entre dans les problèmes de compléxité, unalgorithme de com-pléxitéO(n2) signifie que son temps d’exécution pourn données sera de l’ordreden2, il existe de grande familles d’algorithme :
– Les algorithmes de classe P, un algorithme est dans P s’il peut être exécutésur une machine de façon deterministe en un temps polynominial, c’est àdire en un temps de compléxitéO(nk) pour unk donné. Le mot déterministesignifie ici que le temps d’exécution de l’algorithme dépenddu point dedépart : l’algorithme peut converger plus rapidement selonque l’on part dupoint a ou b. En général, les algorithmes en P sont ceux qui convergent leplus rapidement.
– Les algorithmes de classe NP, contrairement aux apparences, le N de NPne signifie pas "Non" mais "Non déterministe". Un algorithmeNP a besoind’évaluer toutes les solutions possibles pour converger, quelque soit sonpoint de départ. Intuitivement, un algorithme dans NP est unalgorithmequi énumère l’ensemble des solutions possibles et les testeà partir d’un
9
algorithme polynominial.S’il existe un algortithme pour résoudre un problème, on ditalors que ce pro-
blème est décidable. On sait de plus queP ⊂ NP mais on ne sait pas démontrerle sens contraireNP ⊂ P . Ce problème :P = NP est l’un des septMilleniumPrize Problemsde mathématiques distingués par leClay Instituteen mai 2000.
10
Chapitre 2
Calculs de distances.
2.1 De la verdure : arbres et forêts.
Les arbres et les forêts sont des éléments importants de la théorie des graphes.En effet la plupart des graphes utilisés dans la pratique sont des arbres, par exempleen informatique ou l’on peut représenter un réseau hiérarchisé sous cette forme.Donnons une définition d’une forêt et d’un arbre.
Définition 2.1.0.7 (Forêt) Soit un grapheG = (S, A), G est appelé une forêt s’ilest acyclique.
Définition 2.1.0.8 (Arbre) Un arbre est une forêt connexe.
FIG. 2.1 – Arbre.
Ainsi avec ces deux définitions, on peut dire qu’une forêt estun graphe dontles composants sont des arbres. Les sommets de degré 1 sont appelés les feuillesd’un arbre. Tout arbre possède au moins une feuille, pour s’en convaincre on peut
11
par exemple considérer le sommet final du plus long chemin. Unautre fait trèsutile, si nous retirons une feuille d’un arbre, ce qui reste est encore un arbre.
Théorème 2.1.1Les propositions suivantes sont équivalentes.SoitT un graphe, alors :
1. T est un arbre.
2. Quel que soient deux sommets deT , ils sont liés par une seule et uniquechaîne.
3. T est de connexité minimale, c’est à dire queT est connexe maisT − e nel’est plus quel que soit l’arêtee deT .
4. T est acyclique de façon maximale, c’est à dire queT ne contient aucuncycle maisT + xy en contient un quel que soit les deux sommets non adja-centsx ety deT .
Preuve : Montrons1) ⇒ 2) : PuisqueT est un arbre, il est connexe, alorspour toute paire de sommersx et y de T , il existe dansT au moins une chaîned’extrémitésx ety. L’unicité découle du Lemme des deux chaînes 1.1.0.2.
Montrons2) ⇒ 3) : Soit x et y deux sommets deT ils sont alors reliés parune seule est unique chaîne, soitxi, xi+1 deux sommets de la chaîne reliantx ety tels quexi, xi+1 soient adjacents, alors en supprimant l’arêtexixi+1, il n’existeplus de chaînes reliantx ety, T est donc bien de connexité minimale.
Montrons que3) ⇒ 4) : Soit x et y deux sommets non adjacents deT , T estconnexe donc il existe une chaînePx→y reliantx et y, en rajoutant l’arêteyx à lachaînePx→y, on crée un cycle.
Montrons4)⇒ 1) : Soitx ety deux sommets non adjacents deT , alorsT +xy
contient un cycle dontxy ert nécessairement un arête. En supprimant l’arêtexy
de ce cyle, on obtient une chaîne deT d’extrémitésx ety. DoncT est connexe etacyclique, c’est un arbre.�
Définition 2.1.1.1 (Arborescence)SoitG un graphe, l’arborescence deG est leplus petit nombre de forêts (graphes acycliques) formant une partition deG.
Propriété 2.1.1.1 Une forêt ayantk arête possède|S| − k arbres.
Preuve : Partons d’une forêt de|S| arbres contenant chacun 1 sommet et0arête. Chaque arête ajoutée à la forêt réduit d’une unité le nombre d’arborescence,il n’y a donc plus que|S| − 1 arbres. Par récurrence, on l’établit pourk arêtes.�
l’interêt porté aux arbres est dû au fait de leur simplicité,aucun cycle et tous lessommets sont connexes. Les arbres sont aussi utiles pour simplifier des réseaux,
12
prenons un exemple : des spéléologues veulent sécuriser la circulation dans unréseau de grottes souterraines reliées par des galeries. Leréseau est assez com-plexe pour qu’en général plusieurs itinéraires permettentde passer d’une grotte àl’autre. Il n’est donc pas nécessaire que chaque galerie soit sécurisée pour qu’ilexiste toujours entre deux grottes au moins un itinéraire sécurisé. De cet exemplerelativement simple, en peut en sortir la définition de sous graphe couvrant.
Définition 2.1.1.2 (Sous graphe couvrant)Le sous graphe couvrant d’un grapheG = (S, A) est un sous grapheG′ = (S, A′), c’est à dire un sous graphe dont sontsommets tous les sommets deG.
Il est encore plus interessant de connaître la définition d’arbre couvrant : unarbre couvrant est un sous graphe couvrant qui est un arbre. Beaucoup de pro-blèmes en théorie des graphes se ramènent à trouver un arbre couvrant. Maiscomment savoir si l’on peut trouver un arbre couvrant ? Avec le théorème suivant.
Théorème 2.1.2Tout graphe connexe contient un arbre couvrant.
Ainsi finalement dans tout graphe connexe, on peut en extraire en arbre cou-vrant.
2.2 Calcul des distances et plus court chemin.
2.2.1 Calcul des distances.
Prenons le métro parisien ; vous êtes à une stationa et vous souhaitez vousrendre à une stationb ; quelles rames prendre pour minimiser le temps en métro ?En terme de graphes : quel est le plus court chemin pour rejoindre deux sommets ?Le problème du plus court chemin est un des thèmes de la théorie des graphes surlequel de nombreux mathématiciens ont travaillé. On peut citer pour l’exempleEdsger Wybe DIJKSTRA (1930-2002), mathématicien et informaticien néerlan-dais. Dans cette section, nous nous intéresserons à son algorithme pour le calculdu plus court chemin dans un graphe.
Mais avant toutes choses, donnons la définition d’une distance dans un graphe.
Définition 2.2.0.1 (Distance)La distance entre 2 sommets d’un graphe G connexeest la longueur minimum d’une chaîne de ce graphe admettant ces 2 sommetscomme extrémités. Six et y ne sont pas connexes alors on pose par conventiondG(x, y) = d(x, y) =∞.
Une distance dans un graphe est définie par 3 propriétés :
13
1. d(x, y) = 0⇐⇒ x = y
2. d(x, y) = d(y, x)
3. d(x, y) ≤ d(x, z) + d(z, y)
La troisième propriété découle du Lemme de la chaîne extraite 1.1.0.1 : ladistanced(x, y) entrex ety étant minimale, on ne peut qu’allonger cette distanceen passant par un point intermédiaire.
On peut ainsi, dans un graphe, définir la distance de chaque sommet par rap-port à un sommet fixé (le sommet source). l’algorithme suivant permet de donnerla distance entre deux sommets.
Données: Un grapheG = (S, A) et un sommeta deG
Résultat : Une fonctiond telle que pour tout sommetx deG on aitd(x) = dG(a, x).
pour tout sommetx deG faire1
d(x)←∞2
d(a)← 03
fin4
tant que il reste des sommetst non marqués tels qued(t) 6=∞ faire5
parmis les sommets non marqués, choisir un sommetx qui minimise la6
fonctiond.pour tout voisiny du sommetx vérifiantd(y) =∞ faire7
d(y)← d(x) + 18
fin9
marquer le sommetx.10
fin11
retournerd.12
Algorithme 1 : Calcul des distances.
Pour comprendre cet algorithme nous en donnerons une trace dans la sectionannexe, c’est à dire une repésentation graphique.
14
2.2.2 Le plus court chemin : l’algorithme de Dijkstra.
L’algorithme "Calcul des distances" vu dans la partie précédente marche trèsbien, mais il ne nous assure pas que l’on ait le plus court chemin. L’algorithmede Dijkstra lui, nous donne à coup sûr le plus court chemin en un sommet et lesommet source. Il utilise le fait que la portionu, v d’un plus court cheminu, z
doit être le plus court chemin deu, v. Mais pour que l’algorithme de Dijkstrafonctionne, il faut que les arêtes du graphe soient valuées.
Définition 2.2.0.2 (Valuation) Un grapheG est valué aux arêtes (respectivementsommets) lorsqu’on attribue à chaque arête (respectivement sommet) du grapheune valeur prise dans un ensemble préalablement spécifié.
Pour travailler avec l’algorithme de Dijkstra, on ne valuera que les arêtes, onnotew(e) ouw(xy) la valuation de l’arêtee = xy.
La valuationw(P ) d’une chaîneP est la somme des valuations de chacunesde ses arêtes.
On peut alors donner une nouvelle définition de la distance :
Définition 2.2.0.3 (Distance)La distance entre 2 sommets d’un graphe valué estla valuation minimum d’une chaîne ayant ces deux sommets pour extrémités, soit :
dG,w(x, y) = min{w(P )|P est une chaîne deG d’extrémitésx ety}
Comment marche l’algorithme de Dijkstra ? L’idée est de créer un ensembleSD des sommets dont le plus court chemin depuis un sommet sourcea est connu etde l’élargir jusqu’à contenir tous les sommets. Pour faire cela, on crée une distancet(x) de a vers chaquex 6∈ SD, t(x) étant la longueur du plus court chemina, x
trouvé. Pour calculer les distances, l’algorithme de Dijkstra fait ça de manièregloutonne, c’est à dire qu’il fait toujours les choix qui luisemble le meilleur surle moment. autrement dit, il fait un choix localement optimal dans l’espoir que cechoix mènera à une solution globalement optimale. Un théorème que nous verronsplus tard nous l’assurera, mais concentrons nous maintenant sur cet algorithme.
15
Données: Un grapheG = (S, A) dont les arêtes sont valuées par unefonctionw positive ou nulle et un sommet sourcea deG.
pour tout sommetx deG faire1
t(x)←∞2
t(a)← 03
fin4
pour tout voisinx du sommeta faire5
t(x)← w(a, x)6
fin7
marquer le sommeta.8
tant que il reste des sommetsz non marqués tels quet(z) 6=∞ faire9
parmi les sommets non marqués, choisir un sommetx qui minimise la10
fonctiont.pour tout voisin non marquéy du sommetx faire11
t(y)← min(t(y), t(x) + w(x, y))12
fin13
marquerx14
fin15
retournert.16
Algorithme 2 : Distance de Dijkstra.
La complexité temporelle de l’algorithme de Dijkstra sous cette forme estO(n2). En effet, à chaque étape, on transfère un sommet deS versSD, ce quinous faitn itérations. A l’intérieur de chaque itération, on recherche le sommet deS qui possède la plus petite distance temporaire, opération en O(n) dans le piredes cas,n étant le nombre de sommets.
Afin de mieux le comprendre, nous en donnerons aussi une traceen annexe.Maintenant que nous savons comment marche l’algorithme de Dijkstra, le
théorème suivant nous assure sur le fait que nous obtenons à chaque fois le pluscourt chemin entre un sommet deG et le sommet source.
Théorème 2.2.1Etant donné un grapheG = (S, A) et un sommeta ∈ S(G),l’algorithme de Dijkstra donned(a, x) = t(x) ∀x ∈ S(G).
Preuve :Nous allons démontrer ce théorème par récurrence, on base larécur-rence surk = |SD| = Card(SD) et l’on prouve à chaque itération que :
1. ∀x ∈ SD, t(x) = d(a, x)
2. ∀y 6∈ SD, t(x) est la plus courte distance d’un chemina, y relianty àSD.
Si k = 1, alorsSD = {a} etd(a, a) = t(a) = 0 et la plus courte distance d’unchemina, x reliantx àSD estt(x) = w(a, x), qui est infinie quandax 6∈ A(G).
16
On suppose maintenant que quand|SD| = k, 1) et 2) sont vraies. Soitv unsommet desx 6∈ SD tel quet(x) soit minimisé, l’algorithme de Dijkstra choisiealorsv etS ′
D = SD ∪ {v}.On montre d’abord qued(a, v) = t(v). Un plus court chemin dea à v doit
sortir deSD avant de rencontrerv. L’hypothèse de récurrence établit que la lon-gueur du plus court chemin allant dev à SD estt(v). L’hypothèse de récurrenceet le choix dev nous garantissent aussi qu’un parcourt visitant n’importequelsommet hors deSD et plus tard rencontrantv est au moins de longueurt(v), ainsid(a, v) = t(v) et1) satisfaitS ′
D.Montrons que2) satisfaitS ′
D. Soit z un sommet hors deSD autre quev, parhypothèse, le plus court chemina, z reliantz àSD a comme longueurt(z). Quandnous ajoutonsv à SD, nous devons aussi considérer les chemins reliantz à v.Depuis que nous avons poséd(a, v) = t(v), le plus court chemin a alorst(v) +w(v, z) comme longueur, et nous la comparons avec la valeur précédente det(z)pour trouver le plus court chemin reliantz à S ′
D, ainsi t(z) = min{t(z), t(v) +w(v, z)}.
Donc1) et2) satisfont le nouvel ensembleS ′
D d’ordrek + 1. Ce qui complètela récurrence et prouve le théorème.�
L’algorithme de Dijkstra travaille sur des graphes connexes (il peut aussi tra-vailler sur des graphes qui ne le sont pas, mais alors la distance entre deux som-metsx ety non connexes est∞, distance n’étant pas "très courte"), les plus courtschemins entre deux sommetsx et y dans un graphe connexe sont des chaînes.Si l’on arrivait à rejoindrex et y par une autre chaîne, alors la longueur de ladeuxième chaîne serait plus importante que celle de la première, ce qui contre-dirait l’algorithme de Dijkstra car à ce moment là Dijkstra ne renverrait plusd(a, x) = t(x) ∀x ∈ S(G). Il n’y a donc qu’un seule et unique chaîne reliant deuxsommets sommets après l’application de l’algorithme de Dijsktra à un grapheG.
Théorème 2.2.2Soit G = (S, A) un graphe connexe esta un sommet deG,l’algorithme de Dijkstra appliqué à ce graphe à partir du point a retourne unarbre couvrant.
Preuve : Soit G un graphe eta un sommet deG, supposons que pour unsommetx de G, il existe une chaîne reliantx et a de longeurt′(x) < t(x). Orl’algorithme de Dijkstra donned(a, x) = t(x) ∀x ∈ S(G). Il n’existe donc pas dechaîne de plus courte longueur que celle donnée par l’algorithme de Dijkstra. Iln’existe donc qu’une et une seule chaîne relianta et un sommetx, l’algorithme deDijkstra renvoie donc un graphe connexe, dont chaque sommets ne sont reliés quepar une unique chaîne. Donc l’algorithme de Dijkstra renvoie un arbre en vertuede la propositions 2 du théorème 2.1.1.�
17
Nous sommes donc maintenant sûr que même si l’algorithme de Dijkstra faitun choix optimal localement, globalement, ce choix est aussi optimal.
Mais si l’algorithme de Dijkstra marche aussi bien, c’est qu’il y a une rai-son sous jacente. En effet, les graphes satisfont une structure combinatoire pourlaquelle les algorithmes gloutons marchent très bien : les matroïdes.
2.3 Le pourquoi du comment, les matroïdes.
Il existe une théorie sur les algorithmes gloutons, que nousallons ébaucherici. Cette théorie est utile pour déterminer les situationsoù la méthode gloutonneaboutit à des solutions optimales. Elle s’appuie sur des structures combinatoiresconnues sous le nom de matroïde.
Définition 2.3.0.1 (Fammille héréditaire) Une famille héréditaire est une col-lection d’ensembleF telle que tout sous ensemble d’un ensembleF est aussi dansF . Un ensemble héréditaireM surE consiste en une famille héréditaire non videHM de sous ensemble deE. Les éléments d’une famille héréditaire sont appelésdes éléments indépendants.
Définition 2.3.0.2 (Matroïde) Un matroïde est un coupleM = (E, I) qui vérifieles conditions suivantes :
1. E est un ensemble fini non vide.
2. I est une famille héréditaire
3. SiF ∈ I, H ∈ I et |F | < |H|, alors il existe un élémentx ∈ H − F telqueF ∪ {x} ∈ I, on dit queM vérifie la propriété d’échange.
Ces deux définitions sont bien jolies, mais vous me direz : "quel est le rapportavec les graphes ?". Et bien le voici :
Théorème 2.3.1SiG = (S, A) est un graphe non orienté, alorsMG = (EG, IG)est un matroïde.
Preuve : On aEG = A est un ensemble fini. De plusIG est héréditaire puis-qu’un sous ensemble d’une forêt est une forêt (supprimer desarêtes dans un en-semble d’arêtes acyclique ne crée pas de cycle).
Il reste donc à montrer queMG vérifie la propriété d’échange. SoitGF =(S, F ) estGH = (S, H) des forêts deG telles que|F | < |H| : F et G sontdes ensembles acycliques etH contient plus d’arêtes queF . On sait qu’une forêtayantk arêtes contient|S| − k arbres, doncGF contient|S| − |F | arbres etGH
18
contient|S| − |H| arbres. CommeGH possède moins d’arborescences queGF ,elle doit contenir une arborescenceT dont les sommets se trouvent dans au moins2 arborescences différentes deGF . Par ailleurs, commeT est connexe, elle doitcontenir une arête(uv) telle que les sommetsu etv soient dans des arborescencesdifférentes deGF , donc(uv) peut être assoiciée àGF sans créer de cycles : lapropriété d’échange est vérifiée.�
On vient de montrer que les graphes sont un type de matroïde, il serait main-tenant interessant de savoir comment fonctionne un algorithme glouton sur unmatroïde.
Définition 2.3.1.1 (Extension)Etant donné un matroïdeM = (E, I), on ditqu’un élémentx 6∈ F est une extension deF ∈ I si x peut être ajouté àF enpréservant l’indépendance. Autrement dit,x est une extensionF si F ∪ {x} ∈ I.On dit queF est maximal s’il ne possède aucune extension.
Un algorithme glouton fonctionne donc par extension. Il part d’un ensemblehéréditaireF et regarde tous les élémentsx 6∈ F , si F ∪ {x} est héréditaire, ilcrée alors le nouvel ensembleF ′ = F ∪ {x} et recommence, jusqu’à obtenir unensemble héréditaire maximal.
On dit qu’un matroïdeM = (E, I) est pondéré si l’on dispose d’une fonctionde pondérationw qui affecte un poids strictement positifw(x) à chaque élémentx ∈ E, la fonction de pondération s’étend aux sous ensembles deE par somma-tion :
w(F ) =∑
x∈F
w(x)
Finalement, un algorithme glouton cherche un sous-ensemble indépendant depoids maximal dans un matroïde pondéré. Autrement dit, on dispose d’un ma-troïde pondéréM = (E, I) et on souhaite trouver un ensemble indépendantF ∈ I pour lequelw(F ) est maximisé. Un tel sous ensemble à pondération maxi-male est appelé sous ensemble optimal du matroïde.
Bien sûr, le mot "maximisé" n’est qu’un terme mathématique.Dans le contextequi nous intéresse, en l’occurence le plus court chemin, la fonction de pondérationaffectant des distances, on cherche plutôt à minimiser les distances (à "maximiserla plus courte distance"), et donc à minimiser la pondération du sous ensembleoptimal.
Le lemme est le théorème suivant montrent que les algorithmes glouton sonun bon choix pour un matroïde.
Lemme 2.3.1.1 (Les matroïdes vérifient la propriété du choixglouton) SupposonsqueM = (E, I) soit un matroïde pondéré associé à la fonction de pondération w
19
et queE soit trié par ordre de poids décroissant. soitx le premier élément deEtel que{x} soit indépendant, s’il existe un telx. Six existe, alors il existe un sousensemble optimalF deE qui contientx.
Preuve : Si un telx n’existe pas, alors le seul sous ensemble indépendant estl’ensemble vide{∅} et la démonstration est terminée. Dans le cas contraire, soitH un sous ensemble de non vde optimal. On suppose quex 6∈ H ; si tel n’étaitpas le cas, on feraitF = H et la démonstration s’arêterait là.
Aucun élément deH n’a un poids suppérieur àw(x). Pour le voir, il suffitd’observer quey ∈ H implique de{y} est indépendant, puisqueH ∈ I et I esthéréditaire.
L’ensembleF se construit de la manière suivante. On commence avecF ={x}. Grâce au choix dex, F est indépendant. En se servant de la propriété d’échange,on trouver itérativement un nouvel élément deH pouvant être ajouté àF jus-qu’à ce que|F | = |H|, tout en préservant l’indépendance deF . alors F =H − {y} ∪ {x} pour un certainy ∈ H, et donc
w(F ) = w(H)− w(y) + w(x)
≥ w(H)
CommeH est optimal,F l’est forcément aussi ; et commex ∈ F , le lemmeest démontré.�
Théorème 2.3.2 (Validité de l’algorithme glouton sur les matroïdes) Si M =(E, I) est un matroïde pondéré de fonction de pondérationw, alors l’appel d’unalgorithme glouton retourne un sous ensemble optimal.
20
Chapitre 3
Annexe : trace des algorithmes.
3.1 Trace de l’algorithme "Calcul des distances".
21
qp qp
qp
qp
qp
qp
qpqp
q
g, (∞) h, (∞)
b, (1)
a, (0)c, (1)
d, (∞)e, (1)
f, (1)
i, (∞)
FIG. 3.1 – Trace de l’algorithme "Calcul des distances".a minimise la fonctiond, à chaque voisiny dea, on lui affecte la distanced(y) =d(a) + 1 = 1. On marquea.
qp qp
qp
qp
qp
qpqp
q
q
g, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (∞)e, (1)
f, (1)
i, (∞)
FIG. 3.2 – Trace de l’algorithme "Calcul des distances".c’est maintenantb qui minimise la fonctiond, à chaque voisiny ded, on lui affectela distanced(y) = d(d) + 1 = 2. On marqueb.
22
qp qp
qp
qp
qpqp
q
q
q
g, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (∞)
FIG. 3.3 – Trace de l’algorithme "Calcul des distances".
qp qp
qp
qp
qpqp
q
q
q
q
g, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (2)
FIG. 3.4 – Trace de l’algorithme "Calcul des distances".
23
qp qp
qp
qpqp
q
q
q
q
q
g, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (2)
FIG. 3.5 – Trace de l’algorithme "Calcul des distances".
qp qp
qp
qp
q
q
q
q
q
q
g, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (2)
FIG. 3.6 – Trace de l’algorithme "Calcul des distances".
24
qp qp
q
q
q
q
q
q
q
g, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (2)
FIG. 3.7 – Trace de l’algorithme "Calcul des distances".
qp
q
q
q
q
q
q
q
qg, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (2)
FIG. 3.8 – Trace de l’algorithme "Calcul des distances".
25
q
q
q
q
q
q
q
q qg, (2) h, (2)
b, (1)
a, (0)c, (1)
d, (2)e, (1)
f, (1)
i, (2)
FIG. 3.9 – Trace de l’algorithme "Calcul des distances".
3.2 Trace de l’algorithme de Dijsktra.
Les sommets losanges sont à une distanced = ∞ de a, les sommets à unedistance finie dea sont les pentagones blancs et les sommets marqués par l’algo-rithme sont les pentagones noirs.
qp
qp
qp
qp
ld
ld
ld ld
q
f g
e, (1)
am, (5)
cb, (2)
h, (4)
k
1
6 3
15
2
4
2
1
3
2
FIG. 3.10 – Trace de l’algorithme de Dijkstra.Fin de l’itération 1.m, b, h, e deviennent à distance finie dea. a est marqué.
26
qp
qp
qp
qp qp
ld
ld
q
q
f, (7) g, (4)
e, (1)
am, (5)
cb, (2)
h, (4)
k
1
6 3
15
2
4
2
1
3
2
FIG. 3.11 – Trace de l’algorithme de Dijkstra.Fin de l’itération 2.f, g deviennent à distance finie dea. e est marqué.
qp
qp
qp qp
qp
qp
q
q
q
f, (7) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
1
6 3
15
2
4
2
1
3
2
FIG. 3.12 – Trace de l’algorithme de Dijkstra.Fin de l’itération 3.k, c deviennent à distance finie dea. La valeur ded(h) achangé lors de l’itération.b est marqué.
27
qp
qp qp
qp
qp
q
q
q
q
f, (7) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
1
6 3
15
2
4
2
1
3
2
FIG. 3.13 – Trace de l’algorithme de Dijkstra.Fin de l’itération 4.h est marqué.
qp
qp
qp
qp
q
q
q
q
qf, (5) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
1
6 3
15
2
4
2
1
3
2
FIG. 3.14 – Trace de l’algorithme de Dijkstra.Fin de l’itération 5.La valeur ded(f) a changé.g est marqué.
28
qp
qp
qp
q
q
q
q
q
q
f, (5) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
1
6 3
15
2
4
2
1
3
2
FIG. 3.15 – Trace de l’algorithme de Dijkstra.Fin de l’itération 6.c est marqué.
qp
qp
q
q
q
q
q
q
qf, (5) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
1
6 3
15
2
4
2
1
3
2
FIG. 3.16 – Trace de l’algorithme de Dijkstra.Fin de l’itération 7.f est marqué.
29
qp
q
q
q
q
q
q
q
q
f, (5) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
1
6 3
15
2
4
2
1
3
2
FIG. 3.17 – Trace de l’algorithme de Dijkstra.Fin de l’itération 8.m est marqué.
q
q
q
q
q
q
q
q
q
f, (5) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
2
1
6 3
15
2
4
2
1
3
FIG. 3.18 – Trace de l’algorithme de Dijkstra.Fin de l’itération 9.k est marqué.
30
q q
q
q
q
f, (5) g, (4)
e, (1)
a, (0)m, (5)
c, (4)b, (2)
h, (3)
k, (5)
2
1
3
15
2
1
3
FIG. 3.19 – Arbre couvrant résultant de l’algorithme de Dijkstra.
31
Conclusion
L’algorithme de Dijkstra exposé est un outil simple mais pourtant très utile. Ilest utilisé dans de nombreux domaines tels que les réseaux : Internet utilise unevariante de cet algorithme pour les routages IP connu sous lenom de protocoleOSPF. Malgré cela, l’algorithme de Dijkstra possède des faiblesses : les arêtesdoivent être valuées de façon positive, si les valuations sont négatives, l’algo-rithme de Dijkstra n’est pas utile. Mais dans la pratique L’algorithme de Dijkstrareste le plus utilisé (SNCF, métro, informatique...)
32
Bibliographie
[1] Douglas B. WEST. Introduction to graph Theory. Prentice Hall, 2001.
[2] Reinhard DIESTEL. Graph theory. Springer, 2005.
[3] Olivier COGIS et Claudine ROBERT. Théorie des graphes. Vuibert, 2003.
[4] Thomas H. CORMEN, Charles E. LEISERSON, Ronald L. RIVEST, CliffordSTEIN. Introduction à l’algorithmique. Dunod, 2002.
[5] Christeine FROIDEVAUX, Marie-Claude GAUDEL, Michèle SORIA. Types dedonnées et algorithmes. Ediscience international.
33
Table des figures
1.1 Matrice d’adjacence. . . . . . . . . . . . . . . . . . . . . . . . . 41.2 La chaîneP5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Parcours et chaîne . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Parcours. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Arbre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 223.2 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 223.3 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 233.4 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 233.5 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 243.6 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 243.7 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 253.8 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 253.9 Trace de l’algorithme "Calcul des distances". . . . . . . . .. . . 263.10 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .263.11 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .273.12 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .273.13 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .283.14 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .283.15 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .293.16 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .293.17 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .303.18 Trace de l’algorithme de Dijkstra. . . . . . . . . . . . . . . . . .303.19 Arbre couvrant résultant de l’algorithme de Dijkstra.. . . . . . . 31
34
