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
Cours de Maths expertes. Même notion dans une autre matière : Graphes : représentation et parcours — spé NSI
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 à $5$ sommets et $6$ arêtes : chaque trait relie deux sommets adjacents.
- 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é sortant $d^+(v)$ et degré entrant $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
S'entraîner
Notions clés — Maths expertes
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$.
Un graphe connexe est un graphe où :
Réponse :
Tout sommet peut en atteindre tout autre par un chemin
Un graphe est connexe si, pour toute paire de sommets, il existe au moins un chemin les reliant.
Le parcours en largeur (BFS) utilise :
Réponse :
Une file (FIFO)
BFS explore couche par couche en s'appuyant sur une file (First In, First Out).
Un cycle dans un graphe est :
Réponse :
Un chemin fermé sans répétition de sommet (sauf départ = arrivée)
Un cycle est un chemin qui revient à son point de départ sans repasser par un sommet intermédiaire.
Le parcours en profondeur (DFS) permet surtout de :
Réponse :
Détecter les cycles d'un graphe
DFS explore en profondeur : retomber sur un sommet déjà visité révèle un cycle. C'est BFS qui donne le plus court chemin.
Une suite de degrés $3, 3, 3, 2, 1$ est-elle possible pour un graphe ?
Réponse :
Possible a priori, car la somme $12$ est paire
La somme $3 + 3 + 3 + 2 + 1 = 12$ est paire : la condition nécessaire est satisfaite. Avec $\dfrac{12}{2} = 6$ arêtes, un tel graphe est réalisable.
Supprimer une arête dans un arbre :
Réponse :
Déconnecte le graphe en deux composantes
Un arbre est connexe avec exactement $n - 1$ arêtes ; retirer une arête le coupe en exactement deux composantes.