Graphes
Introduction :
Cette leçon introduira tout d’abord la notion de graphe non orienté, avec sa matrice d’adjacence ainsi que ses éventuels chaînes et cycles, puis nous verrons les graphes orientés et leurs particularités. Nous aborderons enfin l’algorithme de Dijkstra-Moore qui permet de rechercher la plus courte chaîne d’un graphe.
Graphes non orientés
Graphes non orientés
Définitions et propriétés
Définitions et propriétés
Définition
Graphe :
- Un graphe est composé de sommets et d’arêtes reliant certains de ces sommets.
- L’ordre d’un graphe est le nombre de ses sommets.
- Une boucle est une arête reliant un sommet à lui-même.
- Deux sommets reliés par une arête sont dits adjacents.
- Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.
- Un graphe est complet lorsque tous ses sommets sont adjacents.
Propriété
La somme des degrés des sommets d’un graphe non orienté est égale au double du nombre total d’arêtes.
Exemple
Ce graphe possède $5$ sommets ($A$, $B$, $C$, $D$, $E$) ; c’est un graphe d’ordre $5$.
- Il n’est pas complet car les sommets $A$ et $E$ ne sont pas adjacents (ils ne sont pas reliés directement par une arête).
Le tableau ci-dessous représente les degrés des $5$ sommets du graphe :
| Sommet | $A$ | $B$ | $C$ | $D$ | $E$ |
| Degré | $2$ | $3$ | $3$ | $3$ | $3$ |
On peut compter sur le graphes que le nombre total d’arêtes est $7$ et la somme des degrés des sommets est $14$ (soit le double du nombre total d’arêtes).
Exemple
Ce graphe qui possède $4$ sommets ($A$, $B$, $C$, $D$) est un graphe d’ordre $4$ complet car tous ses sommets sont adjacents.
Le tableau ci-dessous représente les degrés des $4$ sommets du graphe :
| Sommet | $A$ | $B$ | $C$ | $D$ |
| Degré | $3$ | $3$ | $3$ | $3$ |
Le nombre total d’arêtes est $6$ et la somme des degrés des sommets est $12$ soit le double du nombre total d’arêtes.
Matrice d’adjacence
Matrice d’adjacence
Définition
Matrice d’adjacence :
La matrice d’adjacence associée à un graphe non orienté d’ordre $n$ dont les sommets sont numérotés de 1 à $n$ la matrice carrée d’ordre $n$ où le terme situé en ligne $i$ et colonne $j$ est égal au nombre d’arêtes reliant $i$ et $j$.
Exemple
La matrice d’adjacence associée à ce graphe d’ordre $5$ est la matrice suivante :
$\begin{aligned}\\ \text{A}\\ \text{B}\\ \text{C}\\ \text{D}\\ \text{E} \end{aligned} \begin{aligned} \text{ A }\ \ \text{ B }\ \ \text{ C }\ \ \text{ D }\ \ \text{ E }\\ \begin{pmatrix} 0&1&0&1&0\\ 1&0&1&0&1\\ 0&1&0&1&1\\ 1&0&1&0&1\\ 0&1&1&1&0 \end{pmatrix} \end{aligned}$
Les sommets doivent être classés dans l’ordre alphabétique, ainsi par exemple le coefficient $1$ situé en ligne $1$ et colonne $2$ signifie qu’il y a une arête qui relie $A$ à $B$.
Le coefficient $0$ situé en ligne $2$ et colonne $4$ signifie qu’il n’y a pas d’arête qui relie $B$ à $D$.
À retenir
La matrice d’adjacence d’un graphe non orienté sera toujours symétrique par rapport à sa première diagonale.
Chaînes et cycles
Chaînes et cycles
Une chaîne est une suite d’arêtes qui, mises bout à bout, permettent d’aller d’un sommet à un autre. Dans une chaîne, on peut prendre plusieurs fois la même arête.
Définition
Chaîne :
- Une chaîne est une liste ordonnée de sommets reliés deux à deux par une arête.
- La longueur d’une chaîne est le nombre d’arêtes qui la composent.
- Une chaîne est fermée lorsque l’origine et l’extrémité sont confondues.
- Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.
Autrement dit, pour qu’une chaîne soit un cycle il faut qu’elle soit fermée et que chacune de ses arêtes n’ait été prise qu’une seule fois.
Exemple
$A$-$D$-$C$ est une chaîne et $A$-$D$-$C$-$B$-$A$ est un cycle.
Propriété
Trouver dans un graphe un nombre de chaînes de longueur donnée
Soit $p$ un entier naturel et $M$ la matrice d’adjacence associée à un graphe non orienté dont les sommets sont numérotés.
Le terme $a_{ij}$ (ligne $i$ colonne $j$) de la matrice $M^p$ donne le nombre de chaînes de longueur $p$ reliant $i$ et $j$.
Exemple
$\text{M}=\begin{aligned}\\ \text{A}\\ \text{ B }\\ \text{ C }\\ \text{ D }\\ \text{ E } \end{aligned} \begin{aligned} \text{ A }\ \ \text{ B }\ \ \text{ C }\ \ \text{ D }\ \ \text{ E }\\ \begin{pmatrix} 0&1&0&1&0\\ 1&0&1&0&1\\ 0&1&0&1&1\\ 1&0&1&0&1\\ 0&1&1&1&0 \end{pmatrix} \end{aligned}$
donc
$\;\text{M}^3=\begin{aligned}\\ \text{A}\\ \text{ B }\\ \text{ C }\\ \text{ D }\\ \text{ E } \end{aligned} \begin{aligned} \text{ A }\ \ \text{ B }\ \ \text{ C }\ \ \text{ D }\ \ \text{ E }\\ \begin{pmatrix} 0&6&2&6&2\\ 6&2&7&2&7\\ 2&7&4&7&5\\ 6&2&7&2&7\\ 2&7&5&7&4 \end{pmatrix} \end{aligned}$
- La matrice nous indique qu’il y a $2$ chaînes de longueur $3$ reliant $B$ à $D$.
Ces chaînes sont : $B$-$C$-$E$-$D$ et $B$-$E$-$C$-$D$.
Graphes connexes et trajets eulériens
Graphes connexes et trajets eulériens
Définition
Graphe connnexe :
Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts, c’est-à-dire si le graphe est « d’un seul tenant ».
Exemple
Ce graphe est connexe.
Ce graphe n’est pas connexe.
Définition
Chaîne eulérienne :
Une chaîne est eulérienne lorsqu’elle contient chaque arête du graphe une et une seule fois. Si cette chaîne est un cycle, on dit qu’il s’agit d’un cycle eulérien.
Théorème
Théorème d’Euler :
Un graphe connexe admet une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair vaut $0$ ou $2$.
Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets sont de degré pair.
À retenir
Le théorème d’Euler permet de savoir rapidement si un graphe connexe comporte une chaîne eulérienne ou un cycle eulérien.
Exemple
Tableau des degrés des $5$ sommets de ce graphe :
| Sommet | $A$ | $B$ | $C$ | $D$ | $E$ |
| Degré | $1$ | $4$ | $1$ | $2$ | $2$ |
Comme le graphe comporte $2$ sommets de degré impair, il existe une chaîne eulérienne (par exemple, $A$-$B$-$E$-$D$-$B$-$C$ est une chaîne eulérienne).
- Cela signifie que l’on peut passer par chaque arête une et une seule fois.
En revanche, comme tous les sommets ne sont pas de degré pair, il n’existe pas de cycle eulérien. Cela signifie qu’aucune chaîne ne permet de revenir au sommet de départ.
Graphes orientés
Graphes orientés
Définition
Définition
Définition
Graphe orienté :
Un graphe orienté est un graphe dont les arêtes sont orientées. Chaque arête ne peut être parcourue que dans le sens de la flèche. Une boucle est une arête orientée dont l’origine et l’extrémité sont les mêmes.
Exemple
Il s’agit d’un graphe orienté de degré $3$.
Il comprend une boucle qui relie le sommet $1$ à lui-même.
Matrice d’adjacence
Matrice d’adjacence
Tout comme pour les graphes non orientés, on peut associer à chaque graphe orienté une matrice d’adjacence.
Définition
Matrice d’adjacence :
La matrice d’adjacence associée à un graphe orienté d’ordre $n$, dont les sommets sont numérotés de $1$ à $n$, est une matrice carrée d’ordre $n$ où le terme figurant en ligne $i$ et colonne $j$ est égal à $1$ s’il existe une arête menant de $i$ à $j$ et à $0$ sinon.
Exemple
La matrice d’adjacence associée à ce graphe d’ordre $3$ est : $\text{M}=\begin{pmatrix} 1&1&0\\1&0&0\\0&1&0 \end{pmatrix}$
Les sommets doivent être classés dans l’ordre alphabétique ou dans l’ordre croissant, ainsi par exemple le coefficient « $1$ » situé en ligne $1$ et colonne $2$ signifie qu’il y a une arête orientée qui mène de ① vers ②.
Le coefficient « $0$ » situé en ligne $3$ et colonne $3$ signifie qu’il n’y a pas d’arête orientée qui mène de ③ vers ③ (pas de boucle au sommet n°$3$).
À retenir
Contrairement à la matrice d’adjacence d’un graphe non orienté, celle d’un graphe orienté n’est pas forcément symétrique par rapport à sa première diagonale.
Propriété
Trouver dans un graphe un nombre de chaîne d’une longueur donnée
Soit $p$ un entier naturel et $M$ la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. Le terme $a_{ij}$ (ligne $i$ colonne $j$) de la matrice $M^p$ donne le nombre de chaînes de longueur $p$ reliant $i$ et $j$.
Astuce
Cette propriété est exactement la même pour les graphes non orientés.
Exemple
$\text{M}=\begin{pmatrix} 1&1&0\\1&0&0\\0&1&0 \end{pmatrix}\;$ donc $\;\text{M}^4=\begin{pmatrix} 5&3&0\\3&2&0\\2&1&0 \end{pmatrix}$
La matrice $\text{M}^4$ nous indique qu’il y a $3$ chaînes de longueur $4$ menant de ① à ②.
Ces chaînes sont : ①-①-①-①-② ; ①-①-②-①-② et ①-②-①-①-②
Graphes étiquetés et graphes pondérés
Graphes étiquetés et graphes pondérés
Définition
Graphe étiqueté :
Un graphe étiqueté est un graphe orienté où chacune des arêtes est affectée d’une lettre ou d’un mot ou de tout autre symbole. Ces symboles sont appelés des étiquettes.
Exemple
À partir de ce graphe étiqueté on peut former certains mots.
Définition
Graphe pondéré :
Un graphe pondéré est un graphe étiqueté dont toutes les étiquettes sont des nombres positifs.
Définition
Poids d’une chaîne :
Le poids d’une chaîne est la somme du poids des arêtes qui la composent. Une plus courte chaîne entre deux sommets est, parmi les chaînes qui relient ces deux sommets, une chaîne de poids minimal.
Exemple
Soit le graphe pondéré d’ordre $5$ ci-contre :
- la chaîne $A$-$B$-$D$-$E$-$C$ de ce graphe est de longueur $4$
- son poids est de $11$
- la plus courte chaîne reliant $A$ à $C$ a pour longueur $2$ et pour poids $6$. Il s’agit de la chaîne $A$-$B$-$C$.
Attention
La longueur d’une chaîne est le nombre d’arêtes qui la composent.
Algorithme de Dijkstra-Moore
Algorithme de Dijkstra-Moore
À retenir
ALGORITHME DE DIJKSTRA-MOORE
L’algorithme de Dijkstra-Moore permet de trouver la plus courte chaîne reliant un sommet à un autre dans un graphe :
Étapes de l’Algorithme de Dijkstra-Moore
- Étape 1 : placer tous les sommets du graphe dans la 1re ligne d’un tableau
- Sur la 2e ligne du tableau, écrire le coefficient $0$ sous le sommet de départ et le coefficient $\infty$ sous les autres sommets.
- Étape 2 : sur la dernière ligne écrite, repérer le sommet $X$ de coefficient minimal.
- Commencer une nouvelle ligne et rayer toutes les cases vides sous $X$.
- Étape 3 : pour chaque sommet $Y$ adjacent à $X$, calculer la somme $P$ du coefficient de $X$ et du poids de l’arête reliant $Y$ à $X$.
- Si $P$ est strictement inférieur au coefficient de $Y$, inscrire $PX$ dans la case correspondante de la colonne $Y$.
- Sinon, inscrire le coefficient de $Y$ et compléter la ligne par des coefficients de la ligne précédente.
- Étape 4 : s’il reste des sommets non sélectionnés, recommencer à l’étape 2.
- Sinon, passer à l’étape 5.
- Étape 5 : la longueur minimale est le nombre lu sur la dernière ligne du tableau.
Exemple
Dans ce graphe, on cherche à déterminer la plus courte chaîne menant de $S$ à $E$.
- La première étape est de placer tous les sommets du graphe dans la première ligne d’un tableau et d’écrire le coefficient $0$ sous le sommet de départ et le coefficient $\infty$ sous les autres sommets.
- La deuxième étape est de repérer sur la ligne écrite le sommet de coefficient minimal et de rayer toutes les cases vides sous ce sommet.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | ||||||
| / | ||||||
| / | ||||||
| / | ||||||
| / | ||||||
| / |
- En troisième étape, pour tous les sommets adjacents à ce sommet de coefficient minimal, on calcule le poids de la chaîne et sous tous les sommets non adjacents, on écrit le coefficient $\infty$.
Ici, le poids de la chaîne $S$-$A$ est $9$ alors que le poids de la chaîne $S$-$I$ est $12$.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | ||||||
| / | ||||||
| / | ||||||
| / | ||||||
| / |
- Il reste des sommets non traités : $V$, $B$ et $E$.
On recommence alors la deuxième étape, on cherche le sommet de coefficient minimal, on le repère et on raye toutes les cases vides sous ce sommet.
On recommence la troisième étape.
En regardant bien le graphe, tu peux remarquer que, pour atteindre le sommet $U$, on a le choix entre $S$-$U$ de poids $20$ ou $S$-$A$-$U$ de poids $17$.
On inscrit le poids minimal dans le tableau en on complète avec le coefficient $\infty$ sous les sommets non adjacents.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | / | $12,S$ | $17,A$ | $30,A$ | $\infty$ | $\infty$ |
| / | / | |||||
| / | / | |||||
| / | / | |||||
| / | / |
On recommence l’opération jusqu’à ce que tous les sommets soient sélectionnés.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | / | $12,S$ | $17,A$ | $30,A$ | $\infty$ | $\infty$ |
| / | / | / | $16,I$ | $30,A$ | $25,I$ | $\infty$ |
| / | / | / | / | $27,U$ | $23,U$ | $\infty$ |
| / | / | / | / | $27,U$ | / | $32,B$ |
| / | / | / | / | / | / | $30,V$ |
- Le poids minimal se lit sur la dernière ligne du tableau, c’est-à-dire $30$.
La plus courte chaîne menant de $S$ à $E$ se lit également dans le tableau : il s’agit de la chaîne $S$-$I$-$U$-$V$-$E$ de poids $30$.