Quiz: Introduction aux graphes et parcours efficaces — 8 Fragen

1. Comment peut-on utiliser la différence entre un graphe orienté et un graphe non orienté pour modéliser un réseau de transport ?

A. En modélisant les stations comme des arcs dans un graphe orienté

B. En considérant que tous les liens ont un sens unique même dans un graphe non orienté

C. En représentant les trajets à sens unique par des arcs dans un graphe orienté

D. En utilisant des arêtes sans direction pour modéliser des trajets à sens unique

Answer: (C)

Erklärung

Le passage précise que dans un graphe orienté les liens sont appelés arcs et ont un sens unique, ce qui permet de modéliser des trajets à sens unique. Les arêtes sans orientation dans un graphe non orienté ne conviennent pas pour représenter des trajets à sens unique. À revoir : Définitions fondamentales des graphes, graphes orientés et non orientés. Appui du cours : « - Dans un graphe orienté, les liens sont appelés arcs et ont un sens unique. - Dans un graphe non orienté, deux sommets sont adjacents s'ils sont reliés par une arête sans orientation. »

2. Comment utiliser la notion de distance pour déterminer la proximité entre deux sommets dans un graphe ?

A. Calculer la somme des degrés des deux sommets

B. Identifier le nombre de cycles contenant les deux sommets

C. Mesurer la longueur du plus court chemin entre les deux sommets en nombre d'arêtes

D. Compter le nombre total de chemins possibles entre les deux sommets

Answer: (C)

Erklärung

La distance entre deux sommets est définie comme la longueur du plus court chemin entre eux, mesurée en nombre d'arêtes ou en somme des poids. Les autres propositions ne correspondent pas à cette définition et ne permettent pas de mesurer directement la proximité entre deux sommets. À revoir : Concepts de voisinage, degré, chemin, cycle, distance et connexité dans les graphes. Appui du cours : « La distance entre deux sommets est la longueur du plus court chemin entre eux, mesurée en nombre d'arêtes ou en somme des poids si pondéré. »

3. En quoi la matrice d'adjacence diffère-t-elle de la liste d'adjacence dans la représentation d'un graphe en Python ?

A. La matrice liste les sommets voisins pour chaque sommet, tandis que la liste d'adjacence est un tableau 2D de 0 et 1

B. La matrice utilise une numérotation des sommets commençant à 0, mais la liste d'adjacence commence à 1

C. La matrice est un tableau 2D indiquant présence d'arêtes par 0 ou 1, alors que la liste d'adjacence est une liste de sous-listes des sommets voisins

D. La matrice contient uniquement les poids des arêtes, alors que la liste d'adjacence contient uniquement les nombres d'arêtes

Answer: (C)

Erklärung

La matrice d'adjacence est un tableau à deux dimensions où chaque case indique par 0 ou 1 la présence d'une arête, tandis que la liste d'adjacence est une liste de sous-listes énumérant les sommets voisins de chaque sommet, ce qui correspond exactement à la définition donnée. À revoir : Représentations des graphes en Python : matrices et listes d'adjacence. Appui du cours : « - Matrice d'adjacence : Structure de données sous forme de tableau à deux dimensions (liste de listes en Python) où le nombre de lignes et de colonnes correspond au nombre de sommets du graphe, chaque case valant 0 ou 1 selon l'absence ou la présence d'une… »

4. Dans quel cas est-il préférable d'utiliser une liste d'arêtes plutôt qu'un dictionnaire pour modéliser un graphe ?

A. Pour appliquer l'algorithme de Bellman-Ford

B. Pour gérer des graphes avec des sommets contigus et numériques

C. Pour optimiser la recherche des voisins d'un sommet

D. Pour manipuler des sommets avec des libellés non numériques

Answer: (A)

Erklärung

La liste d'arêtes est particulièrement adaptée à certains algorithmes comme Bellman-Ford, tandis que le dictionnaire est utile pour conserver les libellés des sommets et leurs voisins. À revoir : Modélisation des graphes avec dictionnaires et listes d'arêtes. Appui du cours : « - La liste d'arêtes est particulièrement adaptée à certains algorithmes comme Bellman-Ford. - Le dictionnaire permet de conserver les libellés des sommets tout en listant leurs voisins. »

