La limite d'échelle de l'arbre couvrant minimal sur le graphe complet

Le problème de l'arbre couvrant minimal d'un graphe consiste à munir les arêtes de ce graphe de poids positifs, et de trouver l'arbre (ou les arbres) couvrant(s) du graphe dont la somme des poids le long des arêtes est minimale. Il s'agit d'un des problèmes d'optimisation les plus élémentaires et les plus étudiés, et en particulier, il existe des algorithmes très simples qui permettent de le résoudre.

On s'intéressera dans cet exposé au cas où le graphe est le graphe complet à $n$ sommets, et où les poids sont aléatoires, indépendants. On verra que les distances de graphe typiques dans l'arbre couvrant minimal aléatoire ainsi obtenu sont de l'ordre de $n^{1/3}$, et que, lorsqu'on ré-échelonne les distances par ce facteur, on a convergence de l'arbre vers un objet limite continu quand $n$ tend vers l'infini. On verra comment la construction de cet objet fait intervenir de façon naturel le graphe aléatoire d'Erdös-Rényi.