Exercices corrigés : introduction aux graphes et aux matrices (201-N11)

a) $S = \{A, B, C, D, E\}$ et $A = \{AB, AC, BC, BD, CD, DE\}$, soit 6 arêtes. On les relève en balayant le dessin dans un ordre fixe, par exemple alphabétique sur le premier sommet, pour n'en oublier aucune ni en compter deux fois.

b) $\deg(A) = 2$ (vers $B$ et $C$), $\deg(B) = 3$ (vers $A$, $C$, $D$), $\deg(C) = 3$ (vers $A$, $B$, $D$), $\deg(D) = 3$ (vers $B$, $C$, $E$), $\deg(E) = 1$ (vers $D$).

c) Somme des degrés : $2+3+3+3+1 = 12$. Nombre d'arêtes : 6. On a bien $12 = 2 \times 6$. Ce contrôle est le premier à faire après avoir relevé un graphe : s'il échoue, c'est qu'une arête a été oubliée ou comptée deux fois.

d) Chaque arête a deux extrémités et contribue donc pour 1 au degré de chacune d'elles, soit 2 au total de la somme des degrés. En sommant sur toutes les arêtes, on obtient $\sum_{s} \deg(s) = 2\lvert A \rvert$. Cette somme est paire ; or les sommets de degré pair y contribuent une quantité paire, donc la contribution des sommets de degré impair doit elle aussi être paire, ce qui n'est possible que s'ils sont en nombre pair. Ici, les sommets de degré impair sont $B$, $C$, $D$ et $E$ : ils sont bien quatre.

e) Dans un graphe simple, il y a au plus une arête par paire de sommets et aucune boucle : le maximum est le nombre de paires, $\dbinom{5}{2} = \dfrac{5 \times 4}{2} = 10$ arêtes, et $\dfrac{n(n-1)}{2}$ en général. Un tel graphe est dit complet. Notre graphe en compte 6 sur 10 possibles.

f) Oui : $A \to B \to D \to E$ est un chemin, et il en existe d'autres, comme $A \to C \to D \to E$. Le graphe est connexe, puisque de proche en proche tout sommet est atteint depuis $A$ : $B$ et $C$ directement, $D$ par $B$, $E$ par $D$. Un graphe à $n$ sommets connexe compte au moins $n-1$ arêtes ; ici $6 \ge 4$, ce qui est cohérent, sans être une preuve à soi seul.

a) Les arcs sont $1 \to 2$, $1 \to 3$, $2 \to 3$, $2 \to 4$, $3 \to 1$ et $4 \to 3$. En rangeant les sommets dans l'ordre 1, 2, 3, 4, la ligne $i$ décrit les arcs QUI PARTENT de $i$ : $M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$. Contrôle : la matrice compte 6 coefficients égaux à 1, autant que le graphe a d'arcs.

b) La somme de la ligne $i$ est le nombre d'arcs partant de $i$, c'est-à-dire son degré SORTANT. La somme de la colonne $j$ est le nombre d'arcs arrivant en $j$, son degré ENTRANT. Confondre les deux est l'erreur qui fausse toute la suite du chapitre, parce qu'elle revient à transposer le graphe.

c) Degrés sortants : $2, 2, 1, 1$, de somme 6. Degrés entrants : sommet 1 reçoit de 3, donc 1 ; sommet 2 reçoit de 1, donc 1 ; sommet 3 reçoit de 1, 2 et 4, donc 3 ; sommet 4 reçoit de 2, donc 1. Somme : $1+1+3+1 = 6$. Les deux sommes valent 6, le nombre d'arcs : chaque arc a exactement un départ et une arrivée. C'est la version orientée du lemme des poignées de main, sans facteur 2.

d) Elle est SYMÉTRIQUE, c'est-à-dire égale à sa transposée. Une arête non orientée entre $i$ et $j$ se lit dans les deux sens, donc $M_{ij} = M_{ji}$. Réciproquement, une matrice d'adjacence symétrique décrit un graphe qu'on peut considérer comme non orienté. Notre matrice ne l'est pas : $M_{12} = 1$ mais $M_{21} = 0$, ce qui confirme que le graphe est bien orienté.

e) Un coefficient $M_{ii} = 1$ signalerait une BOUCLE, c'est-à-dire un arc d'un sommet vers lui-même. Notre graphe n'en a aucune, sa diagonale est nulle. Les boucles sont interdites dans un graphe dit simple, mais elles apparaissent naturellement dès qu'on modélise un automate ou une page web qui pointe vers elle-même.

a) $A+B = \begin{pmatrix} 1 & 6 \\ 5 & 0 \end{pmatrix}$, terme à terme. Pour la combinaison : $2A = \begin{pmatrix} 2 & 4 \\ 6 & -2 \end{pmatrix}$ et $3B = \begin{pmatrix} 0 & 12 \\ 6 & 3 \end{pmatrix}$, donc $2A - 3B = \begin{pmatrix} 2 & -8 \\ 0 & -5 \end{pmatrix}$.

