Quiz — QCM_PL_RO_Graphes_Janv 21_correction.pdf

Question 1 sur 10 20:00

[{"id":26199,"question":"Quel type de graphe est représenté par une matrice d'adjacence symétrique ?","option_a":"Graphe orienté","option_b":"Graphe non orienté","option_c":"Graphe pondéré","option_d":"Graphe complet","option_e":"","option_f":"","bonne_reponse":"b","explication":"Une matrice d'adjacence symétrique indique que pour chaque arête reliant A à B, il existe aussi une arête de B vers A. Cela caractérise un graphe non orienté.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"Graphe orienté\", \"b\": \"Graphe non orienté\", \"c\": \"Graphe pondé","_debug_options_count":4},{"id":26200,"question":"Un graphe possède 5 sommets de degré 2 et 2 sommets de degré 3. Peut-il contenir un chemin eulérien ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"b","explication":"Pour qu'un graphe possède un chemin eulérien, il doit avoir exactement 0 ou 2 sommets de degré impair. Ici, il y a 2 sommets de degré impair (3), donc c'est possible.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"Vrai\", \"b\": \"Faux\", \"c\": \"\", \"d\": \"\"}}","_debug_options_count":4},{"id":26201,"question":"Dans un graphe non orienté, quel est le degré du sommet C si ses voisins sont A, B et D ?","option_a":"1","option_b":"2","option_c":"3","option_d":"4","option_e":"","option_f":"","bonne_reponse":"c","explication":"Le degré d'un sommet correspond au nombre d'arêtes qui lui sont incidentes. Ici, C est relié à A, B et D, donc son degré est 3.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"c\", \"options\": {\"a\": \"1\", \"b\": \"2\", \"c\": \"3\", \"d\": \"4\"}}","_debug_options_count":4},{"id":26202,"question":"Un graphe complet à 4 sommets possède combien d'arêtes ?","option_a":"4","option_b":"6","option_c":"8","option_d":"12","option_e":"","option_f":"","bonne_reponse":"b","explication":"Dans un graphe complet, chaque sommet est relié à tous les autres. Pour 4 sommets, le nombre d'arêtes est donné par la formule n(n-1)\/2 = 4*3\/2 = 6.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"4\", \"b\": \"6\", \"c\": \"8\", \"d\": \"12\"}}","_debug_options_count":4},{"id":26203,"question":"La matrice d'adjacence d'un graphe orienté est-elle toujours carrée ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"Oui, une matrice d'adjacence est toujours carrée car elle représente les relations entre tous les sommets du graphe (même si certains sont isolés).","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"a\", \"options\": {\"a\": \"Vrai\", \"b\": \"Faux\", \"c\": \"\", \"d\": \"\"}}","_debug_options_count":4},{"id":26204,"question":"Quel algorithme permet de trouver le plus court chemin dans un graphe pondéré ?","option_a":"Algorithme de Dijkstra","option_b":"Algorithme de Prim","option_c":"Algorithme de Kruskal","option_d":"Algorithme de Floyd-Warshall","option_e":"","option_f":"","bonne_reponse":"a","explication":"L'algorithme de Dijkstra est utilisé pour trouver le plus court chemin dans un graphe pondéré avec des poids positifs.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"a\", \"options\": {\"a\": \"Algorithme de Dijkstra\", \"b\": \"Algorithme de Prim\", \"c\": \"Algorit","_debug_options_count":4},{"id":26205,"question":"Un graphe avec 3 sommets et 3 arêtes forme-t-il toujours un cycle ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"b","explication":"Non, un graphe avec 3 sommets et 3 arêtes peut former un cycle (triangle) ou une chaîne fermée (deux arêtes reliant A-B et B-C, et une arête reliant A-C).","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"Vrai\", \"b\": \"Faux\", \"c\": \"\", \"d\": \"\"}}","_debug_options_count":4},{"id":26206,"question":"Quelle est la somme des degrés de tous les sommets d'un graphe ?","option_a":"Égale au nombre d'arêtes","option_b":"Égale au double du nombre d'arêtes","option_c":"Égale au nombre de sommets","option_d":"Impossible à déterminer","option_e":"","option_f":"","bonne_reponse":"b","explication":"Chaque arête contribue à augmenter de 1 le degré de deux sommets. Ainsi, la somme des degrés est égale à 2 fois le nombre d'arêtes.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"Égale au nombre d'arêtes\", \"b\": \"Égale au double du nombre d'a","_debug_options_count":4},{"id":26207,"question":"Dans un graphe orienté, une matrice d'adjacence peut-elle avoir des valeurs autres que 0 et 1 ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"Oui, si le graphe est pondéré, les valeurs de la matrice peuvent représenter les poids des arêtes (par exemple, des distances ou des coûts).","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"a\", \"options\": {\"a\": \"Vrai\", \"b\": \"Faux\", \"c\": \"\", \"d\": \"\"}}","_debug_options_count":4},{"id":26208,"question":"Quel est l'objectif principal de l'algorithme de Prim ?","option_a":"Trouver le plus court chemin","option_b":"Construire un arbre couvrant de poids minimal","option_c":"Détecter un cycle eulérien","option_d":"Classer les sommets par degré","option_e":"","option_f":"","bonne_reponse":"b","explication":"L'algorithme de Prim est utilisé pour construire un arbre couvrant de poids minimal dans un graphe pondéré, utile pour des applications comme le réseau électrique.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"Trouver le plus court chemin\", \"b\": \"Construire un arbre couvrant","_debug_options_count":4}]