5. Quelle est la principale différence entre la "coupe" et les "sommets non encore rencontrés" dans un parcours de graphe ?

A. La coupe correspond aux sommets non connectés, alors que les sommets non encore rencontrés sont ceux visités mais non marqués

B. La coupe regroupe les sommets visités, alors que les sommets non encore rencontrés sont ceux visités plusieurs fois

C. La coupe contient des sommets connus mais non visités, tandis que les sommets non encore rencontrés n'ont pas encore été découverts

D. La coupe est un ensemble de sommets visités, tandis que les sommets non encore rencontrés sont ceux visités une seule fois

Answer: (C)

Erklärung

La coupe est définie comme l'ensemble des sommets connus mais non encore visités, tandis que les sommets non encore rencontrés sont ceux qui n'ont pas encore été découverts ou inclus dans le parcours, donc inconnus. À revoir : Principes généraux des parcours de graphes et gestion des ensembles de sommets. Appui du cours : « - **La coupe** : L'ensemble de sommet connus mais non encore visités - **Sommets non encore rencontrés** : Ce sont les sommets du graphe qui n'ont pas encore été découverts ou inclus dans aucun des ensembles de parcours. »

6. Qu'est-ce que le parcours en largeur (BFS) dans un graphe ?

A. Un parcours qui explore uniquement les sommets directement connectés au sommet de départ sans aller plus loin

B. Un parcours qui explore les sommets par ordre croissant de distance depuis le sommet de départ, en utilisant une file pour gérer la coupe

C. Un parcours qui visite les sommets dans un ordre aléatoire sans contrainte de distance

D. Un parcours qui explore les sommets en profondeur avant de revenir en arrière, utilisant une pile

Answer: (B)

Erklärung

Le parcours en largeur (BFS) explore d'abord tous les sommets à distance 1 du départ, puis ceux à distance 2, etc., et utilise une file pour gérer la coupe, ce qui correspond à l'option 0. À revoir : Parcours en largeur (BFS) dans les graphes. Appui du cours : « Parcours en largeur (BFS) : Le parcours en largeur explore d'abord tous les sommets à distance 1 du départ, puis ceux à distance 2, etc., en utilisant une file pour gérer la coupe. »

7. Qu'est-ce que le parcours en profondeur (DFS) dans un graphe ?

A. Un parcours qui explore un graphe en allant aussi loin que possible le long d'un chemin avant de revenir en arrière, utilisant une pile pour gérer la coupe

B. Un parcours qui visite tous les sommets voisins avant d'aller plus loin dans le graphe

C. Un parcours qui utilise une file d'attente pour visiter les sommets par ordre d'arrivée

D. Un parcours qui sélectionne aléatoirement les sommets à visiter sans structure particulière

Answer: (A)

Erklärung

Le DFS est défini comme un parcours qui explore un graphe en allant aussi loin que possible le long d'un chemin avant de revenir en arrière, en utilisant une pile pour gérer la coupe. Les autres options décrivent d'autres types de parcours ou méthodes non conformes à la définition du DFS. À revoir : Parcours en profondeur (DFS) dans les graphes. Appui du cours : « Parcours en profondeur (DFS) : Le parcours en profondeur explore un graphe en allant aussi loin que possible le long d'un chemin avant de revenir en arrière, en utilisant une structure de pile pour gérer la coupe. »

8. Quel est le rôle principal de l'algorithme de Dijkstra dans un graphe pondéré ?

A. Calculer le degré de chaque sommet pour analyser la connectivité du graphe

B. Trouver un cycle dans un graphe en explorant tous les sommets en profondeur

C. Construire efficacement le plus court chemin entre deux sommets en exploitant les distances minimales de façon itérative

D. Transformer un graphe orienté en graphe non orienté pour simplifier son traitement

Answer: (C)

Erklärung

Le texte indique clairement que l'algorithme de Dijkstra exploite de manière itérative les distances minimales pour construire efficacement le plus court chemin entre deux sommets dans un graphe pondéré. Les autres options ne correspondent pas à ce rôle. À revoir : Recherche du plus court chemin et algorithme de Dijkstra sur graphes pondérés. Appui du cours : « L'algorithme de Dijkstra exploite de manière itérative les distances minimales pour construire efficacement le plus court chemin entre deux sommets dans un graphe pondéré. »