Graphes et algorithmique - Maîtriser les fondamentaux

Objectifs d'apprentissage

• Comprendre les concepts fondamentaux des graphes et leurs applications en algorithmique.
• Maîtriser les différentes représentations des graphes (matrices d'adjacence, listes d'adjacence).
• Appliquer les algorithmes de parcours (DFS, BFS) pour résoudre des problèmes de recherche et d'optimisation.
• Étudier les propriétés des arbres et des arbres couvrants de poids minimum (algorithmes de Kruskal et Prim).
• Résoudre des problèmes de plus courts chemins (Dijkstra, Bellman-Ford, Floyd-Warshall).
• Analyser les graphes orientés sans circuit et leurs applications en ordonnancement.
• Explorer les concepts de couplage maximum dans les graphes bipartis et de flot maximum dans les réseaux.
• Étudier la connexité des graphes et les algorithmes associés.
• Aborder les problèmes de coloration de graphes et leurs implications théoriques.

Public cible

Ce cours s'adresse aux étudiants en informatique, en mathématiques appliquées ou en ingénierie ayant des bases en algorithmique et en structures de données. Il est également adapté aux professionnels souhaitant approfondir leurs connaissances en théorie des graphes pour des applications en optimisation, réseaux ou intelligence artificielle. Une familiarité avec les notions de complexité algorithmique et de programmation est recommandée.

Contenu détaillé

Généralités

Introduction aux graphes : définitions, terminologie (sommets, arêtes, degrés), types de graphes (orientés, non orientés, pondérés). Représentations en mémoire et complexité associée.

Arbres

Propriétés des arbres, arbres libres et enracinés. Algorithmes de construction et de recherche. Applications en structures hiérarchiques.

Parcours dans les Graphes

Algorithmes de parcours en profondeur (DFS) et en largeur (BFS). Applications à la détection de cycles, composantes connexes et tri topologique.

Graphes orientés sans circuit

Caractérisation et algorithmes de détection. Utilisation dans l'ordonnancement de tâches (méthode PERT).

Arbre couvrant de poids minimum

Algorithmes gloutons : Kruskal et Prim. Preuves d'optimalité et complexité. Applications en conception de réseaux.

Chemin de coût minimum

Problèmes de plus courts chemins à source unique (Dijkstra, Bellman-Ford) et toutes paires (Floyd-Warshall). Cas des poids négatifs.

Facteurs d’un graphe

Définition des facteurs et des couplages. Lien avec les problèmes d'affectation et d'optimisation combinatoire.

Couplage maximum dans les bipartis

Théorème de König et algorithme hongrois. Applications en affectation de ressources.

Connexité

Composantes connexes, points d'articulation et ponts. Algorithmes de Tarjan pour les graphes fortement connexes.

Flot maximum dans un réseau

Théorème de Ford-Fulkerson. Algorithmes de résolution (Edmonds-Karp). Applications en transport et logistique.

Coloration de graphes

Nombre chromatique, théorème des quatre couleurs. Algorithmes approchés et applications en emploi du temps.

Méthodologie

Le cours combine des exposés théoriques, des études de cas pratiques et des travaux dirigés en programmation. Des projets permettront d'appliquer les algorithmes sur des jeux de données réels.