Leçon 925 : Graphes : représentations et algorithmes.

(2020) 925

Dernier rapport du Jury :

(2019 : 925 - Graphes : représentations et algorithmes.) 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é.

(2017 : 925 - Graphes : représentations et algorithmes.) 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. 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 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é.

Plans/remarques :

2018 : Leçon 925 - Graphes : représentations et algorithmes.


2017 : Leçon 925 - Graphes : représentations et algorithmes.


2016 : Leçon 925 - Graphes : représentations et algorithmes.


2015 : Leçon 925 - Graphes : représentations et algorithmes.


Retours d'oraux :

Pas de retours pour cette leçon.