Lendületesek: Vidnyánszky Zoltán

A gráfelmélet egyik nagy problémája, hogy hogyan írjuk le a nagy, de véges gráfok viselkedését – ezek ugyanis sokszor paradoxonszerűen működnek, így nehezen értelmezhetők. Vidnyánszky Zoltán, az ELTE Analízis Tanszék kutatója és az MTA–ELTE Lendület Borel Kombinatorika és Komplexitás Kutatócsoport vezetője és munkatársai e problémára keresnek megoldásokat. Munkájuk akár a nagy számítógépes hálózatok tervezésekor alkalmazható algoritmusokat is eredményezhet.

2023. december 4.

Vidnyánszky Zoltán matematikus kutatói pályája kezdetétől fogva halmazelmélettel, vagyis a végtelen halmazok viselkedésével foglalkozik. A halmazelméletben és a matematika egészében is a gráfok (vagy más néven hálózatok) vizsgálata kiemelt szerepet tölt be. Ha a véges gráfelméletben használt fogalmakat a lehető legegyszerűbben általánosítjuk végtelen gráfokra, a viselkedésük gyakran antiintuitív, paradoxikus, és nem tükrözi a véges esetbeli tapasztalatainkat.

Vidnyánszky Zoltán

Ennek áthidalásában segít a definiálhatóság fogalma. Egy halmazt akkor mondunk definiálhatónak, ha létezik egy „egyszerű” leírása, bizonyos értelemben egy algoritmus annak eldöntésére, hogy egy adott elem a halmazba tartozik-e. Nem nehéz látni, hogy vannak olyan végtelen halmazok, melyek egyáltalán nem definiálhatóak. A fenti probléma kiküszöbölésének egyik módja tehát, hogy

csak definiálható gráfokat vizsgálunk, és ezek definiálható tulajdonságairól kérdezünk.

„Ily módon sokkal intuitívabbá válik a végtelen hálózatok viselkedése, hiszen a definiálható végtelen hálózatokban megszabadulhatunk a végtelen hálózatok vizsgálatát sokszor jellemző paradoxikus tulajdonságoktól – mondja Vidnyánszky Zoltán, az MTA–ELTE Lendület Borel Kombinatorika és Komplexitás Kutatócsoport vezetője, aki korábban a Kaliforniai Műszaki Egyetem, a Caltech posztdoktori kutatója volt. – Az is kiderül ilyenkor, hogy a nagy véges hálózatok viselkedése nagyon hasonlíthat a végtelen hálózatokhoz.”

Pontosabban jelen esetben a nagy, véges gráfok viselkedését az elosztott hálózatok elméletével írják le, ami az utóbbi években egyre nagyobb érdeklődést vált ki a matematikusok körében. Eszerint adott egy véges számítógépes hálózat, és úgy kell hálózatban problémákat megoldanunk, hogy közben nem látjuk az egész hálózatot. Minden csúcs csak az egész hálózathoz képest kicsiny környezetét látja (szomszédait, a szomszédok szomszédait és így tovább). Bizonyítható, hogy ezen elosztott számítástudományi modellek (hálózatok) némelyike ugyanúgy viselkedik, mint azok a „folytonos” végtelen modellek, amelyeket a Lendület-csoport is vizsgál.

E megközelítést egyébként számos területen alkalmazzuk a természettudományokban. A folyadékokat például folytonos végtelen objektumként modellezik a fizikában, noha tudjuk, hogy a folyadékokban véges sok molekula van. Vagyis – Vidnyánszky Zoltán szavaival – „a játék a véges sok és a definiálható végtelen között szépen működik”.

A kutatócsoport egyik alapvető célja, hogy

lehetővé tegyék a különféle tételek és technikák átvitelét a véges és a végtelen hálózatok között.

A kutatócsoport-vezető szerint a csoport által végzett gyakorlati munka nem fog különbözni bármely matematikai alapkutatási feladattól. „Ritkán használunk számítógépet a kutatáshoz, inkább tollal és papírral dolgozunk” – folytatja Vidnyánszky Zoltán.

A csoportvezető arra számít, hogy a kutatóprogram végére jobban megértik a véges és a végtelen hálózatok közötti kapcsolatot, a köztük lévő átmenetet. A kutatás eredményeként előállhatnak olyan definiálható eljárások a végtelen gráfokon, amelyekről kiderülhet, hogy a véges, elosztott hálózatokon valóban futtatható algoritmusokat adhatnak meg, így nem kizárt, hogy bizonyos nagy számítógépes hálózatok működését hatékonyabbá tehetik.

Lendület Program

A témához kapcsolódó cikkeink