Mathématiques pour l'informatique 201-N11 • Cégep à Montréal

Fiche de révision : graphes et matrices (201-N11)

Les graphes et les matrices sont deux écritures du même objet, et c'est ce va-et-vient que l'examen teste : une question posée sur le dessin se résout souvent plus vite sur la matrice, et l'inverse est vrai aussi.

Cette fiche rassemble les lectures qui rapportent : ce que dit la diagonale, ce que dit la symétrie, ce que compte exactement une puissance, et pourquoi l'ordre d'un produit de transformations n'est jamais indifférent.

Le fil du chapitre

Une matrice d'adjacence n'est pas un tableau de nombres : chaque coefficient est un arc, et une puissance $k$ -ième compte les chemins de longueur EXACTEMENT $k$ .

Ce chapitre fait partie de Mathématiques pour l'informatique, 201-N11

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Remonter plus loin : la chaîne complète (10 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Nombres réels, racines et ensemblesSecondaire 3
2Expressions algébriques et mise en évidenceSecondaire 3
3Équations et inéquations du premier degréSecondaire 3
4Systèmes d'équations : comparaison et graphiqueSecondaire 3
5La manipulation d'expressions algébriquesSecondaire 4 SN4
6La factorisation et les expressions rationnellesSecondaire 4 SN4
7Les équations et les inéquationsSecondaire 4 SN4
8Les systèmes d'équationsSecondaire 4 SN4
9Logique booléenne et mathématique
10Théorie des ensembles et relations

L'essentiel

Degrés, arêtes et le lemme des poignées de main

• $\sum_{s}\deg(s)=2\,|A|$ : chaque arête est comptée une fois à chacune de ses deux extrémités.
• Conséquence immédiate : le nombre de sommets de degré IMPAIR est toujours pair.
• Un arbre couvrant d'un graphe connexe à $n$ sommets compte exactement $n-1$ arêtes.
• Dans un graphe orienté, on distingue le degré SORTANT, lu sur la ligne de la matrice, du degré ENTRANT, lu sur la colonne.

Le lemme sert surtout à réfuter : un énoncé qui annonce des degrés de somme impaire décrit un graphe qui n'existe pas, et le dire rapporte le point sans aucun dessin.

La matrice d'adjacence et ce qu'on y lit

• $M_{ij}=1$ s'il existe un arc de $i$ vers $j$ : la ligne donne les successeurs, la colonne les prédécesseurs.
• $M$ est symétrique SI ET SEULEMENT SI le graphe est non orienté.
• Un coefficient diagonal non nul signale une BOUCLE sur le sommet correspondant.
• La somme d'une ligne est le degré sortant, la somme d'une colonne le degré entrant, et la somme totale est le nombre d'arcs.

Le même graphe des deux côtés : cinq arcs à gauche, cinq coefficients à

1

à droite, et la ligne

1

porte les deux successeurs du sommet

1

Toujours écrire les numéros de lignes et de colonnes autour de la matrice : la moitié des erreurs de lecture viennent d'un coefficient repéré à l'envers.

Les puissances comptent les chemins

• $(M^{k})_{ij}$ est le nombre de chemins de longueur EXACTEMENT $k$ de $i$ vers $j$ , les répétitions de sommets étant autorisées.
• Matrice d'accessibilité : réunion booléenne de $M$ , $M^{2}$ , jusqu'à $M^{n-1}$ .
• Un graphe orienté est fortement connexe si sa matrice d'accessibilité ne contient aucun zéro hors de la diagonale.

« Exactement » est le mot qui coûte des points : pour compter les chemins de longueur AU PLUS $k$ , il faut additionner les puissances, pas lire une seule d'entre elles.

Produit, inverse et transformations

• Le produit matriciel est associatif mais PAS commutatif : $PQ$ et $QP$ sont en général différents.
• $(PQ)^{T}=Q^{T}P^{T}$ et $(PQ)^{-1}=Q^{-1}P^{-1}$ : l'ordre s'inverse.
• $\begin{pmatrix} a & b\\ c & d\end{pmatrix}^{-1}=\dfrac{1}{ad-bc}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}$ , définie seulement si $ad-bc\neq 0$ .
• Les COLONNES d'une matrice de transformation sont les images des vecteurs de base, et l'aire est multipliée par $|\det|$ .

En coordonnées homogènes, un point s'écrit $(x,y,1)$ et les transformations deviennent des matrices $3\times 3$ : c'est ce qui permet d'écrire une translation comme un produit, et donc de la composer avec les autres.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Confondre la somme des degrés et le nombre d'arêtes

