Algorithmique de graphes : Ce qu'il faut savoir. Texte pédagogique couvrant les fondements mathématiques et algorithmiques des graphes, définissant formellement un graphe G = (V,E), les notions de chaîne, cycle, sentier, arbre recouvrant, cocycle et espace vectoriel des cycles sur Z/2Z. La maîtrise de ces notions permet de concevoir et d'analyser des algorithmes pour la recherche de chemins, la détection de cycles, les arbres de poids minimum et les échanges d'arêtes; ce PDF gratuit peut être téléchargé pour usage pédagogique et révision.

🎯 Ce que vous allez apprendre

  • Notions structurales des graphes

    Définition rigoureuse de sommets, arêtes, chaînes, cycles et sentiers, ainsi que notions associées (boucles, arêtes multiples, degrés). Distinction entre graphe simple et multigraphes ; implications sur les formulations et complexités algorithmiques. Exemples types : cycles C_k, chaînes P_k; identification de sentiers eulériens et parcours fermés servant d'appui aux preuves.

  • Arbres et propriétés équivalentes

    Caractéristiques des arbres (connexité minimale, n−1 arêtes, unicité de la chaîne entre deux sommets) et corollaires utiles (sommets pendants, décomposition récursive). Méthodes de preuve et techniques de suppression récursive pour construire ou vérifier des structures arborescentes.

  • Dualité cycle–cocycle et espaces vectoriels

    Construction de l'espace des cycles et des cocycles sur Z/2Z, orthogonalité et calcul des dimensions (dim cycles = m−n+1, dim cocycles = n−1). Bases fondamentales de cycles issues d'un arbre recouvrant et analyse d'indépendance linéaire d'ensembles d'arêtes.

  • Arbres recouvrants de poids minimum (MST)

    Formulation du problème MST avec valuation ω : E → R+, justification que la solution est un arbre, et schéma d'algorithme fondé sur des règles d'échange (coloration Tarjan bleu/rouge). Présentation des principes gloutons conduisant à Kruskal et Prim et analyse de correction par échanges d'arêtes.

  • Techniques de preuve et complexité

    Preuves par induction, lemmes sur isthmes et échanges d'arêtes, et analyses asymptotiques (par ex. O(n+m) pour certains parcours). Accent sur l'argumentation rigoureuse et l'estimation des coûts en fonction de n et m.

  • Exercices dirigés et problèmes

    Problèmes proposés incluant démonstrations classiques (théorème d'Euler, référence au théorème de Cayley) et algorithmes à implémenter. Exercices calibrés pour passer de la théorie aux implémentations et à l'analyse expérimentale.

  • Graphes planaires et plongements

    Propriétés de planarité, plongements dans le plan, notion de faces et dualité de graphe; mention de résultats structurels comme le théorème de Kuratowski et la conjecture/proposition de Wagner dans l'étude de mineurs et de la reconnaissance de planarité.

Structures et représentations informatiques des graphes

Les choix de représentation en mémoire conditionnent fortement la complexité algorithmique et les opérations usuelles (parcours, recherche de voisins, tests d'adjacence). Cette section compare les représentations classiques, précise leurs coûts en espace et en temps pour les opérations courantes, et indique des usages recommandés selon la densité du graphe et les algorithmes ciblés.

Représentations des graphes

La matrice d'adjacence est une matrice n×n où chaque case indique la présence ou le poids d'une arête; accès O(1) au test d'adjacence au prix d'un coût mémoire O(n²), adapté aux graphes denses. La liste d'adjacence stocke pour chaque sommet la liste de ses voisins, réduisant l'espace à O(n+m) et permettant des itérations efficaces sur les voisins, avantageuse pour les graphes creux. Le choix influence directement les performances des parcours et des algorithmes de plus court chemin.

Structures de données pour graphes

Implémentations usuelles : tableaux de listes (vector<list<int>> ou vector<vector<int>>) pour la liste d'adjacence, tableaux 2D ou bitsets pour la matrice. Pour les graphes pondérés, on utilise des couples (voisin, poids) dans les listes. Structures complémentaires — tables de hachage pour accès dynamique, représentations compressées pour très grands graphes — sont évoquées selon contraintes mémoire et temporelles.

Algorithmes de parcours et recherche de chemins

Les parcours constituent des primitives centrales : exploration, détection de cycles, composantes connexes, distances non pondérées. Présentation des paradigmes fondamentaux, complexités et cas d'application, en insistant sur garanties temporelles et spatiales pour un enseignement avancé.

Algorithmes de parcours (BFS et DFS)

Parcours en largeur (BFS) : exploration par couches avec une file, calcule les distances minimales en nombre d'arêtes dans les graphes non pondérés et permet la recherche de chemins en O(n + m). Parcours en profondeur (DFS) : exploration récursive ou itérative utilisant une pile, sert à la détection de cycles, au calcul de composantes fortement connexes (bases pour Kosaraju/Tarjan) et à la construction d'arbres couvrants ; complexité O(n + m).

Modélisation et résolution de problèmes

Transformer une situation concrète en modèle de graphe G=(V,E) commence par identifier entités et relations : les objets (noeuds) deviennent sommets, interactions ou liaisons deviennent arêtes, poids et capacités traduisent coûts ou contraintes. En logistique, par exemple, les entrepôts et clients sont sommets, les routes sont arêtes pondérées par temps ou coût ; en réseaux, les routeurs sont sommets et les liaisons physiques sont arêtes avec capacités. Cette étape de modélisation permet de recadrer un problème réel en termes classiques (plus court chemin, flots, couplages, problèmes de couverture) et d'appliquer les méthodes de la théorie des graphes aux solutions algorithmiques et à l'analyse de complexité.

Théorie des flots et réseaux de transport

Les problèmes de flots formalisent le transport sur des réseaux dirigés ou non : on associe à chaque arête une capacité et éventuellement un coût, puis on cherche un flot satisfaisant contraintes de capacité et conservation. L'algorithme de Ford-Fulkerson exploite des chemins augmentants pour accroître itérativement le flot; la dualité flot-max/coupe-min garantit que le flot maximum égalise la capacité de la coupe minimale. Variantes efficaces (Edmonds–Karp, Dinic) améliorent la complexité pratique. Ces outils sont essentiels pour modéliser le routage, la planification et l'optimisation des ressources dans des contextes industriels et de télécommunications.

Flots, Réseaux et Graphes Planaires

Les graphes planaires, leurs plongements et la notion de dualité entre faces et arêtes offrent des propriétés structurelles exploitables pour certains problèmes de flux et de coupe. Le dual d'un graphe planaire transforme coupes en cycles et inversement, ce qui permet des traductions algorithmiques élégantes. Les résultats de Kuratowski et Wagner caractérisent la non-planarité via mineurs interdits et servent à guider les algorithmes de reconnaissance et d'embedding. Pour les réseaux de transport dont la topologie est géographique, ces propriétés offrent souvent des simplifications algorithmiques et des garanties supplémentaires.

💡 Pourquoi choisir ce cours ?

Rédigé par Michel Habib (enseignement L3, Cachan / IRIF), le texte associe rigueur mathématique et perspectives algorithmiques. L'approche privilégie démonstrations formelles (lemmes, théorèmes) et schémas algorithmiques concrets (règles de Tarjan pour les MST, échanges d'arêtes). L'introduction explicite des espaces vectoriels de cycles/cocycles et les exercices intégrés facilitent la mise en pratique et la préparation à des travaux dirigés ou projets de recherche.

👤 À qui s'adresse ce cours ?

  • Public cible : étudiants en informatique niveau L3 ou équivalent, élèves d'écoles d'ingénieurs et développeurs d'algorithmes souhaitant approfondir la théorie des graphes et les méthodes de conception d'algorithmes sur graphes.
  • Prérequis : compréhension des notions de base en combinatoire et logique (ensembles, relations), maîtrise élémentaire des preuves mathématiques, notions d'analyse de complexité et structures de données classiques (listes, files, tas). Connaissances en théorie des graphes et familiarité avec union-find recommandées pour implémenter MST et autres algorithmes de structure.
  • Préparation aux concours : utile pour la préparation aux concours tels que l'agrégation ou le CAPES, où l'on attend maîtrise des démonstrations classiques et raisonnements algorithmiques précis.

❓ Foire Aux Questions (FAQ)

Comment construit-on une base fondamentale de cycles à partir d'un arbre recouvrant ?

À partir d'un arbre T on considère pour chaque arête e ∈ E(G) \ E(T) le cycle unique contenu dans T + e; l'ensemble de ces cycles µ_e est indépendant et de cardinal m − n + 1, fournissant ainsi une base fondamentale de l'espace des cycles sur Z/2Z.

Quelles sont les conditions pour l'existence d'un sentier eulérien et comment le construire en O(n+m) ?

Un graphe connexe admet un cycle eulérien si et seulement si tous les degrés de sommets sont pairs; la construction algorithmique passe par un parcours hiérarchique des arêtes (algorithme de Fleury ou parcours de type pile construisant un circuit d'Euler) réalisable en temps O(n+m).