1° permettre aux étudiants de se familiariser avec les graphes, qui sont un outil essentiel de l’optimisation combinatoire avec de nombreuses applications à divers problèmes dans les réseaux, et qui apparaîtront dans d’autres cours. L’accent sera mis sur la modélisation et sur l’existence de résultats généraux et de diverses méthodes de résolution.
2° apprendre comment modéliser certains problèmes susceptibles d'être résolus par des méthodes d’Optimisation Combinatoire et de proposer une introduction aux concepts de base de la Recherche Opérationnelle.

1- Exploration, composantes connexes, arbres, arbre couvrant (réseaux LAN, ou algorithmes de configuration de réseau dynamique)
2 - Chemins, flots, et connectivité, flot maximum et coupe minimum (acheminement), connexité (résistance aux pannes des réseaux), problèmes de chemins arcs disjoints (affectation de trafic).
3 - Compatibilité, conflits, domination : couplage et affectation (affectation de clients a des ressources), coloration (routage dans les réseaux optiques), absorbant (positionnement de concentrateurs dans un réseau)
4 - Autres problèmes divers : cycle eulérien, cycle hamiltonien; diffusion (broadcasting et gossiping), localisation et implantation, capacité de Shannon d’un graphe.
5 - Introduction aux ordonnancements.

Aucun, mais a priori, un élève doit pouvoir suivre le raisonnement formel avec un certain niveau d’abstraction.

W. BIENIA : "Introduction à la recherche opérationnelle et optimisation combinatoire", polycopié 2007
V. CHVATAL : "Linear programming", W.H. Freeman Company, 1983
G. FINKE at al : “Recherche Opérationnelle et réseaux” traité IGAT, HERMES, 2002
M. SAKAROVITCH : "Optimisation combinatoire vol.I et II", Hermann, 1984
N.H. XUONG : "Mathématiques discrètes et informatique", Masson, 1992.
I. Charon, A. Germa, O. Hudry, Méthodes d’Optimisation Combinatoire, Collection Pédagogique de Télécommunication, Masson, Paris, 1996
M. Gondran, M. Minoux, Graphes et Algorithmes (2ème ed. revue et augmentée). Eyrolles, Paris, 1985.
J.A. Bondy, U.S.R. Murty, Graph Theory with Applications. North-Holland, 1981.
A. Gibbons, Algorithmic Graph Theory.Cambridge University Press, 1988

Examen écrit de 2 heures.

N1=E1
N2=E2