Sommaire

Introduction
Définitions
Chaînes et cycles eulériens
Chaînes et cycles hamiltoniens
Sous-graphe et graphe partiel
Nombre chromatique d’un graphe
Matrice associée – graphe non-orienté
Matrice associée – graphe orienté
Graphes pondérés
Graphes probabilistes
Algorithme de Dijkstra
Exercices

Introduction

Dans ce chapitre, nous allons parler des différents graphes, de leurs propriétés ainsi que des algorithmes relatifs aux graphes (notamment celui de Dijkstra).
Nous verrons es diverses applications concrètes de la théorie des graphes tout au long du chapitre.

Comme il y a de nombreuses notions nouvelles avec un vocabulaire spécifique, nous commencerons par cela.

Définitions

Haut de page

Tout d’abord, qu’est-ce-qu’un graphe ??

Un graphe est composé de points appelés sommets ou nœuds. Certains de ces points sont reliés entre eux par des arêtes. Ces arêtes sont souvent représentées par des segments mais elles peuvent très bien être courbes.
Exemples de graphes :

La couleur n’a aucune importance, c’est juste pour distinguer le fait qu’il y ait 2 graphes différents.
L’arête entre P et H n’est pas droite mais courbe : c’est tout à fait possible, rien ne l’interdit ! (c’est même mieux pour certains graphes avec de nombreuses arêtes comme on le verra plus loin).

Comme tu le vois, les sommets sont nommés par des lettres pour qu’ils soient identifiables.
Les arêtes en revanche sont nommées par rapport aux 2 points qu’elle relie. L’arête entre A et B peut être notée (A;B) ou (B;A).
Mais on peut très bien nommer les arêtes par des lettres (souvent en minuscule pour ne pas confondre avec les sommets), voire leur attribuer une valeur : c’est ce que nous verrons dans les graphes pondérés en fin de chapitre.

Un peu de vocabulaire à présent :

—
Le nombre de sommets du graphe appelé l’ordre du graphe.
Le degré d’un sommet est le nombre d’arêtes reliées à ce sommet.
—

Ainsi, l’ordre du graphe de gauche ci-dessus est 4, celui du graphe de droite est 3 (pas trop compliqué ).

Dans le graphe de gauche, le degré du sommet A est 1, le degré du sommet B est 3, C et D sont quant à eux de degré 2.

—
ATTENTION à ne pas confondre les notions d’ordre et de degré !
—

Un graphe est dit connexe s’il n’y a pas de point isolé :

Le graphe de droite n’est pas connexe car le sommet D est isolé.

Il existe également des graphes orientés, c’est-à-dire que les arêtes ont un sens
Par exemple :

Sur ce graphe, on peut passer de A à B mais pas de B à A. Ainsi l’arête (A;B) existe mais pas l’arête (B;A) : dans le cas d’un graphe orienté on peut alors parler d’arc, en mettant d’abord le sommet de départ.
Ainsi, comme on peut aller de A à B mais pas de B à A, on parle de l’arc AB (l’arc BA n’existe pas).
Par contre on peut aller de A à D et de D à A : on a mis deux flèches sur la même arête mais on peut très bien faire une arête pour chaque sens, on parle alors d’arcs doubles :

Ce graphe est équivalent au précédent, et il sera parfois utile de mettre deux arcs différents avec une flèche sur chacun au lieu de mettre une seule arête avec deux flèches dessus (nous verrons plus tard pourquoi).

Si toutes les arêtes d’un graphe orienté peuvent se parcourir dans les 2 sens, le graphe est dit symétrique.
Ainsi, le graphe de gauche ci-dessous est symétrique, mais pas celui de droite car l’arc AB existe mais pas l’arc BA :

—
Remarque : un graphe non-orienté est toujours symétrique puisque les arêtes peuvent se parcourir dans les 2 sens.
—

Parmi les graphes orientés, il existe aussi des graphes antisymétriques : de tels graphes ont des arcs entre chaque sommet mais aucun dans les 2 sens : si on prend deux sommets du graphe, il y a nécessairement un arc entre ces deux sommets, mais aucun arc double.
Exemples de graphes antisymétriques :

—
ATTENTION ! Un graphe peut être symétrique, antisymétrique, ou ni l’un ni l’autre !
Il n’est pas forcément symétrique ou antisymétrique.
—

Par ailleurs, deux sommets sont dits adjacents s’il existe une arête ou un arc les reliant : peu importe qu’il soit orienté ou non.
Dans le graphe ci-dessous, A et B sont adjacents, mais A et C ne le sont pas :

Un graphe est alors dit complet si tous les sommets sont adjacents, c’est-à-dire que tout les sommets sont reliés deux à deux entre eux.
Sur l’exemple ci-dessous, le graphe de droite n’est pas complet car il n’y a aucune arête entre B et C :

