925 - Graphes : représentations et algorithmes.2021

Rapport du jury 2019

Cette leçon offre une grande liberté de choix au candidat, qui peut choisir de présenter des algorithmes sur des problèmes variés : connexité, diamètre, arbre couvrant, flot maximal, plus court chemin, cycle eulérien, etc. mais aussi des problèmes plus difficiles, comme la couverture de sommets ou la recherche d’un cycle hamiltonien, pour lesquels il pourra proposer des algorithmes d’approximation ou des heuristiques usuelles. Une preuve de correction des algorithmes proposés est évidemment appréciée. Il est attendu que diverses représentations des graphes soient présentées et comparées, en particulier en termes de complexité.