Erdős-Rényi-tétel

1. Sablon:Label

Erdős–Rényi-tétel

Az **Erdős–Rényi-tétel** a valószínűségi gráfelmélet alapvető eredménye, amely a véletlen gráfok szerkezetét és tulajdonságait vizsgálja. A tétel azt írja le, hogy egy $n$ csúcsú véletlen gráfban milyen valószínűséggel jelennek meg bizonyos tulajdonságok a gráf növekedésével.

Véletlen gráf modell (G(n, p))

Az Erdős–Rényi-modellben egy $G(n,p)$ véletlen gráf:

• $n$ csúcsot tartalmaz,
• minden lehetséges él függetlenül jelenik meg a gráfban valószínűséggel $p$.

A tétel megfogalmazása

Legyen $G(n,p)$ egy véletlen gráf, ahol $p=c/n$, és $c>0$. Ekkor az alábbiak állnak fenn nagy $n$-re: 1. Ha $c<1$, akkor $G(n,p)$ gráfban minden komponens várhatóan kicsi, és nincs összefüggő komponens, amely $\mathrm{\Theta }(n)$ méretű lenne. 2. Ha $c=1$, akkor $G(n,p)$-ban egy „óriás komponens” jelenik meg, amely a csúcsok egy részét lefedi. 3. Ha $c>1$, akkor $G(n,p)$ gráf tartalmaz egy összefüggő komponenst, amely a csúcsok pozitív hányadát ($\mathrm{\Theta }(n)$) lefedi.

Ezt a tételt nevezik néha a **gráfkomponens-átmenet tételének**, mert a gráf szerkezete drasztikusan megváltozik $p$ értékének növekedésével.

Magyarázat

Az Erdős–Rényi-tétel a véletlen gráfok viselkedését írja le a csúcsok számának növelésével. A gráf **kritikus pontja** ($c=1$) az az érték, ahol a gráf szerkezete megváltozik:

• $c<1$: Nincs nagy összefüggő komponens, a gráf ritkán kapcsolt.
• $c=1$: Megjelenik egy „óriás komponens”.
• $c>1$: A gráf erősen összefüggővé válik, és az élek száma gyorsan nő.

Ez a viselkedés hasonlít a **fázisátalakulásokhoz**, például a fizikai rendszerekben tapasztalt kritikus viselkedéshez.

Példa

Tegyük fel, hogy $n=100$, és vizsgáljuk $G(100,p)$ különböző értékeinél:

• Ha $p=0.005$ ($c=0.5$), akkor a gráf sok kis komponensből áll, és a legnagyobb komponens mérete $O(\log n)$.
• Ha $p=0.01$ ($c=1$), akkor megjelenik egy „óriás komponens”, amely a csúcsok körülbelül felét lefedi.
• Ha $p=0.02$ ($c=2$), akkor a gráf egyre inkább összefüggő lesz, és az élek többsége egy nagy komponenshez tartozik.

Alkalmazások

Az Erdős–Rényi-tétel széleskörű alkalmazásokkal rendelkezik:

• **Hálózatelemzés:** Internet, közösségi hálózatok, és biológiai rendszerek vizsgálata.
• **Epidemológia:** A fertőző betegségek terjedésének modellezése véletlen gráfok segítségével.
• **Kombinatorika:** Az extremális gráfok szerkezeti tulajdonságainak megértése.
• **Fizika:** Fázisátalakulások vizsgálata gráfmodellekben.

További megjegyzések

• A tétel az Erdős–Rényi modellre vonatkozik, de általánosítható más véletlen gráf modellekre is.
• Az Erdős–Rényi-modell alapvető szerepet játszik a valószínűségi gráfelméletben és az algoritmusok elemzésében.
• A tételt Pál Erdős és Alfréd Rényi vezette be az 1950-es évek végén, és ezzel megalapozta a véletlen gráfok modern elméletét.