Cours : Graphes et matrices

Graphes non orientés

Graphe non orienté : définitions et vocabulaire

Prenons l’exemple d’un groupe de cinq amis : Alex, Béa, Charles, David et Émeline comparent leurs loisirs et se demandent s’ils pratiquent une activité sportive.
Dans ce groupe, Alex n’aime pas le sport et n’en fait pas. Les autres sont inscrits dans des clubs sportifs de la région.

On appelle un graphe le groupe des cinq amis et la relation « … fait du sport comme… ».

• Cet exemple nous permet d’introduire le vocabulaire propre aux graphes.

Définition

Graphe non orienté et vocabulaire associé :

On appelle graphe non orienté un ensemble fini d’éléments, reliés ou non par une propriété commune.

• Les éléments s’appellent les sommets du graphe.
• Le nombre de sommets s’appelle l’ordre du graphe.
• La relation entre deux éléments est appelée une arête. Les arêtes peuvent se parcourir dans les deux sens.
• S’ils sont reliés entre eux par une arête, deux sommets sont adjacents.
• Si un sommet n’est relié à aucun autre, on dit que c’est un sommet isolé.

Nous constaterons que le vocabulaire utilisé : sommet, arête, adjacent, est largement emprunté à la géométrie.
En effet, on représente habituellement un graphe par un schéma où les sommets sont des points et les arêtes des segments ou des lignes.

Exemple

Dans l’exemple ci-dessus, représentons les cinq amis par des points nommés d’après les initiales de leur prénom : $A$, $B$, $C$, $D$ et $E$.

• La relation « … fait du sport comme… » est schématisée par un segment ou une ligne.

Graphe représentant les relations sportives des cinq amis

• Dans ce graphe, il y a cinq sommets.
• L’ordre du graphe est donc $5$.
• Il y a un sommet isolé : $A$.
• Les sommets $B$ et $C$ sont adjacents, puisqu’ils sont reliés par l’arête $[BC]$.

Nous pouvons parcourir cette arête dans les deux sens : on peut dire que Béa fait du sport comme Charles, mais aussi que Charles fait du sport comme Béa.

• Nous pouvons compter les arêtes de ce graphe : il y en a $6$.

Si Alex ne participe pas à la discussion, le graphe devient un graphe d’ordre $4$ ci-dessous :

Dans ce dernier graphe, chaque sommet est adjacent à tous les autres.

• Un tel graphe s’appelle un graphe complet. Notons-en la définition.

Définition

Graphe complet :

Un graphe complet est un graphe où deux sommets quelconques sont toujours adjacents.

• Autrement dit : dans un graphe complet, chaque sommet est relié à tous les autres.

Dans le cas de nos cinq amis, nous avons dénombré facilement le nombre d’arêtes. Si on prend un graphe plus complexe comme les membres d’un même réseau social ayant un intérêt commun, cela peut s’avérer plus difficile.
Voyons donc une propriété qui permet de calculer le nombre d’arêtes.

Degré des sommets et nombre d’arêtes

Commençons par définir le degré d’un sommet.

Définition

Degré d’un sommet :

Soit un graphe noté $G$.
Le degré d’un sommet de $G$ est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe.

Reprenons le graphe suivant :

Le degré de $A$ est $0$ ; les degrés de $B$, $C$, $D$ et $E$ valent tous $3$.

• Additionnons les degrés : $0+3+3+3+3=12$.
• Nous rappelons que le nombre d’arêtes de ce graphe est $6$.

Prenons maintenant un second exemple.

Exemple

La région administrative du Centre-Val-de-Loire comporte $6$ départements que nous avons numérotés de $1$ à $6$. Nous nous intéressons à la relation « … a une frontière commune avec… ».

• À partir de la carte, nous obtenons le graphe non orienté $G$.

Graphe de la région Centre-Val-de-Loire

Construisons un tableau donnant les degrés des sommets :

Sommet	$1$	$2$	$3$	$4$	$5$	$6$
Degré	$2$	$3$	$3$	$3$	$2$	$5$

• Faisons la somme des degrés : $2+3+3+3+2+5 =18$.
• Nous comptons les arêtes : il y en a $9$.

