Théorie des graphes

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.

Bibliographie

Graphes et hypergraphes - Auteur : Claude Berge - Editeur : Dunod , 1975
Graphes et Algorithmes - Auteur : Michel Gondran et Michel Minoux - Editeur : Eyrolles , 1980

Session 1 ou session unique - Contrôle des connaissances

Session 2 - Contrôle des connaissances