AccueilCPGEQCMQCM : Notions de Graphes en Python QCM : Notions de Graphes en Python 1. Qu’est-ce qu’un graphe ? Un ensemble de points connectés uniquement en cercle. Un couple d’ensembles, les sommets et les arêtes. Une liste de sommets. 2. Dans un graphe orienté, les arêtes… N’ont pas de direction particulière. Représentent des connexions unidirectionnelles. Connectent les sommets en boucle fermée. 3. Qu’est-ce qu’un graphe connexe ? Un graphe dans lequel chaque sommet est isolé. Un graphe dans lequel chaque sommet est relié à au moins un autre sommet. Un graphe où tous les sommets sont reliés entre eux directement. 4. Quelle structure de données est utilisée pour stocker un graphe en utilisant la méthode de la matrice d’adjacence ? Un dictionnaire. Une liste de listes ou une matrice. Un arbre. 5. Que signifie le degré d’un sommet dans un graphe ? Le nombre total de sommets dans le graphe. Le nombre de connexions (arêtes) qu’un sommet a. La distance entre le sommet et le sommet de départ. 6. Dans un parcours en profondeur (DFS), on utilise habituellement… Une file (queue). Une pile (stack). Un tableau. 7. Quelle est la complexité temporelle d’une recherche dans un graphe représenté par une liste d’adjacence ? O(V^2) O(V + E) O(V log V) 8. Comment vérifier si un graphe est cyclique en utilisant un parcours en profondeur ? En vérifiant si tous les sommets ont été visités. En traçant les sommets visités et les arêtes de retour. En calculant la somme des degrés des sommets. 9. Le parcours en largeur (BFS) est généralement utilisé pour : Trouver le chemin le plus court dans un graphe non pondéré. Trouver le plus grand degré d’un sommet. Compter le nombre de cycles dans un graphe. 10. Quelle est la différence principale entre un graphe orienté et un graphe non orienté ? Un graphe orienté n’a pas de cycles. Un graphe orienté a des arêtes avec une direction spécifique. Un graphe orienté a des arêtes qui relient des sommets identiques. Vérifier les réponses Reprendre le QCM
