QCM : Chaînes et cycles eulériens
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteObjectif travaillé
Ce QCM porte sur les chaînes et cycles eulériens et le théorème d'Euler. Pour chaque question, choisissez la bonne réponse parmi les quatre propositions.
Déroulement pas à pas (Correction et Indices)
Question 1 : Qu'appelle-t-on une chaîne eulérienne dans un graphe ?
- (Incorrect) Une chaîne qui passe par tous les sommets une fois et une seule.
- (Correct) Une chaîne qui utilise chaque arête une fois et une seule.
- (Incorrect) Une chaîne fermée dont les sommets sont tous distincts.
- (Incorrect) La chaîne la plus courte entre deux sommets donnés.
Question 2 : Que dit le théorème d'Euler concernant l'existence d'une chaîne eulérienne dans un graphe connexe ?
- (Incorrect) Une chaîne eulérienne existe si tous les sommets sont de degré pair.
- (Correct) Une chaîne eulérienne existe si et seulement si le graphe possède $0$ ou $2$ sommets de degré impair.
- (Incorrect) Une chaîne eulérienne existe si et seulement si le graphe est complet.
- (Incorrect) Une chaîne eulérienne existe si et seulement si le nombre d'arêtes est pair.
Question 3 : À quelle condition supplémentaire un graphe connexe admet-il un cycle eulérien (pas seulement une chaîne) ?
- (Incorrect) Au moins un sommet doit être de degré impair.
- (Correct) Tous les sommets doivent être de degré pair.
- (Incorrect) Le graphe doit être complet.
- (Incorrect) Le nombre de sommets doit être pair.
Question 4 : Soit un graphe connexe à $5$ sommets dont la liste des degrés est $(2\,;\,3\,;\,4\,;\,3\,;\,2)$. Que peut-on conclure ?
- (Incorrect) Le graphe admet un cycle eulérien.
- (Correct) Le graphe admet une chaîne eulérienne, mais pas de cycle eulérien.
- (Incorrect) Le graphe n'admet ni chaîne, ni cycle eulérien.
- (Incorrect) On ne peut pas conclure sans dessiner le graphe.
Question 5 : Un graphe est dit traçable « sans lever le crayon et sans repasser sur une arête » lorsqu'il admet une chaîne eulérienne. Parmi les listes de degrés suivantes (pour des graphes connexes), laquelle correspond à un graphe non traçable ainsi ?
- (Incorrect) $(2\,;\,2\,;\,2\,;\,2)$
- (Correct) $(3\,;\,3\,;\,3\,;\,3)$
- (Incorrect) $(2\,;\,3\,;\,3\,;\,4)$
- (Incorrect) $(4\,;\,4\,;\,4\,;\,4)$
Question 6 : Pour que le théorème d'Euler s'applique et donne une réponse fiable, quelle autre hypothèse doit être satisfaite (au-delà du compte des degrés impairs) ?
- (Incorrect) Le graphe doit être orienté.
- (Correct) Le graphe doit être connexe.
- (Incorrect) Le graphe doit être complet.
- (Incorrect) Le nombre d'arêtes doit être supérieur au nombre de sommets.