Tilfældig almindelig graf - Random regular graph

En tilfældig r -regulær graf er en graf valgt fra , som angiver sandsynlighedsrummet for alle r -regulære grafer på hjørner, hvor og er lige. Det er derfor en bestemt slags tilfældig graf , men regelmæssighedsbegrænsningen ændrer væsentligt de egenskaber, der vil holde, da de fleste grafer ikke er regelmæssige. ${\ displaystyle {\ mathcal {G}} _ {n, r}}$${\ displaystyle n}$${\ displaystyle 3 \ leq r <n}$${\ displaystyle nr}$

Egenskaber ved tilfældige regelmæssige grafer

Som med mere generelle tilfældige grafer er det muligt at bevise, at visse egenskaber ved tilfældigt -regelmæssige grafer holder asymptotisk næsten sikkert . Især for er en tilfældig r -regulær graf af stor størrelse asymptotisk næsten sikkert r -forbundet . Med andre ord, selvom –regelmæssige grafer med mindre tilslutningsmuligheder end der findes, har sandsynligheden for at vælge en sådan graf en tendens til 0 som stigende. ${\ displaystyle m}$${\ displaystyle r \ geq 3}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle n}$

Hvis er en positiv konstant, og er det mindst heltal, der tilfredsstiller ${\ displaystyle \ epsilon> 0}$${\ displaystyle d}$

${\ displaystyle (r-1)^{d-1} \ geq (2+ \ epsilon) rn \ ln n}$

derefter, asymptotisk næsten sikkert, har en tilfældig r -regulær graf højst diameter diameter d . Der er også en (mere kompleks) nedre grænse for diameteren på r -regulære grafer, så næsten alle r -regulære grafer (af samme størrelse) har næsten den samme diameter.

Fordelingen af ​​antallet af korte cyklusser er også kendt: for fast , lad være antallet af cykler med længder op til . Derefter er de asymptotisk uafhængige Poisson -tilfældige variabler med midler ${\ displaystyle m \ geq 3}$${\ displaystyle Y_ {3}, Y_ {4}, ... Y_ {m}}$${\ displaystyle m}$${\ displaystyle Y_ {i}}$

${\ displaystyle \ lambda _ {i} = {\ frac {(r-1)^{i}} {2i}}}$

Algoritmer til tilfældige regelmæssige grafer

Det er ikke -trivielt at implementere det tilfældige udvalg af r -regulære grafer effektivt og på en objektiv måde, da de fleste grafer ikke er regelmæssige. Den parring model (også konfigureringsmodel ) er en metode, som tager NR punkter, og skillevægge dem i n spande med r punkter i hver af dem. Tager en tilfældig matchning af NR punkter, og derefter ordregivende de r punkter i hver spand i et enkelt toppunkt, giver et r -Regelmæssig graf eller Multigraph . Hvis dette objekt ikke har flere kanter eller sløjfer (dvs. det er en graf), er det det nødvendige resultat. Hvis ikke, er en genstart påkrævet.

En forfining af denne metode blev udviklet af Brendan McKay og Nicholas Wormald.

Referencer