[enonce]
Pour chaque affirmation suivante sur la matrice d'adjacence et ses puissances, indiquer si elle est Vraie ou Fausse.
[/enonce]

[etape]
Affirmation : Pour un graphe orienté, la matrice d'adjacence est toujours symétrique.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Bonne réponse !
La symétrie de la matrice n'est garantie que pour un graphe non orienté. Dans un graphe orienté, un arc de $i$ vers $j$ ne donne pas automatiquement un arc de $j$ vers $i$, donc $M_{i,j}$ et $M_{j,i}$ peuvent être différents.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Petit rappel : la symétrie traduit le fait qu'une arête entre $i$ et $j$ se lit dans les deux sens. C'est exactement ce qui n'arrive pas pour un graphe orienté, où le sens d'un arc compte.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. La symétrie de la matrice d'adjacence est caractéristique des graphes non orientés ; pour un graphe orienté, $M_{i,j}$ peut différer de $M_{j,i}$.
[/solution]
[/etape]

[etape]
Affirmation : Dans la matrice d'adjacence d'un graphe non orienté simple (sans boucle, sans arêtes multiples), tous les coefficients diagonaux sont nuls.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Exactement !
Le coefficient $M_{i,i}$ compte le nombre de boucles sur le sommet $i$ (en comptant double pour le cas non orienté). En l'absence de boucle, $M_{i,i} = 0$ pour tout $i$.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Attention : la diagonale $M_{i,i}$ est uniquement liée aux boucles. Sans boucle dans le graphe, aucune diagonale ne peut être non nulle.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. La diagonale de la matrice d'adjacence ne reflète que les boucles ; sans boucle, tous les coefficients diagonaux sont nuls.
[/solution]
[/etape]

[etape]
Affirmation : Soit $M$ la matrice d'adjacence d'un graphe. Le coefficient $(M^{3})_{i,j}$ donne le nombre de chaînes de longueur au plus $3$ allant de $i$ à $j$.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Tu as raison !
$(M^{3})_{i,j}$ donne le nombre de chaînes de longueur exactement $3$ entre $i$ et $j$. Pour les chaînes de longueur au plus $3$, il faudrait calculer $M_{i,j} + (M^{2})_{i,j} + (M^{3})_{i,j}$.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Il ne faut pas confondre « exactement $k$ » et « au plus $k$ ». La puissance $M^{k}$ ne concerne que les chaînes ayant exactement $k$ arêtes ; pour cumuler plusieurs longueurs, il faut additionner plusieurs puissances.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. Le coefficient $(M^{3})_{i,j}$ donne le nombre de chaînes de longueur exactement $3$. Pour « au plus $3$ », on calcule $M + M^{2} + M^{3}$ et on lit le coefficient $(i\,;\,j)$.
[/solution]
[/etape]

[etape]
On considère un graphe à $4$ sommets dont la matrice d'adjacence est :

Affirmation : Le sommet $3$ a pour degré $3$.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]C'est bien ça !
Le degré du sommet $3$ se lit en sommant les coefficients de la ligne (ou colonne) $3$ de $M$ : $1 + 1 + 0 + 1 = 3$.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Pour un graphe non orienté, le degré du sommet $i$ est la somme des coefficients de la $i$-ème ligne de $M$. Reprendre les valeurs ligne par ligne pour le sommet $3$.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. La somme des coefficients de la troisième ligne vaut $1 + 1 + 0 + 1 = 3$, c'est le degré du sommet $3$.
[/solution]
[/etape]

[etape]
Affirmation : Si une matrice $M$ contient une ligne entièrement nulle, alors le sommet correspondant a au moins une arête dans le graphe.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Bravo !
Une ligne entièrement nulle dans $M$ signifie justement que le sommet correspondant n'a aucune arête (ni boucle, ni arête vers un autre sommet) — il est dit isolé. C'est le contraire de l'affirmation.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Lecture inversée à corriger : une ligne nulle dit que le sommet n'est relié à personne. Un sommet avec au moins une arête aurait au moins un coefficient non nul sur sa ligne.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. Une ligne nulle signifie que le sommet est isolé (sans aucune arête). C'est l'inverse qui est vrai : une ligne non nulle correspond à un sommet ayant au moins une arête.
[/solution]
[/etape]

