Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Beharangozó: Virág Bálint: Véletlen gráfok

Virág Bálint

iskolánk volt diákja, a kanadai Toronto Egyetem munkatársa

Véletlen gráfok

2010. október 5.



Feladat Két párhuzamos út (e és f) között A) 1× 2-es, B) 2× 3-as négyzetrács elrendezésben terveznek utakat. Ha a rácspontok közötti mindegyik kis útszakasz (az egyik esetben 5, a másikban 13 ilyen van) egymástól függetlenül ½ valószínűséggel épül meg illetve nem épül meg, akkor mennyi az esélye, hogy az e, f utak egyikéről át lehet jutni a másikra a megépülő utakon át?


1. ábra

Általában, ha egy gráfból úgy készítünk új gráfot, hogy éleit egymástól függetlenül <>i>p valószínűséggel megtartjuk, 1-p valószínűséggel pedig elhagyjuk, akkor perkolációról beszélünk. A perkolációk vizsgálatának nagy lökést adott a felismerés, hogy általuk nagy hálózatok is modellezhetők, elemezhetők.

Az egyik tipikus kérdés, hogy a létrejövő „nagy'” hálózatban vagyis gráfban van-e „nagy” összefüggő részgráf, tehát csúcspontok egymással élekkel összekötésben álló rendszere. A „nagy”-ot a matematika a „végtelen”-nel nevezi meg, így pl már bizonyított az alábbi két eredmény:


2. ábra

I. tétel Ha a kiinduló gráf a 2. ábrán látható, de végtelenül folytatódó 3-reguláris fa és p<½, akkor nulla annak a valószínűsége, hogy a perkolációban van végtelen összefüggő részgráf.

II. tétel (mindegyik irányban) végtelen négyzetrács perkolációjában pontosan akkor lesz végtelen összefüggő részgráf, hogy ha p<½.

A téma nehézségét mutatja, hogy a II. tétel három dimenziós változata máig megoldatlan.


Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.