MP1/MP*: Option Informatique
Un peu de programmation; arbre recouvrant minimal



Présentation

  • Le premier problème porte sur la programmation en Caml.
  • Le deuxième problème étudie la notion d'arbre recouvrant minimal (en anglais: minimal spanning tree) d'un graphe valué. Nous analysons deux algorithmes de construction d'un tel arbre: le premier a été publié par Kruskal en 1956, le second par Prim en 1957 (mais était déjà connu de Jarnik en 1930).