Deux morceaux, des zéros qui persistent

Exercice · niveau 2 · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Connexité

Énoncé

Les sommets d'un graphe $G$ se répartissent en deux paquets non vides $P$ et $Q$ , sans aucune arête entre eux. Montrer que $(A^{d})_{ij} = 0$ pour tout $d \geq 1$ , tout $i$ de $P$ et tout $j$ de $Q$ . Qu'en dit le critère matriciel de connexité ?

Corrigé

Récurrence sur $d$ .

Initialisation. Pour $d = 1$ , $(A^{1})_{ij} = a_{ij} = 0$ : c'est l'hypothèse, il n'y a aucune arête de $P$ vers $Q$ .

Hérédité. Supposons $(A^{d})_{ik} = 0$ pour tout $i \in P$ et tout $k \in Q$ . Soient $i \in P$ et $j \in Q$ ; coupons la somme selon le paquet où vit l'intermédiaire : $(A^{d + 1})_{ij} = k \sum (A^{d})_{ik} a_{k j} = k \in P \sum (A^{d})_{ik} a_{k j} + k \in Q \sum (A^{d})_{ik} a_{k j} .$ Dans la première somme, $k \in P$ et $j \in Q$ donnent $a_{k j} = 0$ . Dans la seconde, $i \in P$ et $k \in Q$ donnent $(A^{d})_{ik} = 0$ par hypothèse de récurrence. Tous les termes sont nuls.

Le critère. Comme $(I_{n})_{ij} = 0$ pour $i \neq = j$ , le coefficient $(i, j)$ de $I_{n} + A + \dots + A^{n - 1}$ est nul : le critère déclare $G$ non connexe, ce qui est bien le cas.

Le point à retenir. Chacune des deux sommes s'annule pour une raison différente — l'une par l'hypothèse, l'autre par la récurrence. Un chemin qui devrait franchir une frontière inexistante n'existe pas, et le produit matriciel le sait.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.