Théorie des graphes

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.

Session 1 ou session unique - Contrôle des connaissances

Session 2 - Contrôle des connaissances