Maths expertes — Graphes
Graphes : vocabulaire, représentation, parcours
Graphes orientés et non orientés, sommets, arêtes, degré, chemins, connexité, parcours
Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Un **graphe** est la façon la plus simple de modéliser des **relations** : des points (les **sommets**) reliés par des traits (les **arêtes**, ou **arcs** si elles ont un sens). Réseaux sociaux, plans de métro, pages web, molécules — tout se décrit par des graphes. Le vocabulaire est précis : le **degré** d'un sommet compte ses arêtes, un **chemin** relie deux sommets de proche en proche, un **cycle** est un chemin fermé, et un graphe est **connexe** si l'on peut aller de n'importe quel sommet à n'importe quel autre. Les **arbres** (connexes sans cycle) sont des graphes minimalistes à $n - 1$ arêtes. Enfin, deux façons d'explorer un graphe structurent toute l'algorithmique : le parcours **en largeur** (BFS, couche par couche) et le parcours **en profondeur** (DFS, le plus loin possible).
Un graphe se définit par deux ensembles : ses sommets et ses arêtes. Selon que les liaisons ont un sens ou non, on parle de graphe orienté ou non orienté.
- Un graphe $G = (S\,;A)$ est donné par un ensemble $S$ de **sommets** et un ensemble $A$ d'**arêtes** (ou d'arcs si orienté).
- **Non orienté :** les arêtes n'ont pas de sens. **Orienté :** les arcs ont un sens ($i \to j$).
- Deux sommets reliés par une arête sont dits **adjacents**.
- Le **degré** d'un sommet est le nombre d'arêtes qui lui sont incidentes.
- **Graphe complet** $K_n$ : tous les sommets reliés deux à deux, soit $\dfrac{n(n-1)}{2}$ arêtes.
Exemple
Dans un graphe représentant un réseau d'amis, chaque personne est un **sommet** et chaque amitié une **arête**. Si Alice est amie avec $3$ personnes, son sommet est de **degré** $3$.
Piège à éviter
Dans un graphe **non orienté**, une arête $\{i\,;j\}$ se compte une seule fois, pas deux. Ne double pas les arêtes en croyant distinguer « $i$ vers $j$ » et « $j$ vers $i$ ».
Compter les degrés révèle une contrainte forte : chaque arête contribue pour $2$ au total des degrés (une extrémité à chaque bout). C'est le **lemme des poignées de main**, simple mais puissant.
- **Lemme des poignées de main :** la somme des degrés de tous les sommets vaut $2 \times (\text{nombre d'arêtes})$.
- **Conséquence :** le nombre de sommets de degré impair est toujours **pair**.
- Pour un graphe orienté : degré **entrant** $d^+(v)$ et degré **sortant** $d^-(v)$.
- $\displaystyle\sum d^+(v) = \sum d^-(v) = \text{nombre d'arcs}$ (graphe orienté).
Exemple
Un graphe à $5$ sommets de degrés $2, 3, 3, 2, 4$ a une somme des degrés $2 + 3 + 3 + 2 + 4 = 14$. Le nombre d'arêtes est donc $\dfrac{14}{2} = 7$.
Piège à éviter
La somme des degrés est **toujours paire** (c'est $2$ fois le nombre d'arêtes). Une liste de degrés de somme **impaire** est donc impossible : c'est un test rapide de cohérence.
Pour circuler dans un graphe, on suit des **chemins**. Selon qu'ils se referment ou non, et selon que tous les sommets sont atteignables, on définit cycles et connexité — des notions clés pour les réseaux.
- Un **chemin** est une suite de sommets $s_1, s_2, \dots, s_k$ avec une arête entre chaque paire consécutive.
- La **longueur** d'un chemin est son nombre d'arêtes.
- Un **cycle** est un chemin fermé (départ = arrivée) qui ne repasse pas par un sommet intermédiaire.
- Un graphe est **connexe** si, pour toute paire de sommets, il existe un chemin les reliant.
- **Composantes connexes :** sous-graphes connexes maximaux ; un graphe connexe en a une seule.
Exemple
Dans le graphe $A - B - C - A$, la suite $A, B, C, A$ est un **cycle** de longueur $3$. Comme on peut joindre n'importe quel sommet à n'importe quel autre, le graphe est **connexe**.
Piège à éviter
Connexe ne veut pas dire complet : un graphe peut être connexe (tout le monde est joignable) sans que chaque sommet soit relié à **tous** les autres. Le complet $K_n$ est un cas particulier.
Un **arbre** est le graphe le plus économe pour rester connexe : aucun cycle, exactement le nombre d'arêtes minimal. Cette structure apparaît partout (hiérarchies, arborescences de fichiers).
- Un **arbre** est un graphe **connexe** et **sans cycle**.
- Un arbre à $n$ sommets a exactement $n - 1$ arêtes.
- Ajouter une arête à un arbre crée un **unique** cycle.
- Supprimer une arête d'un arbre le **déconnecte** en deux composantes.
- **Arbre couvrant** d'un graphe : sous-graphe qui est un arbre et contient **tous** les sommets.
Exemple
Un arbre à $7$ sommets possède exactement $7 - 1 = 6$ arêtes. Si on lui ajoute une $7^{\text{e}}$ arête, on crée un cycle ; si on en retire une, le graphe se coupe en deux morceaux.
Piège à éviter
« Connexe sans cycle » : les **deux** conditions sont nécessaires. Un graphe sans cycle mais non connexe est une **forêt** (réunion d'arbres), pas un arbre.
Explorer systématiquement un graphe se fait de deux manières opposées. Le parcours **en largeur** (BFS) avance par cercles concentriques ; le parcours **en profondeur** (DFS) plonge le plus loin possible avant de revenir.
- **BFS (en largeur) :** on explore tous les voisins d'un sommet avant de passer aux voisins des voisins.
- BFS utilise une **file** (FIFO) et donne le **plus court chemin** (en nombre d'arêtes) depuis la source.
- **DFS (en profondeur) :** on avance le plus loin possible, puis on revient en arrière (retour sur trace).
- DFS utilise une **pile** (LIFO) et permet notamment de **détecter les cycles**.
- **Applications :** tester la connexité, trouver les composantes connexes, calculer des distances.
Exemple
Depuis un sommet source, BFS visite d'abord tous les sommets à distance $1$, puis ceux à distance $2$, etc. : le rang de visite donne directement la distance (en arêtes) à la source — d'où son usage pour le plus court chemin non pondéré.
Piège à éviter
Seul **BFS** garantit le plus court chemin (en nombre d'arêtes) ; **DFS** ne le garantit pas. À l'inverse, DFS est l'outil naturel pour détecter les cycles. Choisis le parcours selon le but.
Quiz - Graphes : vocabulaire, représentation, parcours
10 questions
Articles utiles
Questions fréquentes
Les points clés à retenir sur Graphes : vocabulaire, représentation, parcours, extraits du quiz de révision.
Le degré d'un sommet dans un graphe non orienté est :
Réponse :
Le nombre d'arêtes incidentes à ce sommet
Le degré d'un sommet est le nombre d'arêtes qui lui sont reliées (incidentes).
La somme des degrés dans un graphe à $8$ arêtes vaut :
Réponse :
$16$
Lemme des poignées de main : somme des degrés $= 2 \times (\text{nombre d'arêtes}) = 2 \times 8 = 16$.
Un arbre à $7$ sommets a combien d'arêtes ?
Réponse :
$6$
Un arbre à $n$ sommets a exactement $n - 1$ arêtes ; pour $n = 7$, cela fait $6$.
Le graphe complet $K_5$ a combien d'arêtes ?
Réponse :
$10$
$K_n$ a $\dfrac{n(n-1)}{2}$ arêtes ; pour $n = 5$ : $\dfrac{5 \times 4}{2} = 10$.