1,5 point, et un dessin impossible à réaliser

Ce qu'il ne faut pas écrire

« La somme des degrés vaut $10$ , donc le graphe a $10$ arêtes. »

Ce qu'il faut écrire

« $\sum\deg(s)=2|A|$ , donc $|A|=5$ : chaque arête est comptée deux fois. »

Pourquoi : Une arête a deux extrémités, donc elle contribue une unité à chacun des deux degrés. C'est aussi ce qui interdit une somme de degrés impaire.

2. Lire un graphe orienté comme s'il ne l'était pas

2 points, et tous les chemins calculés ensuite

Ce qu'il ne faut pas écrire

« $M_{12}=1$ , donc $1$ et $2$ sont reliés dans les deux sens. »

Ce qu'il faut écrire

« $M_{12}=1$ donne l'arc de $1$ vers $2$ ; il faudrait $M_{21}=1$ pour l'autre sens, et la matrice n'est pas symétrique. »

Pourquoi : La symétrie de la matrice est exactement la définition du graphe non orienté. Vérifier cette symétrie avant tout calcul prend cinq secondes et évite de compter des chemins qui n'existent pas.

3. Croire qu'une puissance compte les chemins d'au plus k arcs

2 points, c'est la question de comptage de l'examen

Ce qu'il ne faut pas écrire

« $(M^{2})_{13}=1$ , donc il y a en tout un seul chemin de $1$ vers $3$ . »

Ce qu'il faut écrire

« $(M^{2})_{13}=1$ compte les chemins de longueur EXACTEMENT $2$ ; l'arc direct est compté par $M$ , ce qui fait deux chemins de longueur au plus $2$ . »

Le coefficient encadré vaut

1

: un seul chemin de longueur

2

1

vers

3

, celui qui passe par

2

. L'arc direct, lui, est compté dans

M

Pourquoi : Chaque puissance isole une longueur. Pour « au plus $k$ », on additionne les matrices ; pour « existe-t-il un chemin », on prend la réunion booléenne.

4. Supposer que le produit matriciel est commutatif

2 points, et une figure fausse en infographie

Ce qu'il ne faut pas écrire

« $PQ=QP$ , donc l'ordre des transformations n'a pas d'importance. »

Ce qu'il faut écrire

« Le produit n'est PAS commutatif : une rotation suivie d'une symétrie ne donne pas la même figure que la symétrie suivie de la rotation. »

Les mêmes deux transformations, dans les deux ordres : la figure obtenue n'est pas la même, et aucune des deux n'est celle de départ.

Pourquoi : Composer, c'est appliquer l'une puis l'autre : le résultat dépend évidemment de l'ordre. La matrice appliquée EN PREMIER est celle écrite le plus à DROITE dans le produit.

5. Transposer un produit sans inverser l'ordre

1,5 point, et souvent des dimensions incompatibles

Ce qu'il ne faut pas écrire

« $(PQ)^{T}=P^{T}Q^{T}$ . »

Ce qu'il faut écrire

« $(PQ)^{T}=Q^{T}P^{T}$ : la transposition inverse l'ordre des facteurs, comme l'inversion. »

Pourquoi : Le contrôle est dimensionnel : si $P$ est $2\times 3$ et $Q$ est $3\times 4$ , alors $P^{T}Q^{T}$ est un produit $3\times 2$ par $4\times 3$ , qui n'existe pas.

6. Inverser une matrice de déterminant nul

2 points, et la question de réversibilité

Ce qu'il ne faut pas écrire

« $\det=0$ , donc $\dfrac{1}{0}$ vaut l'infini et l'inverse est très grande. »

Ce qu'il faut écrire

« Un déterminant nul signifie que la matrice n'est PAS inversible : la transformation écrase le plan sur une droite. »

Pourquoi : L'aire est multipliée par $|\det|$ : un déterminant nul aplatit toute figure, et une information perdue ne se retrouve pas. L'inverse n'existe donc pas, à aucune valeur.

7. Lire les images des vecteurs de base sur les lignes

1,5 point, et une matrice de transformation transposée

Ce qu'il ne faut pas écrire

« La première LIGNE de la matrice donne l'image du premier vecteur de base. »

Ce qu'il faut écrire

« Ce sont les COLONNES : la première colonne est l'image de $\vec{i}$ , la seconde celle de $\vec{j}$ . »

Pourquoi : Multiplier la matrice par le vecteur $(1\,;0)$ sélectionne exactement la première colonne. Le test se fait de tête et tranche en deux secondes.

