2016. ápr 30.

A matematika új kihívásai: hogyan értsük meg a nagyon nagy véges struktúrákat?

írta: Janguli
A matematika új kihívásai: hogyan értsük meg a nagyon nagy véges struktúrákat?

"Pázmány Péter előadás" - Lovász László

Nagyon nagy gráfok

A tudomány és a technika világában igen sok struktúrát, jelenséget írunk le hálózattal, matematikai kifejezéssel, gráffal, és ezek a gráfok igen nagy méretűek tudnak lenni. Lássunk néhány példát!

Az internet talán a leglátványosabb – és különösen érdekes abból a szempontból, hogy teljes mértékben ember alkotta objektum. Igazából az internet leírásához különböző gráfokat használunk. Az internet fizikai struktúráját leíró internetgráf csúcsait a különböző elektronikai eszközök (számítógépek, routerek, nyomtatók stb.) alkotják, az azokat összekötő éleket pedig a közöttük fennálló összeköttetések (kábelek, rádiókapcsolatok). Az internet logikai struktúráját leíró világhálógráf (webgráf) csúcsai a világhálóról elérhető lapok, élei pedig az egyik lapról a másikra mutató hiperlinkek.

Ezek a gráfok igen nagyok, milliárdnyi csúccsal, és hiába van ember alkotta objektumról szó, a világháló vagy az internet pontos struktúráját leírni igen nehéz. A hálózatokról az elektromos hálózatok jutnak eszünkbe, és ezek között is vannak hatalmas méretűek: például a chipek, az integrált áramkörök, melyek több százezer tranzisztorból állnak. Ezek, az internettel ellentétben, nem spontán módon, lokálisan növekednek, hanem teljes mértékben ember tervezte objektumok. Mégis, ha kicsit is bonyolultabb tulajdonságát akarjuk vizsgálni ezeknek a gráfoknak, akkor igen nagy nehézségekbe ütközünk.

A legnagyobb gráfok talán a statisztikus fizikában fordulnak elő. Egy kristály atomjai olyan gráf csúcsainak tekinthetők, melynek mintegy 1027 csúcsa van. Egy teljesen szabályos kristály esetén ez a gráf unalmas: szabályosan ismétlődő rács. De a valóságban hibák és szennyezések fordulnak elő, amik a szabályosságot megtörik, és a gráf mindjárt „érdekessé” válik.

Az emberi társadalom jelenségeinek tanulmányozásához különböző társadalmi hálózatokat lehet bevezetni. Például, definiálhatunk egy gráfot, melynek csúcsai az emberek, és két csúcs akkor van összekötve, ha ismerik egymást. Ennek a hálózatnak tehát mintegy 8 milliárd csúcsa van, és gráfelméleti tulajdonságai (például, mennyire összefüggő) kihatással vannak arra, hogy betegségek, eszmék, gének milyen gyorsan terjednek. Egy igen ismert és meglepő eredmény ezzel a gráffal kapcsolatban az, hogy az átmérője legfeljebb 6 (Stanley Milgram amerikai pszichológus 1967-ben végzett vizsgálatának eredménye mára szállóigévé vált: „six degrees of separation”). Eszerint bármely két embert is tekintünk, mondjuk egy mexikói földművest és egy orosz olajmunkást, akkor az egyik ismerősének az ismerősének … (6 lépés) … ismerőse lesz a másik. (Egy megjegyzés, ami a későbbiekben fontos lesz: ez nem matematikai tétel, hanem megfigyelés. Ennek megfelelően lehetnek kivételek, mondjuk lehet még olyan indián törzs az Amazonas dzsungeleiben, amely eddig elkerülte a ,,civilizációval” való találkozást. Az állítás az emberek túlnyomó többségére igaz.)

Sok más társadalmi hálózatot is vizsgálnak: betegségek terjedése, genetikai rokonság, vagy akár itt említhető az ún. Erdős-gráf: csúcsai a kutatók, és kettő össze van kötve, ha van közös publikációjuk. (Erdős Pál, a 20. századi matematika egyik óriása, igen sokat dolgozott együtt másokkal, és nagyon sok társszerzője volt; az ő környezetében kezdték megrajzolgatni az Erdős-gráfot, innen kapta a nevét.) Hasonló nagy hálózatokkal lehet leírni ökológiai rendszereket, vagy egy szervezeten belüli enzimek, hormonok kölcsönhatásait. A biológia és az orvostudomány sarkalatos kérdése az agy leírása és működésének megértése. Az idegsejtek által alkotott hálózat az egyik legnagyobb gráf, amit az élő természet produkált, és gráfelméleti tulajdonságai (összefüggősége, a kapcsolatok véletlen vagy meghatározott jellege) magukban is igen fontos és nagy részben megoldatlan kérdések.

Mit lehet kérdezni?