Dans les deux exemples ci-dessus, nous constatons que la somme des degrés des sommets vaut le double du nombre d’arêtes.

Donnons-en une explication.
Soit deux sommets adjacents $S_1$ et $S_2$ : en additionnant leurs degrés, on compte deux fois l’arête qui les relie.

• Nous en déduisons qu’en calculant la somme de tous les degrés, nous compterons deux fois chaque arête.

Nous avons la propriété suivante.

Propriété

Dans un graphe $G$ non orienté, la somme des degrés est égale au double du nombre d’arêtes.

Cette propriété s’avère utile quand il est difficile de dénombrer sur un graphique le nombre d’arêtes.
Prenons un autre exemple pour nous en convaincre.

Exemple

Lors d’un congrès scientifique, $31$ chercheurs et chercheuses se rencontrent. Le jour de l’inauguration, ils échangent tous une poignée de mains.

Considérons qu’il s’agit d’un graphe à $31$ sommets. Les arêtes représentent la poignée de mains échangée. Chacun des $31$ chercheurs serre la main aux $30$ autres.

• Donc le degré de chaque sommet est $30$.

La somme des degrés est $30\times31$.
Donc, d’après la propriété ci-dessus, le nombre d’arêtes du graphe est :

$$\dfrac{30\times31}2=465$$

• Nous en déduisons qu’il y a $465$ poignées de mains échangées.

Attention

L’erreur serait de faire le produit de $30$ par $31$ seulement : dans ce cas, on comptabiliserait deux fois chaque poignée de mains.

De la propriété ci-dessus, nous déduisons également les corollaires suivants.

Propriété

Dans un graphe non orienté :

• la somme des degrés des sommets d’un graphe est paire ;
• il y a un nombre pair de sommets de degré impair.

Intéressons-nous maintenant aux parcours possibles dans un graphe, c’est-à-dire au moyen de passer d’un sommet à un autre.

Parcours dans un graphe non orienté

Quand nous parcourons un graphe, nous empruntons différentes arêtes. Voici le vocabulaire associé au parcours dans un graphe non orienté.

Définition

Chaîne dans un graphe non orienté :

$G$ est un graphe non orienté.
Une chaîne de $G$ est une suite d’arêtes consécutives.

• Si les deux extrémités de la chaîne sont le même sommet, la chaîne est fermée.

Définition

Longueur d’une chaîne :

La longueur d’une chaîne est le nombre d’arêtes qu’elle contient.

Prenons un exemple pour illustrer les parcours dans un graphe.

Exemple

Reprenons le graphe $G$ ci-dessus, montrant les frontières communes entre les départements du Centre-Val-de-Loire. Nous cherchons :

• différentes chaînes qui permettent de passer du sommet $1$ au sommet $6$ ;
• une chaîne qui part de $2$ et revient à $2$.

Graphe de la région Centre-Val-de-Loire

• Prenons la chaîne $1-2-6$. Il y a trois sommets sur ce parcours et deux arêtes.
• La longueur de cette chaîne est donc $2$.

Citons quelques autres chaînes qui permettent de passer de $1$ à $6$ :

• $1-2-3-4-5-6$, de longueur $5$ ;
• $1-2-3-6$, de longueur $3$ ;
• $1-6$, de longueur $1$.

Il y en a bien sûr d’autres, car rien n’empêche d’emprunter la même arête plus d’une fois.
Nous verrons, dans la dernière partie de ce cours, une méthode pour dénombrer les chaînes de longueur donnée entre deux sommets.

• Pour partir du sommet $2$ et revenir au sommet $2$, nous parcourons une chaîne fermée.

Une chaîne fermée d’origine et d’extrémité $2$ est : $2-3-4-6-2$.

• Sa longueur vaut $4$.

Dans la dernière chaîne de l’exemple, nous n’avons parcouru qu’une seule fois chaque arête.

• Cette chaîne s’appelle un cycle.

Définition

Cycle :

Dans un graphe non orienté, un cycle est une chaîne fermée qui ne comporte que des arêtes distinctes.

Allons un peu plus loin : quel que soit le sommet de ce graphe, on peut y accéder à partir de n’importe quel autre sommet en parcourant une chaîne.

• On dit alors que le graphe est connexe.

Définition

Graphe connexe :

