Graphes et optimisation discrète

Au préalable, les outils nécessaires au développement, à la compréhension et à la description des méthodes seront
présentés :
- éléments de calcul différentiel
- théorie des graphes

Programme résumé :
Préambule :
Tous les algorithmes étudiés dans le cours sont présentés ainsi :
- principe de l'algorithme,
- l'algorithme
- étude d'un exemple
- justification de l'algorithme et analyse de sa complexité et/ou de sa convergence

Partie Graphes et applications:
- Généralités : définitions, terminologies
- Parcours de graphes (orientés, non orientés) :
    . parcours en profondeur (version récursive, itérative, forêt couvrante associée)
    . parcours en largeur
- Connexité et forte connexité : définitions, recherche de composantes connexes, fortement connexes
- Plus courts chemins :
      . définitions, conditions d'existence
      . les algorithmes : Dijsktra, Bellman, Floyd
- Arbres de recouvrement minimum :
      . définitions, conditions d'existence, d'unicité
      . les algorithmes : Kruskal, Prim
-  Etudes de problèmes :  problèmes de coloration, tri topologique, ...

Algorithme et Programmation, Analyse et Algèbre

Reconnaître les différents problèmes d'optimisation et associer à chacun d'eux une méthode de résolution.

Ouvrages de références et/ou conseillés:
-  Introduction à l'analyse numérique matricielle et à l'optimisation, Jacques-Louis Lions, Philippe G. Ciarlet
-  Graphes, Berge, Gauthier-Villars, 1983
-  Théorie des graphes et applications , J.C. Fournier, Hermès 2006