Játsszunk el azzal, hogy milyen kérdést is tehetünk fel egy nagyon nagy gráffal kapcsolatban. Gondoljunk például az internetre. Aki tanult gráfelméletet, emlékezzen vissza arra is, hogy milyen tulajdonságok vizsgálatával kezdődött a tananyag. Itt van három alapvető kérdés egy gráffal kapcsolatban (persze sok mást is lehet kérdezni, és érdemes elszórakozni azon, hogy az eszünkbe jutó kérdések értelmesek-e pl. az internetgráfra).

Páros számú pontja van-e a gráfnak? Ez egy gráfnak fontos, sok gráfelméleti kérdésben szerepet játszó tulajdonsága. Például az alábbi tételt szokás a „Gráfelmélet Első Tételé”-nek is nevezni: Ha egy gráf csúcsainak száma páratlan, akkor van legalább egy páros fokú csúcsa. (Egy csúcs foka a csúcsra illeszkedő élek száma.)

Van-e értelme azzal foglalkozni, hogy az internet csúcsainak száma páros-e vagy páratlan? Nyilvánvalóan nincs: bármely másodpercben lesz sok-sok gép, amit kikapcsolnak, vagy új gép, amit bekapcsolnak, tehát a válasz másodpercről másodpercre változik. De még ha lerögzítenénk egy időpontot (mondjuk 2005. december 11-én 20 óra 26 perc 34 másodpercet, nyugat-európai idő szerint), akkor sem lehetne egy-egy gép bekapcsolásának időpontját annyira pontosan megállapítani, hogy a kérdésnek értelme legyen.

Hány éle van a gráfnak? Első ránézésre ennek a kérdésnek sincs több értelme, hiszen itt is másodpercről másodpercre változik a szám. De persze ez a szám csak körülbelül érdekel minket! Ha a válasz csak (mondjuk) 1% pontossággal érdekel minket, akkor ez már tökéletesen értelmes kérdés, az internet élszáma 1%-nyit csak napok alatt változik. Még stabilabb, és ezért értelmesebb kérdést teszünk fel, ha az egy csúcsra eső élek számát, vagyis az átlagos fokszámot kérdezzük. Ez a szám évek alatt változik csak lényegesen.

Összefüggő-e a gráf? Megint elsőre úgy látszik, hogy ez is értelmetlen kérdés, vagy talán inkább, hogy a válasz nyilvánvalóan nemleges: ha valahol a világon egy router elromlik, néhány gép internetkapcsolat nélkül marad, tehát az internet nem lesz összefüggő. Lehet azonban komolyabb probléma is az összefüggőséggel: mondjuk egy különlegesen erős napkitörés, és egy ezzel egybeeső cunami nyomán előfordulhatna, hogy Eurázsia és Amerika között megszűnik az internetkapcsolat. Ekkor nem néhány gép szakad le a rendszerről, hanem maga a rendszer esik szét. (Vagy mondjuk az „ántivilágban” lehetett volna egy kapitalista és egy szocialista internet is…)

Ha a különbséget pontosabban meg akarnának fogalmazni, azt mondhatnánk, hogy csak azt tekintjük összefüggőség-hiánynak, ha a rendszer két olyan részre esik szét, melyek mindegyike a csúcsoknak legalább egy százalékát tartalmazza. (A küszöb persze önkényesen lett választva, lehetne pl. egy ezrelék is.) Azt is érdemes megjegyezni, hogy akkor is szétesettnek tekintenénk a rendszert, ha volna azért valami igen kis kapacitású kapcsolat (mondjuk katonai vagy kormánycsatorna) a két rész között. A gyakorlatban persze ennél bonyolultabb kérdéseket is szeretnénk megválaszolni: Milyen gyors egy keresőalgoritmus? Milyen gyorsan terjed el az interneten egy vírus? Ezeknél a kérdéseknél már nemcsak az a gond, hogy az internet túl nagy: sokkal kisebb gráfon sem könnyű őket megválaszolni, gyakran csak kísérletezéssel, szimulációval tudunk választ kapni.

Véletlen gráfok

Ha egy nagyon nagy gráf tulajdonságait akarjuk vizsgálni (mondjuk, milyen sűrűn vannak benne a háromszögek, vagy hány lépésben lehet egyik csúcsukból a másikba eljutni), akkor jó lenne kisebb, de hasonló gráfot, „modellt” konstruálni. Van, amikor ez természetesen adódik (például egy kristályrács helyett vizsgálhatunk egy sokkal
kevesebb sorból és oszlopból álló rácsot), máskor azonban nem nyilvánvaló, hogyan lehetne egy hatalmas gráfot úgy lekicsinyíteni, hogy fontos tulajdonságai ne változzanak meg.

