Véletlenszerű számolás

A véletlen gráf a gráfok valószínűségi eloszlásának általános kifejezése . A véletlenszerű gráfok egyszerűen leírhatók egy valószínűségi eloszlással vagy egy véletlen folyamattal , amely létrehozza ezeket a gráfokat [1] . A véletlen gráfelmélet a gráfelmélet és a valószínűségszámítás metszéspontjában található . Matematikai szempontból véletlen gráfokra van szükség a tipikus gráfok tulajdonságaira vonatkozó kérdés megválaszolásához. A véletlenszerű gráfok gyakorlati alkalmazásra találtak minden olyan területen, ahol összetett hálózatokat kell modellezni – nagyszámú véletlenszerű gráfmodellt ismerünk, amelyek különböző típusú összetett hálózatokat tükröznek különböző területeken. Matematikai kontextusban a véletlen gráf kifejezés szinte mindig a véletlen gráfok Erdős-Rényi modelljét jelenti . Más összefüggésekben bármely gráfmodell véletlen gráfot jelent .

Véletlenszerű gráfmodellek

Véletlenszerű gráfot kapunk n izolált csúcsból a csúcsokat összekötő élek véletlenszerű összeadásával. A véletlen gráfok modellezésének célja annak meghatározása, hogy a gráf egy bizonyos tulajdonsága melyik szakaszban jelenik meg [2] . A véletlen gráfok különböző modelljei eltérő valószínűségi eloszlást adnak a grafikonon.

A leggyakrabban tanulmányozott a Hilbert által javasolt eloszlás, amelyet -vel jelölünk , amelyben bármely lehetséges él függetlenül jelenik meg valószínűséggel . Annak a valószínűsége, hogy m élű gráfot kapunk, ahol [3] . $G(n,p)$ $0<p<1$ ${\tbinom {N}{m))$ ${\displaystyle p^{m}(1-p)^{Nm))$ $N={\tbinom {n}{2))$

A hozzá közel álló Erdős-Rényi modell , amelyet jelöl , azonos valószínűséget ad minden olyan gráfnak, amelynek pontosan M éle van. Ha -val jelöljük , akkor elemeket fog tartalmazni , és bármely elem kiesik [2] valószínűséggel . Ezt a modellt úgy tekinthetjük, mint egy véletlenszerű folyamat egy bizonyos időpontra ( M ) készült pillanatképét egy gráfon , amely n él nélküli csúcsból indul ki, és minden lépésben hozzáadódik egy új él, amelyet egyenletesen választunk ki a hiányzó élek halmazából. $G(n,M)$ $N={n \choose 2},$ $0\leq M\leq N$ $G(n,p)$ ${\tbinom {N}{M))$ ${\tbinom {N}{M}}^{-1}$ ${\tilde {G}}_{n}$

Ha viszont végtelen csúcshalmazból indulunk ki, és minden lehetséges élt egymástól függetlenül választunk 0 < p < 1 valószínűséggel, akkor egy végtelen véletlen gráfnak nevezett G objektumot kapunk . A triviális esetek kivételével, amikor p 0 vagy 1, egy ilyen G szinte biztosan a következő tulajdonságokkal rendelkezik:

Tetszőleges n + m elem esetén V - ben van egy c csúcs , amely minden csúcshoz szomszédos, és nem kapcsolódik egyikhez sem . $a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V$ ${\displaystyle a_{1},\ldots ,a_{n))$ ${\displaystyle b_{1},\ldots ,b_{m))$

Kiderült, hogy ha a csúcsok halmaza megszámlálható , akkor izomorfizmusig létezik az egyetlen gráf ilyen tulajdonságokkal, nevezetesen a Rado gráf . Így minden megszámlálható végtelen gráf szinte biztosan Rado-gráf, amelyet emiatt néha egyszerűen véletlen gráfnak neveznek . Hasonló eredmény azonban nem igaz a megszámlálhatatlan gráfokra, amelyekre sok (nem izomorf) gráf létezik, amelyek kielégítik a fenti feltételt.

