On s’intéresse à un problème simple d’optimisation combinatoire: les recouvrements de sommets (vertex-covers) minimaux et les recouvrements d’arêtes (matchings) maximaux des arbres étiquetés de Cayley. La probabilité étant uniforme pour une taille fixée, on calcule analytiquement la taille et le nombre moyens de recouvrements extrémaux. Ces calculs s’appuient sur une caractérisation simple des backbones, c’est-à-dire des éléments toujours/jamais couverts. Une évaluation numérique de l’énergie libre est également obtenue en réduisant les arbres aléatoires à des sous-forêts totalement dégénérées.

SPhT CEA