Graphes : Fiche de cours - Mathématiques

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

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

graphe spécialité mathématiques terminale ES

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

graphe spécialité mathématiques terminale ES

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

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

graphe spécialité mathématiques terminale ES

La matrice d’adjacence associée à ce graphe d’ordre $5$ est la matrice suivante :

$\begin{array}{c}\ \text{A}\ \text{ B }\ \text{ C }\ \text{ D }\ \text{ E } \end{array} \begin{array}{r} \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{array}$

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

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

graphe spécialité mathématiques terminale ES

$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

graphe spécialité mathématiques terminale ES

$\text{M}=\begin{array}{c}\ \text{A}\ \text{ B }\ \text{ C }\ \text{ D }\ \text{ E } \end{array} \begin{array}{r} \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{array}\;$ donc

$\;\text{M}^3=\begin{array}{c}\ \text{A}\ \text{ B }\ \text{ C }\ \text{ D }\ \text{ E } \end{array} \begin{array}{r} \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{array}$

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

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

graphe connexe

Ce graphe est connexe.

graphe non 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

graphe spécialité mathématiques terminale ES

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

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

graphe orienté spécialité mathématiques terminale ES

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

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

graphe orienté spécialité mathématiques terminale ES

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

graphe spécialité mathématiques terminale ES

$\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

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

graphe étiqueté spécialité mathématiques terminale ES

À 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

graphe spécialité mathématiques terminale ES

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

À 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 1^re ligne d’un tableau
Sur la 2^e 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

graphe spécialité mathématiques terminale ES

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$ .