Cours Graphes et leurs algorithmes en PDF (Intermédiaire)
Les graphes et leurs algorithmes : Ce qu'il faut savoir. Un graphe est une structure combinatoire constituée d'un ensemble de sommets et d'un ensemble d'arêtes (ou d'arcs pour les modèles orientés) reliant ces éléments ; il permet de représenter relations, dépendances et chemins. Ces notions servent à modéliser réseaux, ordonnancements et problèmes d'optimisation rencontrés en informatique et en ingénierie. Document disponible en PDF et gratuit pour consultation et téléchargement. Support de cours pour niveau intermédiaire, couvrant définitions, preuves et exercices pratiques.
Concepts fondamentaux des graphes
Un sommet (ou nœud) est une entité élémentaire ; une arête relie deux sommets dans un graphe non orienté, tandis qu'un arc est orienté et définit une relation unidirectionnelle. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Un graphe orienté acyclique (DAG) ne contient pas de cycle dirigé et sert souvent à modéliser dépendances et ordonnancement.
Algorithmes de parcours : BFS et DFS
Les parcours en largeur (BFS) et en profondeur (DFS) explorent l'ensemble des sommets selon des stratégies distinctes. BFS visite par couches et permet de calculer des distances non pondérées et de tester la connexité. DFS explore en profondeur, facilite la détection de cycles, la classification d'arêtes et la construction d'arbres couvrants. Ces parcours servent de base pour repérer composantes connexes, ponts et cycles, et constituent des primitives pour des algorithmes plus avancés.
Algorithmes de plus court chemin (Dijkstra, Bellman-Ford)
L'algorithme de Dijkstra calcule des plus courts chemins depuis une source sur un graphe avec poids non négatifs en exploitant une file de priorité pour extraire le sommet de distance minimale. Bellman-Ford traite les graphes avec poids négatifs : il repose sur des opérations de relaxation répétées sur toutes les arêtes, converge en au plus V−1 itérations si aucun cycle de poids négatif n'existe, et détecte l'existence d'un tel cycle si une relaxation supplémentaire réduit encore une distance. La complexité de Bellman-Ford est en O(V·E), adaptée lorsque des poids négatifs doivent être pris en compte.
Composantes connexes
Une composante connexe d'un graphe non orienté est un sous-ensemble maximal de sommets tels que chaque paire de sommets est reliée par un chemin. Dans les graphes orientés, une composante fortement connexe est un sous-ensemble maximal où, pour toute paire (u,v), il existe un chemin de u vers v et un chemin de v vers u. Les composantes (fortement) connexes se détectent par BFS/DFS ou par des algorithmes dédiés comme Kosaraju et Tarjan pour les composantes fortement connexes.
Algorithmes d'Arbres Couvrants Minimaux
Un arbre couvrant minimal (arbre couvrant de poids minimal) relie tous les sommets d'un graphe connexe en minimisant la somme des poids des arêtes. Les approches gloutonnes dominantes sont l'algorithme de Kruskal, qui trie les arêtes par poids et utilise une structure union-find pour éviter les cycles, et l'algorithme de Prim, qui construit un arbre en ajoutant à chaque étape l'arête de moindre poids reliant l'arbre courant à un sommet externe. Ces méthodes sont incontournables pour les problèmes d'optimisation réseau.
Analyse de la Complexité Spatiale et Temporelle
L'impact mémoire et temporel dépend fortement de la représentation choisie : matrice d'adjacence ou liste d'adjacence. Pour des graphes creux, les représentations par listes réduisent la consommation mémoire et accélèrent certains parcours ; pour des graphes très denses, la matrice peut simplifier l'accès constant entre deux sommets. L'analyse permet d'orienter les choix d'implémentation selon la densité et les opérations fréquentes.
| Représentation | Complexité spatiale | Remarques |
|---|---|---|
| Matrice d'adjacence | O(V²) | Accès constant entre deux sommets ; coûteuse en mémoire pour grands V |
| Liste d'adjacence | O(V + E) | Efficient pour graphes creux ; parcours des successeurs en O(degré) |
Ce que vous allez apprendre
- Représentations : matrices et listes — différences entre matrice d'adjacence, matrice d'incidence et listes d'adjacence, avec avantages et inconvénients en mémoire et en complexité. Implémentation et parcours d'une matrice
M[i][j]ou d'une liste d'adjacence et critères de choix selon la densité du graphe. - Propriétés combinatoires et théorèmes — notions de degré, pont, composante connexe, diamètre et ordre, et méthodes de preuve (induction, équivalences). Démonstration que tout arbre possède n−1 arêtes et propriétés utiles pour l'analyse structurelle.
- Chemins, circuits et problèmes de longueur — distinction entre chaîne, chemin, circuit, chemin eulérien et hamiltonien ; formalisation des problèmes de plus court chemin et du chemin critique et stratégie de résolution algorithmique.
- Coloration et conflits de ressources — application du nombre chromatique aux problèmes d'emploi du temps et d'affectation ; formulation des contraintes et heuristiques pour limiter le nombre de couleurs.
- Complexité et choix d'implémentation — coûts d'opérations selon la représentation (par exemple parcours des successeurs en
O(V^2)vsO(V+E)). Capacité à estimer l'impact mémoire et temporel pour orienter la conception du code.
Algorithmes de parcours et connexité
La vérification de la connexité s'effectue par un parcours BFS ou DFS depuis un sommet arbitraire : si tous les sommets sont visités, le graphe est connexe. DFS permet également de détecter des cycles en repérant des arêtes vers des sommets encore en cours d'exploration. Ces méthodes constituent la base pour des algorithmes de composantes fortement connexes et pour la résolution d'exercices illustrant ces propriétés.
Applications : Ordonnancement et Coloration
L'ordonnancement se formalise souvent par des graphes orientés acycliques (DAG) où la détection du chemin critique et l'évaluation de durées maximales sont essentielles pour organiser tâches et ressources. La coloration s'applique aux conflits d'affectation (salles, créneaux, fréquences) ; une modélisation correcte et le choix d'heuristiques réduisent le nombre de couleurs nécessaires dans des instances pratiques.
Exercices et applications pratiques
Exercices corrigés : implémentation de listes d'adjacence et matrices, tests de connexité par BFS/DFS, détection de cycles, mise en œuvre de Dijkstra pour plus court chemin, traitement des poids négatifs avec Bellman-Ford, et instances de coloration pour problèmes d'emploi du temps. Ces travaux pratiques renforcent l'autonomie dans le choix de représentation et l'interprétation des résultats algorithmiques sur cas concrets.
📑 Sommaire du document
- Introduction
- Définition
- Représentation d'un graphe
- Propriétés combinatoires
- Algorithmes de parcours : BFS et DFS
- Algorithmes de plus court chemin
- Algorithmes d'Arbres Couvrants Minimaux
- Exercices et applications pratiques
💡 Pourquoi choisir ce cours ?
Rédigé par Djamal Rebaïne, ce support articule démonstrations mathématiques et exercices pratiques tirés d'exemples concrets (ponts de Königsberg, itinéraires, ordonnancement, coloration). Le document combine formalisation rigoureuse et mises en œuvre en C/C++ ou Java, facilitant le passage de la théorie au code. L'approche pédagogique privilégie l'analyse des représentations et les choix algorithmiques, utile pour évaluer la complexité sur cas réels.
👤 À qui s'adresse ce cours ?
- Public cible : étudiants en informatique et ingénierie, développeurs ou chercheurs confrontés à des problèmes de réseaux, d'ordonnancement ou d'optimisation nécessitant modélisation par graphes.
- Prérequis : mathématiques discrètes (ensembles, preuves par induction), bases en structures de données (tableaux, listes) et programmation en C/C++ ou Java ; notions élémentaires d'analyse de complexité (O-notation).
❓ Foire Aux Questions (FAQ)
- Comment choisir entre matrice d'adjacence et liste d'adjacence pour un grand réseau creux ? Pour un graphe creux (E << V²), la liste d'adjacence est préférée : parcours et itération des successeurs se font en
O(V+E)tandis que la matrice exige des coûts enO(V²)pour l'examen de tous les voisins et génère un surcoût mémoire. - Quelles sont les conditions équivalentes caractérisant un arbre et comment les vérifier ? Un arbre est connexe et possède n−1 arêtes ; il est aussi acyclique et toute paire de sommets est reliée par un unique chemin. Un parcours DFS/BFS vérifie la connexité et détecte les cycles ; comparer le nombre d'arêtes à n−1 confirme la propriété structurelle.