8. Composer les transformations dans l'ordre de lecture

2 points, et un objet placé au mauvais endroit à l'écran

Ce qu'il ne faut pas écrire

« On tourne puis on translate, donc la matrice est $R\times T$ . »

Ce qu'il faut écrire

« La transformation appliquée en PREMIER se place à DROITE : c'est $T\times R$ qui tourne d'abord puis translate. »

Pourquoi : Le produit agit sur un vecteur écrit à droite : la matrice la plus proche du vecteur le rencontre en premier. C'est l'inverse du sens de lecture du français.

9. Vouloir écrire une translation comme une matrice deux par deux

2 points, et la composition demandée devient impossible

Ce qu'il ne faut pas écrire

« La translation de vecteur $(3\,;2)$ s'écrit $\begin{pmatrix} 3 & 0\\ 0 & 2\end{pmatrix}$ . »

Ce qu'il faut écrire

« Une translation n'est pas linéaire : elle exige les coordonnées HOMOGÈNES, où le point devient $(x\,;y\,;1)$ et la matrice $3\times 3$ . »

Pourquoi : Toute matrice $2\times 2$ laisse l'origine fixe, alors qu'une translation la déplace. La troisième coordonnée constante est précisément ce qui permet d'ajouter un vecteur par un produit.

Quelle méthode choisir

Que lire dans une matrice d'adjacence

On regarde la question posée, et l'endroit de la matrice qui y répond.

La matrice d'accessibilité du graphe : tous les coefficients hors diagonale valent

1

, donc tout sommet mène à tout autre.

Si on demande si le graphe est orienté → tester la symétrie : $M_{ij}=M_{ji}$ pour tous les couples

Exemple : un seul couple asymétrique suffit à conclure qu'il est orienté
Si on demande les boucles → lire la DIAGONALE : un coefficient non nul y est une boucle

Exemple : $M_{33}=1$ signale une boucle sur le sommet $3$
Si on demande un degré → somme de la ligne pour le degré sortant, de la colonne pour l'entrant

Exemple : la ligne $1$ somme à $2$ : deux successeurs
Si on demande le nombre de chemins d'une longueur donnée → calculer $M^{k}$ et lire le coefficient, sans additionner les puissances

Exemple : $(M^{2})_{13}=1$
Si on demande si un sommet est atteignable → réunion booléenne de $M$ à $M^{n-1}$ , puis lire le coefficient

Exemple : aucun zéro hors diagonale : fortement connexe

Écrire les numéros autour de la matrice avant toute lecture. Une matrice sans en-têtes est la première cause de coefficient lu à l'envers, et l'erreur ne se voit plus ensuite.

Quelle matrice pour quelle transformation du plan

On identifie la transformation, puis on écrit les images des vecteurs de base EN COLONNES.

Si une rotation d'angle $\theta$ autour de l'origine → $\begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{pmatrix}$ , de déterminant $1$

Exemple : un quart de tour envoie $\vec{i}$ sur $\vec{j}$
Si une homothétie de rapport $k$ → $k$ fois la matrice identité, de déterminant $k^{2}$

Exemple : l'aire est multipliée par $k^{2}$
Si une symétrie axiale → déterminant $-1$ : l'aire est conservée, l'orientation inversée

Exemple : la symétrie d'axe des abscisses envoie $\vec{j}$ sur $-\vec{j}$
Si une translation → coordonnées homogènes obligatoires, matrice $3\times 3$

Exemple : le vecteur de translation occupe la dernière colonne
Si une composition de plusieurs transformations → multiplier de DROITE à GAUCHE dans l'ordre d'application

Exemple : tourner puis translater s'écrit $T\times R$

Le déterminant se lit comme un contrôle : $1$ pour une rotation, $-1$ pour une symétrie, $k^{2}$ pour une homothétie, $0$ pour une projection. Une valeur inattendue signale une colonne mal écrite.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Analyser un graphe par sa matrice

Quand l'utiliser : L'énoncé donne un réseau, un plan de circulation ou un graphe de dépendances et demande des chemins ou la connexité.

1 Numéroter les sommets et écrire la matrice avec ses en-têtes de lignes et de colonnes.
2 Vérifier la cohérence : nombre de coefficients à $1$ égal au nombre d'arcs, diagonale nulle si le graphe est sans boucle.
3 Calculer les puissances demandées, en précisant à chaque fois quelle longueur de chemin est comptée.
4 Conclure sur le graphe, pas sur la matrice : nommer les sommets et les chemins en toutes lettres.

Phrase de conclusion

