Numărătoare aleatorie

Graficul aleatoriu este un termen general pentru distribuția de probabilitate a graficelor . Graficele aleatoare pot fi descrise simplu printr-o distribuție de probabilitate sau un proces aleator care creează aceste grafice [1] . Teoria grafurilor aleatoare se află la intersecția dintre teoria grafurilor și teoria probabilității . Din punct de vedere matematic, graficele aleatoare sunt necesare pentru a răspunde la întrebarea despre proprietățile graficelor tipice . Graficele aleatoare au găsit aplicații practice în toate domeniile în care rețelele complexe trebuie modelate - sunt cunoscute un număr mare de modele de grafice aleatoare, care reflectă diferite tipuri de rețele complexe în diverse domenii. Într-un context matematic, termenulgraficul aleatoriu înseamnă aproape întotdeauna modelul grafic aleatoriu Erdős-Rényi . În alte contexte, orice model de grafic înseamnă un grafic aleatoriu .

Modele aleatorii grafice

Un grafic aleator este obținut dintr-un set de n vârfuri izolate prin adăugarea aleatorie succesivă a muchiilor care leagă vârfurile. Scopul modelării graficelor aleatoare este de a determina în ce stadiu apare o anumită proprietate a graficului [2] . Diferite modele de grafice aleatoare oferă diferite distribuții de probabilitate pe grafic.

Cea mai frecvent studiată este distribuția propusă de Hilbert și notată cu , în care orice muchie posibilă apare independent cu probabilitate . Probabilitatea de a obține un grafic cu m muchii este unde [3] . $G(n,p)$ $0<p<1$ ${\tbinom {N}{m)}$ $p^{m}(1-p)^{Nm)$ $N={\tbinom {n}{2))$

Modelul Erdős-Rényi , care este apropiat de acesta , notat cu , oferă aceeași probabilitate tuturor graficelor care au exact M muchii. Dacă este notat cu , atunci va conține elemente și orice element va fi eliminat cu probabilitate [2] . Acest model poate fi considerat ca un instantaneu pentru un anumit punct de timp ( M ) al unui proces aleatoriu pe un grafic care pornește de la n vârfuri fără muchii și la fiecare pas se adaugă o nouă muchie, aleasă uniform din setul de muchii lipsă. $G(n,M)$ $N={n \alegeți 2},$ $0\leq M\leq N$ $G(n,p)$ ${\tbinom {N}{M)}$ ${\tbinom {N}{M}}^{-1}$ ${\tilde {G}}_{n}$

Dacă, pe de altă parte, pornim de la o mulțime infinită de vârfuri și alegem fiecare muchie posibilă independent cu probabilitatea 0 < p < 1, obținem un obiect G numit grafic aleatoriu infinit . Cu excepția cazurilor triviale în care p este 0 sau 1, un astfel de G are aproape sigur următoarele proprietăți:

Având în vedere orice n + m elemente , există un vârf c în V care este adiacent fiecărui vârf și nu este conectat la niciunul dintre . $a_{1},\ldots,a_{n},b_{1},\ldots,b_{m}\in V$ $a_{1},\ldots,a_{n)$ $b_{1},\ldots,b_{m)$

Rezultă că dacă mulțimea de vârfuri este numărabilă , atunci există, până la izomorfism , singurul graf cu astfel de proprietăți, și anume graful Rado . Astfel, orice graf infinit numărabil este aproape sigur un graf Rado, care din acest motiv este uneori numit pur și simplu un graf aleatoriu . Cu toate acestea, un rezultat similar nu este valabil pentru graficele nenumărate, pentru care există multe grafice (neizomorfe) care satisfac condiția de mai sus.

Un alt model care generalizează modelul grafic aleator al lui Hilbert este modelul de produs punctual aleator . Graficul de produs punctual aleator asociază un vector real cu fiecare vârf . Probabilitatea unei muchii uv între orice vârfuri u și v este o funcție a produsului scalar u • v al vectorilor respectivi.

Matricele de probabilitate de rețea modelează grafice aleatorii în termeni de probabilități de margineîn așa fel încât o anumită marginesă existe într-o anumită perioadă de timp. Acest model poate fi extins la grafice direcționate și nedirecționate, ponderate și neponderate, statice și dinamice. $p_{i,j)$ $e_{{i,j}}$

Pentru M ≃ pN , unde N este numărul maxim posibil de muchii, cele mai frecvent utilizate modele sunt G ( n , M ) și G ( n , p ), aproape întotdeauna interschimbabile [4] .

Un graf regulat aleatoriu formează un caz special care are proprietăți care, în general, pot diferi de graficele aleatoare.

Dacă avem un model de grafic aleatoriu, orice funcție din grafice devine o variabilă aleatoare . Sarcina studierii acestui model este de a determina, sau cel puțin de a estima probabilitatea de apariție a unei proprietăți [3] .

Terminologie

Termenul „aproape sigur” în contextul graficelor aleatoare se referă la o succesiune de spații și probabilități astfel încât probabilitatea de eroare tinde spre zero [3] .

Proprietăți ale graficelor aleatoare

