[enonce]
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.
[/enonce]

[etape]
À quoi sert l'algorithme de Dijkstra ?
[qcm]
[option]Déterminer si un graphe possède une chaîne eulérienne.[/option]
[option]Compter les chaînes de longueur fixée entre deux sommets.[/option]
[option correct="true"]Trouver un plus court chemin entre deux sommets d'un graphe pondéré à poids positifs.[/option]
[option]Calculer le nombre chromatique d'un graphe.[/option]
[reponse statut="correct"]Exactement !
L'algorithme de Dijkstra construit un plus court chemin (au sens du poids total) entre un sommet de départ et un sommet d'arrivée, à condition que tous les poids des arêtes soient positifs.[/reponse]
[reponse motif="Déterminer si un graphe possède une chaîne eulérienne."]Non.
Cette question relève du théorème d'Euler (compter les sommets de degré impair), pas d'un algorithme de plus court chemin. Dijkstra ne s'occupe que des distances pondérées.[/reponse]
[reponse motif="Compter les chaînes de longueur fixée entre deux sommets."]Non.
Le comptage des chaînes de longueur $k$ s'obtient par les puissances de la matrice d'adjacence. Dijkstra ne dénombre pas, il optimise une distance.[/reponse]
[reponse motif="Calculer le nombre chromatique d'un graphe."]Non.
Le nombre chromatique se détermine par un encadrement (degré max et sous-graphes complets) puis un coloriage explicite. Dijkstra ne traite pas la coloration.[/reponse]
[reponse statut="incorrect"]Non.
Dijkstra fournit un plus court chemin entre deux sommets dans un graphe pondéré à poids positifs.[/reponse]
[/qcm]
[/etape]

[etape]
À quelle hypothèse l'algorithme de Dijkstra ne fournit-il plus nécessairement la bonne réponse ?
[qcm]
[option]Le graphe est non orienté.[/option]
[option correct="true"]Certains poids des arêtes sont négatifs.[/option]
[option]Le graphe contient un cycle.[/option]
[option]Plusieurs sommets ont le même degré.[/option]
[reponse statut="correct"]Bonne réponse !
Dijkstra repose sur le principe que la distance d'un sommet déjà traité ne peut plus diminuer. En présence d'arêtes de poids négatif, cette propriété tombe : un détour par une arête de poids négatif peut raccourcir une distance déjà fixée.[/reponse]
[reponse motif="Le graphe est non orienté."]Non.
Dijkstra fonctionne aussi bien sur des graphes orientés que non orientés. Cette caractéristique ne change rien à la validité de l'algorithme.[/reponse]
[reponse motif="Le graphe contient un cycle."]Non.
La présence de cycles ne pose aucun problème tant que les poids restent positifs. L'algorithme passe simplement au sommet non traité de plus petite distance, sans se soucier des cycles.[/reponse]
[reponse motif="Plusieurs sommets ont le même degré."]Non.
Le degré ne joue aucun rôle dans l'algorithme : seules les distances et les poids des arêtes sont utilisés. Avoir des degrés égaux n'a aucun effet sur le résultat.[/reponse]
[reponse statut="incorrect"]Non.
Dijkstra suppose que tous les poids sont positifs ; en présence de poids négatifs, il peut renvoyer une réponse fausse.[/reponse]
[/qcm]
[/etape]

[etape]
Que désigne le nombre chromatique d'un graphe ?
[qcm]
[option]Le nombre total d'arêtes du graphe.[/option]
[option]Le degré le plus élevé parmi tous les sommets.[/option]
[option correct="true"]Le plus petit nombre de couleurs nécessaire pour colorier les sommets sans que deux sommets adjacents partagent une même couleur.[/option]
[option]Le nombre de sommets que l'on peut isoler dans un sous-graphe complet.[/option]
[reponse statut="correct"]C'est bien ça !
Le nombre chromatique, noté $\chi$, est le minimum du nombre de couleurs permettant un coloriage propre du graphe (sommets adjacents toujours de couleurs distinctes).[/reponse]
[reponse motif="Le nombre total d'arêtes du graphe."]Non.
Le nombre d'arêtes ne dépend que de la structure du graphe, pas du coloriage. Le nombre chromatique mesure une difficulté de coloriage, pas une quantité combinatoire d'arêtes.[/reponse]
[reponse motif="Le degré le plus élevé parmi tous les sommets."]Non.
Le degré maximum $d_{\max}$ sert à majorer le nombre chromatique ($\chi \leqslant d_{\max} + 1$), mais il ne lui est pas égal en général.[/reponse]
[reponse motif="Le nombre de sommets que l'on peut isoler dans un sous-graphe complet."]Non.
La taille du plus grand sous-graphe complet (clique) minore le nombre chromatique, mais ne le donne pas exactement. Pour certains graphes, $\chi$ est strictement supérieur à cette taille.[/reponse]
[reponse statut="incorrect"]Non.
Le nombre chromatique est le plus petit nombre de couleurs permettant un coloriage propre des sommets.[/reponse]
[/qcm]
[/etape]