$G$ est un graphe non orienté.
Si deux sommets quelconques peuvent toujours être reliés par une chaîne, alors $G$ est un graphe connexe.

Exemple

Illustrons ce qu’est un graphe non connexe :

Graphe non connexe

Dans ce graphe, il n’est pas possible de trouver une chaîne qui relie, par exemple, les sommets $A$ et $E$.

• Ce graphe n’est pas connexe.

Dans cette première partie, nous avons défini le vocabulaire propre aux graphes non orientés et étudié leurs premières propriétés.
Intéressons-nous maintenant aux graphes orientés.

Graphes orientés

Définitions et vocabulaire

Un graphe orienté présente les mêmes caractéristiques qu’un graphe non orienté, à la différence que les arêtes ont un sens de parcours.

Définition

Graphe orienté et vocabulaire associé :

Un graphe orienté est constitué de sommets.

• Le nombre de sommets s’appelle l’ordre du graphe.
• Certains sommets sont reliés par des arêtes qui sont orientées : elles ne peuvent être parcourues que dans un seul sens.

Prenons un exemple simple de graphe orienté.

Ce graphe est d’ordre $4$, car il a $4$ sommets.
Les sommets $H$ et $G$ sont adjacents, $I$ et $G$ sont également adjacents, ainsi que $K$ et $G$.

Observons à présent le sens de parcours des arêtes :

• il y a une arête qui part de $I$, mais il n’y a pas d’arête qui arrive sur $I$ ;
• il y a une arête qui arrive sur $H$, mais pas d’arête qui part de $H$ ;
• nous pouvons toutefois faire un parcours $G-K-G$ car il y a $2$ arêtes, une dans chaque sens, entre ces $2$ sommets.

Attention

La lecture du sens des arêtes est importante, car elle va déterminer les parcours possibles sur un graphe.
Dans notre exemple, il sera impossible d’effectuer le parcours $K-G-I$ puisque l’arête entre $G$ et $I$ est dans le sens de $I$ vers $G$ uniquement.

Enfin, nous observons pouvoir aller de $K$ vers $K$ avec une seule arête.

• Cette arête s’appelle une boucle.

Définition

Boucle :

Dans un graphe orienté, une boucle est une arête orientée d’origine et d’extrémité identiques.

Prenons à présent un exemple plus complexe pour illustrer la construction d’un graphe orienté.

Exemple

Nous voulons représenter par un graphe la relation « … est un diviseur de… » dans l’ensemble des entiers naturels inférieurs ou égaux à $10$.

• Ce graphe a $10$ sommets : les nombres entiers de $1$ à $10$.
• L’ordre du graphe est donc $10$.
• Nous savons que $5$ et $10$ sont adjacents, puisque $5$ divise $10$. Mais $10$ ne divise pas $5$.

De manière générale, si $\begin{cases} d \text{ divise } n \\ d<n \end{cases}$, alors $n$ ne divise pas $d$.

• L’arête qui relie le sommet $d$ au sommet $n$ sera parcourue dans un seul sens : de $d$ vers $n$.
• Nous avons donc un graphe orienté.

Pour le construire, il faut déterminer les diviseurs possibles de chaque nombre dans l’ensemble donné.
Nous savons que $1$ divise tous les autres ; que $2$ divise les nombres pairs, que $3$ divise $6$ et $9$, etc.

• Voici donc le graphe obtenu :

Graphe des diviseurs

Le sens de parcours de chaque arête est donné par la flèche sur l’arête.
Comme pour un graphe non orienté, nous pouvons utiliser le vocabulaire que nous avons appris au paragraphe précédent.

Ainsi, ce graphe :

• n’est pas complet : en effet, les sommets ne sont pas deux à deux adjacents : par exemple, $9$ et $2$ ne sont pas adjacents puisque $2$ ne divise pas $9$, et $9$ ne divise pas $2$ ;
• ne possède pas de sommet isolé.

Chacun des entiers est divisible par lui-même : nous avons donc représenté le fait que tout entier $n$ admet $n$ comme diviseur par une boucle.

À présent, pouvons-nous parcourir le graphe du sommet $1$ au sommet $10$ ?

• Nous constatons que les parcours suivants sont possibles :

