Véletlen gráf

A Wikipédiából, a szabad enciklopédiából

A matematikában a véletlen gráf egy olyan gráf, amely valamilyen véletlen folyamat során jön létre. A véletlen gráfok elmélete a gráfelmélet és a valószínűségszámítás határterületén fekszik, és a véletlen gráfok szokványos tulajdonságait tanulmányozza. A véletlen gráfokat először Erdős Pál és Rényi Alfréd határozta meg 1959-es közös cikkükben ("On Random Graphs", Publ. Math. Debrecen 6, p. 290-297).

Véletlengráf-modellek[szerkesztés | forrásszöveg szerkesztése]

Egy véletlen gráfot létrehozhatunk úgy, hogy egy n elemű csúcshalmazhoz az éleket véletlenszerűen adjuk hozzá. A különböző véletlengráf-modellek különböző valószínűséggel hozzák létre az egyes gráfokat. A legtöbbet tanulmányozott modell az Erdős–Rényi modell (jele G(n,p)), melyben minden élet a többitől függetlenül p valószínűséggel hozunk létre. Egy ehhez közeli kapcsolatban levő modell (jele G(n,M)) olyan gráfokat tartalmaz, melyeknek pontosan M élük van, és minden egyes ilyen gráf pontosan egyforma valószínűséggel fordul elő.

Az utóbbi modell felfogható, mint a \tilde{G}_n jelű véletlengráf-folyamat pillanatképe egy adott pillanatban. Ez a folyamat egy sztochasztikus folyamat, amely n csúccsal indul, melyet nem kötnek össze élek, és minden egyes lépésben egy új élet hoz létre egyforma valószínűséggel választva a hiányzó élek halmazából.

Minden G=(V, E) gráf esetén, a G gráf éleinek E halmaza felfogható, mint egy bináris reláció a csúcsok V halmazán. Ez a G szomszédsági (adjacencia) relációja, melyben minden a és b pontosan akkor áll relációban, ha \{a,b\}\in E, tehát ab a G egy éle. Ennek következtében minden szimmetrikus R reláció a V felett tekinthető egy V gráf élhalmazának.

Létrehozhatunk egy G objektumot, az úgynevezett végtelen véletlen gráfot, amelynek csúcsainak halmaza egy V végtelen halmaz. A G élhalmaza, mint a V feletti R bináris reláció elégítse ki a következő feltételeket:

  1. R irreflexív,
  2. R szimmetrikus, és
  3. megadva V bármely n+m elemét a_1,\ldots, a_n,b_1,\ldots, b_m \in V, létezik egy c\in V csúcs, amely szomszédos a_1,\ldots, a_n csúcsokkal és nem szomszédos b_1,\ldots, b_m egyikével sem.

Kiderül, hogy ha V megszámlálható, akkor izomorfia erejéig csak egyetlen olyan végtelen véletlen gráf létezik, amit Rado-gráfnak nevezünk.

És vannak még további modellek is.

A véletlen gráfok tulajdonságai[szerkesztés | forrásszöveg szerkesztése]

A véletlen gráfok elmélete a véletlen gráfok olyan tulajdonságait tárgyalja, melyek nagy valószínűséggel előfordulnak a gráfok egy bizonyos eloszlása esetén. Például megkérdezhetjük egy meghatározott n és p érték esetén, hogy mekkora a valószínűsége, hogy G(n,p) összefüggő. Ilyen kérdések tanulmányozásakor a kutatók gyakran a véletlen gráfok aszimptotikus viselkedésére összpontosítanak, azokra az értékekre, amelyeket akkor tapasztalnak, ha az n értéke nagyon nagyra növekszik. A perkolációelmélet a véletlen gráfok összefüggőségével foglalkozik abban az esetben is, ha a a véletlen gráf véletlen nagy.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press

Lásd még[szerkesztés | forrásszöveg szerkesztése]