[etape]
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$ ?
[qcm]
[option]$\chi = 3$.[/option]
[option]$\chi = 5$.[/option]
[option correct="true"]$3 \leqslant \chi \leqslant 5$.[/option]
[option]$\chi = 4$.[/option]
[reponse statut="correct"]Tu as raison !
On a deux encadrements : le sous-graphe complet à $3$ sommets impose $\chi \geqslant 3$ ; le théorème de majoration donne $\chi \leqslant d_{\max} + 1 = 5$. Donc $\chi$ est compris entre $3$ et $5$, sans pouvoir être déterminé exactement à ce stade.[/reponse]
[reponse motif="$\chi = 3$."]Non.
La présence d'un triangle assure $\chi \geqslant 3$, mais pas l'égalité. Selon la structure du graphe, $\chi$ peut très bien valoir $4$ ou $5$.[/reponse]
[reponse motif="$\chi = 5$."]Non.
La valeur $5$ est seulement la borne supérieure donnée par $d_{\max} + 1$. Cette borne n'est pas toujours atteinte : la plupart des graphes ont un nombre chromatique strictement inférieur.[/reponse]
[reponse motif="$\chi = 4$."]Non.
Sans information supplémentaire, on ne peut conclure à l'égalité $\chi = 4$. Les seules informations sûres sont les bornes : $3 \leqslant \chi \leqslant 5$.[/reponse]
[reponse statut="incorrect"]Non.
Avec un sous-graphe complet à $3$ sommets, $\chi \geqslant 3$. Avec $d_{\max} = 4$, $\chi \leqslant 5$. Donc $3 \leqslant \chi \leqslant 5$.[/reponse]
[/qcm]
[/etape]

[etape]
Lors de l'application de l'algorithme de Dijkstra, comment choisit-on à chaque étape le prochain sommet à traiter ?
[qcm]
[option]On prend le sommet de plus grand degré non encore traité.[/option]
[option correct="true"]On prend le sommet non encore traité ayant la plus petite distance provisoire.[/option]
[option]On prend un sommet adjacent au sommet de départ pris au hasard.[/option]
[option]On prend le sommet de plus petit numéro non encore traité.[/option]
[reponse statut="correct"]Bravo !
À chaque étape, on sélectionne parmi les sommets non encore traités celui dont la distance provisoire au sommet de départ est minimale. Une fois ce sommet choisi, on met à jour les distances de ses voisins.[/reponse]
[reponse motif="On prend le sommet de plus grand degré non encore traité."]Non.
Le degré d'un sommet ne participe pas à l'algorithme. Dijkstra utilise uniquement les distances provisoires et les poids des arêtes.[/reponse]
[reponse motif="On prend un sommet adjacent au sommet de départ pris au hasard."]Non.
Le choix doit être déterministe pour garantir un plus court chemin. Prendre un voisin au hasard ne garantit pas que sa distance soit minimale parmi les sommets non encore traités.[/reponse]
[reponse motif="On prend le sommet de plus petit numéro non encore traité."]Non.
Le numéro du sommet ne joue aucun rôle dans l'algorithme. Le critère de sélection est la plus petite distance provisoire courante.[/reponse]
[reponse statut="incorrect"]Non.
À chaque étape, on choisit le sommet non encore traité ayant la plus petite distance provisoire au sommet de départ.[/reponse]
[/qcm]
[/etape]

