Lendületesek – Bérczi Kristóf

Ha a vektorok állása között nincs összefüggés a térben, akkor lineárisan függetlennek nevezzük őket. Ekkor nem lehet belőlük „kikeverni” a nulla vektort. Két dimenzióban a nem egy irányba mutató vektorok a függetlenek, míg a térben pontosan akkor lineárisan független vektorok egy halmaza, ha semelyik három nem esik egy síkra. A függetlenség a lineáris algebrai kutatások egyik legalapvetőbb fogalma.

Bérczi Kristóf Fotó: berkri.web.elte.hu

„Így megszületett a matroidok fogalma. A matroidok tehát olyan absztrakt struktúrák, amelyek lényeges tulajdonságaikban (például a lineáris függetlenségben) megegyeznek, így matematikai értelemben nagyon jó velük dolgozni – mondja Bérczi Kristóf, az ELTE Matematikai Intézet Operációkutatási Tanszék munkatársa, a Lendület-kutatócsoport vezetője. –Sőt a lineáris függetlenség koncepciója a matematika sok más területén is megjelenik, például a gráfelméletben.
A gráfokat csúcsok és a közöttük kapcsolatot teremtő élek építik fel, mintha leegyszerűsített térképek lennének. A gráfoknál is megfigyelhetők azok
a tulajdonságok, amelyek nagyon hasonlítanak a lineáris függetlenség elvére. Adottak tehát hasonló tulajdonságokkal rendelkező, egymástól azonban látszólag távoli matematikai rendszerek, ezért természetes módon felmerült az igény egy olyan elmélet kidolgozására, amely mindezen hasonló jellegzetességeket együttesen képes megfogni, és absztrakt módon általánosítani.

A matroidok levetkőzik az adott struktúra speciális tulajdonságait (például
a gráfok gráfszerűségét), és csak azok a lényeges jellegzetességek maradnak meg belőlük, amelyek kapcsolatot teremtenek a különböző rendszerek között.”

A háttérben megbújó közös vonások

A matroidok lényegében olyan halmazrendszerek, amelyek jól képesek megfogni a függetlenség fogalmát. Ez volt a célja a matroidelmélet atyjának, Hassler Whitney amerikai matematikusnak, amikor 1935-ben megírta
a tudományterületet megteremtő, A lineáris összefüggés absztrakt tulajdonságairól című alapművét. Mára a matroidelméletet a matematika számos területén alkalmazzák, így a gráfelméleten kívül a kombinatorikában, az operációkutatásban és az informatikában is. A nemzetközi matroidelméleti kutatásokban jelentős szerepet játszott Lovász László, a Magyar Tudományos Akadémia előző elnöke.

„A matematikának nagy erőssége, hogy képes észrevenni a különböző területeken használt eszközök hátterében megbújó közös vonásokat, majd ezeket absztrahálja – folytatja Bérczi Kristóf. – Ha ugyanis van egy
a matroidhoz hasonló absztrakt fogalmunk, akkor például absztrakt algoritmusokat tervezhetünk.”

Az elméletnek számos, a valós életre vonatkozó alkalmazása lehetséges. Természetesen a valóságban nem fogunk matroidokkal találkozni, hiszen ezek csak absztrakt konstrukciók, de ha észrevesszük, hogy a háttérben megbúvó struktúra egy matroid, akkor máris alkalmazhatjuk rá a kifejlesztett absztrakt algoritmusokat.

Nyitott kérdések és bizonyítatlan sejtések

A matroidelmélet egyik legszembetűnőbb gyakorlati alkalmazása
a rúdszerkezetek merevségvizsgálata. A rúdszerkezetek (például a hidak állványzatai) csuklókból és az őket összekötő rudakból épülnek fel. Az efféle szerkezetek merevségét (erőhatásnak ellenálló képességét) vizsgálni kell, hiszen senki sem akarja, hogy összedőljön a híd. Bár első ránézésre
a rúdszerkezeteknek nincs közük a matroidokhoz, mégis definiálhatunk egy merevségi matroidot, és a merevségelmélet jelentős része e matroid különböző tulajdonságainak vizsgálatából áll. De a matroidelméletet
a nyomtatott áramkörök tervezésénél is alkalmazzák, hiszen ott is számos matroidszerű jellegzetesség lelhető fel.

