Dossier complet — Théorie des graphes

L2 · S4 · Mathématiques appliquées

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Modéliser une situation relationnelle par un graphe orienté ou non orienté, pondéré ou non, en choisissant une représentation adaptée.

• Calculer et interpréter degrés, chemins, distances, composantes connexes et arbres couvrants avec un vocabulaire précis.

• Exécuter et justifier les parcours BFS et DFS, notamment pour les distances non pondérées, la détection de cycles et l'exploration de composantes.

• Appliquer Dijkstra lorsque les poids sont non négatifs et distinguer soigneusement ce cas de Bellman-Ford et des limites de l'algorithme.

• Construire une solution reproductible sur un petit réseau, analyser sa complexité et communiquer les hypothèses, résultats et limites.

Prérequis

• Savoir manipuler ensembles, fonctions, récurrence simple et raisonnement par cas au niveau licence.

• Maîtriser les bases de l'algorithmique : boucles, files, piles, tableaux, dictionnaires et notation en O grand.

• Être capable de lire du pseudo-code ou du Python élémentaire et de vérifier un résultat sur un exemple.

Cours

1. Vocabulaire et représentations

Idée centrale

Un graphe $G=(V,E)$ décrit des objets (sommets) et des relations (arêtes). Une arête non orientée $\{u,v\}$ est symétrique; un arc $(u,v)$ ne l'est pas. Un graphe peut être simple (pas de boucle ni d'arête multiple), pondéré, ou mixte. Le degré d'un sommet compte ses incidences; dans un graphe non orienté, $\sum_{v\in V}\deg(v)=2|E|$. La matrice d'adjacence coûte $O(|V|^2)$ et donne un test d'existence rapide; une liste de voisins coûte $O(|V|+|E|)$ et convient aux graphes creux.

Exemple guidé. Pour $V=\{A,B,C,D\}$ et $E=\{\{A,B\},\{A,C\},\{B,D\}\}$, les degrés sont $2,2,1,1$ : leur somme vaut $6=2\times3$. La liste de $A$ est $[B,C]$; la matrice a des $1$ en $(A,B),(B,A)$ et ainsi de suite.

Erreurs fréquentes : confondre degré et nombre de sommets, oublier le double comptage, ou appliquer une matrice dense à un très grand graphe creux. Point de contrôle : préciser orientation, poids, boucles et représentation avant tout calcul.

Points-clés

• Un graphe est défini par ses sommets et ses relations; l'orientation change le sens des parcours.
• La somme des degrés vaut deux fois le nombre d'arêtes dans un graphe non orienté.
• Liste de voisins et matrice d'adjacence se choisissent selon la densité et les opérations attendues.

2. Parcours BFS et DFS

Explorer systématiquement

BFS utilise une file FIFO : il traite d'abord les sommets à distance $0$, puis $1$, etc. Dans un graphe non pondéré, le premier marquage donne donc une distance minimale. DFS utilise une pile explicite ou la récursion et suit une branche avant de revenir; il révèle une structure de retour utile pour les cycles et les composantes. Avec une liste de voisins, les deux parcours coûtent $O(|V|+|E|)$ si chaque sommet est marqué dès sa découverte.

Exemple guidé. Depuis $A$, avec voisins dans l'ordre alphabétique et arêtes $AB,AC,BD,CE,DE$, BFS enfile $A$, puis découvre $B,C$, puis $D,E$. Les distances sont $d(A)=0$, $d(B)=d(C)=1$, $d(D)=d(E)=2$; les prédécesseurs donnent un chemin minimal $A-B-D$. DFS peut visiter $A,B,D,E,C$, selon l'ordre.

Erreurs fréquentes : marquer à la sortie plutôt qu'à la découverte, ce qui duplique le travail, ou croire que DFS fournit une distance minimale. Point de contrôle : écrire file/pile, ensemble visité et prédécesseurs sur papier avant de coder.

Points-clés

• BFS garantit les distances minimales seulement quand chaque arête a le même coût.
• DFS explore en profondeur et sert notamment à détecter des retours et des composantes.
• Marquer à la découverte assure un coût linéaire avec des listes de voisins.

