QCM Bilan : Graphes

Ce QCM bilan couvre l'ensemble du chapitre : matrice d'adjacence, chaînes de Markov, plus court chemin (Dijkstra), coloration (nombre chromatique) et synthèse des notions de graphes. Choisissez la bonne réponse parmi les quatre propositions.

Déroulement pas à pas (Correction et Indices)

Question 1 :

À quoi sert l'algorithme de Dijkstra ?

(Incorrect) Déterminer si un graphe possède une chaîne eulérienne.
(Incorrect) Compter les chaînes de longueur fixée entre deux sommets.
(Correct) Trouver un plus court chemin entre deux sommets d'un graphe pondéré à poids positifs.
(Incorrect) Calculer le nombre chromatique d'un graphe.

Question 2 :

À quelle hypothèse l'algorithme de Dijkstra ne fournit-il plus nécessairement la bonne réponse ?

(Incorrect) Le graphe est non orienté.
(Correct) Certains poids des arêtes sont négatifs.
(Incorrect) Le graphe contient un cycle.
(Incorrect) Plusieurs sommets ont le même degré.

Question 3 :

Que désigne le nombre chromatique d'un graphe ?

(Incorrect) Le nombre total d'arêtes du graphe.
(Incorrect) Le degré le plus élevé parmi tous les sommets.
(Correct) Le plus petit nombre de couleurs nécessaire pour colorier les sommets sans que deux sommets adjacents partagent une même couleur.
(Incorrect) Le nombre de sommets que l'on peut isoler dans un sous-graphe complet.

Question 4 :

Soit un graphe dont le degré maximal vaut $d_{\max} = 4$ et qui contient un sous-graphe complet à $3$ sommets (un triangle). Que peut-on affirmer sur son nombre chromatique $\chi$ ?

(Incorrect) $\chi = 3$.
(Incorrect) $\chi = 5$.
(Correct) $3 \leqslant \chi \leqslant 5$.
(Incorrect) $\chi = 4$.

Question 5 :

Lors de l'application de l'algorithme de Dijkstra, comment choisit-on à chaque étape le prochain sommet à traiter ?

(Incorrect) On prend le sommet de plus grand degré non encore traité.
(Correct) On prend le sommet non encore traité ayant la plus petite distance provisoire.
(Incorrect) On prend un sommet adjacent au sommet de départ pris au hasard.
(Incorrect) On prend le sommet de plus petit numéro non encore traité.

Question 6 :

Lequel des énoncés suivants est faux ?

(Incorrect) Pour un graphe non orienté simple, la matrice d'adjacence est symétrique.
(Incorrect) Le nombre chromatique d'un graphe est toujours inférieur ou égal à $d_{\max} + 1$.
(Correct) Tout graphe connexe admet une chaîne eulérienne.
(Incorrect) Le coefficient $(M^{2})_{i,j}$ donne le nombre de chaînes de longueur $2$ allant de $i$ à $j$.

Question 7 :

Soit $M$ la matrice d'adjacence d'un graphe non orienté simple à $4$ sommets, dans lequel on lit $\left(M^{3}\right)_{1,2} = 5$. Que représente ce coefficient ?

(Incorrect) Le nombre d'arêtes reliant directement le sommet $1$ au sommet $2$.
(Correct) Le nombre de chaînes de longueur $3$ reliant le sommet $1$ au sommet $2$.
(Incorrect) La distance minimale entre le sommet $1$ et le sommet $2$.
(Incorrect) Le degré commun des sommets $1$ et $2$.

Question 8 :

Pour une chaîne de Markov de matrice de transition $P$ et de distribution initiale $\pi_0$, par quelle relation obtient-on la distribution $\pi_n$ après $n$ étapes ?

(Incorrect) $\pi_n = P^n \times \pi_0$.
(Correct) $\pi_n = \pi_0 \times P^n$.
(Incorrect) $\pi_n = \pi_0 + n\,P$.
(Incorrect) $\pi_n = \pi_0 \times P \times n$.

Choisir mon niveau

Objectifs travaillés

Déroulement pas à pas (Correction et Indices)

Choisir mon niveau

Objectifs travaillés

Déroulement pas à pas (Correction et Indices)

Enregistrez votre progression