Bases de l’optimisation dans les graphes

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

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.

• 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.