Vocabulaire des graphes en terminale NSI

Qu'est-ce qu'une matrice d'adjacence dans un graphe ?

• Une matrice d'adjacence dans un graphe est une représentation sous forme de tableau où les lignes et colonnes représentent les sommets du graphe, et les valeurs indiquent s'il y a un lien entre les sommets correspondants.

• Une matrice de valeurs aléatoires

• Une liste de sommets sans liens

• Un schéma de couleurs pour le graphe

Comment est représentée une arête dans une matrice d'adjacence ?

• Une arête est représentée par un symbole spécial dans la matrice d'adjacence.

• Une arête est représentée par une valeur non nulle à l'intersection des lignes et colonnes correspondant aux sommets reliés par cette arête.

• Une arête est représentée par une lettre à l'intersection des lignes et colonnes correspondant aux sommets reliés par cette arête.

• Une arête est représentée par une valeur nulle dans la matrice d'adjacence.

Quels sont les avantages de l'utilisation d'une matrice d'adjacence pour représenter un graphe ?

• La matrice d'adjacence est complexe pour accéder à l'information sur les relations entre les sommets

• Les avantages de l'utilisation d'une matrice d'adjacence pour représenter un graphe sont sa simplicité de mise en œuvre, sa facilité pour vérifier la présence d'une arête entre deux sommets, et sa rapidité pour accéder à l'information sur les relations entre les sommets.

• La matrice d'adjacence est difficile à mettre en œuvre

• La matrice d'adjacence est lente pour vérifier les arêtes entre les sommets

Qu'est-ce qu'une liste d'adjacence dans un graphe ?

• Une liste d'adjacence est une structure de données utilisée pour représenter les couleurs des sommets d'un graphe.

• Une liste d'adjacence est une structure de données utilisée pour représenter les distances entre les sommets d'un graphe.

• Une liste d'adjacence dans un graphe est une structure de données utilisée pour représenter les relations entre les sommets d'un graphe. Chaque sommet est associé à une liste de ses sommets adjacents.

• Une liste d'adjacence est une structure de données utilisée pour représenter les chemins entre les sommets d'un graphe.

Comment est stockée l'information des arêtes dans une liste d'adjacence ?

• Les informations des arêtes sont stockées sous forme de listes de successeurs pour chaque sommet.

• Les informations des arêtes sont stockées sous forme de listes de prédécesseurs pour chaque sommet.

• Les informations des arêtes sont stockées sous forme de listes de voisins pour chaque sommet.

• Les informations des arêtes sont stockées sous forme de tableaux bidimensionnels.

Quels sont les avantages de l'utilisation d'une liste d'adjacence pour représenter un graphe ?

• Les avantages de l'utilisation d'une liste d'adjacence pour représenter un graphe sont l'efficacité de stockage des voisins de chaque sommet et la facilité d'accès aux voisins d'un sommet donné.

• Les listes d'adjacence ne permettent pas de stocker les informations sur les sommets du graphe

• L'utilisation d'une liste d'adjacence rend l'accès aux voisins d'un sommet plus lent

• Les listes d'adjacence nécessitent plus de mémoire que d'autres structures pour représenter un graphe

Quelle structure de données est généralement utilisée pour implémenter une matrice d'adjacence en programmation ?

• Une liste chaînée

• Un arbre binaire

• Un ensemble

• Un tableau à deux dimensions

Quelle structure de données est généralement utilisée pour implémenter une liste d'adjacence en programmation ?

• Liste statique

• Arbre binaire

• File de priorité

• Tableau de listes chaînées

Comment peut-on déterminer si deux sommets sont reliés par une arête en utilisant une matrice d'adjacence ?

• Regarder la somme des valeurs dans la ligne correspondant au premier sommet.

• Vérifier si les deux sommets sont adjacents dans la matrice de poids.

• Vérifier si la valeur correspondante dans la matrice d'adjacence est égale à 1.

• Vérifier si la valeur correspondante dans la matrice d'adjacence est égale à 0.

Comment peut-on déterminer si deux sommets sont reliés par une arête en utilisant une liste d'adjacence ?

• Compter le nombre d'arêtes entre les deux sommets dans la liste d'adjacence.

• Vérifier si le deuxième sommet est présent dans la liste d'adjacence du premier sommet.

• Vérifier si le premier sommet est présent dans la liste d'adjacence du deuxième sommet.

• Vérifier si les deux sommets sont de la même couleur dans la liste d'adjacence.