Chaînes et cycles eulériens

Haut de page

Voyons encore quelques définitions qui vont nous amener aux premières propriétés des graphes.

Une chaîne est une succession ordonnée de finie de n+1 sommets adjacents, n étant le nombre d’arêtes de la chaîne. n est appelé la longueur de la chaîne.
« Ordonnée » signifie que l’on parcoure la chaîne dans l’ordre où elle est notée.
Exemple : dans le graphe ci-dessous, ABDHC est une chaîne, constituée de 4 arêtes (n = 4) et 5 sommets (n + 1 = 5).

La chaîne AHCB n’existe pas car A et H ne sont pas adjacents (il n’y a pas d’arête les reliant) mais la chaîne ABCH existe.

Evidemment, la chaîne peut passer plusieurs fois par le même sommet ou le même arc : la chaîne ABDCBCBD est tout à fait possible.

Si le graphe est orienté, on parle de chemin :

Ici CDAB est un chemin, mais CBA n’en est pas un car on ne peut pas aller de C à B (l’arc CB n’existe pas).

La distance entre deux sommets est la longueur de la plus courte chaîne qui les relie.
Prenons le graphe ci-dessous :

Entre les sommets A et D, il existe de nombreuses chaînes :
ABD, ABCD, ABCHD, ABHD, ABHFD, ABCHFD : la plus courte chaîne est ABD, de longueur 2, donc la distance entre A et D est de 2.

Le diamètre est au contraire la longueur de la plus grande chaîne. Ici il y a deux chaînes de longueur 5 (ABHFD et ABCHFD), donc le diamètre entre A et D est de 5.

Il peut arriver qu’une arête relie un sommet… à lui même ! Cela peut modéliser une situation stationnaire par exemple (on s’en servira notamment en probabilités).
Une telle arête est représentée de la manière suivante :

Dans ce graphe, il y a une boucle au sommet B.
Ainsi, on peut avoir le chemin DABBBC.

Un graphe est dit simple s’il n’a aucune boucle et s’il y a au plus une arête entre 2 sommets.
Dans le cas contraire, on parle de multigraphe.

Revenons sur les chaînes : une chaîne est dite fermée si le premier et le dernier point sont les mêmes.
ACFHA est un cycle (qui commence et finit par A), tout comme BCADB (qui commence et finit par B), mais pas ABDCF (qui commence par A mais finit par F).

Une chaîne est dite élémentaire si aucune sommet n’apparaît plus d’une fois.
La chaîne ABCD est donc élémentaire, la chaîne ABCA ne l’est pas (car A apparaît 2 fois).

De la même manière, une chaîne est dite simple si aucun arc n’apparaît plus d’une fois.

—
ATTENTION, ce n’est pas la même chose !
En effet, prenons le graphe suivant :

ABCDA est une chaîne simple (chaque arête de la chaîne n’est prise qu’une fois) mais ce n’est pas une chaîne élémentaire puisque le sommet A est pris 2 fois.
—

Dans l’exemple ci-dessus, ABCDA est ce qu’on appelle un cycle.

—
Un cycle est une chaîne fermée et simple : elle commence et finit par le même point, et chaque arc de la chaîne n’est pris qu’une seule fois (mais tous les arcs du graphe ne sont pas nécessairement pris).
—

Parmi les chaînes et les cycles, il y en a des particuliers que l’on appelle chaînes eulériennes et cycles eulériens.

—
Une chaîne est dite eulérienne si elle contient une et une seule fois toutes les arêtes du graphe (ou tous les arcs dans le cas d’un graphe orienté).
—

Remarque : les sommets peuvent en revanche apparaître plusieurs fois.
Tu dois peut-être avoir déjà joué à ce jeu qui consiste à tracer une maison sans lever le crayon, c’est l’exemple que l’on va prendre !
Sur le graphe suivant, existe-t-il une chaîne eulérienne ?

La réponse est oui : ABDCAEB : cette chaîne passe par toutes les arêtes et n’y passe qu’une seule fois.

Sur cet exemple, c’est simple, mais comment savoir si un graphe possède une chaîne eulérienne ou non ?
Cela va constituer notre première propriété sur les graphes (enfin !)

—
Un graphe possède une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2.
—

Donc tous les sommets doivent être de degré pair, ou tous de degré pair sauf 2 de degré impair.

Dans l’exemple ci-dessus, il n’y a que A et B de degré impair (degré 3), les autres sommets étant de degré pair. Ainsi on peut en déduire que ce graphe possède une chaîne eulérienne (la chaîne ABDCAEB par exemple).
Remarque : un graphe peut posséder plusieurs chaînes eulériennes : ABDCAEB et ABEACDB sont deux chaînes différentes pour le même graphe ci-dessus.