3. Chemins et arbres

Choisir le bon algorithme

Dans un graphe pondéré, le coût d'un chemin est la somme de ses poids. Dijkstra maintient une estimation $d(v)$ et choisit à chaque étape le sommet non traité de plus petite estimation; la relaxation teste $d(v)>d(u)+w(u,v)$. Il est correct si tous les poids sont non négatifs et coûte $O((|V|+|E|)\log|V|)$ avec un tas. Bellman-Ford répète les relaxations $|V|-1$ fois et détecte un cycle négatif, au prix de $O(|V||E|)$.

Exemple guidé. Depuis $A$, arêtes $A\to B:4$, $A\to C:1$, $C\to B:2$, $B\to D:1$, $C\to D:5$. Initialement $d(B)=4,d(C)=1$. On extrait $C$, obtient $d(B)=3$ et $d(D)=6$; on extrait $B$, obtient $d(D)=4$. Le chemin optimal est $A-C-B-D$, coût $4$.

Erreurs fréquentes : utiliser Dijkstra avec un poids négatif, oublier de conserver le prédécesseur, ou comparer seulement le nombre d'arêtes. Point de contrôle : justifier la condition sur les poids et produire distances plus prédécesseurs.

Points-clés

• La relaxation compare le coût connu avec un coût passant par un voisin.
• Dijkstra exige des poids non négatifs; Bellman-Ford traite aussi les poids négatifs sans cycle négatif.
• Un tableau de prédécesseurs reconstruit le chemin, pas seulement sa longueur.

4. Arbres, forêts et connexité

Relier sans redondance

Un arbre non orienté est connexe et sans cycle; avec $n=|V|$ sommets, il possède exactement $n-1$ arêtes. Toute paire de sommets y est reliée par un unique chemin. Une forêt est une union d'arbres. Un arbre couvrant garde tous les sommets d'un graphe connexe, et un arbre couvrant de poids minimal (ACM) minimise la somme des poids. Kruskal trie les arêtes puis ajoute celles qui relient deux composantes distinctes; une structure union-find rend ce test efficace. Prim agrandit un arbre depuis un sommet par l'arête sortante la moins chère.

Exemple guidé. Sur $A-B:1$, $B-C:2$, $A-C:4$, $C-D:1$, $B-D:5$, Kruskal prend $AB$, $CD$, puis $BC$; il obtient $4$ arêtes? Non : avec quatre sommets, il s'arrête à trois arêtes, donc $AB,CD,BC$, coût $1+1+2=4$. L'arête $AC$ créerait alors un cycle.

Erreurs fréquentes : confondre un arbre couvrant et un chemin, ou arrêter avant d'avoir $n-1$ arêtes. Point de contrôle : vérifier connexité, absence de cycle et cardinalité.

Points-clés

• Un arbre à n sommets possède n−1 arêtes et un unique chemin entre deux sommets.
• Kruskal ajoute les arêtes par poids croissant sans créer de cycle.
• Un arbre couvrant minimal optimise un réseau, mais ne minimise pas forcément chaque trajet.

5. Modéliser un réseau et évaluer la solution

Passer du réel au graphe

Une modélisation commence par une convention : sommets = stations, arêtes = liaisons; le poids peut être durée, distance ou coût, mais une seule interprétation doit être utilisée dans l'algorithme. Il faut traiter sommets isolés, sens uniques, égalités de poids et données incohérentes. La complexité se rapporte à $|V|$ et $|E|$, non à la taille du fichier. Une validation utile compare un résultat calculé à une borne simple, teste un petit cas dont la solution est connue et documente les hypothèses.

Exemple guidé. Pour relier quatre stations avec durées $AB=6$, $AC=2$, $CB=3$, $BD=2$, $CD=7$, le plus court trajet $A\to D$ est $A-C-B-D$, soit $2+3+2=7$, plutôt que $A-B-D=8$. Si l'objectif est de construire les lignes les moins coûteuses, on choisira un ACM; si l'objectif est l'itinéraire d'un voyageur, on choisira un plus court chemin : ce ne sont pas la même question.

