Cours Graphes: modélisation et algorithmes en PDF (Avancé)
Graphes: modélisation et algorithmes — synthèse. Discipline des mathématiques discrètes et de l'informatique théorique, la théorie des graphes formalise des réseaux de relations entre objets par des sommets et arêtes. Le support couvre la connexité, les représentations (matrice d'adjacence, matrice d'incidence) et les modèles valués pour longueurs/poids. Sont présentés les algorithmes de parcours (DFS), de plus court chemin (Bellman‑Ford, Dijkstra, Floyd), d'arbres couvrants (Kruskal, Prim) et de flots (Ford‑Fulkerson), illustrés par exemples d'application en routage, ordonnancement et couplage.
Objectifs d'apprentissage
- Notions élémentaires et modélisation — identification des structures : orienté vs non orienté, multigraphe, biparti, arborescence ; représentations et choix mémoire adaptés aux contraintes temporelles et spatiales.
- Parcours et connexité (DFS, composantes) — maîtrise du Depth First Search et variantes pour détecter composantes connexes et fortement connexes ; principes de numérotation et usage de Kosaraju pour extraire les composantes fortement connexes.
- Plus courts chemins — principes de relaxation et comparaison des hypothèses : Bellman‑Ford pour arêtes de poids quelconque et détection de cycles négatifs ; Dijkstra pour poids non négatifs et extraction de distances/prédécesseurs.
- Arbres couvrants de poids minimum — critères d'optimalité et mise en œuvre de Kruskal et Prim ; choix entre union‑find et approche basée sur tas selon densité et représentation.
- Flots et couplages — définition de flot et coupe, graphe résiduel et chemins augmentants ; implémentations de Ford‑Fulkerson et approche pour flot maximum à coût minimal ainsi que couplage dans un graphe biparti.
Modéliser un problème sous forme de graphe permet d'appliquer des techniques d'optimisation combinatoire : formulations en programmation linéaire, algorithmes de flot et heuristiques pour problèmes NP‑difficiles. Les outils étudiés (MST, flots, plus courts chemins, couplages) servent de briques pour relaxations, modèles de coût et schémas d'approximation.
Applications concrètes de la théorie des graphes
Réseaux sociaux
Analyse de communautés, détection d'influenceurs et propagation d'information. Les métriques de centralité (degré, eigenvector, PageRank) et les méthodes de partitionnement (modularity, Louvain) identifient structures et dynamiques ; la modélisation facilite l'évaluation de stratégies de diffusion et la simulation de phénomènes d'information.
Logistique et optimisation des tournées
Modélisation des tournées comme problèmes de chemins et couplages, avec contraintes capacitaires et temporelles. Heuristiques pour le TSP, formulations en programmation entière et relaxations fournissent des solutions exploitables en pratique ; le choix d'une méthode dépend de la taille, de la densité et des contraintes opérationnelles.
Bio‑informatique
Reconstruction d'assemblages, réseaux d'interactions protéine‑protéine et recherche de motifs fréquents. Les structures de type De Bruijn et les algorithmes de parcours et couplage sont utilisés pour assembler séquences et détecter chemins biologiquement pertinents.
Table des matières
- Notions élémentaires sur les graphes — définitions et représentations
- Parcours et problèmes de connexité — DFS, BFS, composantes
- Chemins et distances — Bellman‑Ford, Dijkstra, Floyd
- Arbres couvrants — Kruskal, Prim, union‑find
- Flots et couplages — Ford‑Fulkerson, flot à coût minimal
- Applications et cas d'étude — routage, ordonnancement, couplage
- Complexité des algorithmes de graphes — comparaisons pratiques
- Définitions et notations formelles
Définitions et notations formelles
Dans la théorie des graphes et optimisation, un graphe orienté est noté graphe orientéG = (S, A)oùSdésigne l'ensemble fini des sommets etA ⊆ S × Sl'ensemble des arcs (ordered pairs). Un graphe non orienté s'écritG = (S, E)avecE ⊆ {{u,v} | u,v ∈ S}. Ces notations figurent dans les notes de cours graphes et servent de base aux définitions algorithmiques et aux preuves d'optimalité.
La précision des notations conditionne la correction, la convergence et la complexité des algorithmes. Propriétés telles que degrés, chemins, cycles et composantes s'expriment directement en termes d'ensembles S et A/E, fournissant un socle pour les démonstrations et les analyses de performance.
Complexité des algorithmes de graphes
Résumé des ordres de grandeur pour choisir la méthode adaptée en fonction de la taille n = |S| et du nombre d'arêtes m. Les variantes d'implémentation (tas binaire vs Fibonacci, tri des arêtes) influencent fortement les performances en pratique.
| Algorithme | Complexité typique | Remarques |
|---|---|---|
| DFS / BFS | O(n + m) | Parcours élémentaire pour connexité et ordonnancement topologique. |
| Dijkstra (tas binaire) | O((n + m) log n) | Convient pour poids non négatifs ; implémentation standard avec file de priorité. |
| Dijkstra (tas de Fibonacci) | O(n log n + m) | Amélioration théorique pour graphes denses ; overhead pratique important. |
| Kruskal | O(m log m) ≈ O(m log n) | Tri des arêtes puis union‑find ; performant selon densité. |
| Bellman‑Ford | O(n · m) | Gère poids négatifs et détecte cycles négatifs ; utile sur graphes modestes. |
| Algorithme | Forme | Interprétation |
|---|---|---|
| Dijkstra | O((n + m) log n) | Sur graphes clairsemés, facteur logarithmique lié aux opérations de priorité ; se rapproche de O(n + m) pour très petites tailles de n. |
| Kruskal | O(m log m) | Tri des arêtes domine ; pour m ≈ n, coût ≈ O(n log n) vs O(n + m). |
| Bellman‑Ford | O(n · m) | Croissance quadratique pour graphes denses ; bien au‑dessus d'un coût linéaire O(n + m) sauf pour très petits graphes. |
Notions élémentaires
- Types : orienté / non orienté, multigraphe, graphe simple, biparti, arborescence.
- Représentations : liste d'adjacence, matrice d'adjacence, matrice d'incidence ; choix selon densité et contraintes mémoire/temps.
- Structures auxiliaires : tas, piles, files, union‑find, tables de hachage pour opérations efficaces.
Foire aux questions (FAQ)
Comment l'algorithme de Kosaraju identifie‑t‑il les composantes fortement connexes ?
Kosaraju effectue deux DFS : le premier calcule un ordre de sortie (numérotation suffixe) sur le graphe original ; le second, sur le graphe transposé en parcourant les sommets selon cet ordre décroissant, extrait chaque composante fortement connexe. Les arêtes inter‑composantes respectent l'ordre topologique du graphe réduit, garantissant l'isolation successive des composantes.
Pourquoi choisir Bellman‑Ford plutôt que Dijkstra ?
Bellman‑Ford s'emploie lorsque des arêtes peuvent avoir des poids négatifs : il réalise des relaxations répétées (|S|−1 passes) et détecte des cycles de poids négatif. Dijkstra suppose des poids non négatifs et utilise une stratégie gourmande avec une file de priorité pour réduire la complexité.
Auteur : Brice Mayag — support pédagogique de 42 pages couvrant définitions formelles, algorithmes et cas d'application, conçu pour un public avancé en algorithmique et optimisation.