$$\begin{aligned} &1-10 \\ &1-2-10 \\ &1-5-10 \\ &1-2-2-10 \\ &1-5-5-10 \end{aligned}$$

Astuce

Comme dans un graphe non orienté, on parle de chaîne pour un parcours constitué d’arêtes consécutives.

• Nous trouverons dans certains exercices le mot chemin quand le parcours est orienté.

Si la chaîne ou le chemin a une origine et une extrémité identiques, alors on dira que c’est une chaîne fermée, ou un chemin fermé.

• S’il existe un chemin fermé qui n’emprunte qu’une seule fois une arête nous parlerons parfois de circuit pour un graphe orienté. Le mot est équivalent à cycle.

Notons enfin que les arêtes, dans un graphe orienté, sont parfois appelées arcs.

Voyons à présent comment comptabiliser le nombre d’arêtes qui partent ou arrivent sur un sommet.

Degré des sommets

Le degré d’un sommet a la même signification que dans un graphe non orienté.

Définition

Degré d’un sommet :

Soit un graphe orienté noté $G$.
Le degré d’un sommet de $G$ est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe, quel que soit leur sens de parcours.

Attention

Soit $G$ un graphe et $S$ un de ses sommets.
Une boucle sur un sommet $S$ est considérée comme deux arêtes : en effet, elle part de $S$ et elle arrive vers $S$.

• Elle sera comptée $2$ fois dans le calcul du degré d’un sommet.

Exemple

Reprenons l’exemple du graphe des diviseurs.

• Le degré du sommet $1$ est $11$ : en effet, du sommet $1$ partent $9$ arêtes vers les autres sommets, et la boucle sur $1$ compte pour $2$ arêtes.
• Le degré du sommet $4$ est $5$ : $2$ arêtes qui arrivent, $1$ arête qui part et une boucle.
• Le degré du sommet $6$ est $5$ : $3$ arêtes qui arrivent et une boucle.

La propriété qui s’applique sur la somme de degrés pour un graphe non orienté est encore valable.

Propriété

Dans un graphe $G$ orienté, la somme des degrés est égale au double du nombre d’arêtes.

Nous pourrons nous en servir également pour déterminer le nombre d’arêtes d’un sommet, mais sans pouvoir distinguer celles qui y arrivent ou en repartent.

Dans cette partie, nous avons défini les graphes orientés et montré comment on les représente. Ils seront largement utilisés dans le chapitre suivant sur les chaînes de Markov.
Dans la troisième partie de ce chapitre, nous allons étudier la représentation d’un graphe par une matrice.

Matrices d’adjacence d’un graphe

Matrice d’adjacence d’un graphe non orienté

Soit $G$ un graphe non orienté d’ordre $n$.
Il possède $n$ sommets $S_1$, $S_2$, …, $S_{n-1}$, $S_n$.

• Nous allons associer à ce graphe une matrice $A$.

Faisons d’abord quelques rappels utiles.

Rappel

Une matrice carrée d’ordre $n$ est une matrice qui a le même nombre de lignes et de colonnes.

• On note : $a_{i,j}$, ou $(A)_{i,j}$ le coefficient de la matrice situé à la $i\text{-ème}$ ligne et la $j \text{-ième}$ colonne.

Définition

Matrice d’adjacence d’un graphe non orienté :

Soit $G$ un graphe non orienté d’ordre $n$.
La matrice d’adjacence de $G$ est la matrice carrée $A$ d’ordre $n$ définie par :

Pour tous $i$ et $j$ de $\lbrace 1,\,…,\,n\rbrace$, le coefficient $a_{i,j}$ est égal au nombre d’arêtes qui relient $S_i$ et $S_j$.

Exemple

Reprenons le graphe non orienté que nous avons vu en première partie pour construire sa matrice d’adjacence.

Graphe non orienté à 5 sommets

À retenir

Méthodologie :

Pour construire une matrice d’adjacence :

• on choisit d’ordonner les sommets, notamment quand ils ne sont pas représentés par des nombres ;
• l’ordre du graphe est l’ordre de la matrice, donc on connaît la taille de la matrice à écrire ;
• on indique, sur chaque ligne $i$, le nombre d’arêtes qui relient le sommet $S_i$ aux autres sommets $S_j$ dans l’ordre : de $1$ à $n$.

