Lycée · Terminale · Maths expertes (option Tle)
Graphes — vocabulaire et propriétés
Sommets, arêtes, chemins, cycles et connexité : les fondamentaux de la théorie des graphes (programme de Maths expertes Tle)
À propos de cette page
Ce cours de maths expertes (option tle) en terminale sur « Graphes — vocabulaire et propriétés » suit le programme officiel de maths expertes (option tle) de terminale. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : Définition d'un graphe non orienté, Degré d'un sommet et lemme des poignées de mains, Graphes orientés (digraphes), Chaînes, chemins et cycles. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de terminale à réussir en maths expertes (option tle).
1
Définition d'un graphe non orienté
Un graphe non orienté $G = (V, E)$ est constitué de :
- un ensemble fini non vide $V$ de sommets (vertices) ;
- un ensemble $E$ d'arêtes (edges), chaque arête étant une paire $\{u, v\}$ de sommets ($u \ne v$).
Définition. L'ordre d'un graphe est le nombre de ses sommets, noté $|V|$ ou $n$. Sa taille est le nombre de ses arêtes, noté $|E|$ ou $m$.
Exemple. Soit $G$ avec $V = \{A, B, C, D\}$ et $E = \{\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}\}$. Ce graphe a pour ordre 4 et pour taille 4. Le sommet $A$ est relié à $B$ et à $C$.
Un graphe simple ne comporte ni boucle (arête reliant un sommet à lui-même) ni arêtes multiples (deux arêtes reliant les mêmes sommets). Sauf mention contraire, on travaille avec des graphes simples.
Attention ! Une arête $\{u,v\}$ est identique à $\{v,u\}$ dans un graphe non orienté. Les deux notations désignent la même arête.
Schéma linéaire A – B – C – D illustrant le graphe non orienté de l'exemple.
2
Degré d'un sommet et lemme des poignées de mains
Définition. Le degré d'un sommet $v$, noté $d(v)$ ou $\deg(v)$, est le nombre d'arêtes incidentes à $v$ (c'est-à-dire le nombre de voisins de $v$ dans un graphe simple).
Dans l'exemple précédent : $d(A)=2$, $d(B)=2$, $d(C)=3$, $d(D)=1$.
Théorème (lemme des poignées de mains). Pour tout graphe $G=(V,E)$ : $$\sum_{v \in V} d(v) = 2|E|$$
Démonstration. Chaque arête $\{u,v\}$ contribue exactement 1 au degré de $u$ et 1 au degré de $v$, soit 2 au total. En sommant sur toutes les arêtes, on obtient $2m$.
Corollaire. Dans tout graphe, le nombre de sommets de degré impair est pair. (La somme des degrés est paire, donc les contributions impaires doivent se compenser en nombre pair.)
Exemple. Pour le graphe précédent : $d(A)+d(B)+d(C)+d(D) = 2+2+3+1 = 8 = 2 \times 4$. Seul $D$ (degré 1, impair) et $C$ (degré 3, impair) ont un degré impair : c'est bien un nombre pair (2) de sommets.
| Notion | Définition |
|---|---|
| Sommet isolé | Sommet de degré 0 |
| Feuille / pendant | Sommet de degré 1 |
| Graphe $k$-régulier | Tout sommet est de degré $k$ |
3
Graphes orientés (digraphes)
Définition. Un graphe orienté (ou digraphe) $G = (V, A)$ est constitué d'un ensemble de sommets $V$ et d'un ensemble d'arcs $A \subseteq V \times V$. Un arc $(u, v)$ va de $u$ vers $v$ : $u$ est l'extrémité initiale, $v$ l'extrémité terminale.
Exemple. Un réseau routier à sens unique, un ordonnancement de tâches ou un réseau social (abonnements) sont naturellement représentés par des graphes orientés.
Dans un graphe orienté, on distingue :
- le demi-degré extérieur $d^+(v)$ : nombre d'arcs sortant de $v$ ;
- le demi-degré intérieur $d^-(v)$ : nombre d'arcs arrivant à $v$.
Propriété. $\displaystyle\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = |A|$
Attention ! Dans un graphe orienté, $(u, v)$ et $(v, u)$ sont deux arcs distincts. Un graphe non orienté peut être vu comme un graphe orienté où chaque arête $\{u,v\}$ est remplacée par les deux arcs $(u,v)$ et $(v,u)$.
4
Chaînes, chemins et cycles
Définitions.
• Une chaîne (dans un graphe non orienté) est une suite finie de sommets $v_0, v_1, \ldots, v_k$ telle que $\{v_{i}, v_{i+1\}} \in E$ pour tout $i$. La longueur est le nombre d'arêtes $k$.
• Une chaîne est simple si elle n'emprunte aucune arête deux fois.
• Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet.
• Un cycle est une chaîne simple avec $v_0 = v_k$ (et au moins une arête).
• Une chaîne (dans un graphe non orienté) est une suite finie de sommets $v_0, v_1, \ldots, v_k$ telle que $\{v_{i}, v_{i+1\}} \in E$ pour tout $i$. La longueur est le nombre d'arêtes $k$.
• Une chaîne est simple si elle n'emprunte aucune arête deux fois.
• Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet.
• Un cycle est une chaîne simple avec $v_0 = v_k$ (et au moins une arête).
Dans un graphe orienté. On parle de chemin (suite d'arcs cohérents avec l'orientation) et de circuit (chemin fermé).
Exemple. Dans le graphe $V=\{1,2,3,4\}$, $E=\{\{1,2\},\{2,3\},\{3,4\},\{1,4\},\{2,4\}\}$ :
• $1 - 2 - 3 - 4$ est une chaîne élémentaire de longueur 3.
• $1 - 2 - 4 - 1$ est un cycle de longueur 3.
• $1 - 2 - 4 - 3 - 2$ est une chaîne non élémentaire (2 répété).
• $1 - 2 - 3 - 4$ est une chaîne élémentaire de longueur 3.
• $1 - 2 - 4 - 1$ est un cycle de longueur 3.
• $1 - 2 - 4 - 3 - 2$ est une chaîne non élémentaire (2 répété).
Astuce. Pour montrer qu'une chaîne est élémentaire, il suffit de vérifier que chaque sommet n'apparaît qu'une fois dans la liste (sauf éventuellement le premier et le dernier pour un cycle).
Visualisation du cycle 1 – 2 – 4 – 1 de longueur 3.
5
Connexité d'un graphe
Définition. Un graphe non orienté $G$ est connexe si, pour tout couple de sommets $(u, v)$, il existe une chaîne reliant $u$ à $v$.
Les composantes connexes de $G$ sont les sous-graphes connexes maximaux de $G$.
Les composantes connexes de $G$ sont les sous-graphes connexes maximaux de $G$.
Un graphe connexe à $n$ sommets a au moins $n-1$ arêtes.
Exemple. Le graphe $V=\{A,B,C,D,E\}$, $E=\{\{A,B\},\{B,C\},\{D,E\}\}$ est non connexe : il y a deux composantes connexes $\{A,B,C\}$ et $\{D,E\}$.
Connexité dans un graphe orienté. Un graphe orienté est fortement connexe si pour tout couple $(u,v)$ il existe un chemin de $u$ vers $v$ ET un chemin de $v$ vers $u$. Il est faiblement connexe si le graphe non orienté sous-jacent est connexe.
Méthode. Pour tester la connexité d'un graphe dessiné : choisir un sommet quelconque et vérifier qu'on peut atteindre tous les autres en suivant les arêtes. Si un sommet reste inaccessible, le graphe n'est pas connexe.
Attention ! Un arbre (graphe connexe sans cycle) à $n$ sommets a exactement $n-1$ arêtes. Si on retire une arête, il devient non connexe.
6
Graphes particuliers
| Nom | Définition | Notations |
|---|---|---|
| Graphe complet | Tout couple de sommets est relié par une arête | $K_n$ — a $\frac{n(n-1)}{2}$ arêtes |
| Graphe biparti | $V$ se partitionne en deux ensembles $A$, $B$ ; toutes les arêtes ont une extrémité dans $A$ et l'autre dans $B$ | $K_{p,q}$ (complet biparti) |
| Arbre | Graphe connexe sans cycle | $n$ sommets → $n-1$ arêtes |
| Graphe eulérien | Admet un cycle passant par toutes les arêtes exactement une fois | $\Leftrightarrow$ connexe et tous les degrés pairs |
| Graphe hamiltonien | Admet un cycle passant par tous les sommets exactement une fois | (pas de critère simple) |
Théorème d'Euler. Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Exemple historique. Le problème des 7 ponts de Königsberg (Euler, 1736) demandait de traverser chaque pont exactement une fois. La réponse est non car les 4 sommets ont des degrés impairs : le graphe n'est pas eulérien.
7
Représentations d'un graphe
Un graphe peut être représenté de plusieurs façons équivalentes :
- Dessin : cercles pour les sommets, traits pour les arêtes. Intuitif mais peut être difficile pour les grands graphes.
- Liste d'adjacence : pour chaque sommet, la liste de ses voisins. Économique en mémoire si le graphe est creux.
- Matrice d'adjacence : matrice carrée $n \times n$ où $a_{ij} = 1$ si $\{i,j\} \in E$, 0 sinon. Pratique pour les calculs (voir chapitre suivant).
Exemple. Pour $G$, $V=\{1,2,3\}$, $E=\{\{1,2\},\{2,3\}\}$ :
Liste : $1 \to [2]$, $2 \to [1,3]$, $3 \to [2]$.
Matrice : $\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$.
Liste : $1 \to [2]$, $2 \to [1,3]$, $3 \to [2]$.
Matrice : $\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$.
Astuce. La matrice d'adjacence d'un graphe non orienté est symétrique : $a_{ij} = a_{ji}$. La diagonale est nulle (pas de boucle dans un graphe simple).
En bref
- Un graphe $G=(V,E)$ est un ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté).
- Le degré $d(v)$ compte les arêtes incidentes à $v$ ; la somme des degrés vaut $2|E|$ (lemme des poignées de mains).
- Le nombre de sommets de degré impair est toujours pair.
- Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet ; un cycle est une chaîne fermée.
- Un graphe est connexe si tout couple de sommets est relié par une chaîne.
- $K_n$ (complet) a $\frac{n(n-1)}{2}$ arêtes ; un arbre à $n$ sommets a exactement $n-1$ arêtes.
- Un graphe connexe est eulérien $\Leftrightarrow$ tous ses sommets ont un degré pair.
Bloqué sur ce chapitre ?
Cours particuliers de maths expertes (option tle) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs