Leçon #1240
Actif : false
Numero : 925
Titre : Graphes : représentations et algorithmes.2021
Créé le : 23/07/2026 12:42
Mis à jour : 23/07/2026 12:42
Rapport du jury 2017
Cette leçon offre une grande liberté de choix au candidat, qui peut décider 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.\rmais 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 sera é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é.
Cette leçon offre une grande liberté de choix au candidat, qui peut décider 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.\rmais 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 sera é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é.
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é.
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é.