Établissement
INP - ENSEEIHT
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.