Random spanning tree

Dans cet article, nous proposons un algorithme de complexité polynomiale pour construire un arbre au hasard qui soit un graphe partiel d'un graphe donné. Il consiste essentielleement à construire une arborescence de rang donné sur ce graphe, l'ensemble des arborescences étant ordonné par rapport aux valeurs croissantes de la racine et à racine égale suivant l'ordre lexicographique du codage utilisé pour les arborescences.