Composante
École Nationale Supérieure d'Électrotechnique d'Électronique d'Informatique d'Hydraulique et des Télécommunications
Objectifs
A partir de famille de problèmes pratiques, faire découvrir des concepts et des méthodes de base de la théorie des graphes. Au terme du cours, l'étudiant doit connaître une dizaine de problématiques importantes et des algorithmes appropriés.
Description
Objet de base
Parcours de longueur optimale : algorithmes de Moore-Dijkstra et de Ford.
Ordonnancement : analyse PER
Parcours hamiltoniens : méthodes de Demoucron et de Kaufman - Malgrange
Parcours eulériens
Flots maximaux : algorithme de Ford-Fulkerson
Affectations optimales : méthode hongroise
Propriétés relatives aux cycles, arbres et arborescences Arbres partiels de poids optimal : algorithme de Kruskal Graphes planaires : formule d'Euler.