Mivel sok való életbeli gráf növekedésében a véletlennek nagyon nagy szerepe van, az az ötlet adódik, hogy hasonló véletlen eljárással csináljuk a modellt is. Ez vezet el minket a véletlen gráfokhoz. Nagyon sokféleképpen lehet véletlen módszerrel gráfot generálni. Kezdjük a legegyszerűbb és legtöbbet vizsgált modellel!

Az Erdős–Rényi-modell

Ezt a modellt Erdős Pál és Rényi Alfréd vezette be az 1960-as évek elején írt úttörő cikksorozatában. A modellt két számmal lehet leírni; egy n természetes számmal és egy p valós számmal, melyre 0<p<1 teljesül. Lerögzítünk n csúcsot, és bármely két csúcsot, egymástól függetlenül, p valószínűséggel kötünk össze. (A p = ½ esetben
így fogalmazhatunk: minden csúcspárhoz feldobunk egy forintot, és akkor kötjük össze őket egy éllel, ha fejet látunk.)

erdos_pal_renyi_alfred_graf.jpgErdős Pál és Rényi Alfréd

Az n szám tehát a csúcsok száma; a p számot élsűrűségnek nevezzük. Az élek várható száma pn(n-1)/2, és ha n elég nagy, akkor (a Nagy Számok Törvénye alapján) nagy valószínűséggel körülbelül ennyi lesz az élszám. A p paraméter választásával tehát „belőhetjük”, hogy hány éle legyen a véletlen gráfnak.

Az Erdős–Rényi-modellt igen sokat vizsgálták, mert érdekes tulajdonságai vannak. (Itt most ebbe nem tudunk belemenni.) Amikor olyan véletlen gráfgenerálási folyamatot keresünk, mely pl. az internethez hasonló nagyon nagy gráfot állít elő, az Erdős–Rényi-modell elsők között jut eszünkbe. Elég hamar kiderül azonban, hogy az Erdős–Rényi véletlen gráf nem nagyon hasonlít az internetre. Egy nagyon fontos különbséget mindjárt észrevehetünk, ha a pontok fokait vizsgáljuk.

Az 1 a) ábrán egy 100 csúcsú, 1/10 élsűrűségű Erdős–Rényi-gráf fokszámainak tipikus eloszlását mutatjuk be. (Egy 100 csúcsú gráfnak maximum 100·99/2≈5000 éle lehet. Ha az élsűrűség 1/10, akkor ennek az élszámnak csak kb. 1/10-e, vagyis 500 él van jelen.) Könnyű kiszámítani, hogy az átlagos fokszám ≈10, és ha statisztikát készítünk a fokokról, akkor (jó közelítéssel) az átlag körül harang alakú görbét, a nevezetes normális (vagy Gauss-) eloszlást fogjuk látni. 

nagyon_nagy_grafok2.pngnagyon_nagy_grafok1.png

1. ábra. Egy véletlen gráf és egy gyakorlatból vett gráf fokszámainak eloszlása

A társadalomtudományokban már régebben felfedezték azt a jelenséget, hogy a „való élet”-beli statisztikák igen gyakran ilyen elnyújtott, lassan lecsengő görbékre vezetnek; ezt egyik első leírójáról, George Kinsley Zipf amerikai nyelvészről Zipf-jelenségnek is nevezik. Ilyesféle statisztikát mutatnak egy élettér fajainak egyedszámai, az egyes példányok mérete stb. A számítógépek, hálózatok elemzése is sok további példával szolgál: az internetgráf fokszámain kívül ilyen eredményt kapunk, ha egy tárolón lévő file-ok méretéről készítünk statisztikát.

Mi ebben olyan meglepő, hogy külön „jelenségnek” számít? Aki tanult valószínűségszámítást vagy statisztikát, tudja, hogy egy mérés, megfigyelés eredménye általában az átlaga körül normális eloszlású. Ennek magyarázatát is megadja az elmélet (az ún. Centrális Határeloszlás-tétel): ha az átlagtól való eltérés sok kis, egymástól független hiba összege, akkor az közelítőleg normális eloszlású lesz. Az Erdős–Rényi véletlen gráf fokszámeloszlását ez teljesen megmagyarázza. De milyen általános matematikai magyarázata lehet annak, hogy a „való életbeli” gráfok fokszámeloszlása egészen más?

Urnák

Hogy egy kis bepillantást nyújtsunk a Zipf-jelenség matematikai hátterébe, idézzük föl sok valószínűség-tankönyv kedvencét, az urnát. Két urnába dobáljunk be 100 golyót, minden lépésben véletlenszerűen választva ki, hogy melyikbe dobjuk a következőt. A két urnában általában nem pontosan ugyanannyi golyó lesz, de a Nagy Számok Törvénye alapján közelítőleg ugyanannyi. Ha a kísérletet sokszor megismételjük, és statisztikát készítünk arról, hogy mondjuk az első urnába hány golyót dobtunk, akkor az átlag (50) körül mindkét irányban meredeken lefutó Gauss-görbét fogunk látni (2 a) ábra).