On peut même aller plus loin en disant que si le graphe possède uniquement 2 sommets de degré impair, la chaîne eulérienne doit commencer par un de ces deux points et finir par l’autre point.
Dans notre exemple, A et B sont les seuls de degré impair : une chaîne eulérienne va donc nécessairement commencer par A et finir par B, ou commencer par B et finir par A.

Si en revanche tous les sommets sont de degré pair, tu peux commencer par n’importe quel sommet.

Parlons maintenant des cycles eulériens :

—
Un cycle est dit eulérien s’il contient une et une seule fois toutes les arêtes du graphe (ou tous les arcs dans le cas d’un graphe orienté).
—

Un cycle eulérien est donc une chaîne eulérienne mais qui part et arrive au même point.

On a alors la propriété suivante :

—
Un graphe possède un cycle eulérien si et seulement si tous les sommets sont de degré pair.
—

C’est donc plus contraignant qu’une chaîne eulérienne car il ne peut pas y avoir de sommet de degré impair.
Ainsi dans l’exemple de la maison ci-dessus, le graphe ne possède pas de cycle eulérien car il y a deux sommets de degré impair.

En revanche, dans le graphe suivant, tous les sommets sont de degré pair, donc il y a un cycle eulérien :

Il y a même plusieurs cycles eulériens, par exemple : AEBCDBA, BDCBEAB, CBEABDC etc…

Si le graphe possède au moins un cycle eulérien, on parle de graphe eulérien.

Ces propriétés seront très utiles dans les applications concrètes des graphes.

Chaînes et cycles hamiltoniens

Haut de page

Les chaînes et cycles eulériens passent une et une seule fois par toutes les arêtes.
Les chaînes et cycles hamiltoniens quant à eux passent une et une seule fois par tous les sommets.

—
Une chaîne est hamiltonienne si elle passe une et une seule fois par tous les sommets du graphe.
Un cycle est hamiltonien s’il passe une et une seule fois par tous les sommets du graphe.
—

Et là tu vas dire : « oui mais si c’est un cycle, il commence et finit par le même sommet, donc on passe deux fois par le même sommet !! »
Oui en effet mais ce sommet est considéré comme unique (sinon en effet un cycle hamiltonien ne voudrait rien dire…).

Contrairement aux chaînes et cycles eulériens il n’y a pas de propriété permettant de savoir à coup sûr qu’une graphe possède une chaîne ou un cycle hamiltonien ou non.
Il existe en revanche un théorème correspond à un cas particulier :

—
Si un graphe est complet, alors il admet un chemin hamiltonien.
—

Encore faut-il avoir un graphe complet, ce qui n’est pas toujours le cas…

Dans l’exemple ci-dessous, le graphe de gauche possède une chaîne hamiltonienne (AEBDC par exemple) mais pas de cycle hamiltonien.
Le graphe de droite possède à fois une chaîne hamiltonienne (DAEBC notamment) et un cycle hamiltonien (AEBCDA par exemple) :

Sous-graphe et graphe partiel

Haut de page

Les sous-graphes et graphes partiels peuvent être utiles dans certains cas (on le verra pour le nombre chromatique juste après).

Un sous-graphe, c’est quand on prend uniquement certains sommets du graphe et toutes les arêtes présentes entre ces sommets.
Exemple :

Comme tu le vois, on a pris les sommets A, B, C et D ainsi que toutes les arêtes reliant ces points.

Pour un graphe partiel, on prend également certains sommets mais pas forcément toutes les arêtes.
Exemple :

Là encore on a pris les sommets A, B, C et D, mais pas les arêtes AB et BC qui sont pourtant présentes dans le graphe d’origine : c’est donc un graphe partiel.

Pour un graphe donné, il existe évidemment de nombreux sous-graphes et graphes partiels.

Nombre chromatique d’un graphe

Haut de page

Voyons maintenant quelque chose que les élèves apprécient beaucoup généralement : le nombre chromatique.

—
Le nombre chromatique d’un graphe est le nombre minimal de couleurs pour colorier chaque sommet de sorte que deux sommets adjacents n’aient pas la même couleur.
—

Concrètement, c’est comme si les sommets représentaient des pays et les arêtes des frontières, et il faut faire en sorte que deux pays ayant une frontière commune n’aient pas la même couleur.
Prenons la carte de l’Europe (en tout cas une partie) : les pays sont des sommets dont la première lettre du pays représente la lettre du sommet (sauf A’ pour Autriche car il y a 2 A : Allemagne et Autriche) : nous n’avons pas pris les îles qui ont une frontière uniquement avec la mer^^

Avec 4 couleurs, on peut faire en sorte que deux pays ayant une frontière n’aient pas la même couleur, mais avec 3 c’est impossible (tu peux essayer), donc le nombre chromatique de ce graphe est 4, voici un exemple de coloration possible :

