Rédigé et vérifié par un professeur diplômé de l’École Polytechnique. Découvrir le professeur
En mathématiques, un graphe est un ensemble de points, appelés sommets, reliés par des traits, appelés arêtes : c’est l’outil idéal pour modéliser un réseau — des amis sur un réseau social, des routes entre des villes, des pages web reliées par des liens. Au programme de maths expertes en terminale, puis prolongé en prépa, ce chapitre relie les graphes aux matrices. Tu trouveras ici : les définitions exactes, tout le vocabulaire, les méthodes, des figures, trois exercices corrigés et une FAQ.
Au programme
- 🔵 Seconde (SNT) — thème « Réseaux sociaux » : graphe, distance, diamètre.
- 🔵 Terminale (maths expertes) — chapitre « Graphes et matrices », BO spécial n°8 du 25 juillet 2019.
- 🔵 Terminale (NSI) — structures de données et parcours de graphes.
- 🟠 Prépa ECG1 / ECG2 — maths appliquées (BO spécial n°1 du 11 février 2021) : connexité, graphes probabilistes, chaînes de Markov.
Cadre du cours : on travaille avec des graphes finis. Les propriétés de degrés et de connexité ci-dessous concernent les graphes non orientés ; on précise chaque passage aux graphes orientés. Une boucle non orientée compte deux fois dans le degré de son sommet.
I. Qu’est-ce qu’un graphe ?
Un graphe est un objet mathématique volontairement épuré : on ne garde que deux ingrédients, des sommets et des arêtes qui relient certains de ces sommets. Peu importe la forme du dessin — seules comptent les connexions.
Définition — Graphe
Un graphe est la donnée d’un ensemble de points, les sommets, et d’un ensemble de lignes, les arêtes, dont chacune relie deux sommets. Deux sommets reliés par une arête sont dits adjacents.
On peut donc dessiner le même graphe de mille façons : ce qui le définit, c’est « qui est relié à qui », pas la position des points sur la feuille.
A. Sommets et arêtes : la définition
Prenons un graphe à quatre sommets numérotés 1, 2, 3, 4, avec les arêtes 1–2, 1–3, 2–3 et 3–4. Le sommet 3 est relié à trois autres sommets ; le sommet 4 n’est relié qu’au sommet 3.
B. Graphe, graphique ou graphe d’une fonction : ne pas confondre
C’est la confusion la plus fréquente. En théorie des graphes, un graphe n’a rien à voir avec un graphique (un diagramme en barres, une courbe) ni avec le graphe d’une fonction (la courbe représentative étudiée en analyse, l’ensemble des points de coordonnées \((x\,;\,f(x))\)).
Ne pas confondre : « graphe » désigne ici un réseau de points et de liens ; « graphique » désigne une représentation visuelle de données ; le « graphe d’une fonction » est une courbe. Si tu cherches à lire une image ou un antécédent sur une courbe, c’est du côté de l’étude de la courbe représentative d’une fonction qu’il faut regarder, pas ici.
C. Trois exemples pour comprendre
- Réseau d’amis : les sommets sont des personnes, une arête relie deux amis.
- Réseau routier : les sommets sont des villes, les arêtes sont les routes.
- Web : les sommets sont des pages, les arêtes sont les liens hypertextes.
D. Aux origines : les ponts de Königsberg
En 1736, Euler démontre l’impossibilité de traverser les sept ponts de Königsberg chacun une seule fois, même sans revenir au départ. La modélisation par sommets et arêtes fait apparaître quatre sommets de degré impair : ce problème historique introduit les chaînes eulériennes.
II. Le vocabulaire de base
Avant toute méthode, il faut parler la langue des graphes. Trois mots reviennent sans cesse : adjacent, degré et ordre.
A. Sommets adjacents et degré d’un sommet
Définition — Degré
Le degré d’un sommet est le nombre d’arêtes qui en partent. On le note parfois \(d(s)\) pour un sommet \(s\).
Dans notre graphe précédent : \(d(1)=2\), \(d(2)=2\), \(d(3)=3\) et \(d(4)=1\).
B. Ordre d’un graphe
L’ordre d’un graphe est simplement son nombre de sommets. Notre graphe est d’ordre 4.
C. Somme des degrés et nombre d’arêtes
Propriété — Lemme des poignées de main
Dans tout graphe, la somme des degrés de tous les sommets est égale au double du nombre d’arêtes :
\(\displaystyle\sum_{s} d(s) = 2 \times (\text{nombre d'arêtes})\)
Démonstration. Chaque arête possède exactement deux extrémités. Quand on additionne les degrés de tous les sommets, chaque arête est comptée deux fois — une fois pour chacune de ses extrémités. La somme des degrés vaut donc bien le double du nombre d’arêtes. ∎
Vérifions sur notre graphe : \(2+2+3+1 = 8\), soit \(2 \times 4\) arêtes. ✓ Ce lemme sert de garde-fou : si tu obtiens une somme de degrés impaire, tu as fait une erreur.
Toute la théorie des graphes dans une fiche
Définitions, vocabulaire, lemme des poignées de main, matrice d’adjacence et chaînes de Markov : l’essentiel du chapitre sur une seule fiche de révision.
📄 Télécharger la fiche PDFImprime-la et retrouve les définitions utiles avant le contrôle.
III. Les grandes familles de graphes
Tous les graphes ne se ressemblent pas : certains ont des flèches, d’autres des poids, certains relient tout le monde. Voici les familles à connaître, détaillées dans le cours types de graphes.
| Famille | Caractéristique | Exemple |
|---|---|---|
| Graphe non orienté | Les arêtes n’ont pas de sens | Réseau d’amis |
| Graphe orienté | Les arêtes (arcs) ont un sens (flèches) | Liens entre pages web |
| Graphe complet | Tous les sommets sont deux à deux adjacents | Tournoi « tous contre tous » |
| Graphe pondéré | Chaque arête porte un nombre (poids) | Distances entre villes |
| Arbre | Graphe connexe sans cycle | Arborescence de fichiers |
Un cas particulier important est le graphe pondéré dont les poids sont des probabilités : on parle alors de graphe probabiliste, directement lié aux chaînes de Markov (section VI).
IV. Chaînes, cycles et connexité
Se déplacer dans un graphe, c’est enchaîner des arêtes. C’est ici qu’apparaît l’une des notions centrales du programme : la connexité.
Définitions — Chaîne, cycle, graphe connexe
- Une chaîne est une suite d’arêtes consécutives ; sa longueur est son nombre d’arêtes.
- Un cycle est une chaîne fermée (qui revient à son point de départ) sans répéter d’arête.
- Un graphe est connexe lorsque toute paire de sommets peut être reliée par une chaîne.
Erreur classique : croire qu’un graphe « sans sommet isolé » est forcément connexe. C’est faux. Deux arêtes disjointes (1–2 et 3–4) forment un graphe sans aucun sommet isolé… et pourtant non connexe, car on ne peut pas aller de 1 à 4. La bonne définition reste toujours : toute paire de sommets reliée par une chaîne.
La méthode complète pour montrer qu’un graphe est connexe (ou qu’il ne l’est pas) est détaillée dans le cours dédié.
V. Représenter un graphe par une matrice
Un dessin devient vite illisible dès qu’il y a beaucoup de sommets. On traduit alors le graphe en tableau de nombres : la matrice d’adjacence. C’est le pont entre les graphes et les matrices, et le cœur du programme de maths expertes.
Définition — Matrice d’adjacence
La matrice d’adjacence d’un graphe à \(n\) sommets est la matrice \(A\) de taille \(n \times n\) dont le coefficient \(a_{ij}\) vaut le nombre d’arêtes entre le sommet \(i\) et le sommet \(j\).
Pour notre graphe à quatre sommets (arêtes 1–2, 1–3, 2–3, 3–4), la matrice d’adjacence est :
\(A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\)Pour un graphe non orienté, cette matrice est toujours symétrique (l’arête 1–3 est aussi l’arête 3–1).
Le résultat le plus puissant du chapitre : le coefficient situé à la ligne \(i\) et la colonne \(j\) de \(A^n\) donne le nombre de chaînes de longueur \(n\) entre les sommets \(i\) et \(j\). Par exemple, le coefficient \((1\,;\,4)\) de \(A^2\) vaut 1 : il existe exactement une chaîne de longueur 2 de 1 à 4, à savoir 1–3–4.
Ce théorème se démontre par récurrence, en s’appuyant sur le produit matriciel et les puissances de matrices. Toute la méthode est développée dans la matrice d’adjacence. Côté informatique, on peut aussi stocker un graphe sous forme de liste d’adjacence et le parcourir : voir représenter un graphe en Python.
VI. Graphes probabilistes et chaînes de Markov
Quand on met des probabilités sur les arêtes d’un graphe orienté, on obtient un graphe probabiliste, qui modélise l’évolution d’un système entre plusieurs états. C’est le second grand volet de maths expertes.
Imagine un service d’abonnement avec deux états : « abonné » (A) et « désabonné » (B). Chaque mois, 80 % des abonnés le restent et 20 % se désabonnent ; 30 % des désabonnés se réabonnent. On résume ces transitions dans une matrice de transition :
\(P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}\)
L’étude de l’évolution à long terme (la distribution invariante) fait l’objet du cours chaîne de Markov. En prépa, la matrice \(P\) y est étudiée comme matrice stochastique, en lien avec les valeurs propres.
VII. Les graphes dans la vie réelle
Si ce chapitre figure au programme, c’est parce que les graphes sont partout. Quelques applications concrètes :
- Réseaux sociaux (SNT) : amitiés, distances entre profils, diamètre du réseau.
- GPS : trouver le plus court chemin entre deux villes sur un graphe pondéré.
- Web et PageRank : L’idée historique de PageRank attribue une importance aux pages grâce à une marche aléatoire sur le graphe du web, modélisée par une chaîne de Markov.
- Génétique, files d’attente, modèle d’Ehrenfest : autant de systèmes qui changent d’état avec des probabilités.
La théorie des graphes irrigue aussi la data science (knowledge graphs), mais ce sont les mêmes objets mathématiques que ceux de ce cours.
VIII. Parcours par niveau : de la Seconde à la prépa
Les graphes se retrouvent à chaque étape de la scolarité, avec un niveau d’exigence croissant. Voici comment s’organise la progression.
| Niveau | Notions clés | Programme | Page du cours |
|---|---|---|---|
| 🔵 Seconde (SNT) | Graphe, distance, diamètre | Réseaux sociaux | Graphe connexe |
| 🔵 Terminale (maths expertes) | Vocabulaire, matrice d’adjacence, chaînes de Markov | BO spécial n°8 (2019) | Toutes |
| 🔵 Terminale (NSI) | Structures de données, parcours | NSI | Graphes en Python |
| 🟠 Prépa ECG1 | Connexité, critère matriciel | BO spécial n°1 (2021) | Matrice d’adjacence |
| 🟠 Prépa ECG2 | Chaînes de Markov, états stables | BO spécial n°1 (2021) | Matrice stochastique |
| 🔴 Prépa scientifique | Parcours, plus court chemin, concours | ITC | Graphes en Python |
IX. Exemples d’application
Trois applications pour vérifier que les définitions sont bien en place. Pour une série complète et progressive, va voir les exercices corrigés sur les graphes.
Exercice 1 — Ordre et degrés ★
On considère un graphe à cinq sommets A, B, C, D, E, avec les arêtes A–B, A–C, B–C, C–D, D–E. Donne l’ordre du graphe, le degré de chaque sommet, puis vérifie le lemme des poignées de main.
Voir la correction de l’exercice 1
Le graphe a 5 sommets, donc son ordre est 5.
On compte les arêtes incidentes à chaque sommet : \(d(A)=2\), \(d(B)=2\), \(d(C)=3\), \(d(D)=2\), \(d(E)=1\).
Somme des degrés : \(2+2+3+2+1 = 10\). Or le graphe a 5 arêtes, et \(2 \times 5 = 10\).
Le lemme des poignées de main est bien vérifié.
Exercice 2 — Connexité, un raisonnement ★★
Un graphe a pour sommets 1, 2, 3, 4 et pour arêtes 1–2, 2–3, 3–1. Le sommet 4 n’a aucune arête. Ce graphe est-il connexe ? Justifie sans te contenter de dire « il n’y a pas de sommet isolé ».
Voir la correction de l’exercice 2
Ici le sommet 4 est isolé, mais le vrai argument est le bon test : peut-on relier toute paire de sommets par une chaîne ?
Essayons de relier le sommet 1 au sommet 4 : aucune arête ne part de 4, donc aucune chaîne ne peut y aboutir.
Il existe donc une paire de sommets non reliée : le graphe n’est pas connexe. Il possède deux composantes connexes : le triangle {1, 2, 3} et le sommet {4}.
Exercice 3 — Matrice d’adjacence et chemins ★★
Soit le graphe non orienté à trois sommets 1, 2, 3 avec les arêtes 1–2 et 2–3. Écris sa matrice d’adjacence \(A\), puis calcule le coefficient ligne 1 colonne 3 de \(A^2\) et interprète-le.
Voir la correction de l’exercice 3
La matrice d’adjacence est :
\(A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\)Le coefficient ligne 1 colonne 3 de \(A^2\) est le produit de la ligne 1 de \(A\) par la colonne 3 de \(A\) :
\((0 \times 0) + (1 \times 1) + (0 \times 0) = 1\)Ce coefficient vaut 1 : il existe exactement une chaîne de longueur 2 entre le sommet 1 et le sommet 3, à savoir 1–2–3. ✓
X. Erreurs fréquentes
Les fautes de ce chapitre sont presque toujours les mêmes. Les connaître, c’est déjà les éviter.
Erreur n°1 — « Pas de sommet isolé = connexe ». Faux : deux arêtes disjointes le prouvent. La connexité exige une chaîne entre toute paire de sommets.
Erreur n°2 — Confondre graphe et graphique. Un graphe est un réseau de sommets et d’arêtes ; un graphique est un diagramme ; le graphe d’une fonction est une courbe. Trois objets distincts.
Erreur n°3 — Oublier le facteur 2 dans la somme des degrés. La somme des degrés vaut deux fois le nombre d’arêtes, jamais une fois.
Erreur n°4 — Mélanger chaîne, cycle et chemin. La chaîne (graphe non orienté) devient chemin dans un graphe orienté ; le cycle est une chaîne fermée. Respecte le vocabulaire du non orienté en maths expertes.
XI. Questions fréquentes
Qu’est-ce qu’un graphe en maths ?
Un graphe est un ensemble de points appelés sommets, reliés par des traits appelés arêtes. Deux sommets reliés sont dits adjacents. Un graphe sert à modéliser un réseau : des amis, des villes connectées par des routes, ou des pages web reliées par des liens. Seules comptent les connexions, pas la position des points.
Quelle est la différence entre un graphe et un graphique ?
Un graphe est un réseau de sommets et d’arêtes (théorie des graphes). Un graphique est une représentation visuelle de données, comme un diagramme en barres ou une courbe. Ce sont deux notions totalement différentes qui portent, en français, des noms proches. Le « graphe d’une fonction » est encore autre chose : c’est sa courbe représentative.
Quel est le sens du mot graphe ?
En mathématiques, « graphe » vient du grec et désigne une structure faite de sommets reliés par des arêtes. Attention : le mot a d’autres sens dans la langue courante (graffiti, abréviation de « graphique »), mais dans ce cours il désigne toujours l’objet de la théorie des graphes.
Quels sont les types de graphes ?
Les principaux types sont : le graphe non orienté, le graphe orienté (avec flèches), le graphe complet (tous les sommets reliés), le graphe pondéré (arêtes munies de poids), le graphe probabiliste et l’arbre (connexe sans cycle). Chaque famille est détaillée dans le cours « types de graphes ».
Comment calculer le degré d’un sommet ?
Le degré d’un sommet est le nombre d’arêtes qui en partent. Il suffit de compter les traits qui touchent ce sommet. Vérification utile : la somme des degrés de tous les sommets doit être égale au double du nombre d’arêtes (lemme des poignées de main).
Quelle est la différence entre une chaîne, un cycle et un chemin ?
Un cycle est ici une chaîne fermée sans répétition d’arête. Si les sommets ne se répètent pas non plus, sauf au départ et à l’arrivée, on parle de cycle élémentaire.
À quoi servent les graphes dans la vie réelle ?
Les graphes modélisent les réseaux sociaux, les trajets GPS (plus court chemin), le classement des pages web par Google (PageRank), les files d’attente ou encore la génétique. C’est pour cette universalité qu’ils figurent au programme de maths expertes et de prépa.
Qu’est-ce qu’une matrice d’adjacence ?
La matrice d’adjacence d’un graphe à n sommets est un tableau carré de taille n×n dont le coefficient ligne i colonne j indique le nombre d’arêtes entre les sommets i et j. Son grand intérêt : les coefficients de la puissance n-ième de cette matrice comptent les chaînes de longueur n entre les sommets.
XII. Pour aller plus loin
Tu maîtrises maintenant le vocabulaire et les grandes idées de la théorie des graphes. Pour approfondir chaque notion, continue avec :
- Inégalité de Markov : énoncé, démonstration et applications (du lycée à la prépa)
- Réussir les maths expertes en terminale et viser la prépa
- Probabilités Totales (Terminale) : Formule et Méthodes
- Le raisonnement par récurrence : principe, méthode et exemples