A 2 b) ábrán látható Pólya-urna kicsit máshogy működik: most is két urnába dobálunk be 100 golyót, de minden lépésben egy-egy urnába azzal arányos valószínűséggel dobunk be egy golyót, hogy hány golyó van már benne. Hogy az eljárás elinduljon, tegyünk mindkét urnába 1-1 golyót. Most egyforma sok golyó van a két urnában, tehát a harmadik golyót egyforma valószínűséggel dobjuk egyik vagy másik urnába. Mondjuk, hogy az első urnába dobtuk. Ekkor a negyedik golyót már kétszer akkora valószínűséggel dobjuk az első urnába, mint a másodikba, vagyis az első urna valószínűsége 2/3, a másodiké 1/3. Általában, ha az első urnában a, a másodikban b golyó van, akkor a következő golyót a/(a + b) valószínűséggel dobjuk az első urnába, és b/(a + b) valószínűséggel a másodikba.

polya_gyorgy.jpgEz egy kicsit mesterkéltnek tűnhet, adjunk hát egy második leírást is: amikor egy golyót akarunk bedobni (a harmadik golyótól kezdve), akkor az véletlenszerűen kiválaszt az urnákban levő golyók közül egy „példaképet”, és abba az urnába megy, amelyikben az van. (Lehetne a Pólya-urnát Divat-urnának vagy Sznob-urnának is nevezni…) Ha egy tipikus lefutás eredményét nézzük, akkor a két urnában nem egyforma sok golyó lesz. (Persze nem jósolhatjuk meg előre, hogy melyikben lesz több, hiszen a két urna szerepe szimmetrikus. Hol az egyikben, hol a másikban.) Ez nem meglepő, hiszen annak az urnának, amelyik az elején egy kis előnyt szerez, jó esélye van rá, hogy ezt az előnyét meg is tartsa. 

lovasz_laszlo_nagyon_nagy_grafok2aa.bmplovasz_laszlo_nagyon_nagy_grafok2a.bmp
2a. ábra. Két közönséges urna

lovasz_laszlo_nagyon_nagy_grafok2bb.bmplovasz_laszlo_nagyon_nagy_grafok2b.bmp

2b. ábra. Két Pólya-urna

Ha a kísérletet nagyon sokszor megismételjük, a 2 b) ábrán látható meglepő statisztikát fogjuk látni: vagyis az első urnában az esetek 1/99 részében lesz 1 golyó, az esetek 1/99 részében lesz 2 golyó, …, az esetek 1/99 részében lesz 99 golyó. (Matematikai érdeklődésű olvasók számára érdekes feladat ennek a bebizonyítása.)

Ha két urna helyett hárommal dolgozunk, hasonló képet kapunk: a közönséges urnákban nagyjából egyforma számú golyó lesz, és az első urnába jutó golyók számának statisztikája az átlag körüli Gauss-görbét mutat. A Pólya-urnákban különböző számú golyó lesz, és a statisztika egészen más képet mutat, egy lineárisan csökkenő görbét (3. ábra). Ha az urnák számát növeljük, a közönséges urnák továbbra is Gauss-görbét adnak, míg a Pólya-urna egyre meredekebben lecsengő görbét (de azért soha nem lesz olyan meredek, mint a Gauss-görbe). Ha nagyon sok urnát használunk, akkor a Pólya-urna statisztikáját exponenciális függvénnyel lehet leírni (y = e-x). 

lovasz_laszlo_nagyon_nagy_grafok3aa.bmplovasz_laszlo_nagyon_nagy_grafok3a.bmp3a. ábra. Három közönséges urna

lovasz_laszlo_nagyon_nagy_grafok3bb.bmplovasz_laszlo_nagyon_nagy_grafok3b.bmp3b. ábra. Három Pólya-urna

A Barabási–Albert-gráf

A Pólya-urna azt mutatja, hogy egy igen természetes, egyszerű véletlen folyamat vezethet olyan eloszláshoz, amely a normális eloszlástól gyökeresen különbözik, nem reprodukálja azonban a Zipf-jelenséget.

1999-ben Barabási Albert László és Albert Réka olyan véletlen gráfmodellt javasoltak, amelynek fokszámai az 1 b) ábrához hasonló statisztikát adnak. A legegyszerűbb változatban ez a modell a következőképpen működik. Kiindulunk két, éllel összekötött csúcsból, majd minden lépésben születik egy új csúcs, ez kiválaszt magának egy öregebb csúcsot, és azzal összeköti magát. Az öregebb csúcsot véletlenszerűen választja, méghozzá úgy, hogy egy csúcs választásának valószínűsége arányos a fokszámával. (Sznob gráfnak is nevezhetnénk: minél népszerűbb egy régi csúcs, annál nagyobb valószínűséggel köti hozzá magát az új csúcs.) Az internet növekedése persze nem ennyire egyszerű, de érdemes megnézni, hogy amilyen gráfot így kapunk, mennyire tükrözi az internet megfigyelt tulajdonságait.

