Comment déterminer si un graphe… : En calculant I_n + A + A^2 + … + A^ n-1… — ECG1 appliquées | 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}$ .

Maîtriser

Reconnaître

Résoudre

Que ferais-tu face à un exercice de ce type ?

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 ?

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 !

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.

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

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

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