1. Dans un graphe, comment appelle-t-on un lien orienté entre deux sommets ?
Un cycle
Une arête
Un chemin
Un arc
Un arc
Explication
Un arc est un lien orienté, donc avec une direction. Une arête correspond au cas non orienté.
Un arc
Explication
Un arc est un lien orienté, donc avec une direction. Une arête correspond au cas non orienté.
Un chemin qui revient au sommet de départ
Explication
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é.
La liste des voisins du sommet
Explication
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.
Comme une clé avec une liste vide
Explication
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é.
Il existe un lien entre les deux sommets
Explication
La valeur 1 indique la présence d’un lien entre les sommets correspondants. La valeur 0 indique au contraire l’absence de lien.
Il fixe l’interprétation des lignes et des colonnes
Explication
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.
En comptant le nombre de voisins dans sa liste
Explication
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.
Le BFS explore d’abord les voisins du niveau courant
Explication
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.
Ajouter A vers B et aussi B vers A
Explication
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.
Vérifier qu’il n’a pas déjà été visité
Explication
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.
En comptant le nombre de voisins dans la liste associée au sommet
Explication
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.
Lancer un parcours en largeur ou en profondeur depuis un sommet et vérifier que tous les sommets sont atteints
Explication
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é.
Mémorisez les réponses avec 12 flashcards sur Notions clés des graphes et parcours.
Sommet — définition ?
Point représentant une entité dans un graphe.
Arête — rôle ?
Liaison non orientée entre deux sommets.
Arc — différence ?
Liaison orientée avec flèche.
Consultez la fiche de révision complète sur Notions clés des graphes et parcours.
Voir la fiche →Mathématiques
Mathématiques
Mathématiques
Physique
Physique
Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.
Générateur de QCM