b) $AB = \begin{pmatrix} 1(0)+2(2) & 1(4)+2(1) \\ 3(0)+(-1)(2) & 3(4)+(-1)(1) \end{pmatrix} = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$. Et $BA = \begin{pmatrix} 0(1)+4(3) & 0(2)+4(-1) \\ 2(1)+1(3) & 2(2)+1(-1) \end{pmatrix} = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$. Les deux produits diffèrent : le produit matriciel n'est PAS commutatif. C'est la différence la plus importante avec le produit des nombres réels, et en infographie elle a un sens concret : tourner puis translater ne donne pas la même image que translater puis tourner.

c) $A^{T} = \begin{pmatrix} 1 & 3 \\ 2 & -1 \end{pmatrix}$ et $B^{T} = \begin{pmatrix} 0 & 2 \\ 4 & 1 \end{pmatrix}$ : la première ligne devient la première colonne.

d) $(AB)^{T} = \begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$. Et $B^{T}A^{T} = \begin{pmatrix} 0(1)+2(2) & 0(3)+2(-1) \\ 4(1)+1(2) & 4(3)+1(-1) \end{pmatrix} = \begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$. Les deux coïncident. Le point à retenir est l'INVERSION de l'ordre : la transposée d'un produit est le produit des transposées prises à l'envers. La même inversion se produit pour l'inverse d'un produit.

e) Le produit $PQ$ existe si et seulement si le nombre de COLONNES de $P$ égale le nombre de LIGNES de $Q$. Si $P$ est de taille $m \times n$ et $Q$ de taille $n \times p$, alors $PQ$ est de taille $m \times p$. C'est la vérification à faire avant tout calcul : bien souvent, $AB$ existe et $BA$ n'existe pas, ce qui règle la question de la commutativité sans le moindre calcul.

f) $A^{2} = AA = \begin{pmatrix} 1(1)+2(3) & 1(2)+2(-1) \\ 3(1)+(-1)(3) & 3(2)+(-1)(-1) \end{pmatrix} = \begin{pmatrix} 7 & 0 \\ 0 & 7 \end{pmatrix}$. Ce n'est évidemment pas la matrice des carrés, qui vaudrait $\begin{pmatrix} 1 & 4 \\ 9 & 1 \end{pmatrix}$. Le résultat est ici remarquable : $A^{2} = 7I$, donc $A$ se comporte comme une racine carrée de 7 fois l'identité. On en déduit d'ailleurs immédiatement que $A$ est inversible, d'inverse $\dfrac{1}{7}A$.

a) On multiplie $M$ par elle-même. Ligne 1 : le sommet 1 pointe vers 2 et 3, donc la ligne 1 de $M^{2}$ est la somme des lignes 2 et 3 de $M$, soit $(0,0,1,1) + (1,0,0,0) = (1,0,1,1)$. Ligne 2 : le sommet 2 pointe vers 3 et 4, somme des lignes 3 et 4 : $(1,0,0,0)+(0,0,1,0) = (1,0,1,0)$. Ligne 3 : le sommet 3 pointe vers 1, donc la ligne 1 de $M$ : $(0,1,1,0)$. Ligne 4 : le sommet 4 pointe vers 3, donc la ligne 3 de $M$ : $(1,0,0,0)$. D'où $M^{2} = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$. Ce procédé, où chaque ligne du produit est une somme de lignes, est beaucoup plus rapide que le calcul coefficient par coefficient quand la matrice ne contient que des 0 et des 1.

b) Le coefficient $(1,1)$ de $M^{2}$ vaut 1 : il existe exactement un chemin de longueur 2 du sommet 1 vers lui-même, à savoir $1 \to 3 \to 1$. C'est un cycle de longueur 2, et il apparaît sur la diagonale : les coefficients diagonaux de $M^{k}$ comptent les cycles de longueur $k$ passant par chaque sommet.

c) $M^{3} = M^{2}M$. Ligne 1 : $(1,0,1,1)$ sélectionne les lignes 1, 3 et 4 de $M$, dont la somme vaut $(0,1,1,0)+(1,0,0,0)+(0,0,1,0) = (1,1,2,0)$. En continuant : $M^{3} = \begin{pmatrix} 1 & 1 & 2 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$. Le coefficient $(1,3)$ vaut 2 : il y a deux chemins de longueur 3 de 1 vers 3, à savoir $1 \to 2 \to 4 \to 3$ et $1 \to 3 \to 1 \to 3$. Le second repasse par des sommets déjà vus, ce qui est autorisé : c'est bien pour cela que le coefficient vaut 2 et non 1. Confondre chemin et chemin sans répétition est l'erreur qui fait rater ce théorème.

