QCM : Introduction aux graphes et parcours — 6 questions

Question 1

1. Quel est l’effet principal de l’utilisation d’exemples introductifs pour la modélisation par graphe dans l’apprentissage ?

Ils facilitent la compréhension concrète des concepts abstraits du graphe.

Ils garantissent que tous les graphes modélisés sont sans cycle.

Ils permettent d’éviter l’utilisation de parcours en largeur ou profondeur.

Ils simplifient la représentation en supprimant les détails inutiles.

Explication

Les exemples introductifs illustrent concrètement comment modéliser différentes situations par des graphes, ce qui facilite la compréhension des concepts abstraits et leur application pratique dans l'apprentissage.

Answer

Ils facilitent la compréhension concrète des concepts abstraits du graphe.

Question 2

2. Qui est crédité d'avoir formulé ou introduit la notion de graphe en mathématiques et en informatique ?

Leonhard Euler

Carl Friedrich Gauss

Isaac Newton

Bernhard Riemann

Explication

Leonhard Euler est le mathématicien qui a introduit la notion de graphe dans ses travaux, notamment avec le problème des ponts de Königsberg en 1736, ce qui lui vaut d'être crédité de la formulation du concept de graphe.

Answer

Leonhard Euler

Question 3

3. Quelle structure de données en Python est couramment utilisée pour représenter une matrice d’adjacence d’un graphe ?

Un ensemble (set) contenant tous les sommets et arêtes du graphe

Une liste simple contenant tous les sommets du graphe

Un dictionnaire d’adjacence où chaque clé est un sommet et la valeur une liste de voisins

Une liste de listes où chaque sous-liste représente une ligne de la matrice d’adjacence

Explication

La représentation par une liste de listes est une méthode couramment utilisée en Python pour créer une matrice d’adjacence, où chaque sous-liste représente une ligne de la matrice, indiquant la présence ou absence d’arêtes entre les sommets.

Answer

Une liste de listes où chaque sous-liste représente une ligne de la matrice d’adjacence

Question 4

4. En quoi le parcours en largeur diffère-t-il de la recherche de cycles lors du parcours en profondeur ?

Le parcours en largeur ne permet pas de détecter les cycles, contrairement à la recherche de cycles en DFS qui utilise une coloration spécifique.

Le parcours en largeur explore le graphe niveau par niveau, tandis que la recherche de cycles en DFS détecte la présence de boucles en suivant un chemin profond.

Le parcours en largeur se limite à explorer un seul chemin, tandis que la recherche de cycles en DFS explore tout le graphe en profondeur.

Le parcours en largeur utilise une pile pour explorer le graphe, alors que la recherche de cycles en DFS utilise une file d'attente.

Explication

Le parcours en largeur explore un graphe niveau par niveau, ce qui est différent de la détection de cycles en DFS qui consiste à repérer la présence d’un sommet gris rencontré lors de l’exploration en profondeur, indiquant une boucle.

Answer

Le parcours en largeur explore le graphe niveau par niveau, tandis que la recherche de cycles en DFS détecte la présence de boucles en suivant un chemin profond.

Question 5

5. À quel moment précis lors de l'exécution du parcours en profondeur un sommet est-il marqué comme découvert ?

Au moment où il est exploré pour la première fois lors de l'algorithme DFS

Au moment où il est colorié en noir après exploration complète

Lorsqu'il est ajouté à la liste d'attente dans le parcours en largeur

Lorsqu'on a terminé d'explorer tous ses successeurs

Explication

Le sommet est marqué comme découvert lors de la première fois qu'il est rencontré et exploré dans l'algorithme DFS, ce qui correspond à sa première coloration en gris. Les autres options correspondent à d'autres étapes ou à des notions liées à d'autres types de parcours, mais pas à la découverte initiale.

Answer

Au moment où il est exploré pour la première fois lors de l'algorithme DFS

Question 6

6. Comment peut-on utiliser un parcours en profondeur pour détecter la présence d’un cycle dans un graphe orienté ?

En comptant le nombre d'arêtes dans le graphe, car un nombre élevé indique un cycle.

En observant si un sommet non découvert est relié à un sommet déjà noir, ce qui indique un cycle.

En vérifiant si, lors de l'exploration, un sommet gris apparaît comme successeur, ce qui indique un cycle.

En s'assurant que tous les sommets ont un degré entrant nul, ce qui évite les cycles.

Explication

Lors du parcours en profondeur (DFS), si lors de l'exploration d’un sommet, l’on rencontre un successeur qui est déjà gris, cela signifie qu’il y a une boucle fermée, donc un cycle dans le graphe orienté. Les autres options ne correspondent pas à la méthode de détection de cycle lors d’un DFS.

Answer

En vérifiant si, lors de l'exploration, un sommet gris apparaît comme successeur, ce qui indique un cycle.

QCM : Introduction aux graphes et parcours — 6 questions

Questions et réponses du QCM

1. Quel est l’effet principal de l’utilisation d’exemples introductifs pour la modélisation par graphe dans l’apprentissage ?

2. Qui est crédité d'avoir formulé ou introduit la notion de graphe en mathématiques et en informatique ?

3. Quelle structure de données en Python est couramment utilisée pour représenter une matrice d’adjacence d’un graphe ?

4. En quoi le parcours en largeur diffère-t-il de la recherche de cycles lors du parcours en profondeur ?

5. À quel moment précis lors de l'exécution du parcours en profondeur un sommet est-il marqué comme découvert ?

6. Comment peut-on utiliser un parcours en profondeur pour détecter la présence d’un cycle dans un graphe orienté ?

Révisez avec les flashcards

Approfondir avec la fiche

Cours similaires

Introduction à l'Intelligence Artificielle Symbolique

Introduction aux documents et sécurité en construction

Introduction à l'Informatique et IA

Introduction aux marchés publics et réglementations du bâtiment

Gestion des imprimantes Windows et PDF

Introduction aux bases de données relationnelles

Crée tes propres QCM