Il n’y a pas de propriété permettant de connaître le nombre chromatique d’un graphe.
Cependant, il y a un théorème permettant de donner le nombre chromatique maximum :

—
Si le plus haut degré des sommets est noté x, alors le nombre chromatique est au plus égal à x + 1.
—

Dans le graphe ci-dessus, le degré maximal est 8 (celui du sommet A), donc le nombre chromatique est inférieur ou égal à 9.
Bon c’est vrai que ça n’a pas beaucoup d’intérêt dans le cas présent puisque finalement le nombre chromatique est 4, donc bien en-dessous de 9, mais c’est parfois assez utile !

Il y également d’autres propriétés intéressantes :

—
Si un graphe est complet, alors son nombre chromatique est égal au nombre de sommets.
—

En effet, si un graphe est complet, tous les sommets sont reliés entre eux, on ne peut donc pas colorier deux sommets de la même couleur, donc il y a donc autant de couleurs que de sommets.

Cela entraîne la propriété suivante :

—
Si un graphe possède un sous-graphe complet, le nombre chromatique est supérieur ou égal au nombre de sommets de ce sous-graphe complet.
—

Cela permet de trouver une valeur minimale pour le nombre chromatique, tandis que le théorème vu précédemment permet de trouver un nombre maximal : on peut ainsi encadrer la valeur du nombre chromatique, ce qui simplifie sa recherche.

Dans l’exemple de la carte d’Europe, le sous-graphe composé des sommets A, F et S est un sous-graphe complet : le nombre chromatique est donc supérieur ou égal à 3.
Comme on a vu qu’il était inférieur ou égal à 9, on peut dire qu’il est compris entre 3 et 9.

Matrice associée – graphe non orienté

Haut de page

Voyons maintenant tout autre chose : la matrice associée à un graphe.
Il est conseillé de lire (et comprendre !) auparavant le cours sur les matrices pour bien comprendre ce qui suit.

Tout d’abord pour un graphe non orienté.
Imaginons que l’on ait un graphe avec n sommets, que l’on classe dans l’ordre alphabétique : la matrice associée sera une matrice carrée de taille n x n (n lignes et n colonnes).

Nous allons prendre un exemple, ce sera plus simple : 4 sommets A, B, C et D (donc n = 4) :

La case (i ; j) (i^ème ligne et j^ème colonne) sera égale au nombre d’arêtes reliant la lettre de la i^ème à la lettre de la j^ème colonne.
Dans un graphe non orienté, comme il n’y a pas de sens, la matrice sera toujours symétrique !

—
La matrice associée à un graphe non-orienté sera nécessairement symétrique.
—

Prenons le graphe suivant :

La matrice associée est la suivante :

Cette matrice est bien symétrique !

Expliquons la en détails, ligne par ligne.
La première ligne correspond aux chemins partant de A : on peut uniquement de A à B, donc il y a un 1 dans la colonne B, et 0 ailleurs.
La deuxième ligne correspond aux chemins partant de B : on peut aller à A, C et D, donc il y a un 1 dans les colonnes A, C et D.
La troisième ligne correspond aux chemins partant de C : on peut aller à B et D, donc il y a un 1 dans les colonnes B et D et 0 ailleurs.
La quatrième ligne correspond aux chemins partant de D : on peut aller à B et C, donc il y a un 1 dans les colonnes B et C et 0 ailleurs.

On met à chaque fois 1 car il n’y a qu’une seule arête entre chaque point, mais on peut très bien imaginer que ce ne soit pas le cas :

Dans ce schéma, il y a 2 arêtes entre A et B et même 3 entre C et D, on met donc 2 et 3 dans les cases correspondantes de la matrice :

Tu as peut-être remarqué que jusqu’à présent les diagonales des matrices sont toutes nulles : en effet, elles représentent le trajet entre A et A, B et B, C et C ainsi que D et D. Or il n’y a pas d’arête entre un sommet et lui-même !
Mais il pourrait y en avoir, c’est ce que l’on appelle une boucle comme on l’avait vu dans les définitions. Cela arrive généralement dans les graphes orientés que nous maintenant étudier.

Matrice associée – graphe orienté

Haut de page

Pour les graphes orientés, comme les arcs reliant les sommets ont un sens, la matrice n’est pas nécessairement symétrique.
Prenons le graphe suivant :

La matrice associée à ce graphe est :

Comme tu le vois la matrice n’est pas symétrique.
Tu remarqueras que la diagonale n’est pas nulle, il y a 1 au niveau du trajet B-B car il y a une boucle au niveau de B.

Mais à quoi sert la matrice associée ?
Tout simplement à trouver les chemins d’une certaine longueur.