d) Par définition du produit, $(M^{2})_{ij} = \sum_{k} M_{ik}M_{kj}$. Chaque terme de cette somme vaut 1 exactement quand $M_{ik} = 1$ ET $M_{kj} = 1$, c'est-à-dire quand il existe un arc de $i$ vers $k$ ET un arc de $k$ vers $j$ : cela décrit précisément un chemin $i \to k \to j$ de longueur 2 passant par $k$. La somme sur $k$ compte donc tous les chemins de longueur 2 de $i$ à $j$, un par sommet intermédiaire possible. Le passage au cas général se fait par récurrence, en écrivant $M^{k+1} = M^{k}M$ et en découpant chaque chemin de longueur $k+1$ en un chemin de longueur $k$ suivi d'un arc.

e) C'est la somme de la première ligne de $M^{2}$ : $1+0+1+1 = 3$. Autre lecture : le sommet 1 a deux successeurs, 2 et 3, qui ont respectivement 2 et 1 successeurs, soit $2+1 = 3$ chemins. Les deux comptes coïncident, ce qui valide le calcul matriciel.

a) Un chemin qui repasse deux fois par le même sommet contient un cycle que l'on peut supprimer sans changer ses extrémités. Pour $i \neq j$, s'il existe un chemin de $i$ à $j$, il en existe donc un sans répétition : il visite au plus $n$ sommets et compte au plus $n-1$ arcs. Pour un retour de $i$ vers lui-même, en revanche, le cycle peut visiter les $n$ sommets et compter alors $n$ arcs. Il faut donc aller jusqu'à $M^{n}$, et $M^{n-1}$ ne suffit que si l'on se limite aux couples de sommets distincts. La question suivante montre que cette nuance n'est pas théorique.

b) On réunit $M$, $M^{2}$, $M^{3}$ et $M^{4}$ en mettant un 1 dès que l'une des quatre en a un. $M$ donne les paires $(1,2), (1,3), (2,3), (2,4), (3,1), (4,3)$ ; $M^{2}$ ajoute $(1,1), (1,4), (2,1), (3,2), (3,3), (4,1)$ ; $M^{3}$ ajoute $(2,2), (3,4), (4,2)$. À ce stade, une seule position reste à 0, la position $(4,4)$ : quinze cases sur seize sont remplies. Elle est comblée par $M^{4}$, grâce au cycle $4 \to 3 \to 1 \to 2 \to 4$, qui compte quatre arcs. La matrice d'accessibilité est donc entièrement remplie de 1. C'est l'illustration exacte de la question a) : ce cycle passe par les quatre sommets, il lui faut donc quatre arcs, et s'arrêter à $M^{3}$ aurait conclu à tort que le sommet 4 ne peut pas revenir à lui-même.

c) Oui. Un graphe orienté est fortement connexe quand tout sommet est accessible depuis tout autre, ce qui se lit exactement sur une matrice d'accessibilité entièrement remplie de 1. Le cycle $4 \to 3 \to 1 \to 2 \to 4$ suffit d'ailleurs à s'en convaincre sans matrice : il passe par les quatre sommets, donc en le parcourant assez longtemps on va de n'importe quel sommet à n'importe quel autre.

d) Un arbre couvrant d'un graphe connexe à $n$ sommets compte exactement $n-1$ arêtes, ici $5-1 = 4$. Le graphe en a 6, il faut donc en retirer $6-4 = 2$, en veillant à ne casser aucune connexion. Par exemple retirer $BC$ et $CD$ laisse $AB$, $AC$, $BD$, $DE$, qui relient bien les cinq sommets sans cycle. Le nombre d'arêtes à retirer, $\lvert A \rvert - \lvert S \rvert + 1$, s'appelle le nombre cyclomatique et compte les cycles indépendants du graphe.

e) L'algorithme de Warshall est fait de trois boucles imbriquées sur les sommets, chacune de longueur $n$ : son coût est en $n^{3}$ opérations. C'est plus économique que de calculer et de réunir les $n-1$ premières puissances de $M$, ce qui coûterait $n$ multiplications de matrices à $n^{3}$ opérations chacune, soit $n^{4}$. La différence tient à une seule idée : Warshall met à jour la matrice EN PLACE, en autorisant progressivement les sommets intermédiaires.

a) $H = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} = 2I$. Les images sont $H(P_{1}) = (2,2)$, $H(P_{2}) = (8,2)$ et $H(P_{3}) = (2,6)$ : chaque coordonnée est doublée. Une homothétie de rapport $k$ centrée à l'origine est toujours $kI$, et c'est la seule famille de matrices qui commute avec toutes les autres.

