#GraphesCopier le lien

Un graphe G = (V, E) modélise des connexions : réseaux, dépendances entre tâches, chemins. La théorie fournit un vocabulaire précis (degrés, chemins, connexité) et des algorithmes génériques qui ne dépendent que de cette structure : parcours en largeur et en profondeur, plus courts chemins, arbres couvrants, ordre topologique.

Prérequis : ensembles et relations (produit cartésien, propriétés), un peu de Python (dictionnaires, ensembles, boucles), notation O pour les complexités.

Objectifs d'apprentissage :

• Choisir une représentation (liste d'adjacence ou matrice) selon la densité du graphe et l'algorithme visé.
• Exécuter et implémenter BFS et DFS en citant leur invariant et leur complexité O(|V| + |E|).
• Prouver que BFS calcule les distances exactes dans un graphe non pondéré.
• Calculer des plus courts chemins à poids positifs avec Dijkstra et comprendre l'hypothèse de positivité.
• Construire un arbre couvrant minimal par Kruskal ou Prim et justifier la correction par la propriété de coupe.
• Produire un ordre topologique (Kahn) et détecter les cycles ; compter les marches par puissances de matrice.

#Vocabulaire et premier théorèmeCopier le lien

• Sommet, arête : V est l'ensemble des sommets (|V| = n), E l'ensemble des arêtes (|E| = m). Graphe non orienté : arêtes {u, v} ; orienté : arcs (u, v).
• Degré : nombre d'arêtes incidentes à un sommet. Noté d(v).
• Chemin, cycle : suite de sommets reliés par des arêtes, distinctes sauf le départ qui rejoint l'arrivée pour un cycle simple.
• Connexité : il existe un chemin entre toute paire de sommets ; sinon le graphe se décompose en composantes connexes.
• Densité : m proche de n² pour un graphe dense, proche de n pour un graphe creux. C'est le premier critère de choix de représentation.

Théorème (lemme des poignées de mains). Dans un graphe non orienté, la somme des degrés vaut 2·|E|.

Preuve. Chaque arête {u, v} contribue 1 au degré de u et 1 au degré de v : elle ajoute exactement 2 à la somme des degrés. Sommer sur les m arêtes donne 2m. ∎

Corollaire immédiat : le nombre de sommets de degré impair est pair, puisque la somme des degrés est paire. Appliqué à un graphe simple : deux personnes ont toujours le même nombre d'amis (sinon il faudrait n valeurs de degrés deux à deux distinctes, dans {0, ..., n−1} ; or 0 et n−1 ne peuvent pas coexister, il n'y a donc que n−1 degrés disponibles pour n sommets : le principe des tiroirs s'applique).

#ReprésentationsCopier le lien

• Liste d'adjacence : dict/dict-list de V vers ses voisins. Espace O(n + m) ; parcourir les voisins d'un sommet coûte O(d(v)) ; tester une arête donnée coûte O(n) au pire. Choix naturel pour les graphes creux.
• Matrice d'adjacence : tableau n × n, A[i][j] = 1 si arête. Espace O(n²) ; tester une arête en O(1) ; parcourir les voisins coûte O(n). Choix raisonnable pour les graphes denses ou les calculs de puissances A^k.

#Parcours BFS (liste d'adjacence)Copier le lien

L'invariant de BFS : la file contient des sommets dont les distances diffèrent d'au plus un, et un sommet entre dans la file exactement une fois, la première fois qu'on découvre sa distance définitive.

Pourquoi BFS donne les distances. Par récurrence forte sur la distance d. Le sommet source est traité avec d = 0. Supposons que tous les sommets à distance ≤ d soient traités en couches croissantes et aient tous été enfiler avant tout sommet à distance d + 1. Un sommet w à distance d + 1 possède un voisin u à distance d (par définition du plus court chemin) ; quand u est traité, w n'est pas encore visité, donc il est marqué et enfilé avec dist(w) = dist(u) + 1 = d + 1. Réciproquement, un sommet ne peut pas être découvert avec une distance plus petite que sa distance réelle : toute arête ne réduit la distance connue que d'au plus un par rapport à un prédécesseur déjà correct (inégalité triangulaire |dist(u) − dist(v)| ≤ 1 pour une arête). L'algorithme retourne donc exactement d(s, ·). ∎

#Parcours DFS (récursif et itératif)Copier le lien

#BFS vs DFS en un coup d'œilCopier le lien

• BFS parcourt le graphe par couches croissantes de distance en utilisant une file. Idéal pour trouver un plus court chemin dans un graphe non pondéré ; explore large avant d'aller loin.
• DFS suit un chemin en profondeur avec une pile ou la récursion. Utile pour détecter des cycles, produire un tri topologique ou explorer des composantes connexes ; explore loin avant de revenir.

Les deux visitent chaque sommet et chaque arête au plus une fois : complexité O(n + m) en liste d'adjacence. Seul l'ordre de visite change.

#Atelier interactif : file vs pileCopier le lien

#Plus courts chemins à poids positifs : DijkstraCopier le lien

L'invariant de Dijkstra : quand un sommet u est extrait de la file avec la plus petite distance courante, cette distance est définitive.

Preuve. Notons dist(v) la vraie distance de la source à v, et raisonnons par l'absurde au moment où u est extrait avec d(u) > dist(u). Tout chemin de la source vers u quitte l'ensemble S des sommets déjà fixés par un arc (x, y) avec x fixé et y non fixé : le préfixe jusqu'à x est exactement d(x) par hypothèse d'induction, donc d(y) ≤ d(x) + w(x, y) ≤ longueur de ce chemin = dist(u) < d(u), car les poids sont ≥ 0. Mais y est encore dans la file avec une clé d(y) < d(u) : cela contredit le choix minimal de u à l'extraction. ∎

L'hypothèse de positivité est exactement ce qui valide l'inégalité d(y) ≤ dist(u) : avec un arc négatif, l'argument s'effondre.

Trace à la main (à refaire avant de lire la sortie) : extraction de A(0), découvertes B=4 et C=2 ; extraction de C(2), découvertes D=10 et E=12 ; extraction de B(4), C reste à 2 (4+1=5 ne l'améliore pas), D passe à 9 (4+5) ; extraction de D(9), E passe à 11 (9+2) ; puis extraction des entrées périmées. Sortie attendue : {'A': 0, 'C': 2, 'B': 4, 'D': 9, 'E': 11}. Le chemin A→B→D→E (poids 11) est optimal ; le détour A→C→D (2+8) coûte 9 à D seulement après le passage par B.

#Arbres couvrants minimaux (MST)Copier le lien

Un arbre couvrant est un sous-ensemble d'arêtes qui garde le graphe connexe, sans cycle : exactement n−1 arêtes pour n sommets (retirez une arête : plus connexe ; ajoutez-en une : un cycle apparaît). Minimal signifie : poids total minimum.

Propriété de coupe (correction de Kruskal et Prim). Soit une coupe (S, V∖S) et une arête e de poids minimal traversant cette coupe. Il existe un MST contenant e.

Preuve. Soit T un MST ne contenant pas e. T ∪ {e} contient un unique cycle, qui traverse la coupe au moins deux fois : il contient une autre arête {f} traversant la coupe. Or w(f) ≥ w(e). Remplaçons f par e : T' = T − {f} + {e} est encore couvrant sans cycle, de poids w(T') = w(T) − w(f) + w(e) ≤ w(T). Comme T était minimal, w(T') = w(T) et T' est aussi un MST, contenant cette fois e. ∎

#Kruskal (Union-Find)Copier le lien

Déroulé sur l'exemple : les arêtes triées par poids sont AB(1), BC(2), AC(3), BD(4), CE(5), DE(7).

1. AB(1) : A et B dans des composantes différentes, acceptée. Composantes {A,B}, {C}, {D}, {E}.
2. BC(2) : acceptée, composante {A, B, C}.
3. AC(3) : A et C déjà connectés, rejetée (elle créerait le cycle A-B-C-A).
4. BD(4) : acceptée, composante {A,B,C,D}.
5. CE(5) : acceptée, tout est connecté : 4 arêtes = n−1, arrêt.

MST total : 1 + 2 + 4 + 5 = 12. À chaque acceptation, l'arête est la plus légère traversant la coupe « composante courante / reste du graphe » : la propriété de coupe garantit la minimalité.

Correction structurelle : union-find rejette exactement les arêtes dont les extrémités sont déjà dans la même composante, c'est-à-dire exactement celles qui créeraient un cycle. Le résultat est donc connexe et acyclique : un arbre, et la boucle s'arrête à n−1 arêtes.

#Kruskal en trois étapesCopier le lien

1. Trier les arêtes par poids croissant.
2. Parcourir la liste et ajouter une arête si elle ne crée pas de cycle (testé via union-find ou composantes connexes).
3. Arrêter lorsque l'on a sélectionné arêtes : on obtient alors un arbre couvrant minimal.

#Prim (tas binaire)Copier le lien

Prim maintient un ensemble visité S et choisit toujours l'arête minimale traversant la coupe (S, V∖S) : c'est la propriété de coupe appliquée directement, une arête après l'autre. Sur le même graphe, il construit A–B(1), B–C(2), B–D(4), C–E(5), total 12 : même poids que Kruskal, comme le théorème l'impose (le MST peut différer si des poids sont égaux, son poids non).

#Compter les arbres couvrantsCopier le lien

Savoir qu'un arbre couvrant existe est une chose ; savoir combien il en existe en est une autre. Le théorème de Kirchhoff répond à la question par un déterminant.

Laplacien d'un graphe. Soit $G$ un graphe non orienté à $n$ sommets, sans boucle. Son laplacien est la matrice $L = D - A$, où $D$ est la matrice diagonale des degrés et $A$ la matrice d'adjacence :

$L_{ij} = \begin{cases} \deg(i) & \text{si } i = j \\ -1 & \text{si } \{i,j\} \in E \\ 0 & \text{sinon} \end{cases}$

Le laplacien est symétrique, ses lignes et ses colonnes somment à $0$ (donc $L$ est singulière : le vecteur $(1,\ldots,1)$ est dans son noyau).

Théorème (Kirchhoff, ou matrice-arbre). Le nombre d'arbres couvrants de $G$ est égal à n'importe quel cofacteur de $L$ : on supprime une ligne et la colonne de même indice, et on prend le déterminant de la matrice $(n-1) \times (n-1)$ obtenue. Le résultat ne dépend pas de l'indice choisi.

Pourquoi cela fonctionne (esquisse). On écrit $L = B B^{\mathsf T}$ où $B$ est la matrice d'incidence orientée du graphe (une ligne par arête, une colonne par sommet). Le théorème de Cauchy-Binet exprime alors tout cofacteur de $L$ comme une somme de carrés de déterminants de sous-matrices de $B$ ; un déterminant non nul correspond exactement à un choix d'arêtes formant un arbre couvrant. ∎

Exemple vérifié : le réseau maillé. On appelle échelle (ou réseau maillé) à $m$ mailles le graphe obtenu en mettant $m$ carrés côte à côte : $2(m+1)$ sommets et $3m + 1$ arêtes. Pour $m = 1$ c'est le carré $C_4$ ; pour $m = 2$ c'est l'hexagone allongé.

En appliquant le théorème de Kirchhoff (et en vérifiant par énumération exhaustive), le nombre d'arbres couvrants de l'échelle à $m$ mailles est

$A_m = \frac{(2+\sqrt3)^{\,m+1} - (2-\sqrt3)^{\,m+1}}{2\sqrt3}.$

Les premières valeurs sont $A_1 = 4$, $A_2 = 15$, $A_3 = 56$, $A_4 = 209$, $A_5 = 780$.

Vérifications. Pour $m = 1$, le graphe est $C_4$ : un arbre couvrant s'obtient en retirant une des 4 arêtes du cycle, donc $A_1 = 4$ ✓. Pour $m = 2$, l'énumération exhaustive donne $15$ ✓. Pour $m = 3$, elle donne $56$ ✓.

Récurrence. La suite vérifie

$A_m = 4A_{m-1} - A_{m-2}, \qquad A_1 = 4, \ A_2 = 15,$

ce qui se vérifie immédiatement sur les valeurs : $4 \cdot 15 - 4 = 56$ ✓, $4 \cdot 56 - 15 = 209$ ✓. L'équation caractéristique $r^2 - 4r + 1 = 0$ a pour racines $2 \pm \sqrt3$, ce qui explique la forme close : $A_m$ est combinaison de $(2+\sqrt3)^m$ et $(2-\sqrt3)^m$.

Ordre de grandeur. Comme $2 + \sqrt3 \approx 3{,}732$, le nombre d'arbres couvrants croît comme $3{,}732^m$ — exponentiellement, alors que le graphe n'a que $3m+1$ arêtes. Le comptage des arbres couvrants est donc un problème intrinsèquement exponentiel : il n'existe pas d'algorithme polynomial pour les énumérer, seulement pour les compter (par le déterminant).

#Chemins et circuits eulériensCopier le lien

Un chemin eulérien est un chemin qui passe par chaque arête exactement une fois (les sommets peuvent être revisités). Un circuit eulérien est un chemin eulérien qui revient à son point de départ.

Théorème (Euler). Un graphe non orienté connexe admet un circuit eulérien si et seulement si tous ses sommets sont de degré pair. Il admet un chemin eulérien (non fermé) si et seulement s'il a exactement deux sommets de degré impair, qui sont alors les extrémités du chemin.

Idée de la preuve. Nécessité : à chaque passage par un sommet, le chemin consomme deux arêtes incidentes (une entrante, une sortante) ; les sommets intérieurs sont donc de degré pair, et seules les extrémités peuvent être impaires. Suffisance : on construit le circuit par une marche gloutonne qui ne repasse pas par une arête, puis on recolle les cycles obtenus. ∎

À ne pas confondre avec un chemin hamiltonien, qui passe par chaque sommet exactement une fois. Le critère d'Euler est une condition de degrés, vérifiable en $O(n+m)$ ; décider s'il existe un chemin hamiltonien est un problème NP-complet. C'est un exemple frappant de deux problèmes visuellement proches dont les complexités diffèrent radicalement.

Formule d'Euler pour les graphes planaires. Un graphe planaire est un graphe dessinable dans le plan sans croisement d'arêtes. Pour un tel graphe connexe à $n$ sommets, $m$ arêtes et $f$ faces (la face extérieure comprise) :

$n - m + f = 2.$

Cette formule entraîne qu'un graphe planaire simple vérifie $m \leq 3n - 6$ (car chaque face est bordée par au moins 3 arêtes, et chaque arête borde 2 faces, donc $3f \leq 2m$). On en déduit que $K_5$ n'est pas planaire : $n = 5$ et $m = 10 > 3 \cdot 5 - 6 = 9$. De même $K_{3,3}$ n'est pas planaire ($m = 9 > 3 \cdot 6 - 6 = 12$ ne suffit pas à conclure ; il faut la variante pour graphes sans triangle, $m \leq 2n - 4$, qui donne $9 > 8$).

#Tri topologique (Kahn) et détection de cyclesCopier le lien

Un ordre topologique d'un graphe orienté acyclique (DAG) est un ordre total sur les sommets tel que tout arc u → v vérifie u avant v. Il n'existe que si le graphe est sans cycle : si un ordre tel existait et qu'un cycle u₁ → u₂ → ... → u₁ fût présent, on aurait u₁ < u₂ < ... < u₁, impossible pour un ordre strict. Réciproquement, un graphe sans cycle admet toujours un sommet de degré entrant nul (sinon, en remontant les prédécesseurs, on revisiterait un sommet et fabriquerait un cycle), et Kahn construit l'ordre en éliminant itérativement ces sommets.

#Kahn en pratiqueCopier le lien

1. Mettre dans la file tous les sommets de degré entrant nul.
2. Retirer un sommet, l'ajouter à l'ordre topologique, décrémenter le degré entrant de ses successeurs.
3. Dès qu'un successeur atteint le degré 0, l'ajouter dans la file.
4. S'il reste des sommets avec un degré strictement positif en fin d'algorithme, le graphe avait un cycle.

L'argument de terminaison est le même que celui de l'existence : un DAG possède toujours un sommet de degré entrant nul disponible, donc la file se vide complètement si et seulement si le graphe est acyclique. Double usage de Kahn : ordonnancer (compilation, dépendances de paquets) et détecter les cycles (deadlocks potentiels).

#Notations et formules utilesCopier le lien

• Graphe simple : G = (V, E) avec |V| = n, |E| = m.
• Somme des degrés : additionner tous les degrés d'un graphe non orienté donne 2 · |E| (chaque arête compte deux fois).
• Nombre maximal d'arêtes d'un graphe simple non orienté : n(n−1)/2 ; orienté : n(n−1).
• Matrice d'adjacence : matrice binaire A de taille n × n où A[i][j] = 1 si l'arête (i, j) existe. La puissance A^k compte les chemins de longueur k, par récurrence : (A^(k+1))[i][j] = Σ_r (A^k)[i][r] · A[r][j] additionne les marches aboutissant en r en k étapes puis sautant en j.
• Relaxation (plus courts chemins pondérés positifs) : mettre à jour d(v) lorsque d(u) + w(u, v) est plus petit ; tous les algorithmes de la famille (Dijkstra, Bellman-Ford, Ford-Fulkerson) tournent autour de cette primitive.
• Complexités : BFS/DFS O(n + m) ; Dijkstra avec tas binaire O((n + m) · log n) ; Bellman-Ford O(n · m) ; Kruskal O(m · log m) ; Kahn O(n + m).

#Exemple: comptage de chemins avec A^kCopier le lien

Soit un graphe non orienté à 4 sommets avec arêtes . La matrice A vaut :

10 1 1 021 0 0 131 0 0 140 1 1 0

On vérifie que : chemins de longueur 2 de 1 vers 4, soit 1→2→4 et 1→3→4. En effet (A²)[1][4] = A[1][2]·A[2][4] + A[1][3]·A[3][4] = 1·1 + 1·1 = 2. Le calcul matriciel énumère et additionne automatiquement toutes les marches intermédiaires, sans les lister à la main.

#Questions types d'examenCopier le lien

• Parcours : prouver que BFS retourne des plus courts chemins dans un graphe non pondéré (récurrence sur les couches, comme ci-dessus).
• MST : justifier que Kruskal ne crée jamais de cycle, termine avec n−1 arêtes, et qu'un échange d'arêtes préserve la minimalité (propriété de coupe).
• Topologie : expliquer pourquoi un cycle empêche tout ordre topologique, et prouver qu'un DAG a toujours un sommet de degré entrant nul.
• Comptage : calculer le nombre de chemins de longueur k via , en explicitant le produit matriciel sur une ligne.

#Checklist « graphes » avant examenCopier le lien

• Distinguer clairement les graphes non orientés/orientés et pondérés/non pondérés.
• Savoir reconstruire un arbre BFS/DFS à partir d'un graphe et d'un sommet racine.
• Vérifier systématiquement les hypothèses de connexité, de poids positifs, d'acyclicité avant d'appliquer un théorème.
• Citer l'invariant associé à chaque algorithme : file par couches pour BFS, pile et retour arrière pour DFS, composantes pour Kruskal, coupe et clé minimale pour Prim, degrés entrants pour Kahn.
• Recalculer à la main le résultat attendu sur un petit exemple avant de le comparer à l'exécution.

#Pièges courantsCopier le lien

• Oublier de marquer les sommets visités avant de les empiler/enfiler : duplication de traitement, voire boucle infinie.
• Confondre la complexité de Dijkstra O((n + m) log n) avec celle d'un BFS : Dijkstra exige des poids ≥ 0.
• Appliquer un tri topologique à un graphe contenant un cycle, ou à un graphe non orienté : vérifier toujours l'acyclicité orientée.
• Croire qu'un MST unique suit de l'algorithme : seuls les poids égaux créent des choix ambigus ; le poids total, lui, est toujours le même.

#Mini-quizCopier le lien

#Exercice avec correctionCopier le lien

Construisez le MST du graphe suivant par Kruskal puis par Prim depuis A, et comparez : sommets {A, B, C, D, E}, arêtes AB(3), AC(1), BD(6), BE(5), CD(4), CE(2), DE(7).

#CorrectionCopier le lien

Kruskal : tri des arêtes AC(1), CE(2), AB(3), CD(4), BE(5), BD(6), DE(7).

1. AC(1) acceptée : composante {A, C}.
2. CE(2) acceptée : C et E séparés, composante {A, C, E}.
3. AB(3) acceptée : B isolé, composante {A, B, C, E}. D reste seul.
4. CD(4) acceptée : D isolé, tout est connecté, 4 arêtes = n−1, arrêt.

Poids total : 1 + 2 + 3 + 4 = 10.

La question piège de la ligne 4 : CD traverse-t-elle deux composantes ? Oui, D n'a encore jamais été touché. Comparez avec AC à l'étape 1, où C était bien isolé : c'est le test union-find, pas la valeur du poids, qui décide.

Prim depuis A : coupe initiale ({A}, reste). Candidats AB(3), AC(1) : minimum AC(1). Puis depuis {A,C} : candidats CD(4), CE(2), AB(3) : minimum CE(2). Puis {A,C,E} : candidats CD(4), AB(3), BE(5) : minimum AB(3). Puis {A,B,C,E} : candidats CD(4), BE(5), BD(6) : minimum CD(4). Total : 1 + 2 + 3 + 4 = 10.

Les deux algorithmes construisent exactement le même arbre ici et le même poids 10 : la propriété de coupe impose que tout MST a ce poids. BD(6), BE(5) et DE(7) ne sont jamais les minimales de leur coupe au moment de leur examen.

Méthode de vérification : recenser à chaque étape la coupe courante et ses arêtes candidates, puis contrôler que l'arête retenue est bien la plus légère ; ensuite vérifier n−1 arêtes, connexité, et absence de cycle en comptant les composantes fusionnées.