Appliquons cette méthode au graphe.
Nous pouvons naturellement classer les sommets par ordre alphabétique :

• L’ordre du graphe est $5$, donc nous devons écrire une matrice carrée d’ordre $5$.
• La $1^{\text{re}}$ ligne concerne le $1^{\text{er}}$ sommet $A$, donc nous y indiquons le nombre d’arêtes qui relient :
• $A$ à $A$ : $\textcolor{#3CB371}{a_{1,1}=0}$ ;
• $A$ à $B$ : $\textcolor{#3CB371}{a_{1,2}=0}$ ;
• $A$ à $C$ : $\textcolor{#3CB371}{a_{1,3}=0}$ ;
• $A$ à $D$ : $\textcolor{#3CB371}{a_{1,4}=0}$ ;
• $A$ à $E$ : $\textcolor{#3CB371}{a_{1,5}=0}$.
• La $2^{\text{e}}$ ligne concerne le $2^\text{e}$ sommet $B$, donc nous y indiquons le nombre d’arêtes qui relient :
• $B$ à $A$ : $\textcolor{#FFA500}{a_{2,1}=0}$ ;
• $B$ à $B$ : $\textcolor{#FFA500}{a_{2,2}=0}$ ;
• $B$ à $C$ : $\textcolor{#FFA500}{a_{2,3}=1}$ ;
• $B$ à $D$ : $\textcolor{#FFA500}{a_{2,4}=1}$ ;
• $B$ à $E$ : $\textcolor{#FFA500}{a_{2,5}=1}$.
• Voici donc la matrice avec ses deux premières lignes :

$$\begin{pmatrix} \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 \\ \textcolor{#FFA500}0 & \textcolor{#FFA500}0 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 \\ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \\ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \\ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \end{pmatrix}$$

• Nous poursuivons ainsi pour les $3$ autres sommets pour obtenir la matrice d’adjacence de ce graphe :

$$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{pmatrix}$$

Astuce

Faisons une remarque supplémentaire sur cette matrice : matérialisons, avec des couleurs, la diagonale et observons les coefficients de part et d’autre de cette diagonale.

$$\begin{pmatrix} \red 0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 \\ \textcolor{#3CB371}0 & \red 0 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 \\ \textcolor{#3CB371}0 & \textcolor{#FFA500}1 & \red 0 & \textcolor{#9400D3}1 & \textcolor{#9400D3}1 \\ \textcolor{#3CB371}0 & \textcolor{#FFA500}1 & \textcolor{#9400D3}1 & \red 0 & \textcolor{#1E90FF}1 \\ \textcolor{#3CB371}0 & \textcolor{#FFA500}1 & \textcolor{#9400D3}1 & \textcolor{#1E90FF}1 & \red 0 \end{pmatrix}$$

Nous observons les mêmes groupes de coefficients de part et d’autre de la diagonale, en symétrie.
Pour l’expliquer, intéressons-nous aux coefficients de la matrice.

Soit $i$ et $j$ deux entiers de $\lbrace 1,\,…,\,n \rbrace$.
Comparons $a_{i,j}$ et $a_{j,i}$.

• $a_{i,j}$ est le nombre d’arêtes entre le sommet $S_i$ et le sommet $S_j$.
• $a_{j,i}$ est le nombre d’arêtes entre le sommet $S_j$ et le sommet $S_i$ : ces deux nombres sont donc les mêmes !
• Ainsi, quels que soient $i$ et $j$ de $\lbrace 1,\,…,\,n\rbrace$, on a : $a_{i,j}=a_{j,i}$.

On dit que la matrice $A$ est une matrice symétrique.
Ceci nous aidera à distinguer les matrices d’adjacence des graphes non orientés de celles correspondant à un graphe orienté, que nous verrons dans le prochain paragraphe.

Prenons maintenant un deuxième exemple pour illustrer comment on obtient un graphe à partir d’une matrice d’adjacence.

Exemple

Considérons un graphe $G$, dont la matrice d’adjacence est :

$$\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$$

• Nous cherchons à représenter $G$.

À retenir

Méthodologie :

• L’ordre de la matrice carrée donne l’ordre du graphe, donc le nombre de sommets.
• On schématise les sommets par des points que l’on nomme avec des lettres ou des chiffres, ou en suivant les consignes de l’énoncé.
• On utilise les coefficients $a_{i,j}$ pour relier les sommets par des arêtes.

Appliquons cette méthode.

• La matrice est d’ordre $4$, donc il y a $4$ sommets dans ce graphe.
• Appelons les $4$ sommets dans cet ordre : $A$, $B$, $C$ et $D$.
• La $1^{\text{re}}$ ligne nous donne le nombre d’arêtes qui relient le sommet $1$, soit $A$, aux autres :

• Nous pouvons donc commencer à faire le graphe :

• Puis nous le complétons en procédant de même avec les autres lignes.

Astuce

Nous l’avons dit plus haut, la matrice d’adjacence d’un graphe non orienté est symétrique. Nous pouvons donc ne nous intéresser qu’aux coefficients de la diagonale et à ceux « au-dessous » ou « au-dessus ».

Nous avons vu comment représenter une matrice d’adjacence d’un graphe non orienté. Qu’en est-il maintenant pour un graphe orienté ?

Matrice d’adjacence d’un graphe orienté

Soit $G$ un graphe orienté d’ordre $n$ : il possède $n$ sommets $S_1$, $S_2$, …, $S_{n-1}$, $S_n$.

• Nous allons associer à ce graphe une matrice $A$.

Définition

Matrice d’adjacence d’un graphe orienté :

Soit $G$ un graphe orienté d’ordre $n$.
La matrice d’adjacence de $G$ est la matrice carrée $A$ d’ordre $n$ définie par :

Pour tous les entiers $i$ et $j$ de $\lbrace 1,\, …,\,n\rbrace$, le coefficient $a_{i,j}$ est égal au nombre d’arêtes qui partent de $S_i$ vers $S_j$.

À retenir

Méthodologie :

Pour construire la matrice d’adjacence d’un graphe orienté :

• on choisit un ordre pour les sommets ; quand ils ne sont pas représentés par des nombres, on doit fixer un ordre ;
• l’ordre du graphe est l’ordre de la matrice, donc on connaît la taille de la matrice à écrire ;
• on indique, sur chaque ligne $i$, le nombre d’arêtes qui partent du sommet $S_i$ vers les autres sommets $S_j$, dans l’ordre : de $1$ à $n$.

Exemple

Prenons l’exemple des $8$ groupes sanguins humains, avec leur rhésus, et la relation « … est donneur pour le groupe… ».
Ils sont représentés par le graphe ci-dessous.

Graphe des groupes sanguins

Notons les groupes dans cet ordre :

• Le graphe est d’ordre $8$, donc nous devons construire une matrice carrée $A$ d’ordre $8$.

Pour construire la matrice, nous serons attentifs au sens de parcours des arêtes.

• Détaillons la $1^\text{re}$ ligne de la matrice $A$.

Du sommet $\text O+$, partent $4$ arêtes, vers $\text O+$, $\text A+$, $\text B+$ et $\text {AB}+$. Donc :

• $\textcolor{#3CB371}{a_{1,1}=a_{1,3}=a_{1,5}=a_{1,7}=1}$ ;
• les autres coefficients sont nuls.
• De même, intéressons-nous à la $2^\text{e}$ ligne de $A$.

Du sommet $\text{O}-$ partent des arêtes vers tous les autres sommets, y compris $\text{O}-$.

• Pour tout $j$, $ \textcolor{#FFA500}{a_{2,j}=1}$.
• Nous procédons ainsi ligne par ligne, et nous obtenons la matrice :

$$\begin{pmatrix} \textcolor{#3CB371}1 & 0 & \textcolor{#3CB371}1 & 0 & \textcolor{#3CB371}1 & 0 & \textcolor{#3CB371}1 & 0 \\ \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}$$

• Nous observons que cette matrice n’est pas symétrique, contrairement aux matrices d’adjacence d’un graphe non orienté.

Voyons maintenant comment représenter un graphe dont on connaît la matrice d’adjacence.

Exemple

Nous cherchons le graphe associé à la matrice suivante :

$$A=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{pmatrix}$$

• Cette matrice est d’ordre $3$, donc le graphe dont elle est la matrice d’adjacence est d’ordre $3$ : il y a trois sommets, que l’on notera $1$, $2$ et $3$.
• En observant la $1^\text{re}$ ligne, nous déduisons que du sommet $1$ partent trois arêtes vers les sommets $1$, $2$ et $3$.
• En observant la $2^\text{e}$ ligne, nous déduisons que du sommet $2$ part une arête vers $2$ – c’est donc une boucle. Il n’y a pas d’arête vers le sommet $1$ : nous en déduisons qu’il s’agit d’un graphe orienté.

Nous aurions pu également le déduire en observant la matrice et en constatant qu’elle n’est pas symétrique.

• Voici donc le graphe orienté obtenu :

Nous allons maintenant nous servir des matrices d’adjacence pour déterminer le nombre de chaînes ou de chemins de longueur donnée entre deux sommets.

Nombre de chemins de longueur $n$ entre deux sommets

Prenons l’exemple d’un parcours sportif où il y a plusieurs ateliers : un saut de haies, des barres parallèles, des espaliers et un saute-mouton.

• Les parcours conseillés entre les différents ateliers sont schématisés par les arêtes du graphe orienté ci-dessous.

Alex, qui vient de commencer le sport mais aime la variété, cherche le nombre de parcours de longueur $3$ entre le départ $D$ et l’arrivée $A$, bien sûr en respectant les sens conseillés.
Pour trouver ce nombre, nous allons utiliser la propriété suivante.

Propriété

Soit $m\in \mathbb N^*$, $G$ un graphe d’ordre $n$, de sommets $S_1$, $S_2$, …, $S_{n-1}$, $S_n$, et $A$ sa matrice d’adjacence.
Pour tous entiers $i$ et $j$ : le nombre de chemins – ou chaînes – de longueur $m$ entre $S_i$ et $S_j$ est $(A^m )_{i,j}$.

• C’est-à dire le coefficient de la matrice $A^m$ situé à la $i\text{-ème}$ ligne et la $j\text{-ième}$ colonne.

Démonstration

Considérons un graphe $G$ d’ordre $n$ de sommets $S_1$, $S_2$, …, $S_{n-1}$, $S_n$, et $A$ sa matrice d’adjacence.
$S_i$ et $S_j$ sont deux sommets quelconques de ce graphe.

Quel que soit $m\in \mathbb N^*$, on note : $P_m$ la propriété : « $(A^m )_{i,j}$ est le nombre de chaînes de longueur $m$ entre $S_i$ et $S_j$ ».

• Nous allons démontrer cette propriété par récurrence.
• Initialisation : démontrons $P_1$.

$(A^1 )_{i,j} = (A)_{i,j}$ est le coefficient $a_{i,j}$ de la matrice $A$.
D’après la définition de la matrice d’adjacence, $a_{i,j}$ est le nombre d’arêtes qui relient $S_i$ et $S_j$ ; c’est donc le nombre de chaînes de longueur $1$ entre $S_i$ et $S_j$.

• $P_1$ est donc vraie.
• Hérédité : supposons qu’il existe $m\in \mathbb N^*$ tel que $P_m$ soit vraie.

Nous supposons donc que $(A^m )_{i,j}$ est le nombre de chaînes de longueur $m$ entre $S_i$ et $S_j$, quels que soient les sommets $S_i$ et $S_j$.

Considérons une chaîne de longueur $m+1$.
Nous pouvons la décomposer en deux chaînes consécutives :

• une chaîne de longueur $m$ qui part du sommet $S_i$ jusqu’à un sommet quelconque, que l’on notera $S_k$ ;
• puis une chaîne de longueur $1$ qui part de $S_k$ jusqu’à $S_j$.

Dénombrons ces chaînes.

• D’après l’hypothèse de récurrence $P_m$, le nombre de chaînes de longueur $m$ entre $S_i$ et $S_k$ est $(A^m )_{i,k}$ , le coefficient de la matrice $A^m$ placé en $i\text{-ème}$ ligne et $k\text{-ième}$ colonne.

Pour chacune de ces chaînes de longueur $m$, il y a $a_{k,j}$ arêtes entre $S_k$ et $S_j$, donc il y a $a_{k,j}$ chaînes de longueur $1$.
Donc le nombre de chaînes de longueur $m+1$ qui passent par $S_k$ au bout de $m$ arêtes est $(A^m )_{i,k}\times a_{k,j}$

• Pour avoir le nombre total de ces chaînes de longueur $m+1$, nous devons donc faire la somme sur l’ensemble des sommets $S_k$ possibles.

Ainsi le nombre de chaînes de longueur $m+1$ entre $S_i$ et $S_j$ est :

$$(A^m)_{i,1}\times a_{1,j}+(A^m )_{i,2}\times a_{2,j}+…+ (A^m )_{i,n} \times a_{n,j}$$

Nous nous rappelons que c’est le coefficient placé sur la ligne $i$ et la colonne $j$, obtenu en multipliant la matrice $A^m$ par la matrice $A$ :

$$A^m\times A=A^{m+1}$$

Nous avons donc montré que $(A^{m+1})_{i,j}$ est le nombre de chaînes de longueur $m+1$ entre $S_i$ et $S_j$.

• $P_{m+1}$ est vraie.
• Conclusion : la propriété $P_m$ : « $(A^m)_{i,j}$ est le nombre de chaînes de longueur $m$ entre $S_i$ et $S_j$ », est vraie pour tout $m\in \mathbb N^*$.

Remarque :
Cette démonstration est juste que le graphe soit orienté ou non.

Exemple

Reprenons l’exemple du début de ce paragraphe :

Graphe orienté représentant le parcours sportif

À retenir

Méthodologie :

Pour déterminer le nombre de chemins de longueur $m$ entre deux sommets $S_i$ et $S_j$ :

• trouver la matrice d’adjacence $A$ du graphe ;
• calculer à la main, ou à la calculatrice, la matrice $A^m$ ;
• trouver le coefficient situé à la ligne $i$ et la colonne $j$ de cette matrice.
• Ce sera le nombre de chemins cherché.

Appliquons cette méthode ici.

• La matrice d’adjacence de ce graphe est une matrice carrée $A$ d’ordre $6$ puisqu’il y a $6$ sommets.

Écrivons cette matrice en utilisant la méthode que nous avons vue au point b : nous ordonnons les sommets dans l’ordre où ils sont écrits :

Attention

Comme c’est un graphe orienté, nous ne comptons que les arêtes qui partent du sommet vers un autre.

$$A=\begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$

• Calculons maintenant $A^3$, puisque nous cherchons les chemins de longueur $3$.

À l’aide de la calculatrice, nous obtenons :

$$A^3=\begin{pmatrix} 0 & \purple 1 & 0 & \textcolor{#FFA500}1 & 0 & \red 2 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & \green 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \blue 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Le coefficient cherché est le coefficient $(A^3)_{1,6}$ puisqu’on cherche le nombre de chemins de longueur $3$ qui partent de $D$ ($1^\text{re}$ ligne) vers $A$ ($6^\text{e}$ colonne).
Nous lisons dans la matrice que $\red{(A^3 )_{1,6}= 2}$.

• Cela signifie qu’il n’y a que $\red 2$ chemins de longueur $3$ qui partent de $D$ vers $A$.

Si Alex voulait parcourir d’autres chemins de longueur $3$ et terminer tout de même à l’arrivée, il pourrait tricher en partant des espaliers, car il existe entre $E$ et $A$ $\green 1$ chemin de longueur $3$, ou en commençant par le saute-mouton, puisque là aussi il existe $\blue 1$ chemin de longueur $3$ qui mène de $S$ à $A$.

Remarquons enfin que, s’il respecte le départ et souhaite se limiter à un chemin de longueur $3$, il peut aussi s’arrêter aux barres parallèles ($\purple 1$ chemin entre $D$ et $P$) ou au saut de haies ($\textcolor{#FFA500}1$ chemin aussi entre $D$ et $H$).

Dans cet exemple, nous avons pris un graphe d’ordre $6$.
Mais les applications dans les réseaux routiers ou les interactions entre membres d’un même réseau social peuvent impliquer plusieurs centaines de sommets et des chemins plus longs à trouver.
L’utilisation de cette propriété et des moyens de traitement informatiques permettent d’optimiser les chemins entre deux sommets d’un graphe.