Médaille
N°1 pour apprendre & réviser du collège au lycée.
Graphes

Déjà plus de

1 million

d'inscrits !

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

bannière definition

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.
bannière propriete

Propriété

La somme des degrés des sommets d’un graphe non orienté est égale au double du nombre total d’arêtes.

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

Ce graphe possède 55 sommets (AA, BB, CC, DD, EE) ; c’est un graphe d’ordre 55.

  • Il n’est pas complet car les sommets AA et EE 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 55 sommets du graphe :

Sommet AA BB CC DD EE
Degré 22 33 33 33 33

On peut compter sur le graphes que le nombre total d’arêtes est 77 et la somme des degrés des sommets est 1414 (soit le double du nombre total d’arêtes).

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

Ce graphe qui possède 44 sommets (AA, BB, CC, DD) est un graphe d’ordre 44 complet car tous ses sommets sont adjacents.

Le tableau ci-dessous représente les degrés des 44 sommets du graphe :

Sommet AA BB CC DD
Degré 33 33 33 33

Le nombre total d’arêtes est 66 et la somme des degrés des sommets est 1212 soit le double du nombre total d’arêtes.

Matrice d’adjacence

bannière definition

Définition

Matrice d’adjacence :

La matrice d’adjacence associée à un graphe non orienté d’ordre nn dont les sommets sont numérotés de 1 à nn la matrice carrée d’ordre nn où le terme situé en ligne ii et colonne jj est égal au nombre d’arêtes reliant ii et jj.

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

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

ABCDE A    B    C    D    E (0101010101010111010101110)\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 11 situé en ligne 11 et colonne 22 signifie qu’il y a une arête qui relie AA à BB.

Le coefficient 00 situé en ligne 22 et colonne 44 signifie qu’il n’y a pas d’arête qui relie BB à DD.

bannière à retenir

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

bannière definition

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.

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

AA-DD-CC est une chaîne et AA-DD-CC-BB-AA est un cycle.

bannière propriete

Propriété

Trouver dans un graphe un nombre de chaînes de longueur donnée

Soit pp un entier naturel et MM la matrice d’adjacence associée à un graphe non orienté dont les sommets sont numérotés.

Le terme aija_{ij} (ligne ii colonne jj) de la matrice MpM^p donne le nombre de chaînes de longueur pp reliant ii et jj.

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

M=A B  C  D  E  A    B    C    D    E (0101010101010111010101110)\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

  M3=A B  C  D  E  A    B    C    D    E (0626262727274756272727574)\;\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 22 chaînes de longueur 33 reliant BB à DD.
    Ces chaînes sont : BB-CC-EE-DD et BB-EE-CC-DD.

Graphes connexes et trajets eulériens

bannière definition

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

bannière exemple

Exemple

graphe connexe

Ce graphe est connexe.

graphe non connexe

Ce graphe n’est pas connexe.

bannière definition

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.

bannière theoreme

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 00 ou 22.

Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets sont de degré pair.

bannière à retenir

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

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

Tableau des degrés des 55 sommets de ce graphe :

Sommet AA BB CC DD EE
Degré 11 44 11 22 22