Tekinthetjük a csúcsokat Pólya-urnáknak. Minden lépésben egy golyót dobunk be a Pólya-urna szabályai szerint, és ezzel egy időben egy új csúcs (urna) születik, benne egy golyóval. A két utóbbi golyót tartalmazó urnát (csúcsot) éllel kötjük össze. Nem nehéz belátni, hogy az így konstruált véletlen gráf egy fa, vagyis összefüggő, és nincs benne kör (zárt poligon). Albert és Barabási kísérletileg megfigyelték, majd többen be is bizonyították (Bollobás, Riordan, Spencer és Tusnády, illetve Móri), hogy ha a gráfot eléggé nagyra növesztjük, akkor a fokszámainak eloszlása az 1 b) ábrán láthatóhoz hasonló lesz, pontosabban a k fokú csúcsok száma 1/k3 -bel lesz arányos.

Azóta sok hasonló modellt vezettek be és elemeztek, melyek a „való életbeli” gráfok más fontos tulajdonságait tükrözik. Nem mondhatjuk azonban, hogy teljesen értjük, milyen véletlen folyamatok vezetnek pl. a Zipf-jelenséghez.

Nagy gráfok tesztelése

Mint már volt róla szó, a nagyon nagy gráfok nehezen vizsgálhatók. Egy lehetséges módszert a statisztika sugall: a nagy gráfból (nevezzük G-nek) mintát veszünk, vagyis véletlenszerűen kiválasztjuk mondjuk 1000 csúcsát, és megállapítjuk, hogy ezek közül melyek vannak összekötve. Az így kapott kisebb gráfot (nevezzük G’- nek) vizsgálva, megpróbálunk a nagy gráf tulajdonságaira következtetni.

Például kíváncsiak vagyunk a G gráf élsűrűségére, vagyis hogy a lehetséges n(n-1)/2 csúcspár hányad része van éllel összekötve. (Itt n a G gráf csúcsainak száma, ami sok milliárd lehet.) Legyen ez az ismeretlen szám p. Azt várhatjuk, hogy a kiválasztott 1000 csúcs között is ennyi az élsűrűség, vagyis körülbelül p1000·999/2 csúcspár lesz összekötve. De azt meg tudjuk számolni, hogy hány él fut a kiválasztott csúcsok között: mondjuk 134 865 élt számolunk, akkor tehát

p x1000 x 999/2 = 134865,

amiből p = 0,27. Ez persze csak statisztikai becslés a G gráf élsűrűségére: mindössze annyit állíthatunk, hogy az élsűrűség nagy valószínűséggel közel van 0,27-hoz.

Ez az egyszerű példa nem volt nagyon meglepő, de vannak sokkal kevésbé nyilvánvaló tulajdonságok is, melyeket ilyen módszerrel lehet tesztelni. Mondjuk, kíváncsiak vagyunk arra, hogy szétesik-e a G gráf két nagy részre, melyek között nincs él. Rövid meggondolás mutatja, hogy ha G-ben mondjuk van 5 csúcs, melyeket a többivel nem köt össze él, de a maradék rész összefüggő, akkor a véletlen mintából ennek az 5 elszigetelt pontnak a létezéséről semmit nem tudunk meg. Ezért a kérdés csak úgy értelmes, ha ,,nagy” részekről beszélünk, amelyek mindegyike a csúcsoknak (mondjuk) legalább 1/3-át tartalmazza.

Tegyük föl először, hogy a gráf 2 részre bomlik, melyek egyike a csúcsok 3/5-ét, a másika a csúcsok 2/5-ét tartalmazza, és melyek között nincs él. Jelöljük a két csúcshalmazt A-val és B-vel. Ha most 1000 csúcsot kiválasztunk véletlenszerűen, a Nagy Számok Törvénye alapján azt fogjuk tapasztalni, hogy kb. 600 kiválasztott csúcs A-ba, kb. 400 pedig B-be fog esni. Az 1000 csúcson látható G’ gráf tehát maga is két részre fog szétesni, nagyjából az eredeti G gráfhoz hasonló arányban.

Mit látunk akkor, ha a G gráf nem bomlik két nagy részre? A kivett 1000 ponton lá- tott G’ gráf ettől még széteshet két nagy részre, melyeket nem köt össze közvetlenül egyetlen él sem, de a gráf általunk nem vizsgált, sokkal nagyobb részében eljuthatunk egyikből a másikba akár sokféleképpen is.