« $(M^{2})_{13}=1$ : il existe un unique chemin de longueur $2$ du sommet $1$ vers le sommet $3$ , celui qui passe par le sommet $2$ . »

Le piège : Annoncer un résultat sur la matrice sans revenir au graphe : le point de conclusion porte sur le réseau décrit par l'énoncé.

Barème : 1 point la matrice avec ses en-têtes, 1 point par puissance correcte, 1 point la conclusion en termes de sommets.

Composer des transformations du plan

Quand l'utiliser : L'énoncé demande la matrice d'une suite de transformations, ou l'image d'une figure.

1 Écrire chaque transformation séparément, en donnant les images des vecteurs de base en colonnes.
2 Décider si les coordonnées homogènes sont nécessaires : dès qu'il y a une translation, elles le sont.
3 Multiplier dans l'ordre INVERSE de l'application, la première transformation à droite.
4 Vérifier par le déterminant, puis appliquer à un point simple pour contrôler.

Phrase de conclusion

« La composée s'écrit $T\times R$ : le point est d'abord tourné par $R$ , puis déplacé par $T$ . »

Le piège : Multiplier dans l'ordre du français, ce qui applique les transformations à l'envers.

Barème : 1 point par matrice écrite, 1 point l'ordre du produit, 1 point la vérification sur un point.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

La somme des degrés est paire

Additionner tous les degrés annoncés : le total doit valoir exactement le double du nombre d'arêtes, donc être pair.

Une liste de degrés de somme $9$ décrit un graphe qui n'existe pas.
Le compte des coefficients à un

Compter les $1$ de la matrice et le comparer au nombre d'arcs du dessin.

Cinq arcs sur le graphe et six coefficients dans la matrice : un arc a été ajouté par erreur.
Le déterminant attendu

Rotation $1$ , symétrie $-1$ , homothétie de rapport $k$ donne $k^{2}$ . Un déterminant qui ne correspond pas signale une colonne fausse.

Une rotation dont la matrice a un déterminant $-1$ est en fait une symétrie.
Le test sur un point simple

Appliquer la matrice composée à l'origine ou à $(1\,;0)$ et vérifier que l'image est celle attendue géométriquement.

Une translation qui laisse l'origine fixe : les coordonnées homogènes ont été oubliées.

L'exercice type décortiqué

Un réseau à quatre carrefours

Quatre carrefours sont reliés par des voies à sens unique : de $1$ vers $2$ , de $2$ vers $3$ , de $3$ vers $4$ , de $4$ vers $1$ , et une voie directe de $1$ vers $3$ .

Écrire la matrice d'adjacence, compter les trajets de longueur $2$ , et dire si l'on peut aller de n'importe quel carrefour à n'importe quel autre.

Étape 1

Matrice $M$ : la ligne $1$ vaut $0\ 1\ 1\ 0$ , la ligne $2$ vaut $0\ 0\ 1\ 0$ , la ligne $3$ vaut $0\ 0\ 0\ 1$ et la ligne $4$ vaut $1\ 0\ 0\ 0$ .

Pourquoi

Une ligne par carrefour de DÉPART. Écrire les en-têtes évite l'erreur la plus fréquente, qui est de remplir la matrice transposée.

Étape 2

Contrôle : cinq coefficients à $1$ pour cinq voies, et la diagonale est nulle puisqu'aucune voie ne boucle sur un carrefour.

Pourquoi

Deux vérifications gratuites avant tout calcul. Une matrice fausse à cette étape rend toutes les puissances fausses sans que rien ne le signale.

Étape 3

$M^{2}$ : la ligne $1$ vaut $0\ 0\ 1\ 1$ , la ligne $2$ vaut $0\ 0\ 0\ 1$ , la ligne $3$ vaut $1\ 0\ 0\ 0$ et la ligne $4$ vaut $0\ 1\ 1\ 0$ .

Pourquoi

Chaque coefficient s'obtient en combinant une ligne et une colonne, ce qui revient à enchaîner deux arcs. La ligne $1$ de $M^{2}$ est la somme des lignes $2$ et $3$ de $M$ .

Étape 4

$(M^{2})_{13}=1$ : un seul trajet de longueur $2$ de $1$ vers $3$ , celui qui passe par $2$ .

Pourquoi

La voie directe $1\to 3$ n'est PAS comptée ici : elle est de longueur $1$ et figure dans $M$ . Au total, deux trajets de longueur au plus $2$ .

Étape 5

Somme totale des coefficients de $M^{2}$ : $6$ trajets de longueur $2$ dans tout le réseau.

Pourquoi