Erreurs fréquentes : mélanger distance et durée, oublier les arcs interdits, ou annoncer un résultat sans unité. Point de contrôle : écrire objectif, poids, algorithme et complexité en quatre lignes.

Points-clés

• Une modélisation explicite sépare objets, relations, orientation, poids et objectif.
• Plus court chemin et arbre couvrant minimal répondent à des besoins différents.
• Une conclusion vérifiable inclut unités, hypothèses, complexité et tests limites.

Exercices corrigés

Exercice 1 · Fondamental

Dans le graphe non orienté V={A,B,C,D,E} et E={{A,B},{A,C},{B,C},{C,D}}, calculez le degré de chaque sommet, vérifiez la formule de la somme des degrés et indiquez les sommets de degré impair.

Correction détaillée

On compte les incidences : deg(A)=2 (AB, AC), deg(B)=2 (BA, BC), deg(C)=3 (CA, CB, CD), deg(D)=1 (DC), deg(E)=0. La somme vaut 2+2+3+1+0=8. Il y a |E|=4 arêtes, donc 2|E|=8 : la vérification est correcte. Les sommets de degré impair sont C et D. E est isolé, ce qui n'empêche pas la formule.

Exercice 2 · Fondamental

Sur le graphe non orienté dont les arêtes sont AB, AC, BD, CE, DF et EG, lancez BFS depuis A en visitant les voisins par ordre alphabétique. Donnez l'ordre de découverte, les distances et un chemin minimal vers F.

Correction détaillée

On marque A à la découverte et on l'enfile. On traite A : découverte de B puis C, distances 1. On traite B : découverte de D, distance 2. On traite C : découverte de E, distance 2. On traite D : découverte de F, distance 3. On traite E : découverte de G, distance 3. L'ordre de découverte est A,B,C,D,E,F,G. Les distances sont 0,1,1,2,2,3,3 respectivement. Les prédécesseurs de F sont D, de D sont B, de B est A : un chemin minimal est A-B-D-F, de longueur 3.

Exercice 3 · Intermédiaire

Appliquez Dijkstra depuis S au graphe orienté pondéré S→A=4, S→B=2, B→A=1, A→C=3, B→C=7, B→D=5, C→D=1. Donnez l'ordre de sélection, les distances finales et un plus court chemin vers D.

Correction détaillée