Más szóval: ha azt látjuk, hogy a kivett csúcsok által alkotott gráf nem bomlik két nagy részre, akkor nagy valószínűséggel azt állíthatjuk, hogy az eredeti gráf sem bomlik föl; de abból, hogy a kivett rész fölbomlik, nem következtethetünk arra, hogy a nagy gráf is fölbomlik. Egy gyengébb következtetést mégis levonhatunk: a nagy gráf fölbomlik két nagy részre úgy, hogy az ezeket összekötő élek száma a lehetségesnek csak elenyésző töredéke. Ennek a bizonyítása egyáltalán nem könnyű, és megint csak többen járultak hozzá a megoldáshoz (Goldreich, Goldwasser és Ron, illetve Arora, Karger és Karpinski neve említendő).

Közelítés kisebbel és nagyobbal

Az előző fejezetben tárgyalt gráftesztelési módszerek azért működnek, mert a gráfból választott véletlen részgráf sok fontos paraméter tekintetében hasonlít a gráfhoz. Úgy is mondhatnánk, hogy jól közelíti a gráfot. Ezzel tehát választ adtunk a bevezetőben feltett kérdésre, hogy a nagyon nagy gráfok közelíthetők-e kisebbel: bizonyos értelemben igen. (Visszatérünk még arra a kérdésre, hogy milyen értelemben is közelítik egymást ezek a gráfok.)

Az első ilyen irányú eredmény Szemerédi Endre 1974-ben publikált ún. Regularitási Lemmája.1 A lemma pontos megfogalmazásától eltekintünk, inkább megpróbáljuk szemléltetni a következő fejezetben. De mit jelent az, hogy „nagyobbal” közelítés? Arra a megállapításra gondolok, hogy „a végtelen a nagyon nagy véges közelítése”. Ha a kristályra gondolunk, mint nagyon nagy gráfra, akkor láthatjuk, miről van szó: egy makroszkopikus kristályra sok szempontból úgy lehet gondolni, mint folytonos anyagra, melyen különböző fizikai paraméterek (hőmérséklet, feszültségek) folytonos (általában sokszor differenciálható) függvényekkel írhatók le. Így aztán felírhatók rájuk differenciálegyenletek, sorfejtések, alkalmazható az analízis hatalmas fegyvertára.

Attól tehát, hogy a nagyon nagy gráfot még nagyobbal (végtelen naggyal) helyettesítettük, nem bonyolultabb lett, hanem egyszerűbb, vagy legalábbis jobban kezelhető. Van-e hasonló folytonos közelítése általában a nagyon nagy gráfoknak? Látni fogjuk, hogy a válasz (bizonyos feltételek mellett) igenlő.

Egy szemléletes kép

Induljunk ki a 4. ábrán látható gráfból. A csúcsok és élek ilyen ábrázolása szemléletes, de például egy számítógépbe való bevitelhez nehezen használható; szokásosabb az ábra jobb oldalán látható táblázattal megadni a gráfot. Ehhez a csúcsokat megszámozzuk 1-től 14-ig, a tetején indulva, az óramutató járása szerint; az, hogy a 2. sor 3. eleme 1, azt jelenti, hogy a 2. és 3. csúcs össze van kötve.

lovasz_laszlo_nagyon_nagy_grafok4.bmp4. ábra. Egy gráf; a szomszédossági táblázata, és „keresztrejtvény” ábrája

Ez a táblázat az emberi szemnek igen keveset mond, ezért a következőképpen módosítjuk: minden 0-t egy kis fehér négyzettel, minden 1-est egy kis fekete négyzettel helyettesítünk; így egy olyan rajzot kapunk, ami egy keresztrejtvényre emlékeztet. Az 5. ábra bal fele egy 100 csúcsú Erdős–Rényi véletlen gráf „keresztrejtvény” ábrá- ja, és bizony nem mond sokat. Messziről nézve egyenletesen szürkének látszik, nem különböztethető meg a jobb oldali szürke mezőtől, amit úgy jellemezhetünk, hogy a bal oldali ábra sötétségét átlagoltuk. A véletlen gráf tehát a szürke, struktúra nélküli ábrának felel meg.

lovasz_laszlo_nagyon_nagy_grafok5.bmp5. ábra. Egy Erdős–Rényi véletlen gráf „keresztrejtvény” ábrája és annak átlagoltja

A 6. ábra bal fele egy „sakktáblát” mutat. Minél nagyobb sakktáblát nézünk, annál kevésbé különböztethető meg ez is az egyenletes szürkétől. De ha más sorrendbe állítjuk a sorait és oszlopait, a páratlan sorszámúakat véve előre, akkor igen egyszerű ábrát kapunk, amely csak négy egyszínű részből áll. A sakktábla tehát csak amiatt szürke, mert összekevertük a sorait; ha azokat megfelelő sorrendbe rakjuk, akkor egyszerű, de nagyon határozott struktúrát látunk.

lovasz_laszlo_nagyon_nagy_grafok6.bmp6. ábra. Egy nagy sakktábla és ugyanaz átrendezve