Appelons M la matrice associée au graphe précédent.
Imaginons que l’on cherche les chemins entre 2 points, par exemple A et B, de longueur 3.
On calcule tout simplement M³ !
Le calcul donne (entraîne-toi à le faire !) :

Si je cherche les chemins de A vers B, je regarde à la première ligne (chemins partant de A) et la deuxième colonne (ceux arrivant à B) : je constate qu’il y a un 2.
Cela signifie qu’il y a 2 chemins de longueur 3 entre A et B.
Et en effet, si je cherche « à la main » ces chemins, j’en trouve 2 : ABBB et ADAB, et il n’y en a pas d’autres !

Un 0 dans la matrice M³ s’interprète évidemment comme l’absence de chemin de longueur 3 entre 2 points.
On constate par exemple un 0 à la troisième ligne – première colonne : cela signifie qu’il n’y a pas de chemin de longueur entre allant de C à A (et si tu cherches avec le graphe tu constateras qu’en effet il n’y a pas de tel chemin !).

Si on cherche les chemins de longueur 4, on calcule M⁴, les chemins de longueur 5 M⁵ etc…
De tels exercices peuvent faire intervenir les puissances de matrices, ce pourquoi il est conseillé de lire le chapitre correspondant.

Graphes pondérés

Haut de page

Jusqu’à présent les arêtes n’avaient pas de valeur associée, mais il existe des graphes, appelés graphes pondérés, pour lesquels chaque arête est associé à une valeur.
Par exemple :

Les sommets peuvent par exemple représenter des gares, les arêtes des voies ferrées et les valeurs associées le temps de trajet entre les gares.
Ici il faudrait par exemple 3 minutes pour aller de A à B (ou l’inverse), 5 minutes pour aller de B à C etc…
L’énoncé précisera évidemment si le temps est en minutes ou en heures, ou s’il s’agit d’autre chose !

La valeur de chaque arête est appelé le poids, d’où le terme de graphe pondéré.

A noter qu’il existe évidemment des graphes pondérés ET orientés (que l’on va étudier juste après).

Il peut également y avoir plusieurs arêtes reliant deux sommets mais avec des valeurs différentes.
Exemple :

On voit ici qu’il y a 2 arêtes entre C et D : une pondérée à 12 et l’autre à 15.
On peut imaginer que C et D sont des villes par exemple, et que l’on peut aller de l’une à l’autre en voiture en 12 minutes, ou en train en 15 minutes, ce pourquoi il y a 2 arêtes pondérées différemment.

Une des applications courantes des graphes pondérés sont les graphes probabilistes.

Graphes probabilistes

Haut de page

Les graphes probabilistes sont des graphes pondérés et orientés.
On les utilise dans les cas où un système peut être dans plusieurs états et passer de l’un à l’autre. Les sommets représentent ces différents états.

On peut imaginer un moteur, qui est soit en marche, soit à l’arrêt : on aurait donc un sommet représentant l’état de marche et un autre l’état d’arrêt.

On peut aussi imaginer une personne qui est soit malade, soit en bonne santé : un sommet représenterait l’état malade et l’autre l’état en bonne santé.

Dans ces deux exemples nous n’avons que 2 états mais on peut très bien en avoir plus, et donc plus de sommets.

Cependant, dans la plupart des exercices on n’étudie que les cas à 2 états (donc 2 sommets), ce pourquoi la suite de l’étude se fera dans ce cas-là (mais le cas avec plus de sommet est identique !).

Prenons donc un système à deux états que nous nommeront E1 et E2.
Quand on est dans l’état E1, on peut soit rester dans l’état E1 soit passer à l’état E2.
Rester dans l’état E1 se fait avec une certaine probabilité que l’on notera p11, et passer à l’état E2 se fait avec une probabilité que l’on notera p12.
(p11 car on part de 1 et reste dans 1, et p12 car on part de 1 et on va dans 2).
Comme on fait nécessairement un des deux choix, on a : p11 + p12 = 1.
Remarque : le passage à l’état E2 ou le fait de rester dans E1 se fait à intervalles de temps réguliers, par exemple, tous les jours ou tous les mois, cela sera déterminé dans l’énoncé. En tout état de cause, chaque passage correspond à 1 transition (d’où le nom de matrice de transition).

Le graphe correspondant ressemble pour l’instant à cela (il sera complété par la suite) :

De même, quand on est dans l’état E2, on peut soit rester dans l’état E2 soit passer à l’état E1.
Rester dans l’état E2 se fait avec une certaine probabilité que l’on notera p22, et passer à l’état E1 se fait avec une probabilité que l’on notera p21.
(p22 car on part de 2 et reste dans 2, et p21 car on part de 2 et on va dans 1).
Comme on fait nécessairement un des deux choix, on a : p22 + p21 = 1.

