Numérique et sciences informatiques (spécialité) · TerminaleBac
Quiz sur les représentations des graphes : Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Un graphe est non orienté (arêtes) ou orienté (arcs) ; un graphe pondéré associe un nombre à chaque arête.
- Un même graphe peut se dessiner de plusieurs façons : le dessin n'est pas le graphe.
- Deux représentations en machine : la matrice d'adjacence (tableau de 0 et 1) et les listes de voisins (dictionnaire de listes).
- La matrice dépend de l'étiquetage des sommets ; elle est symétrique pour un graphe non orienté.
- Matrice : test d'arête immédiat, mais n² cases ; listes : économes quand il y a peu d'arêtes.
Avant de commencer
Ce quiz porte sur la façon de représenter un graphe, sur le papier puis dans un programme. Tu y rencontreras la différence entre graphe orienté et non orienté, le graphe pondéré, la matrice d'adjacence, les listes de voisins et le choix de la représentation la plus adaptée.
Les graphes servent à modéliser des situations très variées : molécules, réseaux sociaux, réseaux de transport figurent parmi les exemples cités pour leur capacité à décrire des relations 3. En NSI, tu dois savoir passer d'un dessin à une structure de données, et inversement.
Comment bien utiliser ce quiz
Quiz
16 questions · correction immédiate · ton score reste sur ton appareil.
-
Le programme distingue le graphe non orienté, défini par un ensemble de sommets et un ensemble d'arêtes, du graphe orienté, défini avec des arcs 1. Un arc va d'un sommet vers un autre, une arête relie deux sommets sans sens. Le nombre de sommets n'a aucun lien avec l'orientation, et les deux types se dessinent sans difficulté.
-
C'est faux : la représentation graphique d'un graphe n'est pas unique, et deux schémas différents peuvent représenter le même graphe 1. Ce qui définit le graphe, ce sont ses sommets et ses liens, pas la position des points sur la feuille.
-
Les arcs ou arêtes d'un graphe peuvent se couper sur le dessin 1. Un croisement n'ajoute aucun sommet : seuls les points nommés sont des sommets. Il n'est pas toujours possible d'éviter les croisements, et cela n'a aucun rapport avec l'orientation.
-
Le sommet 2 est relié à 0, à 1 et à 3, donc ses voisins sont {0, 1, 3} et son degré vaut 3. L'erreur tentante est de répondre 4 en comptant le sommet lui-même, ou 2 en oubliant l'arête 2-3.
-
Chaque arête non orientée apparaît deux fois dans la matrice : et . Avec 4 arêtes, on obtient coefficients égaux à 1. Répondre 4 revient à oublier la symétrie de la matrice.
-
Une arête relie et dans les deux sens, donc . Sans boucle, aucun sommet n'est relié à lui-même : la diagonale est nulle. La diagonale de 1 correspondrait à des boucles sur tous les sommets, et le nombre de 1 dépend des arêtes, pas du nombre de sommets.
-
Dans un graphe orienté, chaque arc ne donne qu'un seul 1 : , , et . On compte donc 4. Doubler le résultat, comme pour un graphe non orienté, est l'erreur à éviter : la matrice d'un graphe orienté n'est en général pas symétrique.
-
Dans un graphe pondéré (ou valué), chaque arête porte un nombre, son poids, qui peut représenter une distance, un coût ou une capacité 3. Le nom d'un sommet est une étiquette de sommet et non un poids d'arête : c'est la confusion à éviter.
-
Les molécules sont représentées par des graphes d'atomes et de liaisons 3 : un atome est un sommet, une liaison relie deux atomes, donc c'est une arête. Inverser les rôles ferait relier des liaisons entre elles, ce qui n'a pas de sens pour une molécule.
-
La matrice dépend de la façon dont les sommets sont étiquetés : en inversant deux étiquettes, on inverse les colonnes correspondantes de la matrice d'adjacence 3, et pour garder la cohérence les lignes aussi. Le graphe, lui, reste le même ; c'est seulement sa description qui change. Penser que la matrice est inchangée revient à croire qu'elle ne dépend pas du numérotage.
-
La matrice est un tableau , soit cases, quel que soit le nombre d'arêtes. Répondre 1 000 revient à confondre la matrice avec une simple liste de sommets. C'est ce coût en qui pousse à préférer les listes de voisins quand il y a peu d'arêtes.
-
Les listes de voisins ne mémorisent que les liens qui existent, donc leur taille suit le nombre d'arêtes. La matrice réserve une case pour chaque couple de sommets, y compris pour les nombreux couples non reliés. Quand le graphe est dense, c'est-à-dire quand presque tous les couples sont reliés, l'écart disparaît.
-
Dans cette représentation par dictionnaire, la clé est un sommet et la valeur est la liste de ses voisins :
g[0]vaut[1, 2]. Ce n'est pas une ligne de matrice, qui serait[0, 1, 1](des 0 et des 1 indexés par sommet). Ici aucune valeur de poids n'est stockée. -
C'est vrai : avec une matrice, on lit directement
M[i][j]. Avec des listes de voisins, il faut chercher dans la liste de , ce qui demande de la parcourir si elle n'est pas triée. C'est l'avantage principal de la matrice, payé par une mémoire en . -
C'est faux. Un arc de vers met 1 en sans imposer 1 en . Avec l'arc 0→1 seul, et . La symétrie est une propriété des graphes non orientés, pas des graphes orientés.
-
La notion d'adjacence relie les sommets que joint une arête 1. Comme une arête non orientée n'a pas de sens, l'adjacence va dans les deux directions. L'adjacence à sens unique n'a de sens que pour les arcs d'un graphe orienté.
Les questions qu'on se pose
Faut-il préférer la matrice d'adjacence ou les listes de voisins au bac ?
Cela dépend de l'énoncé et du graphe. La matrice donne un test d'arête immédiat mais occupe cases ; les listes de voisins suivent le nombre d'arêtes. Pour un graphe avec peu de liens, les listes sont plus économes. Justifie toujours ton choix par l'un de ces critères.
Pourquoi la matrice change-t-elle quand on renumérote les sommets ?
Parce que la matrice dépend de l'étiquetage : échanger deux étiquettes échange les colonnes correspondantes 3 (et de même les lignes). Le graphe reste identique, seule sa description change. Pour comparer deux matrices, assure-toi qu'elles utilisent le même numérotage.
Un graphe pondéré se représente-t-il aussi avec une matrice ?
Oui. Un graphe pondéré associe un nombre à chaque arête 3. On peut alors placer ce poids dans la case à la place du 1, en choisissant une valeur spéciale pour l'absence d'arête. Avec des listes, on stocke dans la liste de des couples (voisin, poids).
Sources
- Document officiel eduscol : Graphes (structures de données), Éduscol. Consulté le 7 novembre 2026.
- Représentation graphique, Wikipédia. Consulté le 7 novembre 2026.
- Théorie des graphes, Wikipédia. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.