Katona Gyula

Hogyan lett "magyar matematika" a kombinatorika?

III. Véletlen gráfok

A matematikán belül a gráfelmélet egy hatalmas és szerteágazó terület, melyből ez alkalommal csak a véletlen gráfokról fogok szólni. Sok esetben az összekötések véletlenül jönnek létre. Például amikor egy folyékony anyag megfagy, akkor a molekulák között véletlen kapcsolatok jönnek létre. De még jobb példa az internet. Hogy két internetező pont között létrejött-e kapcsolat, az eléggé véletlen. Erdős Pál és Rényi Alfréd az 1960-as években, amikor még számítógép is alig volt, nemhogy internet, kidolgozták a véletlen gráfok elméletét.

7. ábra

Csináljunk most egy ilyen véletlen gráfot a számítógéppel (7. ábra). Legyen n=32 pontunk, és kezdetben ne legyen egyetlen él se közöttük. Azért választottuk a 32-t, mert az a 2 ötödik hatványa, azaz a 32 kettes alapú logaritmusa 5, s ennek szerepe lesz a továbbiakban. Az elmélet kritikus értéke lesz, ami itt:

Most vegyünk két pont között egy élet véletlenül, az összes lehetséges élből egyforma valószínűséggel. Most vegyünk még egyet a maradék, még ki nem választott élek közül, ismét egyforma valószínűséggel és így tovább. Mindig egyforma valószínűséggel vegyünk egyet a még nem választott élek közül. Így persze minden egyes gráfhoz eljuthatunk, és ugyanazzal a valószínűséggel, de ha a gráf bizonyos tulajdonságát, formáját nézzük, akkor már észre fogjuk venni, hogy bizonyos formák gyakoribbak, mint más formák.

8. ábra

összefüggőkomponens

9. ábra