Le graphe complet est alors celui-là :

La matrice de transition de ce graphe est alors la suivante :

A noter que la somme des coefficients sur une même ligne sera toujours égal à 1 (p11+12=1 et p22+p21=1).

Quel est l’intérêt de cette matrice ?
Pour comprendre l’intérêt d’une telle matrice, il faut d’abord poser p₀ la probabilité d’être dans l’état E1 initialement.
On note aussi q₀ la probabilité d’être dans l’état E2 initialement.
On a donc p₀ + q₀ = 1.
(les valeurs de p₀ et q₀ sont généralement données dans l’énoncé)

On note de la même manière p₁ la probabilité d’être dans l’état E₁ après la première transition, et q₁ la probabilité d’être dans l’état E₂ après la première transition : p₁ + q₁ = 1.
Puis p₂ la probabilité d’être dans l’état E₁ après la deuxième transition, et q₂ la probabilité d’être dans l’état E₂ après la deuxième transition : p_n + q_n = 1.
De manière générale, on note p_n la probabilité d’être dans l’état E₁ après la n-ième transition, et q_n la probabilité d’être dans l’état E₂ après la n-ième transition : p_n + q_n = 1.

—
Remarque : la notation p₁, p₂ etc… n’a rien à voir avec p11, p12 etc… de la matrice de transition.
Le calcul de p₁ se fera évidemment à partir de p11, p12, p21 et p22, mais attention à ne pas confondre les notations.
—

Mais comment calculer p₁, q₁, p₂, q₂ etc… ?

On pourrait montrer par récurrence que, en notant X₀ la matrice ligne (p₀, q₀), X_n la matrice ligne (p_n, q_n), et M la matrice de transition du graphe, on a :

Avec la formule des probabilités totales, on pourrait en effet montrer la formule de récurrence suivante :

On se retrouve une fois de plus à calculer une puissance de matrice !
Une fois le calcul de Mⁿ effectué, on peut facilement trouver X_n et donc p_n et q_n.

—
ATTENTION à ne pas inverser en disant X_n = MⁿX₀ ou X_n+1 = MX_n
—

Dernière chose avant de passer à la suite : l’état stable.
L’état stable correspond à un état où les probabilités d’être dans l’état 1 ou 2 sont constantes. C’est-à-dire que même après une transition, les probabilités p_n et q_n.
On a donc p_n et p_n+1 et q_n = q_n+1
Donc X_n = X_n+1, et d’après la formule de récurrence vue plus haut, on a donc :

avec X = (p q) état stable du système

p correspond à la limite de la suite (p_n) et q à la limite de la suite(q_n).

Pour trouver l’état stable du système, il suffit de résoudre ce système, qui admet une unique solution si et seulement si la matrice M ne comporte aucun 0.

Voyons un exemple, cela sera plus parlant !

Reprenons un des exemples décrit précédemment : E1 correspond au fait pour une personne d’être en bonne santé, E2 au fait d’être malade.
Initialement, la personne est en bonne santé, ce qui se traduit par p₀ = 1 et q₀ = 0.
Une épidémie se déclare :
– chaque jour, si une personne est en bonne santé, elle a 80 % de chances de tomber malade le jour suivant.
– chaque jour, si une personne est malade, est a 40 % de chances de rester malade.

Ces phrases s’interprètent de la manière suivante : p12 = 0,20 et p22 = 0,40.
Or p11 + p12 = 1 et p21 + p22 = 1, on en déduit que p11 = 0,80 et p21 = 0,60.

Le graphe est alors le suivant :

La matrice de transition est alors :

Si l’on cherche la proportion de malades au bout de 3 jours, il faut calculer M³.
Un calcul donne :

On applique alors la formule X₃ = X₀M³, et on trouve :
X₃ = (0,392 0,608)
On a donc p₃ = 0,392 et q₃ = 0,608.

Ainsi au bout de 3 jours, la probabilité d’être malade est de 0,608 soit 60,8 % de malades.

Cherchons maintenant l’état stable : on peut calculer Mⁿ, puis X_n et donc trouver p_n et q_n et faire la limite, mais il est beaucoup plus rapide de résoudre X = XM.

On arrive au système suivant :

Ce système se résout de manière un peu spécial. En effet, si tu additionnes les lignes, tu trouveras p + q = p + q, ce qui ne va pas donner grand chose…
Il faut donc remplacer une des 2 lignes (la 2ème par exemple) par une autre égalité reliant p et q : p + q = 1
On a donc le système :

Ce système se résout très simplement, et on trouve p = 3/7 et q = 4/7.

On peut bien sûr vérifier que l’on ne s’est pas trompé en calculant XM avec X = (3/7 4/7), et on doit trouver X (puisque X = XM).