[etape]
Affirmation : Pour un graphe non orienté simple, le coefficient $(M^{2})_{i,i}$ est égal au degré du sommet $i$.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Parfait !
$(M^{2})_{i,i}$ compte les chaînes de longueur $2$ partant de $i$ et y revenant. Une telle chaîne est de la forme $i \to k \to i$ : elle correspond à un voisin $k$ de $i$. Le nombre de tels parcours est exactement le nombre de voisins de $i$, c'est-à-dire son degré.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Le calcul $(M^{2})_{i,i} = \sum_{k} M_{i,k} M_{k,i}$ se simplifie (graphe simple non orienté, $M_{k,i} = M_{i,k}$, valeurs $0$ ou $1$) en $\sum_{k} M_{i,k} = $ degré de $i$. C'est un résultat classique.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. Pour un graphe simple non orienté, $(M^{2})_{i,i}$ compte les chaînes $i \to k \to i$, et il y en a autant que de voisins de $i$, soit le degré de $i$.
[/solution]
[/etape]

[enonce]
Ce QCM porte sur la matrice d'adjacence d'un graphe et l'interprétation de ses puissances. Pour chaque question, choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
Soit un graphe non orienté à $n$ sommets, sans boucle ni arête multiple. Quelle propriété sa matrice d'adjacence $M$ vérifie-t-elle toujours ?
[qcm]
[option]Elle est diagonale.[/option]
[option correct="true"]Elle est symétrique et ne contient que des $0$ et des $1$.[/option]
[option]Elle est triangulaire supérieure.[/option]
[option]Sa somme de coefficients vaut $n$.[/option]
[reponse statut="correct"]Tu as raison !
Pour un graphe non orienté, l'arête entre $i$ et $j$ apparaît symétriquement : $M_{i,j} = M_{j,i}$. L'absence de boucle et d'arêtes multiples impose des coefficients dans $\{0\,;\,1\}$.[/reponse]
[reponse motif="Elle est diagonale."]Non.
Une matrice diagonale n'a des coefficients qu'en position $(i\,;\,i)$. Or l'absence de boucle impose justement $M_{i,i} = 0$ : la matrice est presque toujours hors diagonale.[/reponse]
[reponse motif="Elle est triangulaire supérieure."]Non.
Pour un graphe non orienté, la matrice est symétrique, donc les coefficients sous la diagonale sont identiques à ceux du dessus. Une matrice triangulaire conviendrait pour un graphe orienté très particulier, pas pour le cas général non orienté.[/reponse]
[reponse motif="Sa somme de coefficients vaut $n$."]Non.
La somme des coefficients de $M$ vaut $2 \times \text{(nombre d'arêtes)}$ pour un graphe non orienté simple, et n'a aucune raison de coïncider avec l'ordre $n$ du graphe.[/reponse]
[reponse statut="incorrect"]Non.
La matrice d'un graphe non orienté simple est symétrique et à coefficients dans $\{0\,;\,1\}$.[/reponse]
[/qcm]
[/etape]

[etape]
Dans un graphe non orienté, le sommet numéroté $3$ porte une boucle (et pas d'autre arête issue de lui). Que vaut le coefficient $M_{3,3}$ de la matrice d'adjacence ?
[qcm]
[option]$0$[/option]
[option]$1$[/option]
[option correct="true"]$2$[/option]
[option]$3$[/option]
[reponse statut="correct"]Exactement !
Dans un graphe non orienté, une boucle compte $2$ sur la diagonale. C'est cohérent avec la règle « le degré d'un sommet est obtenu en sommant la ligne (ou la colonne) correspondante » : la boucle contribue $2$ au degré.[/reponse]
[reponse motif="$0$"]Non.
Cela reviendrait à ignorer la boucle. Or la boucle est bien une arête du graphe et elle se traduit par un coefficient non nul sur la diagonale.[/reponse]
[reponse motif="$1$"]Non.
Le piège est de compter la boucle comme une simple arête. Dans le cas non orienté, on convient qu'une boucle contribue deux fois au coefficient diagonal pour rester cohérent avec le calcul du degré.[/reponse]
[reponse motif="$3$"]Non.
La règle ne dépend pas du numéro du sommet : peu importe que le sommet soit le $3$ ou un autre, une boucle non orientée vaut toujours $2$ sur la diagonale.[/reponse]
[reponse statut="incorrect"]Non.
Dans un graphe non orienté, une boucle ajoute $2$ au coefficient diagonal correspondant.[/reponse]
[/qcm]
[/etape]

[etape]
Soit $M$ la matrice d'adjacence d'un graphe et soit $k \geqslant 1$ un entier. Que représente le coefficient $(M^{k})_{i,j}$ ?
[qcm]
[option]Le nombre de chemins de longueur au plus $k$ entre $i$ et $j$.[/option]
[option correct="true"]Le nombre de chaînes de longueur exactement $k$ reliant $i$ à $j$.[/option]
[option]La distance minimale entre $i$ et $j$.[/option]
[option]Le nombre d'arêtes communes à $i$ et $j$.[/option]
[reponse statut="correct"]C'est bien ça !
D'après le théorème du cours, $(M^{k})_{i,j}$ donne le nombre de chaînes de longueur exactement $k$ allant de $i$ à $j$. Pour les chaînes de longueur au plus $k$, on additionne $M, M^{2}, \dots, M^{k}$.[/reponse]
[reponse motif="Le nombre de chemins de longueur au plus $k$ entre $i$ et $j$."]Non.
Confusion classique entre « exactement $k$ » et « au plus $k$ ». Pour obtenir le nombre de chaînes de longueur au plus $k$, il faut additionner les coefficients correspondants des matrices $M, M^{2}, \ldots, M^{k}$.[/reponse]
[reponse motif="La distance minimale entre $i$ et $j$."]Non.
La distance minimale est obtenue par d'autres méthodes (parcours en largeur, Dijkstra...). $(M^{k})_{i,j}$ compte des chaînes, il ne mesure pas un plus court chemin.[/reponse]
[reponse motif="Le nombre d'arêtes communes à $i$ et $j$."]Non.
Le nombre d'arêtes reliant directement $i$ à $j$ est lu dans $M$ lui-même (cas $k = 1$), pas dans $M^{k}$ pour $k \geqslant 2$.[/reponse]
[reponse statut="incorrect"]Non.
Le coefficient $(M^{k})_{i,j}$ donne le nombre de chaînes de longueur exactement $k$ entre les sommets $i$ et $j$.[/reponse]
[/qcm]
[/etape]

[etape]
Pour un graphe à $5$ sommets, on a calculé $(M^{2})_{1,4} = 3$. Comment interpréter ce résultat ?
[qcm]
[option]Il existe $3$ chaînes de longueur au plus $2$ allant de $1$ à $4$.[/option]
[option correct="true"]Il existe $3$ chaînes de longueur exactement $2$ allant de $1$ à $4$.[/option]
[option]Le sommet $1$ a $3$ voisins en commun avec le sommet $4$.[/option]
[option]Le sommet $1$ est à distance $3$ du sommet $4$.[/option]
[reponse statut="correct"]Bonne réponse !
Une chaîne de longueur $2$ entre $1$ et $4$ est de la forme $1 \to k \to 4$ où $k$ est un sommet intermédiaire. Le coefficient $(M^{2})_{1,4} = 3$ signifie qu'il y a exactement $3$ tels parcours.[/reponse]
[reponse motif="Il existe $3$ chaînes de longueur au plus $2$ allant de $1$ à $4$."]Non.
$(M^{2})_{i,j}$ ne compte que les chaînes de longueur exactement $2$. Pour obtenir « au plus $2$ », il faut ajouter $M_{1,4}$ (les arêtes directes) au résultat.[/reponse]
[reponse motif="Le sommet $1$ a $3$ voisins en commun avec le sommet $4$."]Non.
Cette interprétation est juste pour un graphe non orienté simple (sans boucle ni arêtes multiples) : les voisins communs correspondent alors aux sommets intermédiaires des chaînes de longueur $2$. Mais en présence de boucles ou d'arêtes multiples, ce n'est plus vrai. La lecture officielle reste : « nombre de chaînes de longueur exactement $2$ ».[/reponse]
[reponse motif="Le sommet $1$ est à distance $3$ du sommet $4$."]Non.
Le coefficient calculé est $3$, mais il quantifie un nombre de chaînes, pas la longueur d'une chaîne. La distance correspondrait à la plus petite valeur de $k$ telle que $(M^{k})_{1,4} > 0$.[/reponse]
[reponse statut="incorrect"]Non.
$(M^{2})_{1,4} = 3$ signifie qu'il existe $3$ chaînes de longueur exactement $2$ allant de $1$ à $4$.[/reponse]
[/qcm]
[/etape]

[etape]
On considère le graphe orienté à $3$ sommets dont la matrice d'adjacence (lignes et colonnes dans l'ordre $1$, $2$, $3$) est :

Combien existe-t-il d'arcs partant de $2$ et arrivant à $3$ ?
[qcm]
[option]$0$[/option]
[option correct="true"]$1$[/option]
[option]$2$[/option]
[option]Impossible à dire sans la figure.[/option]
[reponse statut="correct"]Bravo !
La matrice $M$ se lit ligne par ligne : à la ligne $2$, colonne $3$, on lit $M_{2,3} = 1$. Il y a donc exactement un arc de $2$ vers $3$.[/reponse]
[reponse motif="$0$"]Non.
Lire $M_{2,3}$ revient à regarder la $2$-ème ligne et la $3$-ème colonne. Il faut bien repérer la ligne (sommet d'origine) avant la colonne (sommet d'arrivée).[/reponse]
[reponse motif="$2$"]Non.
Cette valeur n'apparaît pas dans la matrice : tous les coefficients valent $0$ ou $1$. Vérifier l'emplacement (ligne $2$, colonne $3$) avant de lire le coefficient.[/reponse]
[reponse motif="Impossible à dire sans la figure."]Non.
La matrice d'adjacence donne une description complète du graphe : il n'est pas nécessaire de disposer de la figure pour répondre. Le coefficient $M_{i,j}$ donne directement le nombre d'arcs de $i$ à $j$.[/reponse]
[reponse statut="incorrect"]Non.
On lit $M_{2,3}$ à l'intersection de la deuxième ligne et de la troisième colonne ; il vaut $1$.[/reponse]
[/qcm]
[/etape]

[etape]
Soit $M$ la matrice d'adjacence d'un graphe non orienté à $4$ sommets. Comment obtient-on le nombre de chaînes de longueur au plus $3$ reliant $i$ à $j$ ?
[qcm]
[option]On lit le coefficient $(M^{3})_{i,j}$.[/option]
[option correct="true"]On calcule $M_{i,j} + (M^{2})_{i,j} + (M^{3})_{i,j}$.[/option]
[option]On élève $M$ à la puissance $3$ et on multiplie par $3$.[/option]
[option]On somme tous les coefficients de $M^{3}$.[/option]
[reponse statut="correct"]Tout à fait !
Pour compter les chaînes de longueur $1$, $2$ ou $3$, on additionne le coefficient $(i\,;\,j)$ des matrices $M$, $M^{2}$ et $M^{3}$. Chaque puissance compte exactement les chaînes de la longueur correspondante.[/reponse]
[reponse motif="On lit le coefficient $(M^{3})_{i,j}$."]Non.
Ce coefficient ne compte que les chaînes de longueur exactement $3$. Pour avoir « au plus $3$ », il faut aussi prendre en compte les longueurs $1$ et $2$.[/reponse]
[reponse motif="On élève $M$ à la puissance $3$ et on multiplie par $3$."]Non.
Multiplier par $3$ n'a pas de sens combinatoire : cela triple artificiellement le nombre de chaînes de longueur $3$ et ignore complètement les longueurs inférieures.[/reponse]
[reponse motif="On somme tous les coefficients de $M^{3}$."]Non.
Cela donne le nombre total de chaînes de longueur exactement $3$ dans le graphe (toutes origines et destinations confondues), pas celles entre les deux sommets précis $i$ et $j$.[/reponse]
[reponse statut="incorrect"]Non.
Pour les chaînes de longueur au plus $k$, on additionne les coefficients $(i\,;\,j)$ des matrices $M, M^{2}, \dots, M^{k}$.[/reponse]
[/qcm]
[/etape]