Descriptif
Les graphes constituent un outil mathématique fondamental de la Recherche Opérationnelle. Ils permettent la modélisation de systèmes extrêmement variés. Ceci explique l'essor de la discipline depuis son apparition. L'objectif de ce cours est d'approfondir les connaissances de théorie des graphes et d'algorithmique dans les graphes.Objectifs pédagogiques
Connaître les grands problèmes de graphes, leur résolution et leurs domaines d'applications. Savoir utiliser un logiciel de traitement de graphes
40 heures en présentiel
Diplôme(s) concerné(s)
- Master 2 Parisien Recherche Opérationnelle
- Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Domaine Université Paris Saclay
Mention Informatique.Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Master 2 Parisien Recherche Opérationnelle
Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 12)- le rattrapage est obligatoire si :
- Note initiale < 8
- Crédits ECTS acquis : 4 ECTS
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 4 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
Dans la première partie, des résultats généraux seront présentés (Graphes k-partis, k-connexité, line graph et connectivité, rappel coupe min/flot max, isthme… Puis on traitera les couplages, facteurs, couvertures et stables.Dans la deuxième partie du cours, on s'intéressera aux relations entre les problèmes d'optimisation dans les graphes et la programmation mathématique, en particulier via la dualité et les approches primales-duales. On s'intéressera aux cas où la matrice associée au problème de graphe est totalement unimodulaire. Des problèmes "difficiles" seront présentés: multiflots/multicoupes, arbres de Steiner, ainsi que la réduction à des problèmes "simples" de l'optimisation dans les graphes dans certains cas particuliers.
Enfin, dans la troisième partie, le sujet sera la coloration des graphes dont les applications sont très nombreuses: aspects de complexité, algorithmiques, études dans des graphes particuliers...
