A gráfelmélet lényege
A gráfelmélet ma már a matematika egyik alapköve, alkalmazzák barátsági hálózatok, közlekedési útvonalak vagy épp légitársaságok járathálózatainak vizsgálatára. Az alapgondolat egyszerű: egy rendszer objektumai között bizonyos párok relációban állnak, más párok nem. Ezeket az objektumokat – legyenek emberek, városok vagy országok – pontokként (csúcsokként) ábrázoljuk, az őket összekapcsoló kapcsolatokat pedig vonalakként (élekként). Így lesz például egy esküvői ülésrendből, egy közúti térképből vagy egy világtérképből is gráf.
A gráf és a látásmód
Maria Chudnovsky, a Princeton Egyetem matematikusa, szenvedélyesen vonzódik a diszkrét matematikához, különösen a gráfelmélethez. Nevetve meséli, hogy már főiskolásként is ezek voltak a leginkább hozzá illő tárgyak: azok, amelyek után sem kellett tanulni, hiszen mélyen gyökeret vertek benne. Az igazi áttörést az hozta, amikor bekerült a Princetonba, ahol a diszkrét matematika fellegvára éppen a gráfelméletben bontakozott ki. Az elmélet vizuális gondolkodásmódot kíván: Chudnovsky számára minden matematikai gondolatmenet képekké áll össze, a papíron pontokat húz, vonalakat köt össze, vizuális modelleket alkot. Csak a végső levezetést írja le, amikor már biztos abban, hogy nem hagyott ki semmit.
Az esküvő mint gráfelméleti probléma
Chudnovsky nemcsak elméleti szinten alkalmazza az elméletet: például esküvője ülésrendjét is gráfelméleti alapon tervezte. A vendégeket csúcsokként ábrázolta, és ha két vendég ellenségek voltak (nem ülhettek egy asztalhoz), közéjük élt húzott. A cél az volt, hogy minden asztalnál csak egymással békében lévő emberek üljenek – vagyis a gráfot színekkel csoportosítsa úgy, hogy egy színben (asztalnál) ne üljenek ellenségek. Ha kevés az „él” a gráfban, vagyis az ellenségek száma alacsony, a feladat az úgynevezett mohó algoritmussal gyorsan megoldható: egymás után kitöltöm az asztalokat, ügyelve arra, hogy ne ültetek össze ellenségeket. A gyakorlati életben tehát a gráfelmélet szinte bármilyen szervezési kérdésben bevethető, legyen akár útvonaltervezés, akut betegszállítás vagy éppen szemétgyűjtési logisztika.
A színezés problémája, a tökéletes gráfok és nagy áttörések
A gráf színezési problémája főként azzal foglalkozik, hányféle színt (kategóriát, asztalt) kell alkalmazni, hogy két összekapcsolt csúcs ne kapjon ugyanolyan színt. Ez például országok esetében azt jelenti, hogy a térképen két szomszédos ország ne legyen azonos színnel jelölve; innen ered a híres Négy szín tétel (Four Colour Theorem) is, amely szerint a Föld bármely térképét legfeljebb négy színnel kiszínezhetjük úgy, hogy a közös határszakaszon érintkező országok különböző színt kapnak.
A tökéletes gráfok olyan speciális gráfok, amelyeknél a legnagyobb, teljesen összekapcsolt részgráf (klikk) mérete pontosan annyi, ahány szín a teljes gráf kiszínezéséhez kell. Ennek jelentőségét a hatvanas években a francia matematikus, Claude Berge ismerte fel, és megfogalmazta az erős tökéletes gráf sejtést, amely csak 2002-ben nyert bizonyítást Chudnovsky és három kollégája jóvoltából. Maga a bizonyítás hatalmas, 150 oldalas tanulmány lett, rengeteg részgráfra, esetre, szerkezeti felbontásra alapozva. Kulcsa, hogy a bonyolult egész helyett sikerült esetekre bontást alkalmazni – minden egyes helyzetben más-más módszer működött.
Matematika, kultúra, személyesség
Chudnovsky orosz származású, tizenévesen Izraelbe költözött, így számára a matematika egyetemes kommunikációs eszköz lett. Mint mondja: nem számít, ki milyen jól beszéli a helyi nyelvet, a matek „magától beszél”. Ha valami bizonyítható, az mindenütt igaz. A matematika nyelve kulturális, földrajzi és nyelvi határokon átível. Ez az oka annak is, hogy nem érzékeli problémának, ha saját kutatásában az absztrakt dolgok dominálnak – hiszen a világ minden táján akad együttműködő kolléga, akivel egy nyelvet beszél a matematikán keresztül.
Szépség, intuíció, öröm
Chudnovskyt a munkában nem a problémák nehézségi szintje motiválja, hanem az a pillanat, amikor egy addig lezáratlan, káosznak tűnő rendszerről kiderül: valójában leírható szabályai vannak. Imádja, ha valamiben strukturális rendet fedez fel. Az örömöt az apró „eureka-pillanatok” jelentik számára. Vannak, akiket az absztrakt szépség, másokat a kihívás vagy épp az ellentmondás izgat. A matematikai kutatás szépsége, hogy mindenkinek megvan a maga egyéni motivációja – és a matematika mindenki számára univerzális alapokat nyújt az értelmezéshez.