Ainsi, au bout d’un certains temps, la population va se stabiliser avec 3/7 de personnes en bonne santé et 4/7 de personnes malades.

Algorithme de Dijkstra

Haut de page

L’algorithme de Dijkstra permettant de déterminer le plus court chemin entre deux points dans un graphe.
Imaginons que l’on ait le graphe suivant :

Les sommets représentent par exemple des gares et les poids sur les arêtes le temps de trajet en minutes entre les gares.
On veut aller de A à D en passant par le chemin le plus rapide.
On voit assez facilement que le chemin ABCD est de poids total 3 + 4 + 2 = 9 et que les autres sont plus longs.
En effet ABD est de poids 3 + 9 = 12, et le chemin ABCD en passant par l’arête de poids 14 est de 3 + 4 + 14 = 21.

Ici il n’y a pas beaucoup de points ni beaucoup d’arêtes, donc pas besoin d’algorithme particulier.
Mais quand on a un graphe plus compliqué comme celui ci-dessous, c’est indispensable !!

Le principe de l’algorithme est le suivant : on va tracer un tableau, chaque colonne correspondant à un sommet :

Première étape : comme on part de A, la colonne A sera vide (ça c’est facile ), on peut mettre un 0 dans la 1ère case et on tire un trait vertical pour signifier qu’on ne touchera plus à cette case.

Comme on part de A, on regarde tous les sommets que l’on peut atteindre en partant de A : ici c’est B et D.
On met alors dans les colonnes B et D le poids du chemin correspondant, suivant de la lettre de laquelle on vient (ici on vient de A).
La lettre peut être mise entre parenthèse ou précédée d’un tiret.
Les autres colonnes sont quant à elles inchangées.
On obtient le tableau suivant :

A partir de maintenant, toutes les étapes se feront en 2 temps.
1er temps : on s’intéresse maintenant au sommet de poids le plus petit : ici B a un poids plus petit que D, on va donc prendre B.
On commence par tirer un trait vertical dans la colonne B pour signifier que l’on n’y touchera plus (comme A !).
On va regarder tous les sommets accessibles depuis B.
On voit que l’on peut atteindre A, D, C et G.
On peut déjà oublier A puisque l’on a dit que l’on ne touchait plus à A.
Concernant les autres sommets, on additionne le poids de l’arête avec le poids du sommet que l’on considère, ici B donc 3.
Ainsi, pour D on aura 3 + 2 = 5, pour C on aura 3 + 8 = 11, et pour G 3 + 12 = 15.
Evidemment ces valeurs sont suivies de B puisque l’on vient du point B :

2ème temps : on vérifie que les nouvelles valeurs ne sont pas plus petites que les valeurs qu’il y avait avant.
Ici C et G n’avaient pas de valeur auparavant, donc pas de problème.
Pour D, on avait auparavant 10, on a maintenant 5 : c’est plus petit, donc c’est bon !
En effet, cela signifie que l’on a trouvé un chemin de poids 5 pour arriver à D, alors qu’auparavant on avait trouvé un chemin de poids 10. Comme on cherche à chaque fois le plus court chemin, on garde le 5.
Nous verrons plus tard ce qu’il faut faire quand le nouveau chemin trouvé est plus grand.

On recommence :
1er temps : on s’intéresse au sommet de poids le plus petit, qui est maintenant D. On tire un trait vertical au niveau de la colonne D.
On regarde tous les sommets accessibles depuis D : il y a A, B, C et E.
A et B ont déjà été faits : on les oublie.
Pour C et E, comme précédemment, on additionne le poids de l’arête avec le poids du sommet que l’on considère, ici D donc 5.
Ainsi, pour C on aura 5 + 4 = 9, pour E on aura 5 + 5 = 10.
Ces valeurs sont suivies de D puisque l’on est passé par D. On obtient :

2ème temps : on vérifie que les nouvelles valeurs ne sont pas plus petites que les valeurs qu’il y avait avant.
Ici le poids de G n’a pas changé : pas de problème.
Le poids de E est nouveau : pas de problème.
Le nouveau poids de C (9) est plus petit que celui d’avant (11) donc pas de problème non plus !
Donc là encore rien à faire dans ce 2ème temps.

On recommence :
1er temps : on s’intéresse au sommet de poids le plus petit (attention à bien considérer le G qui n’est plus sur la même ligne mais qui a un poids). C’est ici C : on tire un trait vertical au niveau de la colonne C.
On regarde tous les sommets accessibles depuis C : il y a B, D, E et F.
B et D ont déjà été faits : on les oublie.
Pour E et F, comme précédemment, on additionne le poids de l’arête avec le poids du sommet que l’on considère, ici C donc 9.
Ainsi pour E on aura 9 + 2 = 11, pour F on aura 9 + 3 = 12.
Ces valeurs sont suivies de C puisque l’on est passé par C. On obtient :