La somme de tous les coefficients d'une puissance donne le nombre total de chemins de cette longueur, ce qui fournit un contrôle global du calcul.

Étape 6

Accessibilité : la réunion booléenne de $M$ , $M^{2}$ et $M^{3}$ ne contient aucun zéro hors de la diagonale.

Pourquoi

Sur quatre sommets, il suffit d'aller jusqu'à $M^{3}$ : un chemin plus long repasserait par un carrefour déjà visité.

Conclusion rédigée

« Il existe un unique trajet de longueur $2$ de $1$ vers $3$ , et six trajets de longueur $2$ en tout. Le réseau est fortement connexe : depuis n'importe quel carrefour, on atteint tous les autres. »

L'erreur classique sur cet exercice : Répondre qu'il n'y a qu'un seul trajet de $1$ vers $3$ : la voie directe est de longueur $1$ et s'ajoute à celle de longueur $2$ .

À savoir par cœur

• $\sum\deg(s)=2|A|$ : la somme des degrés est toujours PAIRE, et le nombre de sommets de degré impair aussi.
• $M$ symétrique si et seulement si le graphe est non orienté ; un coefficient diagonal non nul est une BOUCLE.
• $(M^{k})_{ij}$ compte les chemins de longueur EXACTEMENT $k$ . Pour « au plus », on additionne les puissances.
• Un arbre couvrant d'un graphe connexe à $n$ sommets a exactement $n-1$ arêtes.
• $PQ\neq QP$ en général ; $(PQ)^{T}=Q^{T}P^{T}$ et $(PQ)^{-1}=Q^{-1}P^{-1}$ .
• Une matrice est inversible si et seulement si $ad-bc\neq 0$ , et l'aire est multipliée par $|\det|$ .
• Les COLONNES d'une matrice de transformation sont les images des vecteurs de base ; la première transformation appliquée s'écrit à DROITE.
• Une translation exige les coordonnées homogènes : une matrice $2\times 2$ laisse toujours l'origine fixe.

Questions fréquentes

Pourquoi la somme des degrés vaut-elle deux fois le nombre d'arêtes ?

Parce que chaque arête possède deux extrémités et ajoute donc une unité au degré de chacune. En additionnant tous les degrés, on compte chaque arête exactement deux fois. Il en résulte que la somme est toujours paire, et que le nombre de sommets de degré impair l'est aussi.

Que compte exactement la puissance k-ième de la matrice d'adjacence ?

Le nombre de chemins de longueur exactement k entre deux sommets, en autorisant le passage plusieurs fois par un même sommet. Elle ne compte donc pas les chemins plus courts : l'arc direct relève de la matrice elle-même. Pour obtenir les chemins d'au plus k arcs, il faut additionner les puissances.

Comment savoir si un graphe orienté est fortement connexe ?

En construisant la matrice d'accessibilité, réunion booléenne des puissances de un jusqu'à n moins un pour n sommets. Si cette matrice ne contient aucun zéro en dehors de la diagonale, alors depuis chaque sommet on atteint tous les autres, et le graphe est fortement connexe.

Dans quel ordre multiplier des matrices de transformation ?

De droite à gauche selon l'ordre d'application. La matrice la plus proche du vecteur, donc la plus à droite, agit en premier. Tourner puis translater s'écrit donc translation multipliée par rotation, ce qui est l'inverse du sens de lecture habituel et cause la plupart des erreurs.

Pourquoi une translation demande-t-elle les coordonnées homogènes ?

Parce qu'une matrice deux par deux laisse toujours l'origine fixe, alors qu'une translation la déplace : elle n'est pas une transformation linéaire. En ajoutant une troisième coordonnée constante égale à un, le déplacement devient une colonne de la matrice trois par trois, ce qui permet de le composer avec les rotations.

Passer à la pratique

Exercices corrigés : Introduction aux graphes et aux matrices

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Fiche précédente Récurrence et récursivité Fiche suivante Dénombrement et probabilités

Voir aussi

Toutes les fiches Tous les exercices Tutorat au cégep Tuteur maths pour l'informatique (201-N11)Ensembles et relations (201-N11)Matrices et systèmes (201-NYC)Cours de mathématiques

Vous suivez le cours 201-N11 en informatique au cégep ?

Contactez-moi pour une première séance. Bachelier en informatique de McGill et maître en informatique appliquée de Concordia, je fais le lien entre les matrices du cours et ce qu'elles pilotent ensuite : les graphes, les réseaux et l'affichage à l'écran.

Me contacter WhatsApp

Site par Studio Squalli