A Szemerédi-partíció

A megfelelő sorrend kiválasztása más gráfoknál is kimutatja az egyébként rejtett struktúrát. A 7. ábra első fele ugyanazt a gráfot ábrázolja, mint a 4. ábra, de máshogy számoztuk a csúcsokat: a sorrendet úgy választottuk, hogy ha megcsináljuk a „keresztrejtvény” ábrát, látszódjon, hogy a gráfnak van egy ritkább része, meg egy sűrűbb része, és a kettő között egy közepesen sűrű összeköttetés. A 7. ábra második felét úgy kaptuk, hogy az első felét négy kisebb négyzetre bontottuk, és mindegyik sötétségét átlagoltuk. Szóban elmondva ez az ábra a következő információt mondja: a pontok egyik felében az élsűrűség 0,86, a másik felében 8/21≈0,38, a kettő között pedig 23/49≈0,47. Más átrendezéssel ezt a struktúrát már nem tudnánk élesebbé tenni: az egyes részek már menthetetlenül egyenletesen szürkék, vagyis véletlenszerűek (persze egy ilyen kis gráfon ez nem látszik jól; ha az egyes részeknek mondjuk 100 csúcsa volna, akkor megállapíthatnánk, hogy olyanok, mint az 5. ábra keresztrejtvénye).

lovasz_laszlo_nagyon_nagy_grafok7.bmp7. ábra. Egy Szemerédi-partíció

Tegyük föl, hogy egy gráfról csak a 7. ábra jobb oldalán levő közelítést ismerjük, meg a csúcsok számát, de az utóbbi nagyon nagy (legyen mondjuk n). Mennyit mond el ez a három szám (0,86, 0,38 és 0,47) a gráfról? Nem sokat: pl. nem tudjuk megállapítani csak ezek alapján, van-e elszigetelt csúcs, vagy összefüggő-e a gráf. Más tulajdonságokat azonban meg tudunk mondani: tudjuk például, hogy az élek száma közelítőleg 0,86·n2/4+0,38·n2/4+0,47·n2/2 = 0.2725·n2, ahol n a csúcsok száma. Kevésbé nyilvánvaló módon meg tudjuk becsülni a háromszögek számát is, vagy azt, hogy a gráf „lényegében összefüggő”-e.

Szemerédi 1975-ben bebizonyította a következő eredményt, a híres Regularitási Lemmát. Induljunk ki egy nagyon nagy gráfból, és adjunk meg egy hibahatárt, mondjuk 1%-ot. Ekkor a gráf felbontható korlátos számú részre (ezek száma csak a hibahatártól függ, nem függ a gráftól) úgy, hogy a megfelelő kisebb négyzeteken a keresztrejtvény-ábra véletlenszerű. Az ilyen felbontást Szemerédi-partíciónak nevezzük. A Regularitási Lemmát a gráfelmélet és a számítástudomány igen sok területén alkalmazzák. Igen szorosan kapcsolódik pl. a fent vázolt témakörhöz, a nagyon nagy gráfok teszteléséhez. Kiderült például, hogy (megint csak igen informálisan fogalmazva) pontosan azok a gráftulajdonságok tesztelhetők, melyeket a Szemerédi-partíció meghatároz.

Folytonos közelítés

A 8. ábra bal oldalán egy egyszerű szabály szerint véletlenszerűen növekvő gráf ,,keresztrejtvény” ábrája látható. A szabály kicsit hasonlít az Albert–Barabási-féle gráfra. A gráf minden lépésben vagy egy új csúcsot hoz létre, vagy egy új élt, mely két korábban meglévő, eddig össze nem kötött csúcsot köt össze; a pontpárt egyenletes eloszlás szerint választjuk az összes szóba jövő párból. Azt, hogy új csúcsot vagy új élt hoz-e létre, ugyancsak a véletlen dönti el, de úgy, hogy az él létrejötte n-szer valószínűbb, mint az új csúcsé, ahol n a már meglévő csúcsok száma. A folyamatot 100 csúcsnál állítottuk meg. Látható, hogy a korábban született csúcsok között sokkal sűrűbbek az élek, ami persze nem meglepő.

lovasz_laszlo_nagyon_nagy_grafok8.bmp8. ábra. Egy egyszerűen növekedő véletlen gráf ,,keresztrejtvény” ábrája, annak folytonos közelítése és Szemerédi-partíciója

Ami viszont érdekes, az a 8. ábra közepén levő képpel való összehasonlítás. Itt a f(x,y) = min(1-x,1-y) függvény szürkeskálás ábrázolása látható (vagyis ahol a függvény értéke 1, ott fekete a megfelelő pixel, ahol 0, ott fehér). A két kép igen hasonlít, ha 100 helyett 1000 csúcsig mentünk volna el, nem is igen lehetne őket szemmel megkülönböztetni. Azt mondhatjuk tehát, hogy a fent leírt módon növekedő gráfot az f(x,y) = min(1-x,1-y) függvény közelíti meg, éspedig annál jobban, minél nagyobb a gráf.

