|
 Objectifs
Ce cours est conçu comme une suite du cours de Mathématiques Discrètes de candidature. Il comporte un approfondissement mathématique de la théorie des graphes, ainsi que l'analyse et l'implémentation de certains algorithmes exacts et heuristiques qui sont des outils de bases pour des applications telles que les problèmes de tournées et d'horaires, de conception de réseau, de VLSI etc.
Cahier des charges
Partie 1. Structure et caractérisation des graphes
Concepts de base (connexité, nombre cyclomatique, cycles et co-cycles, mineurs)
Classes de graphes et leur reconnaissance : graphes planaires, série-parallèle, etc...
Partie 2. Problèmes polynomiaux
Flots (théorèmes de Menger et Hall. Algorithmes récents de flot maximum et de flot à coût minimum, analyse de complexité par amortissement etc. , implémentation)
Algorithmes géométriques en 2-D (algorithmes de proximité, enveloppe convexe, diagrammes de Voronoi et triangulations de Delaunay, arbre euclidien minimum, modèles probabilistes)
Partie 3. Problèmes difficiles
Ensembles stables, cliques et coloration (dualité, graphes parfaits, polynome chromatique, algorithme heuristique pour coloration, horaires, etc)
Autres problèmes tels que le voyageur de commerce, le partitionnement de graphes (algorithmes d'échange et application).
Le cours INMA2691 est mentionné dans les programmes suivants :
MAP2 Ingénieur civil en mathématiques appliquées
|
