Notion de graphes (partie 2/2)

## Objectifs et prérequis À la fin de ce chapitre, l’élève pourra : - définir précisément les notions de sommet, d’arête, de degré, de graphe orienté/non orienté, de graphe valué, de arbre, de graphe connexe, de chemin, de cycle et de sous‑graphe ; - distinguer les différents types de graphes (simple, complet, bipartite, multigraphe) et en donner des exemples concrets ; - déterminer le degré d’un sommet et appliquer le lemme de la main poignée ; - expliquer les propriétés de connexité, d’arbre et de graphe eulérien/hamiltonien ; - mettre en œuvre les algorithmes de parcours en profondeur (DFS) et en largeur (BFS) pour explorer un graphe ; - appliquer l’algorithme de Dijkstra pour déterminer le plus court chemin dans un graphe valué à poids non négatifs ; - construire un arbre couvrant de poids minimal avec les algorithmes de Prim ou de Kruskal ; - résoudre des problèmes d’optimisation liés aux réseaux (transport, télécommunications, ordonnancement) en modélisant la situation par un graphe adapté. **Prérequis** : notions de ensembles, de fonctions, de matrices (représentation d’un graphe par matrice d’adjacence ou matrice d’incidence), de raisonnement par récurrence et de base de la logique propositionnelle. ## Introduction Les graphes constituent un outil modélisant des relations binaires entre des objets. En Terminale, ils apparaissent dans divers contextes : réseaux de communication, circuits électroniques, ordonnancement de tâches, analyse de données sociales, etc. Le programme officiel MINESEC/IGE organise l’étude en trois leçons : le vocabulaire de base (Leçon 21), puis deux leçons consacrées à des propriétés fondamentales et à des algorithmes classiques (Leçons 16 et 22). Cette approche par compétences vise à ce que l’élève sache non seulement définir les concepts, mais aussi les manipuler, les démontrer et les appliquer à des situations concrètes. ## I. Quelques vocabulaires (Leçon 21) ### Définitions de base > **Définition** : Un graphe non orienté est un couple $G=(V,E)$ où $V$ est un ensemble fini de sommets (ou nœuds) et $E$ un ensemble d’arêtes non orientées, chaque arête étant un couple non ordonné $\{u,v\}$ avec $u,v\in V$. > **Définition** : Un graphe orienté (ou digraphe) est un couple $G=(V,A)$ où $A\subseteq V\times V$ est un ensemble d’arcs ordonnés $(u,v)$. Un graphe peut être **valué** lorsqu’on associe à chaque arête (ou arc) un poids réel $w(e)\in\mathbb{R}$ ; on note alors $G=(V,E,w)$. ### Types de graphes - **Graphe simple** : aucune boucle (arête reliant un sommet à lui‑même) et au plus une arête entre deux sommets donnés. - **Multigraphe** : autorise plusieurs arêtes parallèles entre le même couple de sommets. - **Graphe complet** $K_n$ : tout couple distinct de sommets est relié par une arête ; il possède $\frac{n(n-1)}{2}$ arêtes. - **Graphe bipartite** : il existe une partition $V=V_1\cup V_2$ telle que toute arête relie un sommet de $V_1$ à un sommet de $V_2$. - **Graphe arbre** : graphe connexe acyclique (voir § II). ### Degré d’un sommet > **Définition** : Dans un graphe non orienté, le degré $\deg(v)$ d’un sommet $v$ est le nombre d’arêtes incidentes à $v$. Dans un graphe orienté, on distingue le degré d’entrée $\deg^{-}(v)$ (nombre d’arcs entrant en $v$) et le degré de sortie $\deg^{+}(v)$ (nombre d’arcs sortant de $v$). **Lemme de la main poignée** : $$\sum_{v\in V}\deg(v)=2|E|.$$ *Démonstration* : chaque arête contribue exactement 2 à la somme des degrés (une pour chaque extrémité). #### Exemple 1 (simple) Considérons le graphe $G$ avec $V=\{a,b,c,d\}$ et $E=\{\{a,b\},\{b,c\},\{c,d\},\{d,a\}\}$. - $\deg(a)=2$ (arêtes $\{a,b\},\{d,a\}$) - $\deg(b)=2$ - $\deg(c)=2$ - $\deg(d)=2$ La somme des degrés vaut $8=2|E|$ puisque $|E|=4$. #### Exemple 2 (délicat) Soit $G$ un graphe simple sur $n$ sommets où chaque sommet a degré $k$ (graphe $k$-régulier). Alors $nk=2|E|$, donc $|E|=\frac{nk}{2}$. En particulier, $nk$ doit être pair ; cela impose une condition de parité sur $n$ et $k$. ## II. Quelques propriétés et algorithmes (Leçon 16) ### Connexité > **Définition** : Un graphe non orienté est **connexe** si tout couple de sommets est relié par au moins un chemin. Un graphe orienté est **fortement connexe** si, pour tout couple $(u,v)$, il existe un chemin dirigé de $u$ vers $v$ et un chemin dirigé de $v$ vers $u$. **Proposition** : Un arbre avec $n$ sommets possède exactement $n-1$ arêtes. *Démonstration* : par récurrence sur $n$. Pour $n=1$, l’arbre trivial a $0=1-1$ arête. Supposons vraie pour tout arbre de taille $n$. Prenons un arbre $T$ de $n+1$ sommets ; il possède une feuille $f$ (sommet de degré 1). En supprimant $f$ et son arête incidente, on obtient un arbre $T'$ de $n$ sommets, qui par hypothèse a $n-1$ arêtes. En rétablissant $f$, on ajoute exactement une arête, donc $T$ a $(n-1)+1=n$ arêtes. ### Parcours en profondeur (DFS) et en largeur (BFS) **Algorithme DFS** (récursif) : 1. Marquer le sommet de départ $s$ comme visité. 2. Pour chaque voisin $v$ de $s$ non encore visité, appeler DFS($v$). **Algorithme BFS** (file) : 1. Initialiser une file $F$ avec $s$ et marquer $s$ visité. 2. Tant que $F$ n’est pas vide : extraire le sommet $u$ en tête, puis pour chaque voisin $v$ de $u$ non visité, le marquer visité et l’enfiler. Ces deux procédures visitent chaque sommet et chaque arête au plus une fois ; leur complexité en temps est $O(|V|+|E|)$. #### Exemple 1 (DFS) Graphe $G$ : $V=\{1,2,3,4,5\}$, $E=\{\{1,2\},\{1,3\},\{2,4\},\{3,5\}\}$. Partant de $1$ : - Visiter $1$, puis explorer $2$ → $4$ (fin de branche), revenir à $2$, puis à $1$. - Explorer $3$ → $5$. Ordre de visite : $1,2,4,3,5$. #### Exemple 2 (BFS) Même graphe, départ en $1$ : - File initialement $[1]$. - Extraire $1$, ajouter $2,3$ → file $[2,3]$. - Extraire $2$, ajouter $4$ → file $[3,4]$. - Extraire $3$, ajouter $5$ → file $[4,5]$. - Extraire $4$ (aucun nouveau voisin), puis $5$. Ordre de visite : $1,2,3,4,5$. ### Propriétés eulériennes et hamiltoniennes (rappel) - Un graphe connexe possède un **circuit eulérien** (parcours utilisant chaque arête exactement une fois) si et seulement si tout sommet a un degré pair. - Un graphe possède un **chemin hamiltonien** (visite chaque sommet exactement une fois) si il existe un ordre des sommets tel que chaque paire consécutive soit reliée par une arête ; aucune caractérisation simple connue, mais des conditions suffisantes (ex. théorème de Dirac : si $\deg(v)\ge n/2$ pour tout $v$, alors le graphe est hamiltonien). ## III. Quelques propriétés et algorithmes (Leçon 22) ### Plus court chemin – algorithme de Dijkstra > **Théorème de Dijkstra** : Dans un graphe valué $G=(V,E,w)$ avec des poids non négatifs, l’algorithme de Dijkstra partant d’un sommet source $s$ calcule les distances minimales $d(v)=\min\{\text{poids d’un chemin }s\leadsto v\}$ pour tout $v\in V$. **Preuve esquissée** : on maintient un ensemble $S$ de sommets dont la distance minimale est connue. À chaque étape, on ajoute le sommet $u\notin S$ ayant la plus petite valeur temporaire $dist(u)$. Comme les poids sont non négatifs, aucun chemin passant par un sommet hors de $S$ ne peut offrir une distance plus petite que $dist(u)$ ; donc $dist(u)$ est définitive. #### Exemple 1 (simple) Graphe valué : - Sommets $V=\{A,B,C,D\}$ - Arêtes et poids : $AB=2$, $AC=5$, $BC=1$, $BD=2$, $CD=3$. Source $A$. Étape 0 : $dist(A)=0$, autres $=\infty$. Étape 1 : choisir $B$ (dist=2). Mettre à jour : $dist(C)=\min(5,2+1)=3$, $dist(D)=\min(\infty,2+2)=4$. Étape 2 : choisir $C$ (dist=3). Mettre à jour : $dist(D)=\min(4,3+3)=4$ (inchangé). Étape 3 : choisir $D$ (dist=4). Résultat : $d(A)=0$, $d(B)=2$, $d(C)=3$, $d(D)=4$. #### Exemple 2 (délicat) Graphe avec un sommet intermédiaire pouvant être contourné : $V=\{S,X,Y,T\}$, arêtes : $SX=4$, $SY=2$, $XT=1$, $YT=5$, $XY=2$. Source $S$. Étape 0 : $dist(S)=0$. Étape 1 : choisir $Y$ (dist=2). Mettre à jour : $dist(X)=\min(4,2+2)=4$, $dist(T)=\min(\infty,2+5)=7$. Étape 2 : choisir $X$ (dist=4). Mettre à jour : $dist(T)=\min(7,4+1)=5$. Étape 3 : choisir $T$ (dist=5). Chemin optimal $S\to Y\to X\to T$ de poids $2+2+1=5$, meilleur que $S\to X\to T$ ($4+1=5$) et $S\to Y\to T$ ($2+5=7$). ### Arbre couvrant de poids minimal – algorithmes de Prim et de Kruskal > **Définition** : Un **arbre couvrant** d’un graphe connexe valué $G=(V,E,w)$ est un sous‑graphe qui est un arbre et qui contient tous les sommets de $V$. Son poids est la somme des poids de ses arêtes. Un **arbre couvrant de poids minimal (ACPM)** est un arbre couvrant de poids le plus petit possible. **Algorithme de Prim** (glouton, démarre d’un sommet arbitraire) : 1. Initialiser $T=\{s\}$ (sommet de départ) et $A=\emptyset$. 2. Tant que $T\neq V$ : choisir l’arête de poids minimal ayant une extrémité dans $T$ et l’autre dans $V\setminus T$ ; l’ajouter à $A$ et ajouter son sommet nouveau à $T$. **Algorithme de Kruskal** (glouton, trie les arêtes) : 1. Trier toutes les arêtes par poids croissant. 2. Partir avec une forêt vide $F$. 3. Parcourir les arêtes dans l’ordre : ajouter l’arête $e$ à $F$ si elle ne crée pas de cycle (i.e. ses extrémités appartiennent à deux composantes connexes différentes de $F$). 4. Arrêter lorsque $F$ contient $n-1$ arêtes. Les deux algorithmes sont corrects (preuve par échange) et ont une complexité $O(|E|\log|V|)$ avec des structures de données appropriées (tas pour Prim, union‑find pour Kruskal). #### Exemple 1 (Prim) Graphe valué : sommets $V=\{1,2,3,4,5\}$ ; arêtes et poids : $12=1$, $13=4$, $14=3$, $23=2$, $24=5$, $25=6$, $34=1$, $35=7$, $45=2$. Départ du sommet $1$. - $T=\{1\}$ ; arêtes candidates : $12(1)$, $13(4)$, $14(3)$ → choisir $12$. - $T=\{1,2\}$ ; candidats : $13(4)$, $14(3)$, $23(2)$, $24(5)$, $25(6)$ → choisir $23$. - $T=\{1,2,3\}$ ; candidats : $13(4)$, $14(3)$, $24(5)$, $25(6)$, $34(1)$, $35(7)$ → choisir $34$. - $T=\{1,2,3,4\}$ ; candidats : $14(3)$, $24(5)$, $25(6)$, $35(7)$, $45(2)$ → choisir $45$. Arbre couvrant : $\{12,23,34,45\}$ poids total $1+2+1+2=6$. #### Exemple 2 (Kruskal) – **corrigé** Même graphe que ci‑dessus. Trier les arêtes par poids croissant : $AC=1$, $SB=2$, $BC=3$, $SA=4$, $BT=4$, $CT=5$, $AT=7$. - Ajouter $AC$ (pas de cycle). - Ajouter $SB$ (pas de cycle). - Ajouter $BC$ (pas de cycle, relie les deux composantes $\{A,C\}$ et $\{S,B\}$). - À ce stade, nous avons 3 arêtes ($n-1=4$ nécessaires). - Prochaine arête : $SA=4$. Ses extrémités $S$ et $A$ appartiennent maintenant à la même composante $\{S,B,A,C\}$ → créerait un cycle → on la rejette. - Arête suivante : $BT=4$. $B$ dans la grande composante, $T$ isolé → pas de cycle → l’ajouter. Nous avons maintenant 4 arêtes : $AC$, $SB$, $BC$, $BT$. Poids total $=1+2+3+4=10$. Vérification : aucun autre choix ne donne un poids moindre (remplacer $BT$ par $CT$ augmenterait le poids à $11$). Donc l’ACPM est $\{AC,SB,BC,BT\}$ de poids 10. ## Synthèse du chapitre - **Vocabulaire** : sommet, arête/arc, degré, graphe simple/orienté/valué, arbre, graphe connexe, bipartite, complet. - **Propriétés de connexité** : un arbre avec $n$ sommets a $n-1$ arêtes ; lemme de la main poignée $\sum\deg(v)=2|E|$. - **Algorithmes de parcours** : DFS (pile/récursion) et BFS (file) visitent chaque sommet et chaque arête en $O(|V|+|E|)$. - **Plus court chemin** : algorithme de Dijkstra (poids non négatifs) donne les distances minimales depuis une source. - **Arbre couvrant de poids minimal** : Prim (croissance d’un arbre) et Kruskal (tri des arêtes + union‑find) produisent un ACPM. - **Conditions eulériennes** : un graphe connexe possède un circuit eulérien si et seulement si tout sommet a un degré pair. - **Conditions hamiltoniennes** : aucune caractérisation simple ; théorème de Dirac donne une condition suffisante. ## Glossaire - **Sommet** : élément de l’ensemble $V$ d’un graphe. - **Arête** : lien non orienté entre deux sommets (dans un graphe non orienté). - **Arc** : lien orienté $(u,v)$ d’un graphe orienté. - **Degré** : nombre d’incidences d’un sommet (ou degré d’entrée/sortie dans un graphe orienté). - **Graphe connexe** : tout couple de sommets relié par au moins un chemin. - **Arbre** : graphe connexe sans cycle. - **Acyclique** : ne contenant aucun cycle. - **Poids** : valeur réelle associée à une arête ou à un arc (graphe valué). - **Arbre couvrant** : sous‑graphe arbre contenant tous les sommets du graphe initial. - **Algorithme de Dijkstra** : procédure gloutonne calculant les plus courts chemins depuis une source dans un graphe à poids non négatifs. - **Algorithme de Prim** : construction gloutonne d’un ACPM en ajoutant successivement l’arête de poids minimal reliant l’arbre construit au reste du graphe. - **Algorithme de Kruskal** : construction gloutonne d’un ACPM en triant les arêtes et en ajoutant celles qui ne créent pas de cycle. - **Circuit eulérien** : parcours fermé utilisant chaque arête exactement une fois. - **Chemin hamiltonien** : parcours visitant chaque sommet exactement une fois. - **Union‑find** : structure de données permettant de gérer dynamiquement des partitions disjointes (utilisée dans Kruskal). ## Exercices d'application corrigés ### Exercice 1 Soit le graphe non orienté $G$ avec $V=\{a,b,c,d,e\}$ et $E=\{\{a,b\},\{b,c\},\{c,d\},\{d,e\},\{e,a\},\{a,c\}\}$. 1. Déterminer le degré de chaque sommet. 2. Vérifier le lemme de la main poignée. 3. Dire si $G$ est eulérien. **Corrigé** 1. $\deg(a)=3$ (ab, ae, ac), $\deg(b)=2$ (ab, bc), $\deg(c)=3$ (bc, cd, ac), $\deg(d)=2$ (cd, de), $\deg(e)=2$ (de, ea). 2. Somme des degrés $=3+2+3+2+2=12$. $|E|=6$, donc $2|E|=12$ → lemme vérifié. 3. Un graphe connexe possède un circuit eulérien si et seulement si tous les degrés sont pairs. Ici, $a$ et $c$ ont degré impair (3) → $G$ n’est **pas** eulérien. ### Exercice 2 Considérons le graphe orienté $D$ avec $V=\{1,2,3,4\}$ et $A=\{(1,2),(2,3),(3,4),(4,1),(1,3)\}$. 1. Déterminer le degré d’entrée et le degré de sortie de chaque sommet. 2. $D$ est‑il fortement connexe ? Justifier. **Corrigé** 1. - Sommet 1 : sortant → (1,2),(1,3) → $\deg^{+}=2$ ; entrant → (4,1) → $\deg^{-}=1$. - Sommet 2 : sortant → (2,3) → $\deg^{+}=1$ ; entrant → (1,2) → $\deg^{-}=1$. - Sommet 3 : sortant → (3,4) → $\deg^{+}=1$ ; entrant → (2,3),(1,3) → $\deg^{-}=2$. - Sommet 4 : sortant → (4,1) → $\deg^{+}=1$ ; entrant → (3,4) → $\deg^{-}=1$. 2. Pour être fortement connexe, il faut un chemin dirigé de chaque sommet vers chaque autre. On vérifie : - De 1 on atteint 2,3,4 (1→2→3→4). - De 2 on atteint 3,4,1 (2→3→4→1). - De 3 on atteint 4,1,2 (3→4→1→2). - De 4 on atteint 1,2,3 (4→1→2→3). Tous les couples sont accessibles dans les deux sens → $D$ **est** fortement connexe. ### Exercice 3 Appliquer l’algorithme de Dijkstra au graphe valué suivant (source $S$) : $V=\{S,A,B,C,T\}$ ; arêtes et poids : $SA=4$, $SB=2$, $AC=1$, $BC=3$, $CT=5$, $BT=4$, $AT=7$. **Corrigé** Initialisation : $dist(S)=0$, autres $=\infty$. Étape 1 : choisir $B$ (dist=2). Mettre à jour : $dist(A)=\min(4,2+? )$ (pas d’arc $BA$) → reste 4 ; $dist(T)=\min(\infty,2+4)=6$. Étape 2 : choisir $A$ (dist=4). Mettre à jour : $dist(C)=\min(\infty,4+1)=5$ ; $dist(T)=\min(6,4+7)=6$ (inchangé). Étape 3 : choisir $C$ (dist=5). Mettre à jour : $dist(T)=\min(6,5+5)=6$ (inchangé). Étape 4 : choisir $T$ (dist=6). Résultat : $d(S)=0$, $d(B)=2$, $d(A)=4$, $d(C)=5$, $d(T)=6$. Chemin optimal $S\to B\to T$ de poids $2+4=6$ (égal à $S\to A\to C\to T$ : $4+1+5=10$ non optimal). ### Exercice 4 Trouver un arbre couvrant de poids minimal du graphe valué $G$ ci‑dessus (même ensemble de sommets, mêmes arêtes) en utilisant l’algorithme de Kruskal. **Corrigé** Trier les arêtes par poids croissant : $AC=1$, $SB=2$, $BC=3$, $SA=4$, $BT=4$, $CT=5$, $AT=7$. - Ajouter $AC$ (pas de cycle). - Ajouter $SB$ (pas de cycle). - Ajouter $BC$ (pas de cycle, relie les deux composantes $\{A,C\}$ et $\{S,B\}$). - À ce stade, nous avons 3 arêtes ($n-1=4$ nécessaires). - Prochaine arête : $SA=4$. Ses extrémités $S$ et $A$ appartiennent maintenant à la même composante $\{S,B,A,C\}$ → créerait un cycle → on la rejette. - Arête suivante : $BT=4$. $B$ dans la grande composante, $T$ isolé → pas de cycle → l’ajouter. Nous avons maintenant 4 arêtes : $AC$, $SB$, $BC$, $BT$. Poids total $=1+2+3+4=10$. Vérification : aucun autre choix ne donne un poids moindre (remplacer $BT$ par $CT$ augmenterait le poids à $11$). Donc l’ACPM est $\{AC,SB,BC,BT\}$ de poids 10. ### Exercice 5 Un graphe non orienté $G$ possède 7 sommets et 10 arêtes. Sachant que $G$ est connexe, déterminer le nombre de cycles indépendants (nombre de cyclomatic number) de $G$. **Corrigé** Pour un graphe connexe, le nombre de cyclomatic number $\mu = |E| - |V| + 1$. Ici $\mu = 10 - 7 + 1 = 4$. Ainsi, $G$ contient 4 cycles indépendants. ### Exercice 6 Montrer que dans tout arbre, il existe au moins deux feuilles (sommets de degré 1). **Corrigé** Soit $T$ un arbre avec $n\ge 2$ sommets. Supposons le contraire : au plus une feuille. Alors tous les autres sommets ont degré $\ge 2$. La somme des degrés serait alors $\ge 1\cdot 1 + (n-1)\cdot 2 = 2n-1$. Mais dans tout graphe, $\sum\deg(v)=2|E|$. Dans un arbre, $|E|=n-1$, donc $\sum\deg(v)=2(n-1)=2n-2$. On obtient $2n-1\le 2n-2$, contradiction. Donc il doit y avoir au moins deux feuilles. ## Erreurs fréquentes 1. **Confondre degré et degré d’entrée/sortie** : dans un graphe orienté, oublier de distinguer $\deg^{+}$ et $\deg^{-}$ conduit à de mauvais calculs de chemins ou de propriétés d’eulerianité. *Astuce* : toujours préciser si l’on travaille dans le cas orienté ou non orienté et vérifier les deux composantes séparément. 2. **Appliquer Dijkstra à des arêtes à poids négatif** : l’algorithme ne garantit plus la optimalité si un poids est négatif. *Astuce* : vérifier que tous les poids sont $\ge 0$ ; sinon utiliser l’algorithme de Bellman‑Ford. 3. **Oublier de détecter les cycles dans Kruskal** : ajouter une arête qui crée un cycle produit un sous‑graphe qui n’est plus un arbre. *Astuce* : utiliser une structure union‑find pour tester rapidement si deux sommets appartiennent déjà à la même composante. 4. **Penser qu’un graphe eulérien doit être hamiltonien** : les deux notions sont indépendantes. Un graphe peut être eulérien sans contenir de chemin hamiltonien (ex. un cycle de longueur 4). *Astuce* : retenir les caractérisations séparées (degrés pairs pour eulérien, aucune condition simple pour hamiltonien). 5. **Confondre arbre couvrant et arbre couvrant de poids minimal** : tout arbre couvrant n’est pas forcément de poids minimal. *Astuce* : après avoir construit un arbre couvrant, vérifier qu’aucune arête de poids inférieur ne puisse remplacer une arête de l’arbre sans créer de cycle. 6. **Mauvaise interprétation du lemme de la main poignée** : croire que la somme des degrés égale $|E|$ au lieu de $2|E|$. *Astuce* : rappeler que chaque arête contribue à deux sommets. --- *Fin du cours.*