mathématiques appliquées (ECG 1re année) · Chapitre 3 · Exercice d'entraînement

Deux morceaux qu'aucune puissance ne relie

Théorie des graphes · Connexité · ★★★ niveau 3 (difficile)

Énoncé

Un graphe $G$ à six sommets a pour arêtes $\{1,2\},\{2,3\},\{1,3\},\{4,5\},\{5,6\}$. Montrer, sans calculer aucune puissance, que $(A^d{)}_{14}=0$ pour tout $d\ge 1$. Qu'en conclut-on par le critère matriciel de connexité ? Déterminer enfin les composantes de $G$.

Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.