[etape]
Lequel des énoncés suivants est faux ?
[qcm]
[option]Pour un graphe non orienté simple, la matrice d'adjacence est symétrique.[/option]
[option]Le nombre chromatique d'un graphe est toujours inférieur ou égal à $d_{\max} + 1$.[/option]
[option correct="true"]Tout graphe connexe admet une chaîne eulérienne.[/option]
[option]Le coefficient $(M^{2})_{i,j}$ donne le nombre de chaînes de longueur $2$ allant de $i$ à $j$.[/option]
[reponse statut="correct"]Exactement !
Cet énoncé est faux : la connexité ne suffit pas. Il faut en plus que le graphe ait $0$ ou $2$ sommets de degré impair (théorème d'Euler). Les trois autres propositions correspondent à des résultats du cours.[/reponse]
[reponse motif="Pour un graphe non orienté simple, la matrice d'adjacence est symétrique."]Non, cette affirmation est vraie : pour un graphe non orienté, $M_{i,j} = M_{j,i}$ par définition. Cherche plutôt un énoncé qui contredit le cours.[/reponse]
[reponse motif="Le nombre chromatique d'un graphe est toujours inférieur ou égal à $d_{\max} + 1$."]Non, cette affirmation est vraie : c'est précisément le théorème de majoration du nombre chromatique. L'erreur recherchée se trouve dans une autre proposition.[/reponse]
[reponse motif="Le coefficient $(M^{2})_{i,j}$ donne le nombre de chaînes de longueur $2$ allant de $i$ à $j$."]Non, cette affirmation est vraie : c'est l'application directe du théorème sur les puissances de la matrice d'adjacence, avec $k = 2$.[/reponse]
[reponse statut="incorrect"]Non.
L'énoncé faux est : « Tout graphe connexe admet une chaîne eulérienne. » La connexité est nécessaire mais non suffisante : il faut aussi $0$ ou $2$ sommets de degré impair.[/reponse]
[/qcm]
[/etape]

[etape]
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 ?
[qcm]
[option]Le nombre d'arêtes reliant directement le sommet $1$ au sommet $2$.[/option]
[option correct="true"]Le nombre de chaînes de longueur $3$ reliant le sommet $1$ au sommet $2$.[/option]
[option]La distance minimale entre le sommet $1$ et le sommet $2$.[/option]
[option]Le degré commun des sommets $1$ et $2$.[/option]
[reponse statut="correct"]Exactement !
Le coefficient $\left(M^{k}\right)_{i,j}$ donne le nombre de chaînes de longueur $k$ reliant le sommet $i$ au sommet $j$. Ici $k = 3$ : il y a donc $5$ chaînes de longueur $3$ entre les sommets $1$ et $2$.[/reponse]
[reponse motif="Le nombre d'arêtes reliant directement le sommet $1$ au sommet $2$."]Non.
C'est le coefficient $M_{1,2}$ (la matrice elle-même, soit $M^{1}$) qui compte les arêtes directes, c'est-à-dire les chaînes de longueur $1$. Ici la puissance est $3$.[/reponse]
[reponse motif="La distance minimale entre le sommet $1$ et le sommet $2$."]Non.
Les puissances de la matrice d'adjacence comptent des chaînes ; elles ne mesurent pas une distance. La distance minimale relèverait d'un graphe pondéré et de l'algorithme de Dijkstra.[/reponse]
[reponse motif="Le degré commun des sommets $1$ et $2$."]Non.
Le degré d'un sommet se lit sur la somme d'une ligne de $M$, pas sur un coefficient de $M^{3}$. Ce coefficient compte des chaînes de longueur $3$.[/reponse]
[reponse statut="incorrect"]Non.
Le coefficient $\left(M^{k}\right)_{i,j}$ compte les chaînes de longueur $k$ entre $i$ et $j$ : ici, les chaînes de longueur $3$ entre les sommets $1$ et $2$.[/reponse]
[/qcm]
[/etape]

[etape]
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 ?
[qcm]
[option]$\pi_n = P^n \times \pi_0$.[/option]
[option correct="true"]$\pi_n = \pi_0 \times P^n$.[/option]
[option]$\pi_n = \pi_0 + n\,P$.[/option]
[option]$\pi_n = \pi_0 \times P \times n$.[/option]
[reponse statut="correct"]Bien vu !
La distribution $\pi_n$ est un vecteur ligne : on multiplie la distribution initiale (à gauche) par la puissance $n$-ième de la matrice de transition, soit $\pi_n = \pi_0 \times P^n$.[/reponse]
[reponse motif="$\pi_n = P^n \times \pi_0$."]Non.
$\pi_0$ est un vecteur ligne : il se place à gauche de $P^n$. L'écriture $P^n \times \pi_0$ n'a pas le bon format de produit matriciel.[/reponse]
[reponse motif="$\pi_n = \pi_0 + n\,P$."]Non.
L'évolution d'une chaîne de Markov est multiplicative (produit par $P$ à chaque étape), pas additive. On n'ajoute jamais la matrice de transition à la distribution.[/reponse]
[reponse motif="$\pi_n = \pi_0 \times P \times n$."]Non.
Passer de $\pi_0$ à $\pi_n$ revient à appliquer $n$ fois la transition, donc à multiplier par $P^n$, et non par $P$ puis par le nombre $n$.[/reponse]
[reponse statut="incorrect"]Non.
On a $\pi_n = \pi_0 \times P^n$ : le vecteur ligne initial multiplié par la puissance $n$-ième de la matrice de transition.[/reponse]
[/qcm]
[/etape]