„Amikor alkalmazzuk a matroidokról meglévő tudásunkat, sohasem matroidokról beszélünk,

csak felismerjük, hogy matroid áll
a háttérben, de a megoldást már lefordítjuk az adott gyakorlati problémára

– érvel Bérczi Kristóf. – A Lendület-csoportunk kutatási terve három területre fókuszál. Ezek között van elméleti jellegű kérdés és gyakorlati alkalmazás is.”

Bár a matroidokat már az 1930-as évek óta kutatják, még mindig sok nyitott kérdés, illetve bizonyítatlan sejtés létezik velük kapcsolatban. A Lendület-csoport kutatásainak egy része ezért a matroidok struktúrájának megértésére koncentrál. Ez azért fontos a matroidelmélet szempontjából, mert sok
a társterületekről (például a gráfelméletből) érkező sejtés van, ami az általános jelenségek speciális eseteit fogja meg. A kutatók abban bíznak, hogy ha e kérdésekben sikerül előrelépniük, az azonnal alkalmazható lesz más területeken.

Gazdasági alkalmazások

A Lendület-kutatásoknak lesz ennél gyakorlatiasabb irányuk is, vizsgálni fogják ugyanis a kombinatorikus piacok árazását. A kombinatorikus piac mindössze egy olyan piacot jelent, amelyen vannak termékek és vásárlók, és minden vásárlónak van egy a termékekre vonatkozó kiértékelési függvénye. A függvény azt adja meg, hogy a termékek egy halmaza mennyire kedvező a számára (vagyis mennyire találkozik a preferenciáival). Például az autóvásárlók nem feltétlenül ragaszkodnak egyetlen autótípushoz, hanem a különböző márkák eltérő értéket képviselnek a számukra, és ezek az értékek vásárlónként eltérnek.

A kutatás tárgya, hogy egy ilyen piacon

hogyan lehet úgy beárazni a termékeket, hogy a szétosztásuk után mindenki a lehető legelégedettebb legyen,

és ezzel maximálni lehessen az úgynevezett összhasznot (vagyis a vásárlók által megkapott termékek szubjektív értékét). A kereskedelemben használnak olyan ármeghatározási eljárásokat, amelyek e szempontokat veszik figyelembe. Ezek azonban mind statikusak, ami azt jelenti, hogy a kiírt árak változatlanok maradnak, és mindenkire vonatkoznak. Ez a körülmény azonban sok esetben csökkenti az összhasznot, hiszen nem biztosítja a termékek ideális szétosztását, az úgynevezett szociális optimum elérését.

„Vannak kutatások, amelyek a dinamikus árazást vizsgálják. Ez azt jelenti, hogy az árakat minden vásárló távozása után újra meghatározzuk, a megváltozott körülményeknek megfelelően – mondja Bérczi Kristóf. – A kutatócsoportunk azt is vizsgálni fogja, hogy dinamikus árazás esetén mindig elérhető-e
a szociális optimum. Kiderült, hogy e terület lényegi kérdései is nagyon szorosan kapcsolódnak a matroidokhoz.”

A kutatások másik gyakorlati iránya az inverz optimalizálással foglalkozik. Ahogy a neve is utal rá, ez bizonyos értelemben a hagyományos optimalizálás fordítottja, és a legkülönfélébb matematikai feladatokra lehet alkalmazni.
A fordítottság abban áll, hogy a feladat megoldása adott, és az eredeti paramétereket igyekeznek úgy beállítani, hogy azokból a kívánt eredmény jöjjön ki. Például

szeizmológiai vizsgálatoknál alkalmazzák azt az eljárást, hogy az adott és ismert lefutású törésvonalnál visszafejtik, hogy mely paraméterek esetén jöhetett létre. Ezek hátterében is matroidoptimalizálási probléma fedezhető fel.