Egy másik modell, amely általánosítja Hilbert véletlen gráfmodelljét , a véletlenpontos termékmodell . A véletlen pontszorzat gráf minden csúcshoz egy valós vektort társít . Az uv él valószínűsége bármely u és v csúcs között a megfelelő vektorok u • v skaláris szorzatának függvénye .

A hálózati valószínűségi mátrixok véletlenszerű gráfokat modelleznek élvalószínűségek alapjánoly módon, hogy egy adott élegy meghatározott időtartamon belül létezik. Ez a modell kiterjeszthető irányított és nem irányított, súlyozott és súlyozatlan, statikus és dinamikus gráfokra. $p_{i,j}$ $e_{{i,j}}$

M ≃ pN esetén , ahol N az élek lehetséges maximális száma, a leggyakrabban használt modellek a G ( n , M ) és a G ( n , p ), szinte mindig felcserélhetők [4] .

Egy véletlenszerű szabályos gráf olyan speciális esetet képez, amelynek tulajdonságai általában eltérhetnek a véletlen gráfoktól.

Ha van egy véletlen gráf modellünk, akkor a gráfokon lévő bármely függvény valószínűségi változóvá válik . A modell tanulmányozásának feladata egy tulajdonság előfordulási valószínűségének meghatározása, vagy legalább becslése [3] .

Terminológia

A "majdnem biztos" kifejezés a véletlenszerű gráfok kontextusában olyan terek és valószínűségek sorozatára utal, amelyeknél a hiba valószínűsége nullára irányul [3] .

Véletlenszerű gráfok tulajdonságai

A véletlen gráfelmélet a véletlen gráfok tipikus tulajdonságait vizsgálja, amelyek nagy valószínűséggel érvényesek egy bizonyos eloszlásra kapott gráfokra. Például megkérdezhetjük adott n és p érték esetén , hogy mekkora a valószínűsége annak, hogy G ( n , p ) összefügg . Az ilyen kérdések tanulmányozása során a kutatók gyakran a véletlenszerű gráfok aszimptotikus viselkedésére összpontosítanak – azokra az értékekre, amelyekre a különböző valószínűségek hajlamosak az n növekedésével . A perkolációs elmélet a véletlen gráfok összekapcsolhatóságát írja le, különösen a végtelenül nagy gráfokét.

A perkoláció egy gráf (hálózatnak is nevezik) stabilitásához kapcsolódik. Legyen adott egy n csúcsú és átlagos fokszámú véletlen gráf . Távolítsuk el az élek egy véletlenszerű részét, és hagyjunk egy részt. Létezik egy kritikus perkolációs küszöb , amely alatt a hálózat töredezetté válik, felette pedig hatalmas kapcsolódási komponensek [1] [5] [4] [6] [7] [8] . $\langle k\rangle$ $1-p$ $p$ $p_{c}={\tfrac {1}{\langle k\rangle ))$ $p_{c}$

A véletlenszerű gráfokat széles körben alkalmazzák a valószínűségi módszerben , amikor bizonyos tulajdonságokkal rendelkező gráfok létezését próbálják bizonyítani. Egy tulajdonság létezése véletlen gráfokon gyakran azt eredményezheti, hogy a Szémerédy-féle szabályossági lemma szinte minden gráf esetében létezik.

Véletlenszerű reguláris gráfok esetén G ( n , r -reg) az r -reguláris gráfok halmaza, ahol r = r ( n ), ahol n és m pozitív egész számok , 3 ≤ r < n és rn = 2 m egyenletes [2] .

A G gráf fokozatainak sorrendje G n - ben csak a halmazok éleinek számától függ [2]

V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.

