v2.11.0 (5687)

Enseignement spécifique des masters - APM_5RO01_TA : Base de l'optimisation dans les graphes

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)

Domaine Université Paris Saclay

Mention Informatique.

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Inside ENSTA Paris

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS

Pour les étudiants du diplôme Master 2 Parisien Recherche Opérationnelle

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 3 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...
Veuillez patienter