Тест: Notions clés des graphes et parcours — 12 въпроса

1. Dans un graphe, comment appelle-t-on un lien orienté entre deux sommets ?

A. Un cycle

B. Une arête

C. Un chemin

D. Un arc

Answer: (D)

Обяснение

Un arc est un lien orienté, donc avec une direction. Une arête correspond au cas non orienté.

2. Quelle définition correspond à un cycle dans un graphe ?

A. Un sommet sans voisin

B. Un lien entre deux sommets voisins

C. Une suite de sommets sans répétition

D. Un chemin qui revient au sommet de départ

Answer: (D)

Обяснение

Un cycle est bien un chemin qui se referme en revenant au sommet de départ. Les autres propositions décrivent un chemin simple, une arête ou un sommet isolé.

3. Dans un dictionnaire d’adjacence, que représente la valeur associée à une clé ?

A. La liste des voisins du sommet

B. Le degré de tous les sommets

C. La matrice des distances

D. Le nombre total d’arêtes du graphe

Answer: (A)

Обяснение

Chaque clé correspond à un sommet et sa valeur est la liste de ses voisins. C’est précisément la représentation du dictionnaire d’adjacence.

4. Comment doit apparaître un sommet isolé dans un dictionnaire d’adjacence ?

A. Comme une clé absente

B. Comme une clé reliée à elle-même

C. Comme une clé avec une valeur nulle

D. Comme une clé avec une liste vide

Answer: (D)

Обяснение

Un sommet isolé doit quand même figurer dans le dictionnaire, avec une liste vide. Cela permet de ne pas fausser le degré ou la connexité.

5. Dans une matrice d’adjacence, que signifie généralement la valeur 1 à l’intersection d’une ligne et d’une colonne ?

A. Le lien est orienté vers la ligne

B. Le sommet est isolé

C. Il existe un lien entre les deux sommets

D. Les deux sommets ont le même degré

Answer: (C)

Обяснение

La valeur 1 indique la présence d’un lien entre les sommets correspondants. La valeur 0 indique au contraire l’absence de lien.

6. Pourquoi l’ordre des sommets est-il important dans une matrice d’adjacence ?

A. Il remplace la notion de voisinage

B. Il fixe l’interprétation des lignes et des colonnes

C. Il change le nombre d’arêtes du graphe

D. Il détermine la couleur des sommets

Answer: (B)

Обяснение

L’ordre choisi pour les sommets permet de savoir quelle ligne et quelle colonne correspondent à quel sommet. Sans cet ordre, la matrice ne serait pas interprétable.

7. Comment obtient-on le degré d’un sommet dans un dictionnaire d’adjacence non orienté ?

A. En comptant le nombre de sommets du graphe

B. En comptant le nombre de voisins dans sa liste

C. En comptant les chemins qui partent de lui

D. En additionnant les degrés de ses voisins

Answer: (B)

Обяснение

Le degré correspond au nombre de liens incident à un sommet, donc au nombre de voisins listés dans le dictionnaire. Dans un graphe non orienté, cela se lit directement avec la longueur de la liste.

8. Quelle différence décrit le mieux le BFS par rapport au DFS ?

A. Le DFS s’arrête dès qu’un sommet est visité

B. Le BFS explore un chemin le plus loin possible d’abord

C. Le DFS utilise une file avec pop(0)

D. Le BFS explore d’abord les voisins du niveau courant

Answer: (D)

Обяснение

Le BFS parcourt le graphe en largeur, en visitant d’abord les voisins proches avant d’aller plus loin. Le DFS, lui, va au contraire en profondeur.

9. Dans un graphe non orienté, que faut-il faire pour rester cohérent quand on ajoute le lien A—B ?

A. Ajouter A vers B et aussi B vers A

B. Ajouter seulement A vers B

C. Ne rien ajouter si A et B sont voisins

D. Ajouter seulement B vers A

Answer: (A)

Обяснение

Dans un graphe non orienté, un lien doit être réciproque dans la structure du graphe. Si A est relié à B, alors B doit aussi être relié à A.

10. Quel contrôle doit être effectué avant d’ajouter un sommet à la liste des visites lors d’un parcours ?

A. Vérifier qu’il apparaît en première position

B. Vérifier qu’il est isolé

C. Vérifier qu’il n’a pas déjà été visité

D. Vérifier qu’il a le plus grand degré

Answer: (C)

Обяснение

Il faut éviter les répétitions en testant si le sommet a déjà été visité avant de l’ajouter. Sinon, le parcours peut devenir incorrect ou inutilement long.

11. Dans un exercice de bac, comment détermine-t-on le degré d’un sommet à partir d’un dictionnaire d’adjacence ?

A. En comptant le nombre de voisins dans la liste associée au sommet

B. En additionnant les degrés de tous les sommets du graphe

C. En lisant la valeur située sur la diagonale de la matrice

D. En suivant le plus long chemin qui part du sommet

Answer: (A)

Обяснение

Le degré d’un sommet se lit dans le dictionnaire d’adjacence en comptant le nombre d’éléments de sa liste de voisins. La longueur de cette liste donne directement le nombre de liens attachés au sommet.

12. Pour vérifier qu’un graphe est connexe dans un exercice de bac, quelle méthode faut-il utiliser ?

A. Tracer seulement les sommets isolés pour voir s’ils sont reliés

B. Comparer les listes de voisins de deux sommets quelconques

C. Compter uniquement le nombre total d’arêtes du graphe

D. Lancer un parcours en largeur ou en profondeur depuis un sommet et vérifier que tous les sommets sont atteints

Answer: (D)

Обяснение

La connexité se vérifie en effectuant un parcours, en largeur ou en profondeur, puis en contrôlant que tous les sommets sont visités. Compter les arêtes ne suffit pas à conclure sur la connexité.