Arbres couvrants aléatoires de poids minimal et fonction zêta de Riemann

par Shenghui Yang
Article original
Considérez l’expérience suivante :
1. Commencez par un graphe complet à n nœuds, chaque nœud est connecté à tous les autres nœuds.
2. Attribuez à chaque arête un poids aléatoire, choisi uniformément dans l’intervalle [0,1].
3. Calculez l’arbre couvrant de poids minimal (ACM) du graphe.
4. Notez la somme des poids des arêtes dans cet ACT.
Répétez maintenant ce processus à mesure que
n
devient de plus en plus grand. Le fait remarquable est le suivant : le poids total attendu de l’ACT aléatoire s’approche de la valeur de la fonction zêta de Riemann en 3 :
In[]:=
Style
apery’s constant
MATHWORLD TERMS

definition
[[1]],12,FontFamily->"Arial"//Framed
Out[]=
Apéry’s constant is defined by
ζ(3)1.2020569…,
(OEIS A002117) where
ζ(z)
is the Riemann zeta function. Apéry proved that
ζ(3)
is irrational, although it is not known if it is transcendental. Sorokin and Nesterenko subsequently constructed independent proofs for the irrationality of
ζ(3)
. Apéry’s proof involved use of the continued fraction
6
ζ(3)
5+
∞
K
n1
-
6
n
17
3
n
+
3
(n+1)
-12(2n+1)
.
En d’autres termes, un processus purement combinatoire‑probabiliste sur des graphes aléatoires vous conduit de façon inattendue directement à la célèbre constante d’Apéry. Ce théorème a été démontré de manière rigoureuse par A.M. Frieze sur la base des travaux de Walkup, P. Erdös et A. Rényi.
À des fins de visualisation, choisissez un petit graphe complet afin que les étiquettes ne soient pas trop serrées :
In[]:=
n=7;
Attribuez uniformément le poids entre [0,1] sur chaque arête :
In[]:=
ew=RandomReal[{0,1},Binomial[n,2]];
Visualisez le graphe avec le poids des arêtes :
In[]:=
g1=CompleteGraph[n,EdgeWeight->ew,EdgeLabels->"EdgeWeight",EdgeLabelStyle->12,VertexLabels->"Name"]
Out[]=
Trouvez l’arbre couvrant de poids minimal en tant que sous-graphe avec des poids d’arêtes :
In[]:=
mst=FindSpanningTree[g1,VertexLabels->"Name"];​​Grid[{{mst,HighlightGraph[Annotate[g1,EdgeLabels->None],Style[mst,Thickness[0.03],StandardOrange]]}},Dividers->All]
Out[]=
Calculez la longueur de l’arbre couvrant de poids minimal
In[]:=
AnnotationValue[mst,EdgeWeight]
Out[]=
{0.13611,0.362387,0.0901108,0.194014,0.0131534,0.128264}
In[]:=
Total[%]
Out[]=
0.924039
Faites la même chose pour les graphes K-complets pour
K=3,4,5,6,7,10,100,500
 :
v={3,4,5,6,7,10,100,500};
In[]:=
res=Mean@Table[Total[AnnotationValue[​​FindSpanningTree@CompleteGraph[i,EdgeWeight->RandomReal[{0,1},Binomial[i,2]]]​​,EdgeWeight]],{t,10},{i,v}]
Out[]=
{0.642456,0.860396,0.80748,1.08323,1.0249,1.00683,1.19652,1.21045,1.20355}
In[]:=
Grid[{v,res},Dividers->All]
Out[]=
3
4
5
6
7
10
100
500
1000
0.642456
0.860396
0.80748
1.08323
1.0249
1.00683
1.19652
1.21045
1.20355
Nous pouvons également tester le théorème de manière répétée pour un grand graphe complet avec des noyaux parallèles :
In[]:=
LaunchKernels[];
Testez sur 1000 copies de graphes 1000-complets avec des poids d’arêtes aléatoires :
In[]:=
nv=1000;​​data=ParallelTable[Total[AnnotationValue[​​FindSpanningTree@CompleteGraph[nv,EdgeWeight->RandomReal[{0,1},Binomial[nv,2]]]​​,EdgeWeight]],{i,1000}];
Voici la répartition des longueurs de leurs arbres couvrants de poids minimal :
In[]:=
Histogram[data,{0.005}]
Out[]=
La valeur est proche de ζ(3) :
In[]:=
{Mean[data],Zeta[3.]}
Out[]=
{1.20125,1.20206}

Référence

A.M. Frieze, On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, Volume 10, Issue 1, 1985, Pages 47-56, ISSN 0166-218X, https://doi.org/10.1016/0166-218X(85)90058-7.

CITER CE NOTEBOOK

Arbres couvrants aléatoires de poids minimal et fonction zêta de Riemann​
par Shenghui Yang​
Communauté Wolfram, CHOIX DE L’ÉQUIPE, 17 novembre 2025
​https://community.wolfram.com/groups/-/m/t/3577126