Rédigé et vérifié par un professeur diplômé de l’École Polytechnique. Découvrir le professeur
Un réseau routier avec des sens uniques, une liste d’amis sur un réseau social, une arborescence de dossiers, le plan du métro : derrière ces objets si différents se cache une même idée mathématique, le graphe. Mais tous les graphes ne se ressemblent pas. Certains ont des flèches, d’autres non ; certains relient tout le monde à tout le monde, d’autres forment une structure en arbre. Dans cet article, tu vas apprendre à reconnaître et nommer les grandes familles de graphes — orienté, non orienté, simple, complet, pondéré, biparti, arbre — avec pour chacune sa définition exacte, sa figure, sa matrice d’adjacence et les pièges à éviter.
Au programme
- 🔵 Terminale, maths expertes — chapitre « Graphes et matrices » (BO spécial n°8 du 25 juillet 2019) : graphe, sommets, arêtes/arcs, graphe complet, sommets adjacents, degré, ordre.
- 🔵 Seconde, SNT — thème « Réseaux sociaux » (graphe, distance).
- 🟠 Prépa ECG — maths appliquées (BO spécial n°1 du 11 février 2021) : graphes, graphes probabilistes.
- 🔴 Concours et familles avancées — cliques, graphes réguliers, graphe de Petersen.
Ne pas confondre : en mathématiques, un « graphe » désigne un ensemble de sommets reliés par des liens, pas un « graphique » de logiciel de bureautique (histogramme, courbe). Si tu cherches la courbe représentative d’une fonction, va plutôt voir les fonctions en mathématiques.
Convention : sauf mention contraire, les graphes sont finis, simples et non orientés. Certains ouvrages utilisent aussi le terme « graphe simple orienté ». La symétrie d’une matrice ne suffit pas à exclure l’orientation : des arcs réciproques donnent également une matrice symétrique.
I. Graphe orienté et graphe non orienté
Un graphe orienté est un graphe dont les liens, appelés arcs, possèdent un sens : l’arc qui va du sommet A vers le sommet B n’est pas le même que celui qui va de B vers A. On le dessine avec une flèche. Dans un graphe non orienté, les liens, appelés arêtes, n’ont pas de sens : relier A et B, c’est aussi relier B et A. C’est la première distinction à maîtriser : elle change tout le vocabulaire et la matrice.
A. Le graphe orienté : des arcs à sens unique
Formellement, un graphe orienté est la donnée d’un ensemble de sommets et d’un ensemble d’arcs, chaque arc étant un couple ordonné de sommets \((u, v)\) qui se lit « de \(u\) vers \(v\) ». L’arc \((u, v)\) ne dit rien sur l’existence de l’arc \((v, u)\).
Exemple concret : un plan de ville avec des sens uniques. Si la rue va du carrefour A vers le carrefour B à sens unique, on a l’arc \((A, B)\) mais pas l’arc \((B, A)\). Le graphe est orienté.
B. Le graphe non orienté : des arêtes réciproques
Dans un graphe non orienté, une arête relie deux sommets sans privilégier de direction. On la note comme une paire \(\{u, v\}\) : il n’y a pas de différence entre « de \(u\) à \(v\) » et « de \(v\) à \(u\) ». C’est le modèle d’un réseau d’amitié (si A est ami avec B, alors B est ami avec A) ou d’un réseau routier à double sens.
C. Ce que ça change dans la matrice d’adjacence
La différence orienté / non orienté se lit directement sur la matrice d’adjacence du graphe. Le coefficient de la ligne \(i\) et de la colonne \(j\) vaut \(1\) s’il existe un lien de \(i\) vers \(j\), et \(0\) sinon.
- Graphe non orienté : la matrice est symétrique car un lien entre \(i\) et \(j\) est aussi un lien entre \(j\) et \(i\). On a \(a_{ij} = a_{ji}\). Voir la matrice symétrique.
- Graphe orienté : la matrice est quelconque (en général non symétrique). L’arc \((i, j)\) peut exister sans l’arc \((j, i)\).
Réflexe de lecture : on te donne une matrice d’adjacence et on te demande si le graphe est orienté ? Regarde si elle est symétrique. Symétrique \(\Rightarrow\) on peut la lire comme un graphe non orienté. Non symétrique \(\Rightarrow\) le graphe est forcément orienté.
II. Graphe simple, boucles et arêtes multiples
Un graphe simple est un graphe non orienté sans boucle et sans arête multiple : au plus une arête entre deux sommets donnés, et aucun sommet relié à lui-même. C’est le cadre le plus courant au lycée. Dès qu’on autorise plusieurs liens entre deux mêmes sommets ou un sommet relié à lui-même, le graphe n’est plus simple : on parle de multigraphe.
- Une boucle est une arête (ou un arc) qui relie un sommet à lui-même.
- Des arêtes multiples (ou arcs multiples) relient deux fois les mêmes sommets.
Erreur fréquente : confondre « graphe simple » et « graphe non orienté ». Un graphe peut être non orienté sans être simple (s’il a des boucles). « Simple » est une condition supplémentaire : pas de boucle, pas d’arête multiple.
Toutes les familles de graphes sur une seule fiche
Définitions, figures et formes de matrice d’adjacence : l’essentiel du chapitre « Types de graphes » condensé en 2 pages PDF, prêtes à réviser.
📄 Télécharger la fiche PDFGratuit — idéal pour les révisions de dernière minute.
III. Graphe complet et nombre d’arêtes
Un graphe complet à \(n\) sommets, noté \(K_n\), est un graphe simple où chaque paire de sommets est reliée par une arête. Autrement dit, tout le monde est relié à tout le monde. C’est le graphe « le plus dense » possible pour un nombre de sommets donné.
Combien a-t-il d’arêtes ? Il faut compter le nombre de paires de sommets, c’est-à-dire le nombre de façons de choisir 2 sommets parmi \(n\). C’est un problème de combinaisons :
Exemple : un tournoi où 5 joueurs se rencontrent tous une fois. Le graphe des rencontres est \(K_5\), et le nombre de matchs vaut \(\displaystyle\frac{5 \times 4}{2} = 10\).
Attention à la version orientée : si le graphe est orienté complet, chaque paire donne deux arcs (\(i \to j\) et \(j \to i\)). Le nombre d’arcs vaut alors \(n(n-1)\), soit le double.
IV. Graphe pondéré et graphe probabiliste
Un graphe pondéré est un graphe dont chaque lien porte un nombre, appelé poids. Ce poids peut représenter une distance, un temps de trajet, un coût, une probabilité. C’est le modèle derrière un GPS : les sommets sont des carrefours, les arcs sont des routes, et les poids sont les durées de parcours.
Un cas particulier important au lycée est le graphe probabiliste : c’est un graphe orienté et pondéré où les poids des arcs sont des probabilités, et où la somme des poids des arcs issus d’un même sommet vaut \(1\). Ces graphes servent à modéliser les évolutions d’un système entre plusieurs états, et débouchent sur les chaînes de Markov, que tu étudieras avec la matrice de transition.
Définition — Graphe probabiliste
Un graphe probabiliste est un graphe orienté et pondéré, à au plus un arc entre deux sommets, dont tous les poids sont des réels positifs et tels que, pour chaque sommet, la somme des poids des arcs sortants vaut \(1\).
V. Graphe biparti
Un graphe biparti est un graphe dont on peut répartir les sommets en deux groupes de telle sorte que chaque arête relie un sommet d’un groupe à un sommet de l’autre groupe — jamais deux sommets du même groupe. On l’utilise pour modéliser des relations entre deux populations différentes : élèves et options choisies, candidats et postes, acheteurs et produits.
Comment reconnaître un graphe biparti : essaie de colorier les sommets avec deux couleurs seulement, de sorte que deux sommets reliés n’aient jamais la même couleur. Si tu y arrives, le graphe est biparti. Si la propagation des couleurs, de proche en proche, impose deux couleurs à un même sommet, un cycle impair apparaît : le graphe n’est pas biparti.
VI. Arbres, forêts et arborescences
Un arbre est un graphe non orienté, connexe (d’un seul tenant) et sans cycle. C’est la structure d’une arborescence de dossiers ou du plan hiérarchique d’une entreprise. Une propriété fondamentale le caractérise : un arbre à \(n\) sommets possède exactement \(n- 1\) arêtes.
Une forêt est un graphe sans cycle mais pas forcément connexe : c’est une réunion de plusieurs arbres. Pour les graphes orientés, on parle d’arborescence : un arbre avec une racine, où tous les arcs s’éloignent de la racine. La notion de connexité, centrale ici, est détaillée dans le cours sur le graphe connexe.
Piège : « graphe sans cycle » ne suffit pas à définir un arbre. Deux arêtes disjointes forment un graphe sans cycle, mais il n’est pas connexe : c’est une forêt, pas un arbre. Les deux conditions (connexe et sans cycle) sont nécessaires.
VII. Graphes planaires et coloration
Un graphe planaire est un graphe que l’on peut dessiner dans le plan sans croisement d’arêtes en dehors de leurs extrémités communes. Le plan du métro, une carte de régions ou un circuit imprimé posent ce genre de question. Attention : un graphe peut être planaire même si son premier dessin fait apparaître des croisements — il suffit qu’il existe un dessin sans croisement.
La coloration d’un graphe consiste à attribuer une couleur à chaque sommet de façon que deux sommets reliés par une arête aient des couleurs différentes. Le plus petit nombre de couleurs nécessaire est le nombre chromatique. C’est l’outil mathématique derrière les problèmes d’emploi du temps (deux cours en conflit = sommets reliés = couleurs différentes = créneaux différents).
Application : colorier une carte géographique de sorte que deux régions connexes partageant un segment de frontière n’aient jamais la même couleur revient à colorier un graphe planaire. Un célèbre résultat affirme que quatre couleurs suffisent toujours.
VIII. 🔴 Familles avancées (prépa et concours)
Ces familles dépassent le programme de terminale mais reviennent en prépa et aux concours. Les connaître de nom te fera gagner du temps face à un sujet.
- Clique : un sous-ensemble de sommets tous reliés deux à deux. Une clique à \(k\) sommets est un \(K_k\) « caché » à l’intérieur du graphe.
- Graphe régulier : tous les sommets ont le même degré. Un graphe \(k\)-régulier a tous ses sommets de degré \(k\).
- Graphe d’intervalles : chaque sommet représente un intervalle de la droite réelle, et deux sommets sont reliés si leurs intervalles se chevauchent. Sens mathématique, à ne pas confondre avec un graphique de bureautique.
- Graphe de Petersen : un graphe 3-régulier à 10 sommets, exemple classique et contre-exemple fréquent (non planaire, non hamiltonien).
- Graphe acyclique / cordal / parfait : autres familles étudiées en théorie des graphes et en algorithmique.
En prépa ECG : le lien entre une famille de graphes et la forme de sa matrice d’adjacence est souvent exploité. Par exemple, un graphe \(k\)-régulier non orienté a une matrice d’adjacence dont toutes les lignes somment à \(k\). Revois les matrices et la diagonalisation pour exploiter ces structures.
IX. Tableau récapitulatif des familles
Voici la synthèse à garder sous les yeux : pour chaque famille, sa définition en une ligne et la forme de sa matrice d’adjacence.
| Famille | Définition en une phrase | Forme de la matrice d’adjacence |
|---|---|---|
| Graphe orienté | Liens à sens unique (arcs). | Quelconque (souvent non symétrique). |
| Graphe non orienté | Liens réciproques (arêtes). | \(a_{ij} = a_{ji}\) : symétrique. |
| Graphe simple | Non orienté, sans boucle ni arête multiple. | Symétrique, diagonale nulle, coefficients 0 ou 1. |
| Graphe complet \(K_n\) | Toutes les paires reliées (\(\displaystyle\frac{n(n-1)}{2}\) arêtes). | Des 1 partout sauf 0 sur la diagonale. |
| Graphe pondéré | Chaque lien porte un poids. | Coefficients = poids (pas seulement 0/1). |
| Graphe biparti | Deux groupes, arêtes d’un groupe à l’autre. | Blocs nuls sur la diagonale par blocs. |
| Arbre | Connexe, sans cycle (\(n-1\) arêtes). | Symétrique, creuse (peu de 1). |
X. Ne pas confondre : erreurs fréquentes
La plupart des points perdus sur ce chapitre viennent de confusions de vocabulaire. Voici les trois qui reviennent le plus.
Complet ≠ connexe. Un graphe complet est forcément connexe, mais la réciproque est fausse : un graphe peut être connexe (d’un seul tenant) sans que tous ses sommets soient reliés deux à deux. Un arbre à au moins trois sommets est connexe sans être complet. Les arbres à un ou deux sommets sont complets.
Connexe ≠ eulérien. Un graphe connexe n’admet pas forcément de chaîne eulérienne (qui passe une fois par chaque arête). La condition porte sur le degré des sommets, pas seulement sur la connexité. Ce point est détaillé dans le cours sur le graphe connexe.
Simple ≠ non orienté. « Non orienté » dit seulement que les liens n’ont pas de sens. « Simple » ajoute deux conditions : aucune boucle, aucune arête multiple. Un graphe non orienté avec une boucle n’est pas simple.
XI. Exercices corrigés
Entraîne-toi sur ces cinq exercices classés par difficulté. Prends le temps de chercher avant d’ouvrir la correction.
Exercice 1 — Reconnaître le type ★
On considère le réseau d’amitié de quatre élèves : Alice est amie avec Bob et Chloé, Bob est ami avec Chloé, Dimitri n’est ami avec personne. Ce graphe est-il orienté ou non orienté ? Combien d’arêtes possède-t-il ? Est-il connexe ?
Voir la correction de l’exercice 1
L’amitié est une relation réciproque (si Alice est amie avec Bob, Bob est ami avec Alice) : le graphe est non orienté.
Les arêtes sont : Alice–Bob, Alice–Chloé, Bob–Chloé. Il y a donc 3 arêtes.
Dimitri n’est relié à aucun autre sommet : il est isolé. On ne peut pas le rejoindre depuis Alice. Le graphe n’est pas connexe.
Exercice 2 — Compter les arêtes d’un graphe complet ★
Dans un tournoi, 8 équipes se rencontrent toutes une fois. Combien de matchs seront joués ? Même question si le tournoi comptait des matchs aller-retour (chaque paire se rencontre deux fois, une fois chez chacune).
Voir la correction de l’exercice 2
Le graphe des rencontres est le graphe complet \(K_8\) (non orienté, chaque paire reliée une fois).
\(\text{nombre de matchs} = \displaystyle\frac{8 \times 7}{2} = 28\)Pour l’aller-retour, le graphe devient orienté complet : chaque paire donne deux arcs.
\(8 \times 7 = 56\)Il y aurait 28 matchs en simple et 56 matchs en aller-retour.
Exercice 3 — Tester si un graphe est biparti ★★
Un graphe a pour sommets \(1, 2, 3, 4, 5\) et pour arêtes : 1–2, 2–3, 3–4, 4–5, 5–1. Ce graphe (un cycle de longueur 5) est-il biparti ? Justifie.
Voir la correction de l’exercice 3
On essaie de colorier avec deux couleurs, en alternant le long du cycle.
Sommet 1 = bleu, sommet 2 = rouge, sommet 3 = bleu, sommet 4 = rouge, sommet 5 = bleu.
Mais l’arête 5–1 relie deux sommets bleus : la coloration échoue. Comme le cycle est de longueur impaire (5 arêtes), aucune bicoloration n’est possible.
Le graphe n’est pas biparti. Règle à retenir : un graphe est biparti si et seulement s’il ne contient aucun cycle de longueur impaire.
📄 L’essentiel du cours en 2 pages PDF
Exercice 4 — Matrice d’un graphe orienté ★★
Un graphe orienté a pour sommets \(A, B, C\) et pour arcs : \((A, B)\), \((B, C)\), \((C, A)\), \((A, C)\). Écris sa matrice d’adjacence (lignes et colonnes dans l’ordre A, B, C). Est-elle symétrique ? Qu’en déduis-tu ?
Voir la correction de l’exercice 4
Le coefficient en ligne \(i\), colonne \(j\) vaut \(1\) s’il existe un arc de \(i\) vers \(j\).
\(A = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}\)On vérifie : par exemple \(a_{AC} = 1\) (arc \(A \to C\)) et \(a_{CA} = 1\) aussi (arc \(C \to A\)). En revanche \(a_{AB} = 1\) et \(a_{BA} = 0\).
La matrice n’est pas symétrique, ce qui confirme que le graphe est orienté.
Exercice 5 — Propriété d’un arbre ★★★
Un réseau informatique relie 12 ordinateurs. On veut qu’il soit connexe (tout ordinateur peut communiquer avec tout autre) tout en utilisant le minimum de câbles. Combien de câbles faut-il au minimum ? Quelle structure de graphe obtient-on alors ?
Voir la correction de l’exercice 5
Un graphe connexe à \(n\) sommets a besoin d’au moins \(n- 1\) arêtes. Avec moins, il serait en plusieurs morceaux (non connexe).
\(n- 1 = 12- 1 = 11\)Le minimum est donc de 11 câbles. Avec exactement \(n-1\) arêtes et la connexité, le graphe est sans cycle : on obtient un arbre.
À rédiger : « Un graphe connexe à 12 sommets possède au moins 11 arêtes ; ce minimum est atteint par un arbre, graphe connexe et sans cycle. »
XII. Questions fréquentes
Quels sont les différents types de graphes ?
Les grandes familles sont : le graphe orienté (liens à sens unique, les arcs) et non orienté (les arêtes), le graphe simple (sans boucle ni arête multiple), le graphe complet (toutes les paires reliées), le graphe pondéré (liens avec un poids), le graphe biparti (deux groupes de sommets) et l’arbre (connexe et sans cycle). Chaque famille a une forme de matrice d’adjacence caractéristique.
Comment construire un graphe à partir d’un énoncé ?
Repère d’abord les objets à représenter : ce sont les sommets (villes, personnes, états…). Identifie ensuite les relations entre ces objets : ce sont les liens. Demande-toi si la relation a un sens : « va vers » donne un arc (graphe orienté), « est relié à » donne une arête (graphe non orienté). Ajoute enfin les poids si la relation porte une valeur (distance, probabilité).
Quelle est la différence entre une arête et un arc ?
Une arête relie deux sommets sans direction : elle appartient à un graphe non orienté et se note comme une paire. Un arc relie deux sommets avec une direction : il appartient à un graphe orienté et se note comme un couple ordonné. L’arc de A vers B est différent de l’arc de B vers A ; l’arête entre A et B est unique.
Un graphe complet est-il toujours connexe ?
Oui : dans un graphe complet, tous les sommets sont reliés deux à deux, donc on peut aller de n’importe quel sommet à n’importe quel autre. Mais la réciproque est fausse : un graphe connexe n’est pas forcément complet. Un arbre à au moins trois sommets, par exemple, est connexe sans être complet. Complet est une condition bien plus forte que connexe.
Pourquoi un arbre à n sommets a-t-il toujours n − 1 arêtes ?
Parce qu’un arbre est connexe (il faut au moins \(n-1\) arêtes pour relier \(n\) sommets) et sans cycle (ajouter une arête de plus créerait un cycle). Ces deux contraintes se rencontrent exactement à \(n-1\) arêtes : c’est le nombre minimal pour être connexe, et le nombre maximal pour rester sans cycle.
XIII. Pour aller plus loin
Tu sais maintenant reconnaître et nommer les grandes familles de graphes. Pour prolonger ce chapitre et préparer la suite :
- 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
- Arbre de Probabilité (Seconde) : Méthode et Exercices
- Combinatoire et Dénombrement : Cours Complet, Vocabulaire et Formules