Teoria grafurilor aleatoare studiază proprietățile tipice ale grafurilor aleatoare care sunt valabile cu un grad ridicat de probabilitate pentru grafurile obținute pentru o anumită distribuție. De exemplu, putem întreba, pentru valorile date ale lui n și p , care este probabilitatea ca G ( n , p ) să fie conectat . În studierea unor astfel de întrebări, cercetătorii se concentrează adesea pe comportamentul asimptotic al graficelor aleatoare - valorile la care tind diversele probabilități pe măsură ce n crește . Teoria percolației descrie conectivitatea graficelor aleatoare, în special a celor infinit de mari.

Percolarea este legată de stabilitatea unui grafic (numit și rețea). Să fie dat un grafic aleatoriu cu n vârfuri și grad mediu . Să înlăturăm o parte aleatorie a marginilor și să lăsăm o parte. Există un prag critic de percolare , sub care rețeaua devine fragmentată, în timp ce deasupra există componente uriașe de conectivitate [1] [5] [4] [6] [7] [8] . $\langle k\rangle$ $1-p$ $p$ $p_{c}={\tfrac {1}{\langle k\rangle ))$ $p_{c}$

Graficele aleatorii sunt utilizate pe scară largă în metoda probabilistică atunci când se încearcă demonstrarea existenței graficelor cu anumite proprietăți. Existența unei proprietăți pe grafice aleatoare poate avea adesea o consecință, după lema de regularitate a lui Szémerédy , a existenței acestei proprietăți pentru aproape toate graficele.

Pentru graficele regulate aleatoare , G ( n , r -reg) este mulțimea de grafice r -regulate cu r = r ( n ) astfel încât n și m sunt numere întregi pozitive , 3 ≤ r < n și rn = 2 m chiar [2] .

Secvența de grade a unui grafic G în G n depinde doar de numărul de muchii din mulțimi [2]

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

Dacă mulțimea muchiilor M dintr-un grafic aleatoriu G M este suficient de mare încât aproape toate G M au un grad minim de cel puțin 1, atunci aproape orice G M este conex și, chiar și pentru n , aproape orice G M conține un perfect potrivire . În special, în momentul în care ultimul vârf izolat dispare, în aproape toate graficele aleatoare, graficul devine conex [2] .

Aproape orice proces de construire a unui grafic cu un număr par de vârfuri când se atinge un grad minim de 1 sau a unui grafic aleatoriu când se atinge puțin mai mult de ( n /4)log( n ) muchii cu o probabilitate apropiată de 1 asigură existența o potrivire completă, cu excepția poate unui vârf.

Pentru o constantă c , aproape fiecare graf etichetat cu n vârfuri și cel puțin cn log( n ) muchii este hamiltonian . Cu probabilitatea tinde spre 1, adăugarea unei muchii care ridică gradul minim al unui grafic la 2 îl face Hamiltonian.

Colorarea graficelor aleatorii

Având în vedere un grafic aleatoriu G de ordinul n cu vârfuri V ( G ) = {1, …, n }, colorarea poate fi obținută folosind un algoritm lacom (vârful 1 este vopsit cu culoarea 1, vârful 2 capătă culoarea 1 dacă nu este adiacent la 1, altfel capătă culoarea 2 și așa mai departe) [2] .

Arbori aleatoriu

Un arbore aleatoriu este un arbore sau un arbore direcționat format printr-un proces aleatoriu . Într-o gamă largă de grafice aleatorii de ordinul n și mărimea M ( n ), distribuția numărului de arbori de ordinul k este supusă asimptotic legii lui Poisson . Tipurile de arbori aleatori includ arbori de întindere uniform , arbori de întindere minim aleatori , arbori binari aleatoriu , arbori cartezieni , arbori aleatoriu cu căutare rapidă , arbori brownieni și păduri aleatorii .

Istorie

Graficele aleatoare au fost definite pentru prima dată de Erdős și Rényi în cartea lor din 1959 „On Random Graphs” [8] și independent de Hilbert în lucrarea sa „Random graphs” [5] .

Vezi și

Note

↑ 1 2 Béla Bollobás Grafice aleatorii. — Cambridge University Press, 2001.
↑ 1 2 3 4 5 6 Béla Bollobás Grafice aleatorii. — Londra: Academic Press Inc, 1985.
↑ 1 2 3 Béla Bollobás Combinatorică probabilistică și aplicațiile sale. — Providence: Societatea Americană de Matematică, 1991.
↑ 1 2 Rezultate matematice pe grafice aleatoare fără scară. Manual de grafice și rețele / S. Bornholdt, HG Schuster. — Weinheim: Wiley VCH, 2003.
↑ 1 2 E. N. Gilbert. Grafice aleatorii. — Analele statisticii matematice. - 1959. - T. 30. - S. 1141-1144. - doi : 10.1214/aoms/1177706098 .
↑ M.E.J. Newman. Rețele: o introducere. — Oxford, 2010.
↑ Reuven Cohen, Shlomo Havlin . Rețele complexe: structură, robustețe și funcție . — Cambridge University Press, 2010.
↑ 1 2 P. Erdős , A Rényi . Pe graficele aleatorii I . — Publ. Matematică. - 1959. - T. 6. - S. 290-297.

Literatură

A.M. Raygorodsky . Modele aleatorii grafice. — M .: MTsNMO , 2011. — 136 p. - ISBN 978-5-94057-840-6 .

Dicționare și enciclopedii	mare chinezesc Rusă mare
În cataloagele bibliografice	BNF : 12288320t J9U : 987007563131005171 LCCN : sh85111348 NKC : ph664004