Graphes et matrices

I. Matrice d'adjacence

Une matrice d’adjacence est une manière de représenter un graphe sous forme matricielle.
Si le graphe possède $n$ sommets, on construit une matrice carrée $A$ de taille $n \times n$ telle que :

$\checkmark$ $a_{ij} = 1$ s’il existe une arête allant du sommet $i$ vers le sommet $j$ ;

$\checkmark$ $a_{ij} = 0$ sinon.

Dans le cas d’un graphe non orienté, la matrice est symétrique : $a_{ij} = a_{ji}$.

Exemple :

Considérons un graphe orienté à 3 sommets $A$, $B$ et $C$, avec les arêtes suivantes :

$\checkmark$ de $A$ vers $B$

$\checkmark$ de $B$ vers $C$

$\checkmark$ de $C$ vers $A$

On peut numéroter les sommets : $A = 1$, $B = 2$, $C = 3$

On peut réaliser un tableau des relations :

Cela permet de lire facilement, par exemple :

$\checkmark$ Ligne A, colonne B → 1 : il y a un arc de A vers B

$\checkmark$ Ligne C, colonne A → 1 : il y a un arc de C vers A

ce qui s'écrit également $a_{11}=0$ car A n'est pas relié à lui-même ; $a_{12}=1$ car le graphe est orienté de A vers B, etc.

La matrice d’adjacence $M$ est : $M = \begin{pmatrix} 0 \quad 1 \quad 0 \\ 0 \quad 0 \quad 1 \\ 1 \quad 0 \quad 0 \end{pmatrix}$

Chaque $1$ dans la matrice indique la présence d’une arête entre deux sommets.

Passer du tableau des relations à la matrice d'adjacence est immédiat.

II. Graphe probabiliste

Un graphe probabiliste est un graphe orienté dans lequel chaque arête est associée à une probabilité.
Ces probabilités modélisent une transition d’un sommet à un autre selon un processus aléatoire, par exemple une marche aléatoire ou un modèle de Markov que nous verrons ultérieurement.

Pour tout sommet $i$, la somme des probabilités des arêtes sortantes est égale à $1$ : $\displaystyle\sum_{j} P_{ij} = 1$

Exemple :

Prenons un graphe probabiliste à 3 sommets $X$, $Y$ et $Z$.
Depuis chaque sommet, on peut aller vers les autres avec une certaine probabilité :

$\checkmark$ Depuis $X$ : $P(X \rightarrow Y) = 0.6$, $P(X \rightarrow Z) = 0.4$

$\checkmark$ Depuis $Y$ : $P(Y \rightarrow X) = 1.0$

$\checkmark$ Depuis $Z$ : $P(Z \rightarrow Z) = 1.0$ (il boucle sur lui-même)

Ce graphe est probabiliste car : $\displaystyle \sum_{j} P_{ij} = 1 \text{ pour chaque sommet } i$

III. Matrice de transition d’un graphe probabiliste

La matrice de transition $P$ d’un graphe probabiliste est une matrice carrée $n \times n$ dans laquelle :

$\checkmark$ $P_{ij}$ représente la probabilité de passer du sommet $i$ au sommet $j$.

Chaque ligne de $P$ représente une distribution de probabilité, donc :

$\checkmark$ $0 \leq P_{ij} \leq 1$ pour tout $i, j$

$\checkmark$ $\displaystyle\sum_{j=1}^n P_{ij} = 1$ pour chaque ligne $i$

Cette matrice est utilisée dans de nombreux modèles, comme les chaînes de Markov, pour étudier des évolutions probabilistes à travers un graphe.

Exemple :

On reprend les probabilités de l’exemple précédent pour construire la matrice de transition $P$ :

Chaque ligne représente la probabilité de transition à partir d’un sommet donné.
Par exemple, la première ligne indique que depuis $X$, on va vers $Y$ avec une probabilité $0.6$ et vers $Z$ avec une probabilité $0.4$.

IV. Calculer un nombre de chemins de longueur donnée

Théorème :

Soit un graphe de matrice d’adjacence $M$. Le nombre de chemins de longueur $n$ ($n \in \mathbb{N}^*$), d’un sommet $i$ à un sommet $j$, est égal au coefficient de $M^n$ de la ligne $i$ et de la colonne $j$.

Exemple :

Voici un graphe orienté X-Y-Z

$1.$ Donner la matrice d'adjacence de ce graphe.

$2.$ Combien y-a-t-il de chemins de longueur 5 reliant le sommet X au sommet Z ?

Solution :

$1.$ La table des relations est :

On en déduit la matrice d'adjacence :

$M = \begin{pmatrix} 0 \quad 1 \quad 0 \\ 1 \quad 0 \quad 1 \\ 1 \quad 1 \quad 1 \end{pmatrix}$

$2.$ Le nombre de chemins de longueur 5 du sommet X vers le sommet Z est le terme $a_{13}$ de la matrice $M^5$.

Calculons $M⁵$ à la calculatrice.

Il y a donc 5 chemins de longueur 5 du sommet X vers le sommet Z.