Rédigé et vérifié par un professeur diplômé de l’École Polytechnique. Découvrir le professeur
Imagine un réseau de villes reliées par des routes. Peut-on aller de n’importe quelle ville à n’importe quelle autre ? Si oui, le graphe des routes est connexe : il est « d’un seul tenant ». Cette idée intuitive est au cœur du chapitre « graphes et matrices » des maths expertes, et elle revient partout : GPS, réseaux sociaux, pages web. Encore faut-il savoir la démontrer rigoureusement — et éviter le piège classique qui envoie tant d’élèves dans le mur.
Définition — Graphe connexe
Un graphe non orienté est connexe lorsque, pour toute paire de sommets, il existe une chaîne reliant l’un à l’autre. Autrement dit : depuis n’importe quel sommet, on peut atteindre tous les autres en se déplaçant d’arête en arête.
Dans cet article, tu vas trouver la définition exacte (celle que beaucoup de fiches ratent), les quatre méthodes pour montrer qu’un graphe est connexe, les notions de distance et de diamètre, l’extension aux graphes orientés, le théorème d’Euler, et des exercices corrigés pas à pas — du niveau Terminale jusqu’à la prépa ECG.
📘 Au programme
- 🔵 Seconde (SNT) — Réseaux sociaux : distance, diamètre, rayon, centre.
- 🔵 Terminale (maths expertes) — Chaîne, longueur, graphe connexe (BO spécial n°8 du 25 juillet 2019).
- 🟠 Prépa ECG1 — Critère matriciel de connexité \(I + A + \dots + A^{n-1}\) (BO spécial n°1 du 11 février 2021).
I. Chaînes, chemins et cycles : le vocabulaire de base
Avant de parler de connexité, il faut savoir décrire un déplacement dans un graphe. Tout repose sur un mot : la chaîne.
Définition — Chaîne et longueur
Dans un graphe non orienté, une chaîne est une suite de sommets consécutifs reliés deux à deux par une arête. La longueur d’une chaîne est le nombre d’arêtes qu’elle emprunte.
Par exemple, la chaîne \(A- B- D- C\) passe par 4 sommets et emprunte 3 arêtes : sa longueur vaut \(3\). On distingue ensuite deux cas particuliers importants pour la rédaction.
- Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet.
- Une chaîne est simple si elle n’emprunte pas deux fois la même arête.
Définition — Cycle
Dans ce cours, un cycle est une chaîne fermée sans répétition d’arête. Un cycle élémentaire ne répète en outre aucun sommet, sauf le premier qui est aussi le dernier. Le vocabulaire peut varier selon les manuels : précise la convention utilisée.
Chaîne, cycle, chemin : ne pas mélanger. En français, on réserve le mot chaîne aux graphes non orientés et le mot chemin aux graphes orientés (on suit alors le sens des flèches). Un cycle est une chaîne qui boucle. Ce vocabulaire est partagé dans tout le cours de théorie des graphes.
Ce vocabulaire posé, on peut enfin définir précisément ce que signifie « être en un seul morceau ».
II. Qu’est-ce qu’un graphe connexe ?
Un graphe est connexe lorsqu’il existe toujours un chemin pour aller d’un sommet à un autre. Formellement : pour toute paire de sommets, il existe une chaîne qui les relie. Un graphe qui n’est pas connexe se décompose en plusieurs blocs isolés les uns des autres, appelés composantes connexes.
La définition semble simple, mais c’est précisément là que se cache l’erreur la plus répandue sur le web — et dans les copies.
Erreur classique : « connexe = aucun sommet isolé ». C’est faux. Un graphe peut n’avoir aucun sommet isolé et ne pas être connexe. Prends quatre sommets \(A, B, C, D\) avec seulement les deux arêtes \(A-B\) et \(C-D\) : aucun sommet n’est isolé (chacun a un voisin), pourtant il est impossible d’aller de \(A\) à \(C\). Le graphe n’est pas connexe. La connexité se définit par les chaînes entre toutes les paires, jamais par l’absence de sommet isolé.
Définition — Composante connexe
Une composante connexe d’un graphe est un « morceau » maximal connexe : c’est un sous-ensemble de sommets tous reliés entre eux par des chaînes, et qu’on ne peut pas agrandir. Un graphe est connexe si et seulement s’il possède une seule composante connexe.
Ainsi, le graphe du piège précédent a deux composantes connexes : \(\{A, B\}\) et \(\{C, D\}\). Reste à savoir comment, concrètement, décider si un graphe donné est connexe.
Toute la méthode « graphe connexe » en 2 pages PDF
Définitions exactes, les 4 méthodes de preuve, le piège du sommet non isolé et le théorème d’Euler — une fiche claire à garder sous les yeux.
📄 Télécharger la fiche gratuiteIdéale pour réviser avant un contrôle ou un DS.
III. Comment savoir si un graphe est connexe ?
Pour montrer qu’un graphe est connexe, on prouve qu’un chemin existe entre toutes les paires de sommets ; pour montrer qu’il ne l’est pas, on exhibe deux sommets qu’aucune chaîne ne relie. Voici quatre méthodes, de la plus simple (lycée) à la plus avancée (prépa).
A. Sur un petit graphe : la méthode du sommet de référence
Pas besoin de vérifier toutes les paires une à une. Il suffit de choisir un sommet de référence, disons \(A\), et de montrer que chaque autre sommet peut être relié à \(A\) par une chaîne. Si c’est le cas, alors deux sommets quelconques \(X\) et \(Y\) sont reliés : il suffit d’aller de \(X\) à \(A\), puis de \(A\) à \(Y\).
Exemple : un graphe a pour sommets \(A, B, C, D\) et pour arêtes \(A-B\), \(B-C\), \(A-D\). Est-il connexe ?
On prend \(A\) comme référence :
- \(B\) est relié à \(A\) par l’arête \(A-B\) ;
- \(C\) est relié à \(A\) par la chaîne \(C-B-A\) ;
- \(D\) est relié à \(A\) par l’arête \(A-D\).
Tous les sommets atteignent \(A\) : le graphe est connexe. ✓
B. Par un parcours (largeur ou profondeur)
Pour un graphe plus gros, on lance un parcours à partir d’un sommet : on marque ce sommet, puis tous ses voisins, puis les voisins des voisins, etc. À la fin, on compare le nombre de sommets atteints au nombre total de sommets.
Le critère du parcours : si un parcours lancé depuis un seul sommet atteint tous les sommets du graphe, alors le graphe est connexe. Sinon, les sommets atteints forment une composante connexe stricte. Cette idée se programme directement avec le parcours en largeur (BFS) et en profondeur (DFS).
C. 🟠 Par la matrice d’adjacence : le critère \(I + A + \dots + A^{n-1}\) (prépa ECG1)
Au programme de première année de prépa ECG, la connexité se lit directement sur la matrice d’adjacence \(A\). Le point de départ : le coefficient en position \((i,j)\) de \(A^k\) compte le nombre de chaînes de longueur exactement \(k\) entre les sommets \(i\) et \(j\).
Propriété — Critère matriciel de connexité
Soit \(A\) la matrice d’adjacence d’un graphe à \(n\) sommets. Le graphe est connexe si et seulement si la matrice
\(B = I + A + A^2 + \dots + A^{n-1}\)
a tous ses coefficients strictement positifs.
L’idée : entre deux sommets d’un graphe connexe à \(n\) sommets, il existe toujours une chaîne élémentaire de longueur au plus \(n-1\). Additionner les puissances de \(A\) jusqu’à \(n-1\) (avec \(I\) pour la longueur \(0\)) revient donc à compter toutes les chaînes possibles entre deux sommets : si une case de \(B\) reste nulle, c’est qu’aucune chaîne ne relie les deux sommets correspondants.
✍️ Ce que le correcteur attend (prépa). En rédigeant ce critère, justifie toujours la borne \(n-1\) par l’existence d’une chaîne élémentaire. Un simple « on calcule \(B\) » sans cet argument coûte des points : c’est la justification, pas le calcul, qui est notée.
D. Prouver qu’un graphe n’est PAS connexe
C’est souvent plus rapide : il suffit d’exhiber deux sommets \(X\) et \(Y\) et de prouver qu’aucune chaîne ne les relie. Concrètement, on identifie une composante connexe qui ne contient pas tous les sommets. Dès qu’on trouve un groupe non vide, strictement plus petit que l’ensemble des sommets, « fermé » (dont aucune arête ne sort vers le reste du graphe), le graphe n’est pas connexe.
Exemple : sommets \(A, B, C, D, E\), arêtes \(A-B\), \(B-C\), \(D-E\).
Le groupe \(\{A, B, C\}\) est fermé : aucune arête ne le relie à \(D\) ni à \(E\). Il n’existe donc aucune chaîne de \(A\) vers \(D\). Le graphe a deux composantes connexes et n’est pas connexe. ∎
Ces quatre méthodes couvrent tous les exercices. Retiens la hiérarchie ci-dessous selon la taille du graphe et ton niveau.
| Situation | Méthode conseillée | Niveau |
|---|---|---|
| Petit graphe (≤ 6 sommets) | Sommet de référence | 🔵 Lycée |
| Graphe moyen ou en informatique | Parcours BFS / DFS | 🔵 Lycée / NSI |
| Matrice d’adjacence donnée | Critère \(I + A + \dots + A^{n-1}\) | 🟠 Prépa ECG1 |
| Montrer la NON-connexité | Exhiber une composante fermée | 🔵 Lycée |
IV. Distance, diamètre et rayon d’un graphe
Dans un graphe connexe, on peut toujours relier deux sommets — mais à quelle « distance » ? Ces notions, introduites dès la Seconde en SNT pour l’étude des réseaux sociaux, mesurent la compacité d’un graphe.
Définitions — Distance, diamètre, rayon, centre
- La distance entre deux sommets est la longueur de la plus courte chaîne qui les relie.
- L’excentricité d’un sommet est la plus grande distance entre ce sommet et les autres.
- Le diamètre est la plus grande distance entre deux sommets du graphe (la plus grande excentricité).
- Le rayon est la plus petite excentricité ; un sommet qui l’atteint est un centre.
Sur un réseau social modélisé par un graphe connexe, le diamètre est le plus grand nombre de liens dans un plus court chemin entre deux membres. Un chemin de longueur \(d\) possède \(d-1\) sommets intermédiaires. Entre deux composantes distinctes, on peut convenir d’une distance infinie.
Jusqu’ici, nos graphes étaient non orientés. Que devient la connexité quand les arêtes deviennent des flèches ?
V. Graphes orientés : connexité forte et connexité faible
Dans un graphe orienté, on ne circule que dans le sens des flèches. La connexité se dédouble alors en deux notions, selon qu’on respecte ou non l’orientation.
Définitions — Connexité forte et faible
- Un graphe orienté est fortement connexe si, pour toute paire de sommets \((X, Y)\), il existe un chemin orienté de \(X\) vers \(Y\) et un chemin orienté de \(Y\) vers \(X\).
- Un graphe orienté est faiblement connexe si le graphe obtenu en oubliant l’orientation des arêtes est connexe.
La connexité forte est bien plus exigeante que la connexité faible. Un simple chemin \(A \to B \to C\) est faiblement connexe (il tient d’un seul tenant) mais pas fortement connexe (impossible de revenir de \(C\) à \(A\)).
🔴 Lien avec les chaînes de Markov. Une chaîne de Markov est dite irréductible précisément lorsque son graphe de transition est fortement connexe : on peut passer de tout état à tout autre. C’est une condition clé de convergence vers la distribution invariante, au cœur des problèmes de concours.
Terminons par le théorème qui a fait naître toute la théorie des graphes.
VI. Chaînes eulériennes et les ponts de Königsberg
En 1736, Euler étudie les sept ponts de Königsberg : peut-on les traverser chacun une seule fois ? La réponse est non, même sans exiger le retour au départ. L’obstruction vient des quatre sommets de degré impair du graphe associé.
Définition — Chaîne et cycle eulériens
Une chaîne eulérienne est une chaîne qui emprunte chaque arête du graphe une et une seule fois. Si elle revient à son point de départ, c’est un cycle eulérien.
Théorème d’Euler
Un graphe connexe admet :
- un cycle eulérien si et seulement si tous ses sommets sont de degré pair ;
- une chaîne eulérienne (non fermée) si et seulement s’il a exactement deux sommets de degré impair (qui en sont alors les extrémités).
Précision : pour parcourir toutes les arêtes, les sommets incidents à une arête doivent appartenir à une même composante. Des sommets isolés ne gênent pas ce parcours ; en revanche, des arêtes réparties dans deux composantes le rendent impossible. À Königsberg, les quatre sommets impairs empêchent toute chaîne eulérienne.
Ne pas confondre eulérien et hamiltonien. Une chaîne eulérienne passe par chaque arête une fois. Une chaîne hamiltonienne passe par chaque sommet une fois. Pour l’eulérien, il existe un critère simple (degrés) ; pour l’hamiltonien, aucun critère simple n’existe — c’est un problème réputé difficile.
Toutes ces notions se ressemblent : regroupons les confusions à éviter avant de passer à la pratique.
VII. Ne pas confondre : connexe, complet, eulérien
Trois propriétés voisines, trois définitions distinctes. Le tableau suivant les sépare une bonne fois pour toutes.
| Propriété | Définition | Implication |
|---|---|---|
| Connexe | Toute paire de sommets est reliée par une chaîne | — |
| Complet | Toute paire de sommets est reliée par une arête directe | Complet \(\Longrightarrow\) connexe |
| Eulérien | Connexe + tous les degrés pairs (cycle eulérien) | Eulérien \(\Longrightarrow\) connexe |
Copie fautive — diagnostic — correction.
❌ « Le graphe a 5 arêtes donc il est connexe. »
Diagnostic : le nombre d’arêtes ne dit rien de la connexité. Les deux arêtes \(A-B\) et \(C-D\) ne forment pas un graphe connexe, et on pourrait en ajouter d’autres au sein de chaque bloc sans jamais les relier.
✅ Correction : pour conclure à la connexité, il faut exhiber une chaîne entre chaque sommet et un sommet de référence (ou vérifier qu’un parcours atteint tous les sommets).
Attention aussi à la confusion « complet \(\Longrightarrow\) connexe » prise dans le mauvais sens : un graphe connexe n’est pas forcément complet. Un simple chemin \(A-B-C\) est connexe mais loin d’être complet (il manque l’arête \(A-C\)). Pour la liste complète des familles, voir les types de graphes.
Place maintenant à l’entraînement, du calcul direct au raisonnement de type prépa.
VIII. Exercices corrigés
Exercice 1 — Lire une chaîne et sa longueur ★
Un graphe a pour sommets \(A, B, C, D, E\) et pour arêtes \(A-B\), \(B-C\), \(C-D\), \(D-E\), \(B-D\). Donne une chaîne de \(A\) à \(E\) de longueur minimale, puis sa longueur.
Voir la correction de l’exercice 1
On cherche le plus court trajet. En passant par l’arête « raccourci » \(B-D\) :
\(A- B- D- E\)Cette chaîne emprunte 3 arêtes. La chaîne \(A-B-C-D-E\) en emprunterait 4 : elle est plus longue.
La distance de \(A\) à \(E\) vaut donc 3.
Exercice 2 — Montrer qu’un graphe est connexe ★
Soit le graphe de sommets \(A, B, C, D\) et d’arêtes \(A-B\), \(B-C\), \(C-D\). Montre qu’il est connexe.
Voir la correction de l’exercice 2
On prend \(A\) comme sommet de référence et on relie chaque autre sommet à \(A\) :
- \(B\) : chaîne \(B-A\) ;
- \(C\) : chaîne \(C-B-A\) ;
- \(D\) : chaîne \(D-C-B-A\).
Tout sommet est relié à \(A\) par une chaîne. Donc deux sommets quelconques sont reliés (en passant par \(A\)) : le graphe est connexe.
Exercice 3 — Le piège du sommet non isolé ★★
Un élève affirme : « Ce graphe de sommets \(A, B, C, D\) et d’arêtes \(A-B\), \(C-D\) est connexe car aucun sommet n’est isolé. » A-t-il raison ? Justifie et donne les composantes connexes.
Voir la correction de l’exercice 3
L’élève a tort. L’absence de sommet isolé n’implique jamais la connexité.
Montrons la non-connexité : il n’existe aucune chaîne de \(A\) vers \(C\). En effet, les seules arêtes partant du bloc \(\{A, B\}\) restent à l’intérieur de \(\{A, B\}\) (seule arête \(A-B\)). Ce bloc est fermé.
Les composantes connexes sont donc \(\{A, B\}\) et \(\{C, D\}\). Le graphe a deux composantes : il n’est pas connexe.
La fiche de révision « graphe connexe »
Toutes les définitions, le théorème d’Euler et les 4 méthodes de preuve réunis sur 2 pages PDF, prêts à imprimer.
📄 Télécharger la fiche gratuiteGagne du temps à chaque révision.
Exercice 4 — Existence d’une chaîne eulérienne ★★
Un graphe connexe a les degrés suivants : \(A\) : 2, \(B\) : 3, \(C\) : 2, \(D\) : 3, \(E\) : 2. Admet-il une chaîne eulérienne ? Un cycle eulérien ?
Voir la correction de l’exercice 4
On compte les sommets de degré impair : \(B\) (3) et \(D\) (3). Il y en a exactement deux.
Le graphe étant connexe, le théorème d’Euler s’applique :
- deux sommets de degré impair \(\Longrightarrow\) il existe une chaîne eulérienne, d’extrémités \(B\) et \(D\) ;
- tous les degrés ne sont pas pairs \(\Longrightarrow\) pas de cycle eulérien.
Conclusion : chaîne eulérienne oui (de \(B\) à \(D\)), cycle eulérien non.
Exercice 5 — Connexité forte d’un graphe orienté ★★★
Un graphe orienté a pour arcs \(A \to B\), \(B \to C\), \(C \to A\) et \(C \to D\). Est-il fortement connexe ? Faiblement connexe ?
Voir la correction de l’exercice 5
Connexité forte : on cherche un chemin orienté dans les deux sens entre toutes les paires. Or \(D\) n’a aucun arc sortant : impossible de quitter \(D\). Il n’existe pas de chemin de \(D\) vers \(A\). Le graphe n’est pas fortement connexe.
Connexité faible : on oublie l’orientation. Les arêtes deviennent \(A-B\), \(B-C\), \(C-A\), \(C-D\). Depuis \(A\) : \(B\) (direct), \(C\) (direct), \(D\) (via \(A-C-D\)). Tous reliés : le graphe est faiblement connexe.
Bilan : faiblement connexe mais pas fortement connexe — le sommet puits \(D\) casse la connexité forte.
Exercice 6 — 🟠 Critère matriciel (prépa ECG) ★★★
On considère un graphe à 3 sommets de matrice d’adjacence \(A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\). En utilisant le critère \(I + A + A^2\), montre que le graphe est connexe.
Voir la correction de l’exercice 6
Le graphe a \(n = 3\) sommets : on forme \(B = I + A + A^2\) (puissances jusqu’à \(n-1 = 2\)).
Calcul de \(A^2\) :
\(A^2 = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}\)D’où :
\(B=I+A+A^2\)
\(A^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix}\)
\(B=\begin{pmatrix}2&1&1\\1&3&1\\1&1&2\end{pmatrix}\)
Tous les coefficients de \(B\) sont strictement positifs. D’après le critère, le graphe est connexe.
Justification à écrire sur la copie : entre deux sommets d’un graphe connexe à \(n\) sommets, il existe une chaîne élémentaire de longueur \(\leq n-1\) ; sommer \(I, A, \dots, A^{n-1}\) compte toutes ces chaînes, et une case nulle signalerait deux sommets non reliés.
IX. Questions fréquentes
Comment savoir si un graphe est connexe ?
On choisit un sommet de référence et on vérifie que chaque autre sommet peut l’atteindre par une chaîne (ou qu’un parcours lancé depuis un seul sommet atteint tous les autres). Si c’est le cas, le graphe est connexe. Sur une matrice d’adjacence, on vérifie que \(I + A + \dots + A^{n-1}\) n’a aucun coefficient nul.
Qu’est-ce que ça veut dire connexe ?
« Connexe » signifie « d’un seul tenant » : le graphe est en un seul morceau. Concrètement, pour toute paire de sommets, il existe un chemin d’arêtes qui les relie. On peut donc circuler de n’importe quel sommet vers n’importe quel autre sans jamais rester bloqué.
Qu’est-ce qu’un graphe non connexe ?
Un graphe est non connexe lorsqu’il existe au moins deux sommets qu’aucune chaîne ne relie. Il se décompose alors en plusieurs blocs séparés appelés composantes connexes. Attention : un graphe sans sommet isolé peut quand même être non connexe.
Quelle est la différence entre un graphe connexe et un graphe complet ?
Dans un graphe complet, toute paire de sommets est reliée par une arête directe. Dans un graphe connexe, elle est reliée par une chaîne, éventuellement longue. Tout graphe complet est connexe, mais un graphe connexe (comme un simple chemin \(A-B-C\)) n’est généralement pas complet.
Qu’est-ce qu’un graphe fortement connexe ?
C’est une notion propre aux graphes orientés : il est fortement connexe si, pour toute paire de sommets, on peut aller de l’un à l’autre et revenir en suivant le sens des flèches. C’est plus exigeant que la connexité faible (qui ignore l’orientation) et c’est la condition d’irréductibilité d’une chaîne de Markov.
Un graphe connexe peut-il ne pas avoir de cycle ?
Oui. Un graphe connexe sans cycle porte même un nom : c’est un arbre. Un arbre à \(n\) sommets possède exactement \(n-1\) arêtes — le minimum pour rester connexe. Ajouter une arête créerait un cycle, en retirer une le déconnecterait.
X. Pour aller plus loin
Tu maîtrises maintenant la connexité, ses méthodes de preuve et ses extensions. Pour continuer :
- 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
- Suite Arithmético-Géométrique (Terminale) : Formule
- Arbre de Probabilité (Seconde) : Méthode et Exercices
Pour aller plus loin côté outils, le critère matriciel s’appuie sur le raisonnement par récurrence et sur les propriétés de la matrice d’adjacence, qui est symétrique pour un graphe non orienté.
Tu veux progresser plus vite et gagner en rigueur de rédaction ? Découvre les cours particuliers Excellence Maths pour la prépa.