b) La rotation de $90$ degrés envoie $(1,0)$ sur $(0,1)$ et $(0,1)$ sur $(-1,0)$. Ces images sont les colonnes de la matrice, d'où $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$, c'est-à-dire $(x,y) \mapsto (-y,x)$. Images : $R(P_{1}) = (-1,1)$, $R(P_{2}) = (-1,4)$ et $R(P_{3}) = (-3,1)$. La règle générale vaut la peine d'être retenue : les colonnes d'une matrice sont les images des vecteurs de base.

c) La symétrie par rapport à l'axe des abscisses laisse $x$ inchangé et change le signe de $y$ : $S = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$. C'est la transformation que subit implicitement toute image affichée à l'écran, où l'axe vertical est dirigé vers le bas.

d) $T$ est rectangle en $P_{1}$, de côtés $P_{1}P_{2} = 3$ et $P_{1}P_{3} = 2$ : son aire vaut $\dfrac{3 \times 2}{2} = 3$. Après l'homothétie, les deux côtés doublent et l'aire est multipliée par 4 : elle vaut 12. Après la rotation, la figure est superposable à la figure de départ : l'aire reste 3.

e) L'aire est multipliée par $\lvert \det \rvert$. En effet $\det H = 4$ et l'aire a été multipliée par 4 ; $\det R = 0 \times 0 - (-1)(1) = 1$ et l'aire est conservée ; $\det S = -1$, l'aire est conservée mais l'orientation est renversée, ce que le signe négatif signale. Une matrice de déterminant nul écrase la figure sur une droite ou sur un point : l'aire devient nulle, et la transformation n'est pas réversible.

f) Non. Une transformation linéaire fixe toujours l'origine, puisque $M \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$, alors qu'une translation déplace l'origine en $(3,1)$. Aucune matrice $2 \times 2$ ne peut donc translater. C'est précisément le problème que règlent les coordonnées homogènes, en ajoutant une troisième coordonnée valant 1 et en travaillant avec des matrices $3 \times 3$.

a) $\det A = (1)(-1) - (2)(3) = -1 - 6 = -7$, non nul, donc $A$ est inversible. La formule donne $A^{-1} = \dfrac{1}{-7}\begin{pmatrix} -1 & -2 \\ -3 & 1 \end{pmatrix} = \begin{pmatrix} 1/7 & 2/7 \\ 3/7 & -1/7 \end{pmatrix}$. On retrouve le résultat de l'exercice 3 : puisque $A^{2} = 7I$, on a bien $A^{-1} = \dfrac{1}{7}A$.

b) $AA^{-1} = \dfrac{1}{7}A^{2} = \dfrac{1}{7}(7I) = I$. En détaillant : le coefficient $(1,1)$ vaut $1(1/7) + 2(3/7) = 1/7 + 6/7 = 1$ ; le coefficient $(1,2)$ vaut $1(2/7) + 2(-1/7) = 0$. La vérification par le produit est obligatoire, parce qu'une erreur de signe dans la formule de l'inverse ne se voit pas autrement.

c) On développe suivant la première ligne : $\det N = 2\begin{vmatrix} 3 & 1 \\ 1 & 2 \end{vmatrix} - 1\begin{vmatrix} 1 & 1 \\ 0 & 2 \end{vmatrix} + 0 = 2(6-1) - 1(2-0) + 0 = 10 - 2 = 8$. Le troisième terme est nul parce que son coefficient l'est : choisir la ligne ou la colonne la plus creuse épargne un mineur entier, et ici la première ligne comme la troisième contiennent un zéro.

d) $\det R = 1$, et la formule donne $R^{-1} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$. C'est la matrice de la rotation de $-90$ degrés : défaire une rotation, c'est tourner dans l'autre sens. On remarque aussi que $R^{-1} = R^{T}$, ce qui est vrai pour toute matrice de rotation et rend l'inversion gratuite dans un moteur graphique.

e) $\det = (2)(2) - (4)(1) = 0$ : elle n'est pas inversible. Géométriquement, elle écrase tout le plan sur une droite : les deux colonnes $(2,1)$ et $(4,2)$ sont proportionnelles, donc toutes les images sont des multiples de $(2,1)$. L'information est perdue, plusieurs points différents ont la même image, et aucune matrice ne peut défaire cela. C'est exactement ce que traduit un déterminant nul : l'aire est écrasée à zéro.

f) Parce qu'il faut défaire les opérations dans l'ordre inverse de celui où on les a faites. Vérification : $(PQ)(Q^{-1}P^{-1}) = P(QQ^{-1})P^{-1} = PIP^{-1} = PP^{-1} = I$. La même inversion apparaît pour la transposée, $(PQ)^{T} = Q^{T}P^{T}$. Image concrète : pour défaire « mettre ses chaussettes puis ses chaussures », on retire les chaussures d'abord.