Graphes et algorithmes

Votre GPS trouve le trajet le plus rapide parmi des millions de rues. Un orchestrateur de données lance chaque nuit des centaines de traitements dans le bon ordre. Un moteur de recherche classe des milliards de pages en regardant qui cite qui. Un chef de projet sait, avant même de commencer, quelles tâches ne doivent surtout pas prendre de retard. Derrière tous ces exemples se cache le même objet : un graphe, c’est-à-dire des éléments et des relations entre eux.

Ce cours vous apprend à reconnaître un graphe caché dans un problème, puis à le résoudre avec le bon algorithme. Il part du vocabulaire et des parcours, étudie la structure des graphes (connexité, graphes sans circuit, arbres, coloration), puis aborde les problèmes d’optimisation (plus courts chemins, ordonnancement de projets, flots), avant de montrer comment tout cela se retrouve au quotidien en data science. Chaque algorithme est déroulé à la main sur un exemple, puis codé en Python.

Objectifs pédagogiques

À la fin de ce cours, vous serez capable de :

• Modéliser un problème concret (réseau, dépendances, planning, affectation) par un graphe orienté ou non, valué ou non, et choisir sa représentation en mémoire.
• Parcourir un graphe en largeur et en profondeur, et en déduire ses composantes connexes et fortement connexes, sa fermeture transitive et un tri topologique.
• Construire un arbre couvrant de coût minimal avec Kruskal ou Prim, et colorier un graphe avec une heuristique gloutonne en encadrant le nombre chromatique.
• Calculer des plus courts chemins avec Dijkstra, Bellman-Ford ou Floyd-Warshall, en sachant lequel s’applique.
• Ordonnancer un projet par la méthode potentiels-tâches : dates au plus tôt et au plus tard, chemin critique, marges.
• Déterminer un flot maximal et une coupe minimale, et reconnaître les usages des graphes en data (pipelines, PageRank, recommandation, graphes de connaissances).

Prérequis

• Les bases de l’algorithmique : boucles, récursivité, notion de complexité ($O(n)$, $O(n^2)$).
• Python : listes, dictionnaires, ensembles.
• Un peu de logique pour suivre les démonstrations courtes (raisonnement par l’absurde, par récurrence).

Pour le chapitre 10, des notions de probabilités et de chaînes de Markov aident à comprendre PageRank : elles sont présentées dans le cours de modèles stochastiques. Le cours d’apprentissage automatique et celui de programmation logique prolongent certains exemples.

Le plan du cours

Partie 1 · Modéliser et parcourir

1. Découvrez les graphes et leur vocabulaire : graphes orientés ou non, degrés, chemins et chaînes, graphes eulériens et hamiltoniens, représentations en mémoire.
2. Parcourez un graphe en largeur et en profondeur : BFS et DFS, composantes connexes, points d’articulation et isthmes.

Partie 2 · Structurer un graphe

3. Repérez les composantes fortement connexes : descendants et ascendants, fermeture transitive par Roy-Warshall, composantes fortement connexes et graphe réduit.
4. Ordonnez un graphe sans circuit : mise en niveaux, détection de circuit, tri topologique par Kahn ou par DFS.
5. Construisez un arbre couvrant de coût minimal : arbres, nombre cyclomatique, algorithmes de Kruskal et de Prim.
6. Colorez un graphe : stables et cliques, nombre chromatique et ses bornes, Welsh-Powell et DSatur.

Partie 3 · Optimiser et appliquer

7. Calculez les plus courts chemins : Dijkstra, Bellman-Ford, circuits absorbants, Floyd-Warshall.
8. Ordonnancez un projet avec la méthode potentiels-tâches : contraintes, dates au plus tôt et au plus tard, chemin critique, marges totales et libres.
9. Maximisez un flot dans un réseau : flots et coupes, théorème de Ford-Fulkerson, chaînes augmentantes.
10. Mettez les graphes au service de la data : DAG de pipelines, PageRank, recommandation, graphes de connaissances.

Chaque chapitre se termine par un résumé et des exercices corrigés, de difficulté croissante.

D’où vient ce cours

Ce cours reprend l’enseignement de graphes et algorithmes suivi en 3e année du cycle ingénieur de l’INSA Rennes, en spécialité informatique (second semestre). Le plan général (graphes non valués, graphes valués, applications à l’ordonnancement et aux flots), les définitions et les notations ($\Gamma$, demi-degrés, cocycles), la fermeture transitive par Roy-Warshall et sa généralisation, la méthode de Foulkes, l’algorithme de Marimont, les deux versions de Kruskal, Moore-Dijkstra, Bellman, la méthode potentiels-tâches et l’algorithme de marquage de Ford-Fulkerson suivent ce cours. Les sujets de devoirs surveillés des années précédentes ont guidé le choix et le style des exercices (adaptation de Roy-Warshall, ordonnancement avec contraintes « au plus tard », coloration pour l’attribution de fréquences, 2-connexité), avec des données entièrement nouvelles.

Le texte, les exemples et les exercices ont été entièrement réécrits. Plusieurs notions ont été complétées à partir de sources standard (les ouvrages de référence en algorithmique et en théorie des graphes, et la documentation de networkx) : les parcours BFS et DFS détaillés, les algorithmes de Tarjan, Kosaraju et Kahn, l’heuristique DSatur, l’algorithme d’Edmonds-Karp, les couplages dans un graphe biparti, ainsi que tout le chapitre 10 sur les usages des graphes en data. Les codes Python sont écrits pour ce cours ; les extraits networkx sont donnés en aperçu.