Ha egy G M véletlenszerű gráfban az M élek halmaza elég nagy ahhoz, hogy szinte minden G M minimális foka legalább 1, akkor szinte minden G M összefügg, és még n esetén is szinte minden G M tartalmaz egy tökéletest. egyezés . Különösen abban a pillanatban, amikor az utolsó izolált csúcs eltűnik, szinte minden véletlenszerű gráfban a gráf összekapcsolódik [2] .

Szinte minden olyan folyamat, amely páros számú csúcsú gráfot hoz létre, amikor eléri az 1-es minimális fokot, vagy véletlen gráfot, ha valamivel több, mint ( n /4)log( n ) él 1-hez közeli valószínűséggel, biztosítja a teljes egyezés, kivéve talán egy csúcsot.

Néhány c konstans esetén szinte minden n csúcsú és legalább cn log( n ) élű gráf Hamilton -féle . Ha a valószínűség 1-re hajlik, ha egy olyan élt adunk hozzá, amely a gráf minimális fokát 2-re emeli, az Hamilton-féle lesz.

Véletlenszerű grafikonok színezése

Adott egy n - rendű véletlenszerű G gráf, amelynek csúcsai V ( G ) = {1, …, n }, a színezés egy mohó algoritmussal érhető el (az 1-es csúcs 1-es színnel van festve, a 2-es csúcs 1-es színt kap, ha nem szomszédos). 1-re, ellenkező esetben 2-es színt kap, és így tovább) [2] .

Random Trees

A véletlenszerű fa egy véletlenszerű folyamat által létrehozott fa vagy irányított fa . Az n rendű és M ( n ) méretű véletlen gráfok nagy tartományában a k rendű fák számának eloszlásaaszimptotikusan a Poisson-törvény hatálya alá tartozik . A véletlenszerű fák típusai közé tartoznak az egyenletes feszülő fák , a véletlenszerű minimális fedőfák , a véletlenszerű bináris fák , a derékszögű fák , a gyorskereső véletlenszerű fák , a Brown-fák és a véletlenszerű erdők .

Történelem

A véletlen gráfokat először Erdős és Rényi definiálta 1959-ben megjelent "On Random Graphs" [8] című könyvében , és egymástól függetlenül Hilbert "Random graphs" [5] című cikkében .

Lásd még

Jegyzetek

↑ 1 2 Bollobás Béla Véletlenszerű grafikonok. – Cambridge University Press, 2001.
↑ 1 2 3 4 5 6 Bollobás Béla Véletlenszerű grafikonok. – London: Academic Press Inc, 1985.
↑ 1 2 3 Bollobás Béla Valószínűségi kombinatorika és alkalmazásai. – Providence: American Mathematical Society, 1991.
↑ 1 2 Matematikai eredmények skála nélküli véletlen grafikonokon. Kézikönyv a gráfokról és hálózatokról / S. Bornholdt, HG Schuster. – Weinheim: Wiley VCH, 2003.
↑ 1 2 E. N. Gilbert. Véletlenszerű grafikonok. — Annals of Mathematical Statistics. - 1959. - T. 30. - S. 1141-1144. - doi : 10.1214/aoms/1177706098 .
↑ M.E.J. Newman. Hálózatok: Bevezetés. – Oxford, 2010.
↑ Reuven Cohen, Shlomo Havlin . Összetett hálózatok: szerkezet, robusztusság és funkció . – Cambridge University Press, 2010.
↑ 1 2 P. Erdős , A Rényi . Véletlenszerű grafikonokon I. — Publ. Math. - 1959. - T. 6. - S. 290-297.

Irodalom

A.M. Raygorodsky . Véletlenszerű diagrammodellek. — M .: MTsNMO , 2011. — 136 p. - ISBN 978-5-94057-840-6 .

Szótárak és enciklopédiák	nagy kínai Nagy orosz
Bibliográfiai katalógusokban	BNF : 12288320t J9U : 987007563131005171 LCCN : sh85111348 NKC : ph664004