Quiz: Introduction aux graphes et parcours — 6 Fragen

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

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

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

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

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

Answer: (A)

Erklärung

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.

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

A. Leonhard Euler

B. Carl Friedrich Gauss

C. Isaac Newton

D. Bernhard Riemann

Answer: (A)

Erklärung

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.

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

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

B. Une liste simple contenant tous les sommets du graphe

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

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

Answer: (D)

Erklärung

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.

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

A. 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.

B. 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.

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

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

Answer: (B)

Erklärung

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.

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

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

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

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

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

Answer: (A)

Erklärung

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.

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

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

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

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

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

Answer: (C)

Erklärung

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.