2ème temps : on vérifie que les nouvelles valeurs ne sont pas plus petites que les valeurs qu’il y avait avant.
Ici le poids de G n’a pas changé : pas de problème.
Le poids de F est nouveau : pas de problème.
En revanche, le poids de E a augmenté puisque puisqu’il était de 10 et qu’il est maintenant de 11 : on a donc trouvé un chemin plus grand pour arriver à E, cela ne nous intéresse pas !!
On va donc tout simplement rajouter une ligne où l’on va remettre le plus petit chemin, à savoir 10 – D :

Comme tu le vois rien de compliqué : si jamais un (ou plusieurs) nouveaux chemins sont plus longs que les précédents, il suffit de rajouter une ligne et de remettre l’ancien chemin et non le nouveau.

On recommence :
1er temps : on s’intéresse au sommet de poids le plus petit (attention à bien considérer le F et le G qui ne sont plus sur la même ligne mais qui ont un poids). C’est ici E : on tire un trait vertical au niveau de la colonne E.
On regarde tous les sommets accessibles depuis C : il y a C, D et F.
C et D ont déjà été faits : on les oublie.
Pour F, on fait 10 + 4 = 14, suivi de E puisque l’on est passé par E. On obtient :

2ème temps : on vérifie que les nouvelles valeurs ne sont pas plus petites que les valeurs qu’il y avait avant.
Ici les poids de G n’a pas changé : pas de problème.
En revanche, le poids de F a augmenté puisque puisqu’il était de 12 et qu’il est maintenant de 14 : on rajoute donc une ligne en remettant l’ancien poids :

On recommence (et oui, encore !) :
1er temps : on s’intéresse au sommet de poids le plus petit : c’est ici F donc on tire un trait vertical au niveau de la colonne F.
On regarde tous les sommets accessibles depuis F : il y a C, E, G et H
C et E ont déjà été faits : on les oublie.
Pour G, on fait 12 + 1 = 13, et pour H 12 + 7 = 19, suivi de F puisque l’on est passé par F. On obtient :

2ème temps : on vérifie que les nouvelles valeurs ne sont pas plus petites que les valeurs qu’il y avait avant.
Le poids de G a diminué passant de 15 à 13 donc rien à faire.
Le poids de H est nouveau : rien à faire non plus !
Ainsi pas besoin de rajouter une ligne pour ce 2ème temps.

On recommence (une dernière fois !) :
1er temps : on s’intéresse au sommet de poids le plus petit : c’est ici G donc on tire un trait vertical au niveau de la colonne G.
On regarde tous les sommets accessibles depuis G : il y a B, F et H
B et F ont déjà été faits : on les oublie.
Pour H on a 13 + 5 = 18, suivi de G puisque l’on est passé par G. On obtient :

2ème temps : on vérifie que les nouvelles valeurs ne sont pas plus petites que les valeurs qu’il y avait avant.
Le poids de H a diminué passant de 19 à 18 donc rien à faire.
Ainsi pas besoin de rajouter une ligne pour ce 2ème temps.

Si on recommençait, on s’intéresserait au sommet H mais qui est relié à F et G que l’on a déjà fait, donc il n’y a plus rien à faire !

Le tableau est désormais terminé ! … mais l’algorithme !

Rassures-toi la dernière étape est simple et rapide.
Il s’agit désormais de répondre à la question, à savoir quel est le plus court chemin entre A et H.
Pour cela on va partir de la fin, donc H.
On regarde donc la colonne H : on voit que le plus court chemin est de poids 18, et passe par G.
Le chemin sera donc A…….GH

On regarde maintenant la colonne G : le plus petit chemin passe par F d’après la dernière case de cette colone.
Le chemin sera donc A……FGH

On continue : la dernière case de la colonne F indique que l’on passe par C : le chemin sera donc A…..CFGH
On continue : la dernière case de la colonne C indique que l’on passe par D : le chemin sera donc A….DCFGH
On continue : la dernière case de la colonne D indique que l’on passe par B : le chemin sera donc A…BDCFGH
On continue : la dernière case de la colonne B indique que l’on passe par A : le chemin sera donc ABDCFGH.

Et voilà, c’est terminé !

Comme on le voit sur le graphe, ce n’est pas le chemin le plus simple ni le plus direct, mais c’est le plus court !

Nous verrons évidemment un exercice en vidéo sur l’algorithme de Dijkstra, ce sera peut-être plus parlant pour toi

Maintenant que tu sais tout (ou presque) sur les graphes, il est temps de passer aux exercices !

Exercices

Haut de page

Pour accéder aux exercices sur la théorie des graphes, clique ici !

Retour au sommaireHaut de la page