Quiz — Graph Theory (Annals of Discrete Mathematics).pdf

Question 1 sur 10 20:00

[{"id":72115,"question":"Quel est le nombre minimum de couleurs nécessaires pour colorier un graphe complet à 5 sommets ?","option_a":"2","option_b":"3","option_c":"4","option_d":"5","option_e":"","option_f":"","bonne_reponse":"d","explication":"Un graphe complet à n sommets nécessite n couleurs pour une coloration propre, car chaque sommet est relié à tous les autres.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"d\", \"options\": {\"a\": \"2\", \"b\": \"3\", \"c\": \"4\", \"d\": \"5\"}}","_debug_options_count":4},{"id":72116,"question":"Un arbre est un graphe connexe sans cycle.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"La définition d'un arbre est correcte : c'est un graphe connexe et acyclique.","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":72117,"question":"Quel algorithme permet de trouver le plus court chemin dans un graphe pondéré ?","option_a":"Algorithme de Prim","option_b":"Algorithme de Kruskal","option_c":"Algorithme de Dijkstra","option_d":"Algorithme de Ford-Fulkerson","option_e":"","option_f":"","bonne_reponse":"c","explication":"L'algorithme de Dijkstra est utilisé pour trouver le plus court chemin depuis un sommet source dans un graphe pondéré sans arêtes négatives.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"c\", \"options\": {\"a\": \"Algorithme de Prim\", \"b\": \"Algorithme de Kruskal\", \"c\": \"Algorith","_debug_options_count":4},{"id":72118,"question":"Un graphe eulérien est un graphe où tous les sommets ont un degré pair.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"Un graphe eulérien est un graphe connexe où tous les sommets ont un degré pair, et qui contient un cycle eulérien (traversant chaque arête une fois).","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":72119,"question":"Quelle est la complexité temporelle de l'algorithme de parcours en largeur (BFS) ?","option_a":"O(1)","option_b":"O(n)","option_c":"O(n + m)","option_d":"O(n²)","option_e":"","option_f":"","bonne_reponse":"c","explication":"La complexité de BFS est O(n + m), où n est le nombre de sommets et m le nombre d'arêtes, car chaque sommet et arête est visité une fois.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"c\", \"options\": {\"a\": \"O(1)\", \"b\": \"O(n)\", \"c\": \"O(n + m)\", \"d\": \"O(n²)\"}}","_debug_options_count":4},{"id":72120,"question":"Un graphe biparti peut toujours être colorié avec 2 couleurs.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"Un graphe biparti est un graphe dont les sommets peuvent être divisés en deux ensembles indépendants. Il est 2-coloriable par définition.","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":72121,"question":"Quel est le nombre minimal d'arêtes dans un graphe connexe à 7 sommets ?","option_a":"5","option_b":"6","option_c":"7","option_d":"8","option_e":"","option_f":"","bonne_reponse":"b","explication":"Un graphe connexe à n sommets a au moins n-1 arêtes (c'est un arbre). Pour 7 sommets, le minimum est donc 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\": \"5\", \"b\": \"6\", \"c\": \"7\", \"d\": \"8\"}}","_debug_options_count":4},{"id":72122,"question":"La matrice d'adjacence d'un graphe non orienté est toujours symétrique.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"Dans un graphe non orienté, si une arête existe entre les sommets i et j, alors l'arête existe aussi entre j et i. La matrice est donc symétrique.","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":72123,"question":"Quel algorithme permet de trouver un arbre couvrant de poids minimal dans un graphe pondéré ?","option_a":"Algorithme de Dijkstra","option_b":"Algorithme de Prim","option_c":"Algorithme de Bellman-Ford","option_d":"Algorithme de Floyd-Warshall","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é et connexe.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0,"_debug_answer_data_type":"string","_debug_answer_data_preview":"{\"correct\": \"b\", \"options\": {\"a\": \"Algorithme de Dijkstra\", \"b\": \"Algorithme de Prim\", \"c\": \"Algorit","_debug_options_count":4},{"id":72124,"question":"Un graphe hamiltonien contient un cycle passant par tous ses sommets.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"a","explication":"Un graphe hamiltonien est un graphe qui contient un cycle hamiltonien, c'est-à-dire un cycle passant exactement une fois par chaque sommet.","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}]