Un cap pour ce chapitre
Ce que vous saurez faire
- Choisir les sommets et les relations d’un modèle.
- Distinguer arêtes non orientées et arcs orientés.
- Interpréter voisinage, chemins et pondérations.
Les bases utiles pour commencer
Définir les éléments et le sens d’un lien
Un graphe comporte des sommets et des relations entre eux. Pour un réseau routier, les sommets peuvent être des carrefours et les liens des portions de route. Pour un réseau social, les sommets peuvent être des comptes et les liens des abonnements. La phrase « il existe un lien lorsque… » doit être précise.
Le dessin est une représentation du modèle, pas nécessairement une carte géographique. Deux sommets proches sur l’écran ne sont pas forcément reliés. Deux traits qui se croisent ne créent pas automatiquement un carrefour : un sommet doit être explicitement présent à l’intersection pour que le modèle l’indique.
Pour construire le modèle, commencez par écrire les sommets même s’ils n’ont aucun lien. Puis ajoutez les relations autorisées d’après l’énoncé. Cela empêche de faire disparaître un lieu isolé ou une personne sans abonnement. Le placement graphique vient ensuite : il doit aider à lire les relations, sans en inventer à partir de la proximité des points.
Une relation peut être réciproque ou orientée
Dans un graphe non orienté, une arête relie deux sommets sans distinguer un départ et une arrivée. Elle convient à une relation symétrique, comme une liaison utilisable dans les deux sens dans un modèle simplifié. Dans un graphe orienté, un arc A vers B n’implique pas un arc B vers A.
Un abonnement illustre cette asymétrie : A peut suivre B sans que B suive A. Il est parfois utile d’utiliser deux arcs opposés pour représenter une relation réciproque dans un graphe orienté. Il faut conserver cette convention lors des recherches de chemins et de la construction d’une matrice.
Lire les voisins et les chemins
Deux sommets reliés par une arête sont voisins. Dans un graphe orienté, on distingue les successeurs, accessibles par un arc sortant, et les prédécesseurs, qui possèdent un arc vers le sommet. Le nombre de relations incidentes permet de définir des degrés, en précisant s’il s’agit des entrées ou sorties pour un graphe orienté.
Un chemin suit une succession de relations autorisées. Dans le cas orienté, il respecte leur sens. Un sommet isolé ne possède aucun lien, mais reste un sommet du graphe. Sa présence peut représenter une information importante, par exemple une station momentanément inaccessible.
Un chemin n’est pas nécessairement une liaison directe. Avec A vers B et B vers C, C est accessible depuis A par deux arcs, mais C n’est pas automatiquement un successeur direct de A. Le nombre de voisins et le nombre de sommets atteignables répondent ainsi à deux questions différentes. Distinguez-les avant de compter ou de programmer un parcours.
Donner un sens aux poids
Une pondération associe une valeur à chaque relation : distance, temps de trajet, coût ou capacité selon la question. Ces grandeurs ne sont pas interchangeables. Pour minimiser un temps de trajet, additionner des kilomètres sans information de vitesse ne répond pas directement au besoin.
Le graphe pertinent dépend donc de l’objectif. Un réseau peut être non orienté pour une liaison physique et orienté pour des autorisations de circulation. La modélisation retire certains détails du monde réel ; elle doit conserver ceux nécessaires à la question et annoncer ce qu’elle simplifie. Les algorithmes ne peuvent corriger une relation mal définie.
Exemple suivi : un réseau d’abonnements
On connaît les arcs A vers B, A vers C, B vers D et C vers D. Les successeurs de A sont B,C ; ses prédécesseurs sont absents. D n’a aucun successeur, mais possède deux prédécesseurs B,C. A peut atteindre D par A,B,D ou A,C,D, sans être relié directement à D.
Ajoutons D vers A. D possède désormais A comme successeur, A possède D comme prédécesseur et des cycles deviennent possibles, par exemple A,B,D,A. Un cycle suit des arcs autorisés et revient au sommet initial. Dans un graphe non orienté représentant les mêmes liaisons comme réciproques, les voisins se lisent dans les deux sens. Le modèle change réellement : ce n’est pas uniquement un autre dessin de flèches.
Comparer un trajet court et un trajet rapide
Un réseau propose A vers B en 2 minutes, B vers D en 8 minutes, A vers C en 4 minutes et C vers D en 3 minutes. Les deux chemins ont deux arcs, mais leurs coûts sont 10 et 7 minutes. Le chemin par C est plus rapide selon la pondération, même si le nombre d’étapes est identique.
Pour une modélisation exploitable, chaque poids doit correspondre à une grandeur homogène. Additionner minutes et kilomètres produirait un nombre sans signification pour le temps total. Les durées doivent également être considérées valables pour le scénario étudié. Un sens interdit exige une orientation, un lieu fermé peut exiger une suppression de liens et une correspondance possible exige un sommet explicite. Ces choix définissent le problème que l’algorithme résoudra ; ils ne sont pas des détails décoratifs.
À vous de faire varier les choses
Le même réseau, deux sens de lecture
Comparez une relation réciproque à une relation orientée. Choisissez un sommet et observez ses possibilités d’entrée et de sortie.
Lire le résultat de l’expérience initiale
Depuis A : B, C
Chaque relation possède un sens. Le tableau indique les départs et arrivées autorisés.
| Relation | Sens autorisé |
|---|---|
| A - B | A vers B |
| A - C | A vers C |
| B - D | B vers D |
| C - D | C vers D |
Changer l’orientation modifie les communications possibles sans changer le nom des sommets.
De la compréhension à l’autonomie
À vous de résoudre
Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.
Un abonnement n’est pas une amitié réciproque
A suit B, B suit C et C ne suit personne. Quel type de graphe représente exactement ces informations ? A est-il nécessairement suivi par B ?
Indice 1
La relation donnée possède un sens.
Indice 2
Aucune relation inverse n’est annoncée.
Comprendre la correction
On utilise un graphe orienté avec les arcs A → B et B → C. Aucun arc B → A n’est déduit. Transformer les arcs en arêtes ajouterait une réciprocité que les données ne garantissent pas.
Choisir une pondération
Deux trajets relient les mêmes lieux : 4 km en 20 minutes et 7 km en 12 minutes. Quelle information pondère le graphe si l’objectif est d’arriver au plus vite ?
Indice 1
Le critère demandé est une durée.
Indice 2
Le chemin le plus court en distance peut être plus lent.
Comprendre la correction
On utilise les temps de trajet, dans une unité commune. Le second trajet est préférable selon ce critère avec 12 minutes. Utiliser les distances sélectionnerait le premier, ce qui répondrait à une autre question. Il faut aussi supposer ces durées valables pour les conditions étudiées.
Un croisement trompeur
Les arêtes A-B et C-D se croisent sur un dessin, sans sommet au croisement. Un élève passe de A à D par cette intersection. Pourquoi ce chemin n’est-il pas justifié ?
Indice 1
Un trait représente une relation complète entre ses extrémités.
Indice 2
Le dessin ne crée pas un sommet implicite.
Comprendre la correction
Le graphe ne donne aucun sommet permettant de passer d’une arête à l’autre. Le croisement graphique peut représenter deux relations indépendantes, comme un pont au-dessus d’une route. Il faudrait ajouter explicitement un sommet et adapter les arêtes pour autoriser ce passage.
Changer la question change le modèle
Une liaison permet à A d’envoyer des messages à B, mais un réglage interdit le retour. Pourquoi une arête non orientée serait-elle insuffisante pour étudier les communications autorisées ?
Indice 1
Le matériel et l’autorisation logique ne décrivent pas le même niveau.
Indice 2
Une arête autorise la lecture dans les deux sens.
Comprendre la correction
Une arête ferait croire que le trajet B vers A est autorisé. Un arc A vers B décrit mieux la communication permise. On pourrait conserver un graphe non orienté pour la connectivité matérielle, mais il faudrait un autre modèle ou des informations supplémentaires pour les autorisations.
Local et accessible
Pour A→B, A→C, B→D, C→D, donnez les successeurs de A, les prédécesseurs de D et deux chemins de A à D. D est-il un successeur direct de A ? Ajoutez D→A et donnez un cycle.
Indice 1
Un successeur utilise un seul arc.
Indice 2
Un chemin peut enchaîner plusieurs arcs.
Comprendre la correction
Les successeurs de A sont B,C ; les prédécesseurs de D sont B,C. Les chemins A,B,D et A,C,D atteignent D en deux arcs. D n’est pas un successeur direct de A. Après l’ajout, A,B,D,A forme un cycle orienté.
Comparer deux pondérations
A-B-D mesure 5 km et dure 12 minutes. A-C-D mesure 8 km et dure 9 minutes. Choisissez le trajet selon une minimisation de distance, puis de temps. Quelle erreur ferait un programme utilisant les kilomètres pour répondre à une demande de durée minimale ?
Indice 1
Le critère choisit la signification des poids.
Indice 2
Un trajet peut être meilleur selon une grandeur et moins bon selon l’autre.
Comprendre la correction
La distance minimale choisit A-B-D, la durée minimale A-C-D. Un programme pondéré en kilomètres répondrait correctement à la première question mais pas à la seconde. Les deux mesures décrivent des objectifs différents, même si les sommets sont identiques.
Un croisement n’est pas une correspondance
Un schéma comporte seulement les arêtes A-B et C-D, qui se croisent visuellement. On souhaite permettre un passage par un nouveau carrefour X au croisement. Donnez les quatre arêtes du modèle modifié et expliquez ce que leur ajout change.
Indice 1
Chaque ancienne route est découpée au nouveau sommet.
Indice 2
Le point X doit appartenir explicitement à l’ensemble des sommets.
Comprendre la correction
Les arêtes sont A-X, X-B, C-X et X-D. X devient un sommet où l’on peut changer de route. Un chemin A-X-D existe alors, tandis que le dessin initial ne l’autorisait pas. Ajouter ce sommet change la connectivité du modèle et doit correspondre à une possibilité réelle du scénario.
Les erreurs qui méritent un détour
- Déduire une relation de la proximité visuelle.
- Seuls les liens définis comptent. Le placement sert à la lisibilité, pas à créer des arêtes.
- Additionner des poids sans vérifier leur signification.
- Distance, durée et capacité ne s’agrègent pas toujours de la même façon. Annoncez le critère étudié.
La fiche à garder
L’essentiel à retenir
- Un graphe dépend d’une définition précise des relations.
- Un arc ne garantit pas sa réciproque.
- Une pondération doit correspondre à la question posée.
Cette notion au bac
Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.
- Bac 2026 · Métropole · Jour 1 : Recto-Verso : jouer avec XOR et chercher la victoire dans un graphe
- Bac 2026 · Métropole · Jour 2 : Taquin : corriger le programme et conserver la résolubilité
- Bac 2026 · Asie · Jour 2 : Jeu de mots : déduire un alphabet par tri topologique
- Bac 2026 · Polynésie · Jour 2 : Taquin et recherche de texte : deux parcours à ne pas interrompre trop tôt
Le prochain pas
- Représenter un graphe en machine
- Parcourir un graphe en profondeur : DFS
- Parcourir un graphe en largeur : BFS
- Chercher des chemins et détecter des cycles
- Tables de routage et protocole RIP
Retrouver le catalogue de Terminale
Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.