Initialisation : d(S)=0, d(A)=4, d(B)=2, d(C)=∞, d(D)=∞. On sélectionne S puis B (2) : A devient 3, C devient 9, D devient 7. On sélectionne A (3) : C devient 6. On sélectionne C (6) : D devient 7, égalité donc pas de changement. Enfin D (7). Distances : S=0, B=2, A=3, C=6, D=7. En remontant les prédécesseurs, D vient de B (ou de C selon la règle d'égalité), et le chemin S-B-D coûte 7; S-B-A-C-D coûte aussi 2+1+3+1=7. Tous les poids étant positifs, Dijkstra est applicable.

Exercice 4 · Intermédiaire

Trouvez un arbre couvrant minimal par Kruskal dans le graphe non orienté à sommets A,B,C,D,E et arêtes AB=4, AC=2, BC=1, BD=5, CD=8, CE=3, DE=2, BE=6. Donnez les arêtes rejetées et le coût total.

Correction détaillée

Tri : BC=1, AC=2, DE=2, CE=3, AB=4, BD=5, BE=6, CD=8. On ajoute BC (composantes BC), AC (ABC), DE (DE), puis CE (ABCDE) : quatre arêtes pour cinq sommets, donc l'arbre est terminé. AB=4 est rejetée car A et B sont déjà reliés; BD=5 et BE=6 relieraient aussi des sommets déjà dans la même composante, tout comme CD=8. Le coût total est 1+2+2+3=8. La structure est connexe et sans cycle, avec |V|-1=4 arêtes.

Exercice 5 · Avancé

Un graphe orienté possède les arcs A→B=2, A→C=5, B→C=-2, B→D=4, C→D=3, D→B=1. Depuis A, déterminez les distances exactes, expliquez pourquoi Dijkstra n'est pas garanti, puis indiquez si le graphe contient un cycle négatif accessible.

Correction détaillée

Le chemin A→B→C coûte 2-2=0, puis A→B→C→D coûte 3. Les distances candidates sont d(A)=0, d(B)=2, d(C)=0, d(D)=3. Dijkstra n'est pas garanti car l'arc B→C a un poids négatif : un sommet sélectionné pourrait être amélioré après sa sélection. Bellman-Ford convient. Le cycle B→C→D→B a un coût -2+3+1=2, donc il n'est pas négatif. Il n'existe pas d'autre cycle négatif accessible dans ce graphe; les distances sont donc bien définies. Une exécution Bellman-Ford relaxe les arcs jusqu'à stabilisation et vérifie qu'une relaxation supplémentaire n'est plus possible.

Quiz d’autoévaluation

Question 1

Dans un graphe non orienté, à quoi est égale la somme des degrés ?

• |V| • |E| ✓ 2|E| • |V|+|E|

Explication : Chaque arête contribue une incidence à chacun de ses deux sommets; elle est donc comptée deux fois.

Question 2

Quelle propriété caractérise BFS dans un graphe non pondéré ?

• Il minimise toujours la somme des poids ✓ Il fournit une distance minimale en nombre d'arêtes • Il détecte tous les cycles négatifs • Il trie les sommets par degré

Explication : La file traite les couches successives, donc le premier marquage d'un sommet correspond au plus petit nombre d'arêtes depuis la source.

Question 3

Quelle structure est naturellement associée à une implémentation itérative de DFS ?

✓ Une pile • Une file FIFO • Une table SQL • Un tas min uniquement

Explication : DFS empile les sommets à explorer et dépile le dernier ajouté, ce qui pousse l'exploration en profondeur.

Question 4

Quelle condition est nécessaire à la garantie classique de Dijkstra ?

• Tous les poids sont égaux à zéro • Le graphe est complet ✓ Les poids sont non négatifs • Le graphe ne contient aucun sommet isolé

Explication : Avec un poids négatif, un sommet déjà choisi pourrait être amélioré plus tard; la preuve gloutonne ne tient plus.

Question 5

Combien d'arêtes possède un arbre comportant n sommets ?

✓ n-1 • n • 2n • n²

Explication : La connexité minimale et l'absence de cycle impliquent exactement n−1 arêtes.

Question 6

Que fait Kruskal lorsqu'une arête triée relie déjà deux sommets de la même composante ?

• Il l'ajoute et crée volontairement un cycle ✓ Il la rejette • Il inverse son orientation • Il double son poids

Explication : La rejeter empêche les cycles; l'arbre est construit en reliant progressivement des composantes distinctes.

Question 7

Quelle représentation est généralement préférable pour un graphe très creux ?

• Une matrice d'adjacence dense ✓ Une liste de voisins • Une image bitmap • Un tableau de degrés uniquement

Explication : La liste de voisins stocke les arêtes présentes et permet un parcours en O(|V|+|E|), sans réserver toutes les cases absentes.

Question 8

Quel énoncé distingue correctement plus court chemin et arbre couvrant minimal ?

• Ils répondent toujours au même problème ✓ Le premier optimise un trajet, le second le coût global de connexion • Le premier interdit les poids, le second les impose • Le second ne peut avoir que deux sommets

Explication : Un plus court chemin concerne une source et une destination; un arbre couvrant relie tout le réseau au moindre coût total.

Glossaire

• Graphe simple — Graphe sans boucle et sans arêtes multiples entre une même paire de sommets.
• Degré — Nombre d'arêtes incidentes à un sommet dans un graphe non orienté; en orienté, on distingue degrés entrant et sortant.
• Chemin — Suite de sommets reliés par des arêtes ou arcs; sa longueur peut compter les arêtes ou sommer leurs poids.
• Composante connexe — Sous-ensemble maximal de sommets reliés deux à deux par des chemins dans un graphe non orienté.
• Relaxation — Mise à jour de la meilleure distance connue lorsqu'un passage par une arête fournit un coût plus petit.
• Arbre couvrant — Sous-graphe connexe sans cycle qui contient tous les sommets du graphe initial.
• BFS — Parcours en largeur utilisant une file et explorant les sommets par couches de distance.
• DFS — Parcours en profondeur utilisant une pile ou la récursion pour suivre une branche avant retour arrière.

TP · Mini-cas : fiabiliser les itinéraires d'un réseau de campus

Une navette relie six lieux A à F. Les liaisons sont orientées quand une rue est à sens unique et portent une durée en minutes. On veut produire un itinéraire le plus rapide depuis A vers chaque lieu, tout en signalant les lieux inatteignables.

Objectifs

• Formaliser les lieux et liaisons dans une liste de voisins pondérée.

• Implémenter ou simuler Dijkstra et reconstruire les chemins par prédécesseurs.

• Comparer un cas sans poids avec BFS pour comprendre l'effet de la durée.

• Tester la solution sur une liaison supprimée et expliquer la limite de l'hypothèse de poids non négatifs.

Étapes

1. Écrire dans un tableau les sommets A-F et au moins huit liaisons, en indiquant orientation et durée; justifier chaque convention.

2. Construire la liste de voisins et vérifier manuellement deux degrés ou nombres de sorties ainsi qu'un sommet éventuellement isolé.

3. Exécuter Dijkstra depuis A, consigner à chaque étape le sommet sélectionné, les distances et les prédécesseurs.

4. Reconstituer le chemin vers deux destinations, puis refaire l'expérience en remplaçant chaque poids par 1 avec BFS.

5. Supprimer une liaison, relancer les calculs et rédiger une conclusion avec complexité, unités, cas d'échec et contrôle indépendant.

Livrables attendus

• Un schéma ou tableau du réseau annoté avec orientation et durées.

• Un tableau de traces (étapes, distances, prédécesseurs) et deux itinéraires expliqués.

• Une note d'une page comparant Dijkstra et BFS, avec tests, hypothèses et limites.

Critères d’évaluation

• Modèle cohérent et unités explicites : 25 %.

• Calculs, prédécesseurs et chemins reconstruits exacts : 35 %.

• Tests de cas limite et analyse de complexité : 20 %.

• Clarté de l'argumentation et distinction trajet/connexion globale : 20 %.

Piste de résolution

Une solution possible utilise A→B=4, A→C=2, C→B=1, B→D=3, C→E=6, D→E=1, E→F=2, B→F=10. Dijkstra donne d(B)=3 par A-C-B, d(D)=6, d(E)=7 et d(F)=9 par A-C-B-D-E-F. Il faut conserver les prédécesseurs C, B, D, E et signaler toute distance infinie. Après remplacement des poids par 1, BFS peut préférer A-C-E-F en trois arcs; cette différence montre que le nombre d'étapes et la durée ne sont pas interchangeables.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — graphes, session normale

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création pédagogique originale, non officielle; il ne s'agit jamais d'une épreuve d'une année passée ni d'une annale. Les justifications et unités sont attendues.

Exercice 1

Soit G non orienté, sommets {1,2,3,4,5,6}, arêtes 12,13,24,35,45,56. Déterminez les composantes connexes, puis donnez un arbre couvrant de chaque composante.

Correction : Les arêtes relient 1 à 2 et 3; 2 à 4; 3 à 5; 4 à 5; 5 à 6. Tous les sommets sont donc dans une seule composante. Un parcours depuis 1 découvre 2,3, puis 4,5, puis 6. En gardant les arêtes de découverte, on obtient 12,13,24,35,56 : cinq arêtes pour six sommets, connexe et sans cycle; c'est un arbre couvrant.

Exercice 2

Calculez les distances depuis S dans le graphe orienté S→A=6, S→B=2, B→A=2, A→C=1, B→C=7, C→D=3, A→D=8, en donnant les prédécesseurs.

Correction : Initialement d(S)=0, d(A)=6, d(B)=2, autres infinis. Après S, on sélectionne B : A devient 4 et C devient 9. On sélectionne A : C devient 5 et D devient 12. On sélectionne C : D devient 8. Les distances finales sont 0,4,2,5,8 pour S,A,B,C,D. Les prédécesseurs sont A←B, B←S, C←A, D←C. Le chemin vers D est S-B-A-C-D, coût 2+2+1+3=8. Tous les poids sont non négatifs, donc Dijkstra est justifié.

Exercice 3

Expliquez pourquoi une matrice d'adjacence n'est pas le meilleur choix pour un graphe de 100 000 sommets et 300 000 arêtes, puis donnez une complexité de parcours adaptée.

Correction : La matrice réserverait 100 000² cases, soit 10 milliards de positions, alors que seules 300 000 relations existent : elle gaspille de la mémoire. Une liste de voisins stocke les sommets et arêtes présentes. BFS ou DFS visite chaque sommet accessible et chaque arête au plus un nombre constant de fois, pour O(|V|+|E|), ici de l'ordre de 400 000 opérations hors coûts de gestion. Il faut aussi prévoir un tableau visité et traiter les composantes si le graphe n'est pas connexe.

Sujet original de préparation — graphes, seconde session

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création pédagogique originale, non officielle; ce n'est ni une véritable annale ni une épreuve d'une année passée. Les conventions doivent être explicitement indiquées.

Exercice 1

Sur le graphe non orienté pondéré A-B=7, A-C=3, C-B=2, B-D=4, C-D=10, D-E=1, calculez un plus court chemin de A vers E et comparez-le au chemin direct par A-B-D-E.

Correction : Le chemin A-C-B-D-E coûte 3+2+4+1=10. Le chemin A-B-D-E coûte 7+4+1=12. Le chemin A-C-D-E coûte 3+10+1=14. Les relaxations successives donnent d(C)=3, puis d(B)=5 via C, d(D)=9 via B, d(E)=10 via D. Le plus court chemin est donc A-C-B-D-E, de coût 10.

Exercice 2

Construisez par Kruskal un arbre couvrant minimal pour les arêtes AB=1, AC=4, BC=2, BD=6, CD=3, CE=5, DE=2, puis prouvez que son coût est 8.

Correction : L'ordre est AB=1, BC=2, DE=2, CD=3, AC=4, CE=5, BD=6. On prend AB, BC, DE, puis CD : les cinq sommets sont reliés avec quatre arêtes, coût 1+2+2+3=8. AC est rejetée car A et C sont déjà connectés par A-B-C; CE et BD sont également dans une même composante. Kruskal est correct par la propriété de coupe : à chaque étape, l'arête la moins chère reliant deux composantes peut appartenir à un ACM.

Exercice 3

Donnez un algorithme en pseudo-code qui compte les composantes connexes d'un graphe non orienté représenté par listes de voisins, puis analysez sa complexité.

Correction : Pseudo-code : visites←ensemble vide; compte←0; pour chaque sommet s : si s non visité, compte←compte+1, empiler s, marquer s; tant que la pile n'est pas vide, u←dépiler; pour v dans voisins[u], si v non visité, marquer v et empiler v. Chaque sommet est marqué une fois et chaque arête est examinée au plus deux fois dans un graphe non orienté; la complexité est O(|V|+|E|), avec O(|V|) mémoire pour visites et la pile.

Parcours de révision sur quatre semaines

Semaine 1 · Vocabulaire, degrés, orientation et représentations

Créer trois petits graphes, calculer degrés et matrices/listes, puis vérifier la somme des degrés à la main. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · BFS, DFS et connexité

Tracer deux parcours avec ordre de voisins fixé, reconstruire un chemin BFS et coder un comptage de composantes. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · Dijkstra, Bellman-Ford et arbres couvrants

Faire deux tableaux de relaxations, repérer un poids négatif, puis appliquer Kruskal sur deux réseaux pondérés. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Modélisation, complexité et entraînement

Réaliser le mini-cas, résoudre un sujet original en temps limité, corriger les unités, hypothèses et cas limites. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.