Nous commencerons par une revue de quelques problèmes célèbres d’optimisation sur des graphes aléatoires: problème d’appariement (Mézard-Parisi, Aldous), voyageur de commerce (Krauth-Mézard, Aldous)… Leur solution n’est souvent pas simple et la réponse peut paraître de prime abord, contre-intuitive. Nous nous concentrerons ensuite sur le problème le plus simple et le plus ancien de cette famille, initié par Frieze, concernant l’arbre couvrant minimal. Nous en présenterons une approche simple et inédite à notre connaissance, et nous verrons pourquoi l’étude des fluctuations de ce problème amène à considérer de nouvelles questions sur le très classique graphe d’Erdös-Rényi.