Comment déterminer si un graphe orienté est connexe à partir de sa matrice d'adjacence ? | MetMat

Comment déterminer si un graphe orienté est connexe à partir de sa matrice d'adjacence ?

En calculant $I_n + A + A^2 + \dots + A^{n-1}$ et en vérifiant que tous ses coefficients sont strictement positifs

Décider si un graphe (orienté ou non) à $n$ sommets est connexe grâce à un critère sur la matrice $I_n+A+A^2+\dots+A^{n-1}$ .

L'objectif

Décider si un graphe (orienté ou non) à $n$ sommets est connexe grâce à un critère sur la matrice $I_n+A+A^2+\dots+A^{n-1}$ .

Le principe

Pour tout couple $(i,j)$ de sommets, le coefficient $(i,j)$ de la matrice $M=I_n+A+A^2+\dots+A^{n-1}$ dénombre les chemins de longueur au plus $n-1$ de $i$ vers $j$ (en comptant $I_n$ pour $i=j$ ) ; le graphe est connexe (ou fortement connexe dans le cas orienté) si et seulement si tous les coefficients de $M$ sont strictement positifs.

La méthode

1
Je détermine la matrice d'adjacence $A$ et le nombre $n$ de sommets du graphe.
Comment construire la matrice d'adjacence d'un graphe (orienté ou non) ?Voir
2
Je calcule les puissances $A,A^2,\dots,A^{n-1}$ et j'en déduis $M=I_n+A+A^2+\dots+A^{n-1}$ .
Comment calculer les puissances $n$-èmes d'une matrice carrée ?Voir
3
Je vérifie le signe de chaque coefficient de $M$ : si tous sont $>0$ , le graphe est connexe ; sinon, je repère les couples $(i,j)$ tels que $M_{i,j}=0$ pour exhiber un défaut de connexité.

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Le graphe orienté à $3$ sommets de matrice $A=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ est-il fortement connexe ?

Étape 1 —

Je détermine la matrice d'adjacence

A

et le nombre

n

de sommets du graphe.

On a $n=3$ et la matrice $A$ est celle du triangle orienté $1\to 2\to 3\to 1$ .

Étape 2 —

Je calcule les puissances

A,A^2,\dots,A^{n-1}

et j'en déduis

M=I_n+A+A^2+\dots+A^{n-1}

Je calcule $A^2=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ puis $M=I_3+A+A^2=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}$ .

Étape 3 —

Je vérifie le signe de chaque coefficient de

M

: si tous sont

>0

, le graphe est connexe ; sinon, je repère les couples

(i,j)

tels que

M_{i,j}=0

pour exhiber un défaut de connexité.

Tous les coefficients de $M$ sont strictement positifs : le graphe est fortement connexe.

Oui, le graphe est fortement connexe.

Application guidée

Le graphe orienté à $3$ sommets de matrice $A=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$ est-il fortement connexe ?

Application autonome 1

Soit le graphe non orienté à $3$ sommets de matrice $A=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ (chemin $1-2-3$ ). Est-il connexe ?

Application autonome 2

Le graphe orienté de matrice d'adjacence $A=\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ est-il fortement connexe ?

Application autonome 3

Soit le graphe orienté à $3$ sommets de matrice d'adjacence $A=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$ . Ce graphe est-il fortement connexe ?

Crée ton compte gratuit pour accéder à la fiche et aux exercices

En calculant In+A+A2+⋯+An−1I_n + A + A^2 + \dots + A^{n-1}In​+A+A2+⋯+An−1 et en vérifiant que tous ses coefficients sont strictement positifs

Pour comprendre, fais des exercices !

En calculant $I_n + A + A^2 + \dots + A^{n-1}$ et en vérifiant que tous ses coefficients sont strictement positifs