A gráfok
A gráfelmélet a matematika viszonylag új kutatási területe. Aki hallott már gráfokról, az biztosan ismeri a Königsbergi hidak problémáját, amit Leonhard Euler 1736-ban bizonyított. A matematika történetében igen jelentős a probléma és az Euler-féle megoldás, hiszen az első gráfelméleti problémaként tarthatjuk számon.
A Königsbergi hidak rejtélye
A poroszországi Königsbergben (napjainkban Kalinyingrád, Oroszország) hét híd ívelt át a várost átszelő Prégel folyón úgy, hogy ezek a folyó két szigetet is érintettek. A városlakók azzal a kérdéssel fordultak Eulerhez, a híres tudóshoz, hogy végig lehet-e menni az összes hídon úgy, hogy mindegyiken csak egyszer haladjanak át, és visszaérjenek a kiindulópontba.
A bizonyítás során a problémát a gráfelmélet nyelvén fogalmazta meg: a folyó partjait, a szigeteket csomópontoknak, míg az őket összekötő hidakat éleknek tekintette. Az élek és csomópontok pedig meghatároznak egy gráfot!
A probléma megoldása sok helyen megtalálható, így ennek megkeresését az olvasóra bízom.
A gráfelmélet hazánkban
A magyar gráfelmélet kezdetének az 1947-es Eötvös matematikai versenyt tekinthetjük, amelyet később Kürschrák József Matematikai Tanulóversenynek neveztek át. Itt szerepelt először gráfelméleti feladat a kitűzött példák között, sőt, már az érettségin is elő-elő került a témakör. Az egyetemi oktatásban az 1970-es évek óta egyre több kurzus is foglalkozik a gráfokkal és alkalmazási területeivel. A legjelentősebb magyar matematikusok végeznek, végeztek kutatásokat a gráfok témakörével kapcsolatban, így például Egerváry Jenő, Erdős Pál, Gallai Tibor, Hajnal Péter, Kőnig Dénes, Lovász László, Rényi Alfréd, Pósa Lajos.
A gráfelmélet kedvelt, dinamikusan fejlődő kutatási terület a matematikusok számára.
Gráfok a mindennapokban
A gráfok segítségével nagyon jól lehet szemléltetni a matematika sokrétű alkalmazását. Meglepőnek tűnhet, hogy a matematikán kívül például az iparban, gazdaságban, közlekedésben és különböző szolgáltatásokban is használnak gráfokat. Talán ez egyik legkézenfekvőbb, legismertebb probléma az utazó ügynök problémája. Adott egy címlista, amit pl. egy kávéautomatákat üzemeltető cég használ, amely az utántöltés során szeretne mindig a leggyorsabb (vagy a legköltséghatékonyabb) útvonalon eljutni a gépeihez.
A különböző útvonalak szemléletes megjelenítésére, modellezésére a gráfok tökéletesen alkalmasak.
A Facebook is gráf?
Napjainkban internetes közösségi portálokon épül ki a fiatalok kapcsolatrendszere, ezeknek a kapcsolatoknak, ismeretségeknek bemutatására a gráfok rendkívül jól használhatók. A Facebook közösségi portálhoz kapcsolható példa segítségével a gráfelmélet alapfogalmai nagyon jól szemléltethetőek.
A Facebook-felhasználók a gráf csúcsai. Bejelölésről vagy megjelölésről akkor beszélhetünk, ha egy személy ismerősnek kér fel egy másik embert. Ebben az esetben a kapcsolat még nem kölcsönös, hanem csak egy irányú, amit irányított élek használatával szemléltethetünk. Az irányított él a bejelölő személy felől a megjelölt személy irányába mutat. Ismeretségen értünk egy kölcsönös kapcsolatot két ember közt akkor, ha azok Facebookon egymás ismerősei.
Az ismeretségek a gráf (irányítatlan) élei.
Ha az egyik ember megjelöli a másikat vagy felkéri ismerősnek, úgy a kapcsolat még nem kölcsönös, Viszont ha a megjelölt személy visszajelöli, visszaigazolja (megerősítés) az őt megjelölő személyt, akkor felőle egy irányított él fog az eredetileg megjelölő személy felé mutatni. Így a két csúcs között már két él van, irányuk ellentétes. A Facebook ezt a zavaró helyzetet a két irányított él „összeolvadásával" oldja fel, és egy irányítatlan él keletkezik, a két személy egymás ismerőse lesz. Ha már két személy ismerős, akkor nem lehet visszakövetni, hogy ki kezdeményezte a kapcsolatot.
További érdekes oldalak:
Zsigó Zsolt cikke
