Composante
École Nationale Supérieure d'Électrotechnique d'Électronique d'Informatique d'Hydraulique et des Télécommunications
Objectifs
Découvrir et maı̂triser quelques apports notoires de la théorie des graphes au travers de méthodes de résolution
de familles classiques de problèmes.
Description
– Recherche de chemins de longueur optimale : méthodes de MOORE-DIJKSTRA et de FORD.
– Applications : Réseaux PERT.
– Recherche de parcours hamiltoniens : méthodes de KAUFMANN/MALGRANGE et DEMOUCRON
– Application : voyageur de commerce. Recherche de mots optimaux : méthode de FORD-FULKERSON.
– Recherche de parcours eulériens : méthode d’ EULER. Problèmes d’affectation : méthode hongroise.
– Arbres, arborescences, cycles et co-cycles. Théorème du nombre cyclomatique.
– Recherche d’arbres de poids optimaux : méthode de KRUSKAL.
– Graphes planaires.