Revenir à Licence d’ informatique

Théorie des graphes

Programme

  • Théorie des graphes: définitions et propriétés élémentaires, chemins, chaines et connexité, flots, couplages, recouvrements, graphes planaires, coloriages.
  • Programmation dynamique: certaine, incertaine et en horizon limité.
  • Programmation linéaire en nombre entiers: le problème du sac à dos simple et multidimensionnel, méthodes heuristiques et par approximations.
  • Programmation linéaire: méthode du simplexe, dualité, écarts complémentaires, algorithme dual, algorithme du simplexe en variables bornées, le problème du transport.

Bibliographie

  • Eléments d’algorithmique, D. Beauquier, J. Berstel, P. Chrétienne, [Masson]
  • Graphes et hypergraphes, C. Berge, [Dunod]
  • Graphes, C. Berge, [Gauthier-Villars]
  • Graphes et algorithmes, M. Gondran, M. Minoux, [Eyrolles]