Slumpmässigt minsta spännträd

Inom matematik kan ett slumpmässigt minimumspännande träd bildas genom att tilldela slumpmässiga vikter från någon fördelning till kanterna på en oriktad graf , och sedan konstruera grafens minsta spännträd .

När den givna grafen är en komplett graf på n hörn, och kantvikterna har en kontinuerlig fördelningsfunktion vars derivata vid noll är D > 0 , så begränsas den förväntade vikten av dess slumpmässiga minimumspännande träd av en konstant, snarare än att växa som en funktion av n . Närmare bestämt tenderar denna konstant i gränsen (när n går till oändligheten) till ζ (3)/ D , där ζ är Riemann zeta-funktionen och ζ (3) är Apérys konstant . Till exempel, för kantvikter som är likformigt fördelade på enhetsintervallet är derivatan D = 1 och gränsen är bara ζ (3) .

I motsats till likformigt slumpmässigt spännande träd av kompletta grafer, för vilka den typiska diametern är proportionell mot kvadratroten av antalet hörn, har slumpmässiga minimumspännande träd för kompletta grafer typisk diameter proportionell mot kubroten.

Slumpmässiga minimumspännande träd av rutnätsdiagram kan användas för invasionsperkolationsmodeller av vätskeflöde genom ett poröst medium och för labyrintgenerering .