Csak semmi politika avagy gráfposzt
Eredeti szerző: jotunder
Lovász Lászlót a Magyar Tudományos Akadémia elnökét külső tagjának választotta a Svéd Királyi Tudományos Akadémia. Tegnap tartotta meg a székfoglaló előadását „Nagyon nagy hálózatok matematikája” címmel.
Matematikus olvasóink most hagyják abba az olvasást, ez nem nekik szól. Megpróbálom nem-matematikusok számára leírni, hogy miről is van szó. Annyi mindenről beszélnek manapság az Akadémiával kapcsolatban, ez itt valami nagyon más lesz. Nem lesz szó Gundel étteremről, emlékműről, O-val kezdődő nevű miniszterelnökökről. Itt most gráfokról lesz szó. Ugyanis Lovász azért mégis csak a gráfokról szól, sőt, és ez még nagyobb dolog, a gráfok kicsit a Lovászról szólnak.
Amit itt leírok, az Lovász László és társszerzői elméletének egy egészen kicsiny töredéke, de azt gondolom, hogy egy igen fontos töredéke. Lovásznak nemrég jelent meg egy majd ötszáz oldalas könyve az Amerikai Matematikai Társaság kiadásában Large Networks and Graph Limits címmel, a scholar.google háromszáz idézetet lát csak a Limits of Dense Graph Sequences című cikkükre, ez egy nagyon nagy téma, amelyről már konferenciákat is rendeztek. Tavaly egy Arbeitgemeinschaft volt a nagy gráfokról Oberwolfachban, ami azt mutatja, hogy nagyon sok tehetséges fiatal is érdeklődik a téma iránt a világban.
Na, akkor in medias res….
1. A nagy gráfok, amelyekről beszélünk végesek ugyan, de óriásiak. Van mondjuk tíz a századikon darab csúcsuk. Az jóval nagyobb, mint a világegyetemben lévő atomok száma. Esélyünk nincs arra, hogy egy ilyen gráfot valaha megértsünk. Az a kérdés, hogyan mondhatunk mégis valamit ezekről az irdatlanul nagy gráfokról és hogyan kell elképzelni őket, amikor már felfoghatatlanul nagyok.
2. A legegyszerűbb kérdés, amit a gráfokról feltehetünk az az, hogy hány élük van. Ezt a következő módon is megkérdezhetjük. Ha véletlenül kiválasztjuk egy gráf két csúcsát, akkor mi az esélye annak, hogy össze lesznek kötve. Ha a gráfban nincsenek élek, akkor ez a valószínűség nulla. Ha a gráfban bármely két csúcs össze van kötve, akkor 1. Mi van akkor, ha a gráf úgy néz ki, hogy a baloldalán van százbillió csúcs, a jobboldalán is van, és a két különböző oldalon levő csúcsok össze vannak kötve, az azonos oldalon levők meg nem. Akkor ez a valószínűség lényegében 1/2.
3. Ennél bonyolultabb kérdéseket is fel lehet tenni. Mi történik, ha három különböző pontot választunk ki véletlenül? Akkor több eset lehetséges. (A) mindenki mindenkivel össze van kötve. (B) senki nincs összekötve senkivel. (C) egy élet látunk. (D) két élet látunk. Mi a valószínűsége az (A),(B),(C),(D) eseteknek? Ezek a valószínűségek valamit elmondanak a gráfról. Valamit már láthatunk belőlük.
4. Ha egy n csúcsú gráfnak sokkal kevesebb (mondjuk egymilliárdszor kevesebb) éle van, mint a teljes gráfnak, akkor ha kiválasztunk három csúcsot, tipikusan egyetlen élet sem fogunk látni. Lovászék elmélete azokról a gráfokról mond el érdekes dolgokat, amelyeknek aránylag sok éle van. Ezeket a gráfokat hívják sűrű gráfoknak.
5. Az általános kérdés a következő: Mi van, ha k (ahol a k lehet 10, 100, 1000 vagy akár százbillió) csúcsot választunk ki véletlenül a gráfból? Mit fogunk látni? Száz csúcsra nagyon sok különböző gráf rajzolható. Minden egyes ilyen lehetséges G gráfnak van valamilyen csekély valószínűsége egy adott hatalmas gráf esetén, amelyből a száz pontot kiválasztottuk. Ha az irdatlanul nagy gráf neve H, akkor jelöljük ezt a valószínűséget p(k,G,H)-nak.
6. Lovászék azt akarták megérteni, hogy két ilyen borzasztóan nagy gráf, H1 és H2, mikor „hasonlít” egymásra. Azt a definíciót adták erre, hogy akkor hasonlítanak, ha már elég nagy k értékekre, minden legfeljebb k csúcsú mintagráfra a p(k,G,H1) és a p(k,G,H2) számok már nagyon közel vannak egymáshoz.
7. Gráfok egy H1, H2, H3,…. sorozatát akkor nevezik konvergensnek, ha minden lehetséges k értékre és G gráfra a p(k,G,H1), p(k,G,H2),p(k,G,H3)… sorozat konvergens. Az a kérdés, hová „tartanak” ezek az egyre hatalmasabb gráfok?
8. A naív, de azért matematikailag már elég ügyes megközelítés a következő. Az egyre nagyobb gráfok csúcsai összeállnak egy folytonos szakasszá. Mit jelent az, hogy „él” ? Miért, mit jelent egy véges gráf? A gráf csúcsainak önmagával vett szorzatának egy részhalmazát jelenti. Akkor pedig ezeknek a folytonos gráfoknak is ilyeneknek kellene lenniük. A szakasz önmagával vett szorzata a négyzet. És akkor ennek a négyzetnek valamilyen részhalmazát nevezzük élhalmaznak.
9. A matematikusok, mint tudjuk, igen te is, nem olvassák a posztot, tehát nem vághatnak közbe, hogy mérhető részhalmazról van szó. Ez a mérhetőség egy kellemetlenség, amivel most nem fogunk foglalkozni, elég az, amivel eddig megterheltük az Olvasót.
10. Amit viszont joggal vethetne közbe a matematikus, de nem veti közbe, mert meg van neki tiltva, az az, hogy amennyiben egy (x,y) pont benne van az „élhalmazban”, akkor legyen benne az (y,x) pont is. A gráfok ilyenek. Ha x össze van kötve y-nal, akkor y is össze van kötve x-szel.
11. Mit jelent egy ilyen folytonos monstrumra az, hogy kiválasztok k csúcsot? Az pont azt jelenti, hogy egyenletesen lerakok k pontot a szakaszra. Bármely két kiválasztott (x,y) párra megnézhetem, hogy az (x,y) pont benne van-e a furcsa folytonos élhalmazomban és így az ilyen folytonos Q gráfokra is definiálható a p(k,G,Q) szám.
12. Azt mondjuk, hogy a Q folytonos gráf limesze a H1,H2,H3,… sorozatnak, ha minden egyes k-ra és G gráfra igaz az, hogy ( lim_{itoinfty} p(k,G,Hi)=p(k,G,Q) ) .
13. Az igaz, hogy minden Q folytonos gráfhoz található egy igazi gráfokból álló sorozat, amelyik hozzá tart. A Lovász-féle varázslat ott kezdődik, hogy nem minden konvergens gráfsorozathoz tartozik ilyen folytonos gráf Q.
14. Amit Lovászék kitaláltak az eggyel bonyolultabb, mint a folytonos gráf. (pontosan tudom, hogy már az is elég bonyolult)
15. Vegyük egy W függvényt a négyzeten (matematikailag precízebben: egy integrálható ( W:[0,1]times [0,1]to [0,1] ) függvényt, amire W(x,y)=W(y,x). )
16. Ez mi ez? – kérdi most az Olvasó. Ez nem is gráf. Mit jelent az, hogy W(x,y)=1/2? Ez valami Schrődinger macskája? Hogy egy ketted eséllyel ott van az a nyomorult él, egy ketted eséllyel meg nincs?
17. Pontosan erről van szó!
18. A Schrődinger macska típusú gráfok (portugálul: graphon) az igazi limeszek. Ha van egy ilyen W macskánk, akkor simán kiszámíthatjuk a p(k,G,W) valószínűséget. Megint kiválasztjuk véletlenül a k pontot a [0,1] szakaszon, de most megállunk egy kicsit macskázni. A kiválasztott x és y pont között nem fogjuk rögtön tudni, hogy van-e él. Fel kell dobnunk egy furcsa érmét, amelyik W(x,y) valószínűséggel az” ÉL”, 1-W(x,y) valószínűséggel a „NEM ÉL” oldalát fogja megmutatni nekünk. Így kétszer is használva a véletlent, kapunk egy gráfot k csúcson.
19. A fentiek szerint a p(k,G,W) valószínűség definiálható. Tehát egy Schrődinger macska gráf, akkor limesze egy H1,H2,H3,… sorozatnak, ha ( lim_{itoinfty} p(k,G,Hi)=p(k,G,W) ) .
20. És ez már a jó fogalom. Minden konvergens sorozathoz van ilyen macska, és minden macskához van hozzá konvergáló sorozata igazi gráfoknak. Itt a vége, fuss el véle.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16519559-6ae7b31d6d01f' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16519559&origin=www.orulunkvincent.hu&obj_id=192691293-16519559-6ae7b31d6d01f&n=1' data-name='like-post-frame-192691293-16519559-6ae7b31d6d01f' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
Én egyelőre a miniszterelnöki értelmezésére várok.
Vajon miért is nincsenek kommentekí???
Kéne még ehhez a poszthoz valami jó kis macskás gif.
Nekem ez nagyon hegyes, ezért leborotváltam Occam borotvájával.
Szóval én végigolvastam, mert nem vagyok matematikus.
És mivel nem vagyok matematikus, nem is értem.
Szóval ez mire jó?
Bájdövéj, szerintem ez a poszt egy üres halmaz, mert aki értené, annak meg van tiltva, hogy végigolvassa, aki meg végigolvassa, úgy hogy eleve nem ért hozzá, tehát szabad neki végigolvasnia, annak meg nem jó semmire……. 🙂
@Aromo a fékezhetetlen: én ma erről akartam írni. mert ma ez volt számomra a valóság.
szerintem egy mérnök vagy egy természettudós ezt nagy vonalakban megértheti. más meg láthatja, hogy nagyjából mivel is foglalkozik az az ember, akit látott a tévében.
@Célkereszt: Így:
Mélyen Tisztelt Jótündér úr!
A magyar politikára oly jellemző homályos dramaturgia folyományaként kézbe vehettem egy írást, amely a Gráfposzt címet és egyben műfaji meghatározást viseli. Az írást Ön jegyzi.
Abból a feltételezésből kiindulva szeretnék köszönetét mondani, hogy a feljegyzés az én számomra is készült.
Köszönöm, hogy az ügyet és az ügy gazdáját (kormány) is méltónak találta arra, hogy toll után nyúljon. Ez manapság rendhagyó, ugyanis a szellem emberei inkább a közélet általános megvetésének tónusát és a felülállás magatartását követik.
Az Ön nagyvonalú gesztusa reflexiók hosszú sorát váltotta ki belőlem. Úgy érzem az Ön írása az első, amely elkerüli a sajnos lassacskán elkerülhetetlen, olcsó politikai lökdösődés kocsmapultját.
@jotunder: ne haragudj, nem akartam a posztot offolni, csak Célkereszt magas labdát adott. Ha gondolod, vedd ki a kommentem nyugodtan
@jotunder: ne haragudj, nem akartam offolni a posztot, csak Célkeresztre muszáj volt lőnöm. Ha gondolod, vedd ki a kommentem nyugodtan
@Érvsebész: ?? 🙂
Hülye blogmotor
@jotunder: Ahá! Jól van, írjál róla nyugodtan, de ettől én – aki nem vagyok mérnök sem természettudós még mindig nem tudom mivel foglalkozik az ember, akit láttam a tévében.
@Érvsebész: 🙂
@Érvsebész: Na most már csak az hiányzik, hogy a fent említett p(k,G,W)-t is egy bizonyos ember definiálja.
@jotunder: (hát csak restelkedem, mert ez a laikus olvasóknak szánt magyarázatod, amit nyilván még a nőklapjacafé olvasói is értenek, én meg nem, erre idióta politikai poénkodásba fogok…)
Jézusom! Már megint rossz álmaim lesznek. Jönnek azok a nagy szőrös gráfok, amik vagy összekötve vannak, vagy nem, de az istennek sem eresztenek. Szóval nekem KO.
@Érvsebész: Tudtam, hogy olvasnom kéne a nők lapja kávét.
Én ezt a gráfot jól ismerem, sőt, el is ismerem, de nagyon nem szeretem:
http://www.wtatennis.com/players/player/2718
@aronsatie: innen már csak egy lépés, hogy a gráf, a gráf a vízbe fúl…
@jotunder: mérnök vagyok, nagy vonalakban megértettem, de nem láttam az embert a tévében, aki nagyjából ezzel foglalkozik.
mert nincs tévém 🙂
imádom jótündér matematikai posztjait.
érteni nem értem, pontosabban csak néha sejtem, hogy mit is mond, de számomra olyanok, mint egy, a háttérben , halkan szóló bach fúga.
kikapcsol, elandalít, megnyugtat.
egy darabig feszült figyelemmel követem a gondolatmenetet, amikor pedig elveszni látszik a fonal, akkor lemegyek alfába és a továbbiakban üres szövegként követem a betűket és már kisérletet sem teszek a megértés irányába. megszűnik a fuldoklás érzése és hagyom, hogy tehetetlen elmémet sodorja magával az ár- sőt élvezem a sodródást.
mérő eszmefuttatásait is szeretem olvasni, a baj az, hogy azokat néha meg is értem. és amikor megértem, akkor rájövök, hogy nem értek egyet vele.
lehet, hogy külön ajándék, hogy jótündért nem értem..?
@kisjuci:
de ha lenne, akkor is csak a nésnölcsennelt néznéd 🙂
@Aromo a fékezhetetlen: Adatbázisműveletek, keresők. Nem kicsik, nagyok 🙂
jótündérnek köszi a posztot!
természettudós vagyok, de én már ott lemaradtam, hogy nem tudom mi a különbség a gráf, a grafikon, vagy a függvény között.
Tényleg van olyan része amit értek.
@kisjuci: +=1
@Aromo a fékezhetetlen: 🙂
(csak az apját meg az öccsét láttam operálni,őt meg a tv-ben,vizuális tipus vagyok,s gyakorló nem elméleti)
@lüke: kieg. Végre nem egy kontraszelektált lett az MTA elnöke,bár ez a poszt eltávolítja a kutatástól
Bevallom, párszor elovastam, mert direkte nem matematikusoknak íródott. A második után kezdtem szégyellni magamat, mert…, mert csak. A harmadik után nagyon csúnyákat gondoltam a jótündérről. Aztán újra szégyelltem magam, mert hiszen nem ő tehet róla (de igen).
Majd jött a megkönnyebbülés, a felmentés! Így mindjárt más: ” egy mérnök vagy egy természettudós ezt nagy vonalakban megértheti”.
Tehát ez egy qrva jó poszt, és nagyon tetszett! :))
meggugliztam kicsinyt mire jó ez és arra jutottam, hogy pölö mikor a gps kitalálja melyik a legrövidebb útvonal, az tán gráfelmélettel működik.
pláne ha nem fizetős útvonalat akarsz (ingyé éleken akarsz menni csak).
de azt írták is valahol, hogy hálózatfejlesztés költségének optimalizálására pl jó.
de ha nagyon eleresztem a fantáziámat és felteszem, hogy eccermajd fogunk galaktikusan űrutazni (ami nem tűnik reálisnak, de hátha mégis), akkor hogyan tájékozódunk és tervezünk útvonalat az űrben? mivel nincs viszonyítási pont, mint a Földön.
viszont ha a világegyetem egy térbeli gráf, akkor biztos ki lehet evvel valamit okoskodni.
amúgy index címlap megint.
szabad asszociációk:
1. persze, le kellett volna menni gráf, valószínűség és társai alap definícióihoz, mert a legtöbben még ezeket sem tudják, hogy eszik vagy isszák őket.
2. én megértettem a levezetést, a 13. pontbeli nem létezik valós határérték gráfot bemondásra elhiszem, szerintem itt az igazi varázslat, mert ha ez nem így lenne,akkor a további (szerintem már triviális) lépésekre nem lenne szükség.
3. viszont ha előveszem az egyetemi tanulmányaimat, akkor valós számokra, a sorozatok konvergenciájára, határértékekre vonatkozó dolgokkal nagyon analóg ez az egész, és csak azt érzem, hogy az ottani tételeket egy az egyben áttették CTRL+C, CTRL+V alapon gráfokra.
@ingyenebed: annyit mondanék, hogy BigData. sehová nem kell menni, csak a mérhetetlen, a Googleban megőrzött információs szemétkupacra kell gondolni, a benne lévő összeköttetésekkel. ha majd jön a kvantumszámítógép, az pont ilyen schrödinger macskája módon fog működni, és pont jól kön neki, hogy van ilyen elmélet kidolgozva, és használhatja,
Az ebbe az igazán szomorú, hogy én ebből két hét múlva szigorlatozok, és most olvastam ezekről először…
Lovász László amúgy ma előadást tart Szegeden.
@ingyenebed: ha megnézed a világ legjobb computer science képzéseit, akkor láthatod, hogy az elméleti képzés tele van kombinatorikai-gráfelméleti jellegű kurzusokkal. nem véletlen.
ezt az elméletet egy konkrét helyen fejlesztették ki. egy bizony épülethez kötődik. one microsoft way, redmond, washington állam.
@is: „3. viszont ha előveszem az egyetemi tanulmányaimat, akkor valós számokra, a sorozatok konvergenciájára, határértékekre vonatkozó dolgokkal nagyon analóg ez az egész, és csak azt érzem, hogy az ottani tételeket egy az egyben áttették CTRL+C, CTRL+V alapon gráfokra.”
ezt nem érzed jól. itt nem számok sorozatáról van szó, hanem gráfok sorozatáról. az, hogy ezeken felvesznek egy távolságot és teljessé teszik (esetünkben kompaktifikálják) az még nem CTRL+C,CTRL+V, főleg, hogy nem az a lényeg, hogy létezik a completion (ez triviális),, hanem az, hogy hogyan is néz ki. az alapvető motiváció a szemerédi regularitási lemma, a gráfelmélet egyik szent grálja, amit ebből az egészből le lehet olvasni, teljesen szemléletessé teszi.
@ingyenebed: az útvonalszámításnál az un. genetikai, vagy mutációs algoritmusok az aktuális bazmegek, tehát nem a gráfot járja be, hanem kvázi véletlenszerű mutációkkal közel log valamennyi n lépésben (de elképzelhető, hogy ebben tévedek) lehet útvonalat találni, a klasszikus algoritmusok kb. n-es ordójához képest.
@jotunder: én elolvastam, mivel csak programozó matematikus vagyok (és abból is főleg programozó), és felteszem azt a kérdést, amivel minden alapkutatásban dolgozó embert fel lehet idegesíteni egy pillanat alatt: és hol lehet ezt a való életben (vö: ipar) használni? 🙂
Hát, én nem matematikus vagyok, de volt szerencsém egy keveset a gráfokról tanulni. Sosem voltam nagy barátságban velük. Főképp azért, mert a legtöbbször a mesterséges intelligencia kutatás tárgynál jöttek elő, amitől szégyen vagy sem, de kivert a víz. 🙂
@sárospataki lány:
Felteszem pl. az általam említett MI kutatásban és fejlesztésben. De majd jotunder kijavít, ha tévednék.
Hogy „mire lehet hsználni” ezt az egészet ? Fölteszem , hogy elsődlegesen azokon a területeken, ahol ezek a gráfok jelen vannak. Az idézett Lovász könyv legeslő bevezető része hoz páldákat ( 1.1 Huge networks everywhere ) hálistennek azt én is megértettem és nem kétséges hogy milyen hatalmas alkalmazási lehetőségek előtt nyit utat nagyon eltérő területeken.
jól gondolom, hogy egy Hi sorozat akkor konvergens, ha minden k-ra és G-re p(k,G,Hi) konvergens?
kicsit sokáig tartott rájönnöm, hogy miért nem elég p(G,H)-t írni, de csak rájöttem (hiába, nem elég irodalomként olvasni). azon még gondolkodom, hogy a mérhetőség-integrálhatóság miért kell. vagy nem is kell, csak kijön, hogy véges gráfok konvergens sorozatának limesze mérhető?
@dr Brcskzf Gröőő: valójában elég p(G,H)-t írni, de ha a k-t odaírja az ember, akkor világos, hogy G egy k csúcsú gráf. és igen, akkor konvergens egy gráfsorozat…
ha nincs mérhetőség, akkor nincs értelme a mintavételnek.
Kb a 8. pontig értettem.
Ezen elakadtam: „egyre nagyobb gráfok csúcsai összeállnak egy folytonos szakasszá” Már miért állnának össze?
((főleg, ha vannak köztük jobb és baloldali csúcsok, esetleg harmadik utasok, anarchisták és liberánsok))
@ámbátor: mondjuk gondold azt, hogy a véges gráf n csúcsai a [0,1] szakaszon az 1/n, 2/n,…..n-1/n, 1 pontok. akkor ha n tart a végtelenhez, a pontokra koncentrált valószínűségeloszlás az egyenletes eloszláshoz tart. úgy ahogy a közelítő szummák a valódi integrálhoz.
@jotunder: Kb így gondoltam, csak a törtekből nekem nem áll össze a folytonosság. Ez inkább amolyan fizikus megközelítés, hogy ha elég sűrű, akkor már mintha folytonos lenne. Matekban a folytonos nálam a szakadásmentességgel alliterál de az nyilván másik domén.
@jotunder: kösz. ebből is látszik, hogy húderégen volt – a kétpontú üres gráf különbözik a hárompontútól.
Jótündér, mondtam már hogy utállak?
(nekem a „gráf” az még mindig csak a Zeppelin)
Ennek a videónak a vége felé is szó van erről a témáról, persze az egészet érdemes megnézni. 🙂
http://www.youtube.com/watch?v=gQ3gEk8AkO8
Én nem vagyok matematikus, ezért nekem csak két kérdésem lenne.
1, ha ez nem matematikusoknak van írva, akkor mi lehet írva a matematikusoknak?
2, Mi az a „gráf” ?
🙂
@DarthVader: 1) arxiv.org/abs/math/0702004
2) pontok, amiket vagy összekötsz vagy nem.
A 19. pontig teljesen világos volt. Ott elvesztettem a fonalat. Most nem tudok rá gombot varrni.