Comme le graphe comporte 22 sommets de degré impair, il existe une chaîne eulérienne (par exemple, AA-BB-EE-DD-BB-CC 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

bannière definition

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.

bannière exemple

Exemple

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

Il s’agit d’un graphe orienté de degré 33.

Il comprend une boucle qui relie le sommet 11 à lui-même.

Matrice d’adjacence

Tout comme pour les graphes non orientés, on peut associer à chaque graphe orienté une matrice d’adjacence.

bannière definition

Définition

Matrice d’adjacence :

La matrice d’adjacence associée à un graphe orienté d’ordre nn, dont les sommets sont numérotés de 11 à nn, est une matrice carrée d’ordre nn où le terme figurant en ligne ii et colonne jj est égal à 11 s’il existe une arête menant de ii à jj et à 00 sinon.

bannière exemple

Exemple

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

La matrice d’adjacence associée à ce graphe d’ordre 33 est : M=(110\100\010)\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 « 11 » situé en ligne 11 et colonne 22 signifie qu’il y a une arête orientée qui mène de ① vers ②.

Le coefficient « 00 » situé en ligne 33 et colonne 33 signifie qu’il n’y a pas d’arête orientée qui mène de ③ vers ③ (pas de boucle au sommet n°33).

bannière à retenir

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

bannière propriete

Propriété

Trouver dans un graphe un nombre de chaîne d’une longueur donnée

Soit pp un entier naturel et MM la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. Le terme aija_{ij} (ligne ii colonne jj) de la matrice MpM^p donne le nombre de chaînes de longueur pp reliant ii et jj.

bannière astuce

Astuce

Cette propriété est exactement la même pour les graphes non orientés.

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

M=(110\100\010)  \text{M}=\begin{pmatrix} 1&1&0\\1&0&0\\0&1&0 \end{pmatrix}\; donc   M4=(530\320\210)\;\text{M}^4=\begin{pmatrix} 5&3&0\\3&2&0\\2&1&0 \end{pmatrix}

La matrice M4\text{M}^4 nous indique qu’il y a 33 chaînes de longueur 44 menant de ① à ②.

Ces chaînes sont : ①-①-①-①-② ; ①-①-②-①-② et ①-②-①-①-②

Graphes étiquetés et graphes pondérés

bannière definition

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.

bannière exemple

Exemple

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

À partir de ce graphe étiqueté on peut former certains mots.

bannière definition

Définition

Graphe pondéré :

Un graphe pondéré est un graphe étiqueté dont toutes les étiquettes sont des nombres positifs.

bannière definition

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.

bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

Soit le graphe pondéré d’ordre 55 ci-contre :

  • la chaîne AA-BB-DD-EE-CC de ce graphe est de longueur 44
  • son poids est de 1111
  • la plus courte chaîne reliant AA à CC a pour longueur 22 et pour poids 66. Il s’agit de la chaîne AA-BB-CC.
bannière attention

Attention

La longueur d’une chaîne est le nombre d’arêtes qui la composent.

Algorithme de Dijkstra-Moore

bannière à retenir

À 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 00 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 XX de coefficient minimal.
  • Commencer une nouvelle ligne et rayer toutes les cases vides sous XX.
  • Étape 3 : pour chaque sommet YY adjacent à XX, calculer la somme PP du coefficient de XX et du poids de l’arête reliant YY à XX.
  • Si PP est strictement inférieur au coefficient de YY, inscrire PXPX dans la case correspondante de la colonne YY.
  • Sinon, inscrire le coefficient de YY 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.
bannière exemple

Exemple

graphe spécialité mathématiques terminale ES

Dans ce graphe, on cherche à déterminer la plus courte chaîne menant de SS à EE.

  • 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 00 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.

SS AA II UU VV BB EE
00 \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 SS-AA est 99 alors que le poids de la chaîne SS-II est 1212.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/
/
/
/
/
  • Il reste des sommets non traités : VV, BB et EE.

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 UU, on a le choix entre SS-UU de poids 2020 ou SS-AA-UU de poids 1717.

On inscrit le poids minimal dans le tableau en on complète avec le coefficient \infty sous les sommets non adjacents.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/ / 12,S12,S 17,A17,A 30,A30,A \infty \infty
/ /
/ /
/ /
/ /

On recommence l’opération jusqu’à ce que tous les sommets soient sélectionnés.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/ / 12,S12,S 17,A17,A 30,A30,A \infty \infty
/ / / 16,I16,I 30,A30,A 25,I25,I \infty
/ / / / 27,U27,U 23,U23,U \infty
/ / / / 27,U27,U / 32,B32,B
/ / / / / / 30,V30,V
  • Le poids minimal se lit sur la dernière ligne du tableau, c’est-à-dire 3030.
    La plus courte chaîne menant de SS à EE se lit également dans le tableau : il s’agit de la chaîne SS-II-UU-VV-EE de poids 3030.