QCM : Matrice d’adjacence et puissances
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteObjectifs travaillés
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.
Déroulement pas à pas (Correction et Indices)
Question 1 : 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 ?
- (Incorrect) Elle est diagonale.
- (Correct) Elle est symétrique et ne contient que des $0$ et des $1$.
- (Incorrect) Elle est triangulaire supérieure.
- (Incorrect) Sa somme de coefficients vaut $n$.
Question 2 : 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 ?
- (Incorrect) $0$
- (Incorrect) $1$
- (Correct) $2$
- (Incorrect) $3$
Question 3 : 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}$ ?
- (Incorrect) Le nombre de chemins de longueur au plus $k$ entre $i$ et $j$.
- (Correct) Le nombre de chaînes de longueur exactement $k$ reliant $i$ à $j$.
- (Incorrect) La distance minimale entre $i$ et $j$.
- (Incorrect) Le nombre d'arêtes communes à $i$ et $j$.
Question 4 : Pour un graphe à $5$ sommets, on a calculé $(M^{2})_{1,4} = 3$. Comment interpréter ce résultat ?
- (Incorrect) Il existe $3$ chaînes de longueur au plus $2$ allant de $1$ à $4$.
- (Correct) Il existe $3$ chaînes de longueur exactement $2$ allant de $1$ à $4$.
- (Incorrect) Le sommet $1$ a $3$ voisins en commun avec le sommet $4$.
- (Incorrect) Le sommet $1$ est à distance $3$ du sommet $4$.
Question 5 : On considère le graphe orienté à $3$ sommets dont la matrice d'adjacence (lignes et colonnes dans l'ordre $1$, $2$, $3$) est :
$M = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$
Combien existe-t-il d'arcs partant de $2$ et arrivant à $3$ ?
- (Incorrect) $0$
- (Correct) $1$
- (Incorrect) $2$
- (Incorrect) Impossible à dire sans la figure.
Question 6 : 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$ ?
- (Incorrect) On lit le coefficient $(M^{3})_{i,j}$.
- (Correct) On calcule $M_{i,j} + (M^{2})_{i,j} + (M^{3})_{i,j}$.
- (Incorrect) On élève $M$ à la puissance $3$ et on multiplie par $3$.
- (Incorrect) On somme tous les coefficients de $M^{3}$.