Ez a függvény nagy gráfunkról igen sokat elmond, és szebb, „analitikusabb” formában, mint a Szemerédi-partíció (amire egy példát a 8. ábra jobb oldalán lá- tunk). Például ha a háromszögek számára vagyunk kíváncsiak, akkor „csak” ki kell számítanunk a következő integrált:

∫ ∫ ∫ W(x,y)W(y,z)W(y,x)dx dy dz

és azt megszorozni a háromszögek lehetséges legnagyobb számával, ami

100C3 = 100·99·98 / 3·2·1 = 161700

Ez a „szép” függvénnyel való közelítés nem csak az ilyen módon konstruált gráfokra igaz. Ha gráfok egy növekvő sorozata olyan, hogy élsűrűségük (a keresztrejtvény-ábrájuk átlagos szürkesége) egy határértékhez tart, és bennük általában minden adott alakzat sűrűségére ugyanez áll, akkor van olyan kétváltozós függvény, melynek értékei 0 és 1 között vannak, és amely a gráfokat egyre jobban közelíti. (A pontos megfogalmazás túlnőne az ismertetés keretein.) Ez a függvény, mint láttuk, igen komplikált gráfsorozat esetén is viszonylag egyszerű lehet, és ha a gráf elég nagy, akkor elég ezzel a függvénnyel dolgozni, felhasználva az analízis hatalmas eszköztárát.

Akkor hát melyik függvény írja le az internetet?

Sajnos, erre a kérdésre a fenti elmélet nem ad értelmes választ. Ha (képzeletben) megcsináljuk az internet keresztrejtvény-ábráját, az majdnem teljesen fehér lesz, hiszen egy-egy csúcs csak a többi csúcs elenyészően kis részével van összekötve. Így azt mondhatjuk, hogy az internetet ilyen módon az azonosan 0 függvény igen jól megközelíti – ami igaz állítás, de semmitmondó. Sajnos a legérdekesebb nagyon nagy gráfokkal hasonló a helyzet. A fenti elmélet sűrű gráfokra alkalmazható, melyek élszáma a maximális lehetséges élszám (n csúcs esetén n(n-1)/2) nem elhanyagolható százaléka.

Van-e valamilyen jobb értelmezése az olyan növekvő gráfsorozatoknak, mind az Albert–Barabási-gráfok, vagy az internet egy jól használható limesze? Megközelíthető-e egyáltalán ilyen módszerekkel az internet (vagy mondjuk az agy) szerkezete? Sűrű gráfok esetén a Szemerédi Lemma azt mondja, hogy megadható korlátos számú numerikus paraméter (az egyes osztályok közötti élsűrűségek), melyek ismeretében a gráf legtöbb fontos tulajdonsága kis hibával kiszámítható. Minél több paramétert adunk meg, annál kisebb lesz ez a hiba. (Az analízisből ismert sorfejtésekhez hasonlít ez.) Megadható-e ritka gráfoknak is jó közelítése, mely kevés paraméterrel leírható? Bár vannak részeredmények, ezekre az igen izgalmas és fontos kérdésekre nem tudjuk a választ. 

Irodalom

Barabási, A., Albert, R.: Emergence of scaling in random networks. Science, 286 (1999), 509–512.

Bollobás B.: Random Graphs. Cambridge University Press (2001).

Erdős P., Rényi A.: On random graphs. I, Publ Math Debrecen, 6 (1959), 290–297. Pitman, J.: Probability. Springer (1999).

Komlós J., Simonovits M., Szemerédi: Regularity Lemma and its applications in extremal graph theory. In Combintorics, Paul Erdős is 80, Vol. II, Bolyai Soc. Math. Stud. 2, Budapest (1996), 295–352.

Milgram, S.: The Small World Problem. Psychology Today, (1967), 60–67.

-

Az 1991-ben bevezetett szokás szerint az egyetemet alapító Pázmány Péter bíborosra történő megemlékezés tudományos részét, a „Pázmány Péter előadás-t egy kiemelkedő professzor tartja saját kutatási területéről.

Szólj hozzá

agykutatás erdős pál gráfelmélet Szemerédi Endre Lovász László gráfok erdős pál matematikus Lovász László matematikus Rényi Alfréd gráfok ábrázolása véges és végtelen szemerédi lemma Barabási Albert László Albert Réka Erdős-Rényi-gráf centrális határeloszlás agygráf nagyon nagy gráfok Regularitási Lemma gráfok fokszáma gráfelmélet alapfogalmak Pólya György Zipf eloszlás Milgram hat lépés hat kézfogás elmélet