Théorie des graphes

# Théorie des graphes ## Introduction La théorie des graphes est une branche des mathématiques discrètes qui trouve des applications dans de nombreux domaines : informatique, réseaux, logistique, biologie, sciences sociales. Au Cameroun, ce chapitre est essentiel pour les séries C et E, car il développe des compétences en modélisation et en algorithmique. Un graphe est un objet mathématique composé de sommets reliés par des arêtes, permettant de représenter des relations binaires entre éléments d'un ensemble. L'objectif de ce chapitre est de maîtriser les concepts fondamentaux, les propriétés structurelles et les algorithmes de parcours et d'optimisation qui en découlent. ## I. Rappels et définitions : graphes et sous-graphes, chaînes/chemins et cycles, graphes connexes ### I.1. Graphes et sous-graphes **Définition (graphe non orienté)** : Un graphe non orienté $G$ est un couple $G = (S, A)$ où $S$ est un ensemble fini non vide de sommets et $A$ est un ensemble de paires non ordonnées de sommets distincts appelées arêtes. On note $S = \{s_1, s_2, \ldots, s_n\}$ et $A \subseteq \{\{u, v\} \mid u, v \in S, u \neq v\}$. **Définition (graphe orienté)** : Un graphe orienté $G = (S, \overrightarrow{A})$ est un couple où $\overrightarrow{A}$ est un ensemble de couples ordonnés $(u, v)$ de sommets distincts appelés arcs. L'arc $(u, v)$ va du sommet $u$ (origine) vers le sommet $v$ (extrémité). **Définition (ordre et taille)** : L'ordre d'un graphe $G = (S, A)$ est le nombre de sommets $|S|$. La taille est le nombre d'arêtes $|A|$. **Définition (degré d'un sommet)** : Le degré d'un sommet $s$, noté $d(s)$, est le nombre d'arêtes incidentes à $s$. Dans un graphe orienté, on distingue le degré entrant $d^-(s)$ (nombre d'arcs arrivant en $s$) et le degré sortant $d^+(s)$ (nombre d'arcs partant de $s$). **Propriété (lemme des poignées de main)** : Pour tout graphe non orienté $G = (S, A)$, on a : $$\sum_{s \in S} d(s) = 2|A|$$ **Définition (sous-graphe)** : Un graphe $H = (S', A')$ est un sous-graphe de $G = (S, A)$ si $S' \subseteq S$, $A' \subseteq A$ et toutes les arêtes de $A'$ ont leurs extrémités dans $S'$. On note $H \subseteq G$. **Définition (sous-graphe induit)** : Soit $S' \subseteq S$. Le sous-graphe induit par $S'$, noté $G[S']$, est le graphe $(S', A')$ où $A' = \{\{u, v\} \in A \mid u, v \in S'\}$. Il contient toutes les arêtes de $G$ dont les deux extrémités sont dans $S'$. > **À retenir** : Un graphe $G = (S, A)$ est défini par un ensemble de sommets $S$ et un ensemble d'arêtes $A$. Un sous-graphe $H = (S', A')$ vérifie $S' \subseteq S$ et $A' \subseteq A$. Le sous-graphe induit $G[S']$ contient toutes les arêtes de $G$ reliant les sommets de $S'$. **Exemple** : Soit $G = (S, A)$ avec $S = \{a, b, c, d\}$ et $A = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$. Le graphe $H = (\{a, b, c\}, \{\{a,b\}, \{b,c\}\})$ est un sous-graphe de $G$. Le sous-graphe induit $G[\{a, b, c\}]$ est $(\{a, b, c\}, \{\{a,b\}, \{a,c\}, \{b,c\}\})$. ```onbuch-svg <svg width="400" height="200" xmlns="http://www.w3.org/2000/svg"> <circle cx="50" cy="100" r="20" fill="lightblue" stroke="black" stroke-width="2"/> <text x="45" y="105" font-size="14">a</text> <circle cx="150" cy="50" r="20" fill="lightblue" stroke="black" stroke-width="2"/> <text x="145" y="55" font-size="14">b</text> <circle cx="150" cy="150" r="20" fill="lightblue" stroke="black" stroke-width="2"/> <text x="145" y="155" font-size="14">c</text> <circle cx="280" cy="100" r="20" fill="lightgreen" stroke="black" stroke-width="2"/> <text x="275" y="105" font-size="14">d</text> <line x1="50" y1="100" x2="150" y2="50" stroke="black" stroke-width="2"/> <line x1="50" y1="100" x2="150" y2="150" stroke="black" stroke-width="2"/> <line x1="150" y1="50" x2="150" y2="150" stroke="black" stroke-width="2"/> <line x1="150" y1="150" x2="280" y2="100" stroke="black" stroke-width="2"/> <text x="60" y="20" font-size="16" font-weight="bold">Graphe G</text> </svg> ``` ### I.2. Chaînes, chemins et cycles **Définition (chaîne)** : Une chaîne de longueur $k$ dans un graphe non orienté $G = (S, A)$ est une suite de sommets $s_0, s_1, \ldots, s_k$ telle que pour tout $i \in \{0, 1, \ldots, k-1\}$, $\{s_i, s_{i+1}\} \in A$. La longueur de la chaîne est le nombre d'arêtes parcourues, soit $k$. **Définition (chemin)** : Dans un graphe orienté, un chemin de longueur $k$ est une suite de sommets $s_0, s_1, \ldots, s_k$ telle que pour tout $i$, $(s_i, s_{i+1}) \in \overrightarrow{A}$. La longueur est le nombre d'arcs. **Définition (chaîne simple et cycle)** : Une chaîne est simple si tous ses sommets sont distincts (sauf éventuellement le premier et le dernier). Un cycle est une chaîne simple de longueur $k \geq 3$ dont le premier et le dernier sommet coïncident : $s_0 = s_k$. **Définition (cycle dans un graphe orienté)** : Un cycle orienté est un chemin $s_0, s_1, \ldots, s_k$ avec $s_0 = s_k$, $k \geq 1$, et tous les sommets $s_0, s_1, \ldots, s_{k-1}$ distincts. > **À retenir** : Une chaîne de longueur $k$ relie $k+1$ sommets par $k$ arêtes. Un cycle est une chaîne fermée simple de longueur $k \geq 3$ (non orienté) ou $k \geq 1$ (orienté). La longueur d'une chaîne ou d'un chemin est le nombre d'arêtes (ou d'arcs) qui le composent. **Exemple** : Dans le graphe $G$ précédent, la suite $a, b, c, d$ est une chaîne simple de longueur 3. La suite $a, b, c, a$ est un cycle de longueur 3. ### I.3. Graphes connexes **Définition (graphe connexe)** : Un graphe non orienté $G = (S, A)$ est connexe si pour toute paire de sommets $u, v \in S$, il existe une chaîne reliant $u$ à $v$. **Définition (composante connexe)** : Une composante connexe de $G$ est un sous-graphe induit maximal connexe. Le nombre de composantes connexes de $G$ est noté $c(G)$. **Propriété** : Un graphe $G$ est connexe si et seulement si $c(G) = 1$. **Définition (graphe fortement connexe)** : Un graphe orienté est fortement connexe si pour toute paire de sommets $u, v$, il existe un chemin de $u$ vers $v$ et un chemin de $v$ vers $u$. > **À retenir** : Un graphe non orienté est connexe si tout couple de sommets peut être relié par une chaîne. Les composantes connexes sont les sous-graphes induits maximaux connexes. Un graphe est connexe si et seulement s'il possède exactement une composante connexe. **Exemple** : Le graphe $G$ de l'exemple précédent est connexe car on peut relier n'importe quelle paire de sommets. Le graphe $H = (\{a, b, c, d\}, \{\{a,b\}, \{c,d\}\})$ n'est pas connexe : il possède deux composantes connexes, $\{a, b\}$ et $\{c, d\}$. ## II. Arbres et arbres couvrants, graphes et sous-graphes valués ### II.1. Arbres **Définition (arbre)** : Un arbre est un graphe non orienté connexe et acyclique (sans cycle). **Propriétés caractéristiques d'un arbre** : Soit $G = (S, A)$ un graphe d'ordre $n = |S|$. Les propositions suivantes sont équivalentes : 1. $G$ est un arbre. 2. $G$ est connexe et $|A| = n - 1$. 3. $G$ est acyclique et $|A| = n - 1$. 4. $G$ est connexe et chaque arête est un pont (son retrait déconnecte le graphe). 5. Pour toute paire de sommets $u, v$, il existe une unique chaîne simple les reliant. **Définition (feuille)** : Dans un arbre, une feuille est un sommet de degré 1. **Propriété** : Tout arbre d'ordre $n \geq 2$ possède au moins deux feuilles. > **À retenir** : Un arbre est un graphe connexe acyclique. Pour un graphe d'ordre $n$, être un arbre équivaut à être connexe avec $n-1$ arêtes, ou acyclique avec $n-1$ arêtes. Entre deux sommets d'un arbre, il existe une unique chaîne simple. **Exemple** : Le graphe $T = (\{a, b, c, d, e\}, \{\{a,b\}, \{b,c\}, \{c,d\}, \{c,e\}\})$ est un arbre d'ordre 5 avec 4 arêtes. Les feuilles sont $a$, $d$ et $e$. ```onbuch-svg <svg width="400" height="200" xmlns="http://www.w3.org/2000/svg"> <circle cx="50" cy="100" r="20" fill="lightyellow" stroke="black" stroke-width="2"/> <text x="45" y="105" font-size="14">a</text> <circle cx="150" cy="100" r="20" fill="lightyellow" stroke="black" stroke-width="2"/> <text x="145" y="105" font-size="14">b</text> <circle cx="250" cy="100" r="20" fill="lightyellow" stroke="black" stroke-width="2"/> <text x="245" y="105" font-size="14">c</text> <circle cx="350" cy="50" r="20" fill="lightyellow" stroke="black" stroke-width="2"/> <text x="345" y="55" font-size="14">d</text> <circle cx="350" cy="150" r="20" fill="lightyellow" stroke="black" stroke-width="2"/> <text x="345" y="155" font-size="14">e</text> <line x1="50" y1="100" x2="150" y2="100" stroke="black" stroke-width="2"/> <line x1="150" y1="100" x2="250" y2="100" stroke="black" stroke-width="2"/> <line x1="250" y1="100" x2="350" y2="50" stroke="black" stroke-width="2"/> <line x1="250" y1="100" x2="350" y2="150" stroke="black" stroke-width="2"/> <text x="150" y="30" font-size="16" font-weight="bold">Arbre T</text> </svg> ``` ### II.2. Arbres couvrants **Définition (arbre couvrant)** : Un arbre couvrant d'un graphe $G = (S, A)$ est un sous-graphe $T = (S, A')$ tel que $T$ est un arbre. Autrement dit, $T$ contient tous les sommets de $G$ et un sous-ensemble d'arêtes formant un arbre. **Théorème fondamental** : Un graphe $G$ est connexe si et seulement s'il contient un arbre couvrant. **Démonstration** : - ($\Leftarrow$) Si $G$ contient un arbre couvrant $T$, alors $T$ est connexe et $T \subseteq G$. Pour toute paire de sommets $u, v$, il existe une chaîne dans $T$ les reliant, donc cette chaîne existe aussi dans $G$. Ainsi, $G$ est connexe. - ($\Rightarrow$) Supposons $G$ connexe. Si $G$ est acyclique, alors $G$ est lui-même un arbre couvrant. Sinon, $G$ contient un cycle. Retirons une arête de ce cycle : le graphe reste connexe (car l'arête retirée appartenait à un cycle, donc tout chemin l'utilisant peut être détourné). On répète ce processus jusqu'à obtenir un graphe connexe acyclique, c'est-à-dire un arbre couvrant. Le processus se termine car le nombre d'arêtes est fini. > **À retenir** : Un graphe est connexe si et seulement s'il possède un arbre couvrant. Un arbre couvrant de $G = (S, A)$ est un sous-graphe $(S, A')$ avec $A' \subseteq A$ qui est un arbre. Tout graphe connexe d'ordre $n$ possède un arbre couvrant avec exactement $n-1$ arêtes. **Exemple** : Le graphe $G$ de la section I possède plusieurs arbres couvrants. L'un d'eux est $T = (\{a, b, c, d\}, \{\{a,b\}, \{a,c\}, \{c,d\}\})$. ### II.3. Graphes et sous-graphes valués (pondérés) **Définition (graphe valué)** : Un graphe valué (ou pondéré) est un graphe $G = (S, A)$ muni d'une fonction de poids $w : A \rightarrow \mathbb{R}_+$ qui associe à chaque arête (ou arc) un nombre réel positif appelé poids. **Définition (poids d'un sous-graphe)** : Le poids d'un sous-graphe $H = (S', A')$ de $G$ est la somme des poids de ses arêtes : $$w(H) = \sum_{e \in A'} w(e)$$ **Définition (poids d'une chaîne)** : Le poids d'une chaîne $C = s_0, s_1, \ldots, s_k$ est : $$w(C) = \sum_{i=0}^{k-1} w(\{s_i, s_{i+1}\})$$ > **À retenir** : Un graphe valué associe un poids $w(e) \geq 0$ à chaque arête. Le poids d'un sous-graphe est la somme des poids de ses arêtes. Le poids d'une chaîne est la somme des poids des arêtes qui la composent. **Exemple** : Considérons le graphe valué suivant avec $S = \{A, B, C, D\}$ et les arêtes pondérées : $w(\{A,B\}) = 4$, $w(\{A,C\}) = 2$, $w(\{B,C\}) = 1$, $w(\{B,D\}) = 5$, $w(\{C,D\}) = 3$. Le poids de la chaîne $A, C, B, D$ est $2 + 1 + 5 = 8$. ```onbuch-svg <svg width="500" height="250" xmlns="http://www.w3.org/2000/svg"> <circle cx="80" cy="125" r="25" fill="lightcoral" stroke="black" stroke-width="2"/> <text x="70" y="130" font-size="16">A</text> <circle cx="250" cy="50" r="25" fill="lightcoral" stroke="black" stroke-width="2"/> <text x="240" y="55" font-size="16">B</text> <circle cx="250" cy="200" r="25" fill="lightcoral" stroke="black" stroke-width="2"/> <text x="240" y="205" font-size="16">C</text> <circle cx="420" cy="125" r="25" fill="lightcoral" stroke="black" stroke-width="2"/> <text x="410" y="130" font-size="16">D</text> <line x1="80" y1="125" x2="250" y2="50" stroke="black" stroke-width="2"/> <text x="150" y="80" font-size="14" fill="red">4</text> <line x1="80" y1="125" x2="250" y2="200" stroke="black" stroke-width="2"/> <text x="150" y="175" font-size="14" fill="red">2</text> <line x1="250" y1="50" x2="250" y2="200" stroke="black" stroke-width="2"/> <text x="260" y="130" font-size="14" fill="red">1</text> <line x1="250" y1="50" x2="420" y2="125" stroke="black" stroke-width="2"/> <text x="340" y="80" font-size="14" fill="red">5</text> <line x1="250" y1="200" x2="420" y2="125" stroke="black" stroke-width="2"/> <text x="340" y="175" font-size="14" fill="red">3</text> <text x="180" y="20" font-size="16" font-weight="bold">Graphe valué G</text> </svg> ``` ## III. Algorithmes : BFS, Kruskal, Prim, Dijkstra ### III.1. Parcours en largeur (BFS - Breadth First Search) **Principe** : Le parcours en largeur explore un graphe niveau par niveau à partir d'un sommet source. On visite d'abord tous les voisins du sommet de départ, puis les voisins des voisins, etc. **Algorithme BFS** : 1. Initialiser une file $F$ vide et un tableau $visité$ à faux pour tous les sommets. 2. Marquer le sommet source $s$ comme visité et l'enfiler dans $F$. 3. Tant que $F$ n'est pas vide : - Défiler le sommet $u$ de $F$. - Pour chaque voisin $v$ de $u$ non visité : - Marquer $v$ comme visité. - Enfiler $v$ dans $F$. - Enregistrer $u$ comme prédécesseur de $v$. **Propriété** : Le BFS permet de déterminer la distance (nombre minimal d'arêtes) entre le sommet source et tous les autres sommets du graphe. Il produit un arbre couvrant appelé arbre BFS. **Complexité** : $O(|S| + |A|)$ pour un graphe représenté par listes d'adjacence. > **À retenir** : Le parcours en largeur (BFS) explore un graphe niveau par niveau à partir d'une source. Il utilise une file et a une complexité $O(|S| + |A|)$. Il permet de calculer les distances minimales en nombre d'arêtes et de construire un arbre couvrant. **Exemple** : Appliquons BFS au graphe valué précédent (en ignorant les poids) avec source $A$. - Étape 1 : File = [A], visités = {A}. - Étape 2 : Défiler A. Voisins de A : B, C. On les marque visités, file = [B, C]. - Étape 3 : Défiler B. Voisins de B : A (déjà visité), C (déjà visité), D. On marque D visité, file = [C, D]. - Étape 4 : Défiler C. Voisins de C : A, B, D (tous visités). File = [D]. - Étape 5 : Défiler D. Voisins de D : B, C (tous visités). File = []. L'arbre BFS est : $A$ racine, enfants $B$ et $C$, puis $D$ enfant de $B$. Les distances depuis $A$ sont : $d(A) = 0$, $d(B) = 1$, $d(C) = 1$, $d(D) = 2$. ### III.2. Algorithme de Kruskal (arbre couvrant de poids minimum) **Problème** : Étant donné un graphe connexe valué $G = (S, A, w)$, trouver un arbre couvrant $T$ tel que $w(T)$ soit minimal. **Algorithme de Kruskal** : 1. Trier toutes les arêtes de $G$ par poids croissant. 2. Initialiser $T = (S, \emptyset)$ (aucune arête). 3. Pour chaque arête $e$ dans l'ordre croissant des poids : - Si l'ajout de $e$ à $T$ ne crée pas de cycle, alors ajouter $e$ à $T$. - Sinon, ignorer $e$. 4. Terminer lorsque $T$ contient $|S| - 1$ arêtes. **Détection de cycle** : On utilise une structure de données union-find (ou ensembles disjoints) pour vérifier si deux sommets sont déjà dans la même composante connexe de $T$. **Complexité** : $O(|A| \log |A|)$ (dominé par le tri des arêtes). > **À retenir** : L'algorithme de Kruskal construit un arbre couvrant de poids minimum en triant les arêtes par poids croissant et en les ajoutant si elles ne créent pas de cycle. Complexité : $O(|A| \log |A|)$. **Exemple** : Appliquons Kruskal au graphe valué précédent. Arêtes triées par poids : $\{B,C\}$ (1), $\{A,C\}$ (2), $\{C,D\}$ (3), $\{A,B\}$ (4), $\{B,D\}$ (5). - Étape 1 : Ajouter $\{B,C\}$. $T = \{\{B,C\}\}$. - Étape 2 : Ajouter $\{A,C\}$. $T = \{\{B,C\}, \{A,C\}\}$. - Étape 3 : Ajouter $\{C,D\}$. $T = \{\{B,C\}, \{A,C\}, \{C,D\}\}$. $T$ a $4 - 1 = 3$ arêtes, on s'arrête. L'arbre couvrant de poids minimum est $T = \{\{B,C\}, \{A,C\}, \{C,D\}\}$ avec poids total $1 + 2 + 3 = 6$. ### III.3. Algorithme de Prim (arbre couvrant de poids minimum) **Principe** : L'algorithme de Prim construit l'arbre couvrant de poids minimum en partant d'un sommet arbitraire et en ajoutant à chaque étape l'arête de poids minimal reliant un sommet déjà dans l'arbre à un sommet extérieur. **Algorithme de Prim** : 1. Choisir un sommet de départ $s$ arbitraire. Initialiser $T = (\{s\}, \emptyset)$. 2. Tant que $T$ ne contient pas tous les sommets : - Parmi toutes les arêtes ayant une extrémité dans $T$ et l'autre hors de $T$, choisir celle de poids minimal. - Ajouter cette arête et le nouveau sommet à $T$. **Implémentation efficace** : Utiliser une file de priorité (tas) pour maintenir les arêtes candidates par poids minimal. **Complexité** : $O(|A| \log |S|)$ avec une file de priorité. > **À retenir** : L'algorithme de Prim construit un arbre couvrant de poids minimum en partant d'un sommet et en ajoutant à chaque étape l'arête de poids minimal reliant l'arbre courant à un sommet extérieur. Complexité : $O(|A| \log |S|)$. **Exemple** : Appliquons Prim au même graphe, en partant de $A$. - Étape 1 : $T = \{A\}$. Arêtes candidates : $\{A,B\}$ (4), $\{A,C\}$ (2). On choisit $\{A,C\}$ (poids 2). $T = \{A, C\}$. - Étape 2 : Arêtes candidates : $\{A,B\}$ (4), $\{B,C\}$ (1), $\{C,D\}$ (3). On choisit $\{B,C\}$ (poids 1). $T = \{A, C, B\}$. - Étape 3 : Arêtes candidates : $\{A,B\}$ (4, déjà dans T), $\{B,D\}$ (5), $\{C,D\}$ (3). On choisit $\{C,D\}$ (poids 3). $T = \{A, C, B, D\}$. L'arbre obtenu est $T = \{\{A,C\}, \{B,C\}, \{C,D\}\}$ avec poids total $2 + 1 + 3 = 6$. C'est le même arbre que Kruskal (l'arbre couvrant de poids minimum n'est pas nécessairement unique, mais ici il l'est). ### III.4. Algorithme de Dijkstra (plus court chemin) **Problème** : Étant donné un graphe valué $G = (S, A, w)$ avec $w(e) \geq 0$, trouver le plus court chemin (poids minimal) entre un sommet source $s$ et tous les autres sommets. **Algorithme de Dijkstra** : 1. Initialiser $dist[s] = 0$ et $dist[v] = +\infty$ pour tout $v \neq s$. 2. Initialiser un ensemble $Q$ contenant tous les sommets. 3. Tant que $Q$ n'est pas vide : - Choisir $u \in Q$ avec $dist[u]$ minimal. - Retirer $u$ de $Q$. - Pour chaque voisin $v$ de $u$ encore dans $Q$ : - Si $dist[u] + w(\{u,v\}) < dist[v]$, alors mettre à jour $dist[v] = dist[u] + w(\{u,v\})$ et enregistrer $u$ comme prédécesseur de $v$. **Condition de validité** : Tous les poids doivent être positifs ou nuls. **Complexité** : $O(|S|^2)$ avec une implémentation naïve, $O(|A| \log |S|)$ avec une file de priorité. > **À retenir** : L'algorithme de Dijkstra calcule les plus courts chemins depuis une source dans un graphe valué à poids positifs ou nuls. Il maintient pour chaque sommet la distance minimale provisoire et met à jour les distances des voisins. Complexité : $O(|S|^2)$ en version naïve. **Exemple** : Appliquons Dijkstra au graphe valué précédent avec source $A$. - Initialisation : $dist[A] = 0$, $dist[B] = dist[C] = dist[D] = +\infty$. $Q = \{A, B, C, D\}$. - Itération 1 : Choisir $A$ ($dist = 0$). Retirer $A$ de $Q$. Voisins de $A$ : $B$ ($0 + 4 = 4 < +\infty$, donc $dist[B] = 4$), $C$ ($0 + 2 = 2 < +\infty$, donc $dist[C] = 2$). - Itération 2 : Choisir $C$ ($dist = 2$, le plus petit). Retirer $C$. Voisins de $C$ : $B$ ($2 + 1 = 3 < 4$, donc $dist[B] = 3$), $D$ ($2 + 3 = 5 < +\infty$, donc $dist[D] = 5$). - Itération 3 : Choisir $B$ ($dist = 3$). Retirer $B$. Voisins de $B$ : $D$ ($3 + 5 = 8 > 5$, pas de mise à jour). - Itération 4 : Choisir $D$ ($dist = 5$). Retirer $D$. Plus de voisins dans $Q$. Résultats : $dist[A] = 0$, $dist[B] = 3$, $dist[C] = 2$, $dist[D] = 5$. Le plus court chemin de $A$ à $D$ est $A \rightarrow C \rightarrow D$ avec poids $2 + 3 = 5$. Le chemin de $A$ à $B$ est $A \rightarrow C \rightarrow B$ avec poids $2 + 1 = 3$. **Tableau récapitulatif des distances** : | Sommet | Distance | Prédécesseur | |--------|----------|--------------| | A | 0 | — | | B | 3 | C | | C | 2 | A | | D | 5 | C | ## Conclusion La théorie des graphes constitue un outil puissant de modélisation et de résolution de problèmes combinatoires. Ce chapitre a permis d'établir les fondements : définitions des graphes et sous-graphes, chaînes, chemins, cycles, connexité, arbres et arbres couvrants, ainsi que les graphes valués. Les quatre algorithmes étudiés — BFS, Kruskal, Prim et Dijkstra — répondent à des problématiques fondamentales : exploration systématique d'un graphe, construction d'un arbre couvrant de poids minimum et recherche de plus courts chemins. Ces outils sont directement mobilisables dans des situations concrètes : optimisation de réseaux de transport, planification de circuits électriques, routage dans les réseaux informatiques, etc. Pour le Baccalauréat camerounais, la maîtrise de ces concepts et algorithmes, tant sur le plan théorique que pratique, est essentielle. Il est recommandé de s'entraîner à appliquer chaque algorithme pas à pas sur des exemples variés et de savoir justifier les propriétés fondamentales, notamment le théorème de caractérisation des graphes connexes par l'existence d'un arbre couvrant.