Náhodný pravidelný graf - Random regular graph
A náhodný r-pravidelný graf je graf vybráno z , což označuje prostor pravděpodobnosti všech r-pravidelné grafy na n vrcholy, kde 3 ≤ r < n a č je sudý.[1] Jedná se tedy o určitý druh náhodný graf, ale omezení pravidelnosti významně mění vlastnosti, které budou obsahovat, protože většina grafů není pravidelných.
Vlastnosti náhodných pravidelných grafů
Stejně jako u obecnějších náhodné grafy, je možné dokázat, že určité vlastnosti náhodné r-pravidelné grafy drží asymptoticky téměř jistě. Zejména pro , náhodný r-pravidelný graf velké velikosti je asymptoticky téměř jistý r-připojeno.[2] Jinými slovy, ačkoli r-pravidelné grafy s konektivitou menší než r pravděpodobnost výběru takového grafu má sklon k 0 jako n zvyšuje.
Li > 0 je kladná konstanta a d je nejmenší vyhovující celé číslo
pak asymptoticky téměř jistě náhodný r-pravidelný graf má průměr nejvíce d. K dispozici je také (složitější) spodní mez na průměru r-pravidelné grafy, takže téměř všechny r-pravidelné grafy (stejné velikosti) mají téměř stejný průměr.[3]
Rozdělení počtu krátkých cyklů je také známé: pro pevné m ≥ 3, let Y3,Y4,…,Ym být počet cyklů o délce až m. Pak Yi jsou asymptoticky nezávislé Poissonovo náhodné proměnné s průměrem[4]
Algoritmy pro náhodné pravidelné grafy
Je netriviální implementovat náhodný výběr r-pravidelné grafy efektivně a nestranně, protože většina grafů není pravidelná. The párovací model (taky konfigurační model) je metoda, která trvá č body a rozdělit je do n kbelíky s r bodů v každém z nich. Náhodné párování č bodů a poté uzavření smlouvy r bodů v každém kbelíku do jediného vrcholu, získá r-pravidelný graf nebo multigraf. Pokud tento objekt nemá více hran nebo smyček (tj. Je to graf), je to požadovaný výsledek. Pokud ne, je nutný restart.[5]
Zdokonalení této metody vyvinulo Brendan McKay a Nicholas Wormald.[6]
Reference
- ^ Béla Bollobás, Náhodné grafy, 2. vydání, Cambridge University Press (2001), oddíl 2.4: Náhodné pravidelné grafy
- ^ Bollobás, oddíl 7.6: Náhodné pravidelné grafy
- ^ Bollobás, část 10.3: Průměr náhodných pravidelných grafů
- ^ Bollobás, oddíl 2.4: Náhodné pravidelné grafy (doplněk 2.19)
- ^ N. Wormald, „Modely náhodných pravidelných grafů“, v angličtině Průzkumy v kombinatorice, Cambridge University Press (1999), str. 239-298
- ^ B. McKay a N. Wormald, „Jednotná tvorba náhodných pravidelných grafů středního stupně“ Journal of Algorithms, Sv. 11 (1990), str. 52-67: [1]