Bases de l'Optimisation dans les Graphes (BOG)

dernière modif : le 18/12/2023 à 16:43:33
Titre :
Bases de l'Optimisation dans les Graphes (BOG)
Section :
Obligatoire
État pour cette année :
OPEN
Mots clés :
Ects :
3
Responsable :
Cédric Bentz (CNAM/CEDRIC)
Intervenants :
Cédric Bentz (CNAM/CEDRIC)
Prérequis :

Couplages, Transversaux, Graphes Bipartis, Flots, Coupes, Programmation Linéaire, Méthodes primales-duales\

Objectif :

  1. Apprendre les théorèmes de base en optimisation dans les graphes, et les techniques de preuve associées, et en particulier en ce qui concerne les notions essentielles que sont les couplages, les transversaux, les flots et les coupes.

  2. Apprendre et comprendre les liens entre l'optimisation dans les graphes et la programmation linéaire, notamment à travers l'utilisation des matrices totalement unimodulaires et des approches primales-duales.

Contenu / Plan :

  • Définitions et propriétés des graphes bipartis, des couplages et des transversaux. Preuves du lemme de Berge, du théorème de König-Egerváry, et du théorème de Hall.

  • Définitions et propriétés des flots et des coupes dans les graphes orientés, et notion de graphe d'écart. Preuve détaillée du théorème de Ford-Fulkerson basée sur l'algorithme du même nom. Présentation synthétique de l'algorithme de Busacker-Gowen pour les flots à coût minimum, basé sur le calcul de plus courts chemins dans le graphe d'écart. Notion de $k$-connexité, et preuve du théorème de Menger comme conséquence du théorème de Ford-Fulkerson.

  • Introduction aux matrices totalement unimodulaires, preuves de quelques propriétés utiles, et conséquences en programmation linéaire. Preuve du théorème de König-Egerváry via la dualité en programmation linéaire et les matrices totalement unimodulaires.

  • Preuve du théorème de Ford-Fulkerson via la dualité en programmation linéaire et les matrices totalement unimodulaires, et conséquences (flots et coupes dans les graphes non orientés, plus court chemin, flot à coût minimum, affectation linéaire, etc.). Le théorème de König-Egerváry vu comme une conséquence du théorème de Ford-Fulkerson.

  • Introduction aux approches primales-duales en optimisation dans les graphes, et liens avec les relations d'exclusion en programmation linéaire. Application à la méthode hongroise pour le calcul d'un couplage parfait à coût minimum dans les graphes bipartis.

  • Examen.

Bibliographie :

  • Claude Berge, Graphes et Hypergraphes, Dunod, 1969.
    R. Ahuja, T. Magnanti et J. Orlin. Networks Flows, Theory, Algorithms,

  • Applications. Prentice Hall, Englewood Cliffs, New Jersey (1993).
    Douglas B. West, Introduction to Graph Theory - Second edition, Prentice Hall, 2001.

  • Reinhard Diestel, Graph Theory (Series - Graduate Text In Mathematics), Springer, 2006.

Liens :
(aucun)
Compétences visées :

Savoir écrire et comprendre des preuves en optimisation dans les graphes, basées sur différentes méthodes (preuves constructives, preuves par l'absurde basées sur des contre-exemples minimaux au sens de l'inclusion, etc.).

Comprendre les liens entre les principaux théorèmes de base en optimisation dans les graphes.

Savoir interpréter le dual en variables entières d'un PL(NE) modélisant un problème d'optimisation dans les graphes.

Savoir utiliser la programmation linéaire pour résoudre certains problèmes d'optimisation dans les graphes (résolution via approches primales-duales ou solveur, lorsque la matrices des contraintes est totalement unimodulaire).

Modalités de contrôle :

Examen lors de la dernière séance.