Gráfok alkalmazása a gyakorlatban

A gráfelmélet a matematika viszonylag új területe. Euler 1736-ban oldotta meg a „königsbergi séta” problémáját, de a tudományág fejlődése csak a XIX. század végén kezdődött el. Kőnig Dénes, a Műegyetem tanára írta az első tudományos színvonalú gráfelméleti könyvet 1936-ban.
Lássunk néhány példát a gráfok alkalmazására! Négy kis település, legyenek A, B, C és D közösen vasútépítésbe kezd. Olyan hálózatot akarnak kialakítani, hogy bármelyik faluból el lehessen jutni a többibe, de mindenhová csak egyféleképpen. A két legnagyobb helységet, C-t és D-t mindenképpen össze kell kötni. Hányféleképpen építhetik meg a vasútvonalakat? Ha hasonló feladattal találkozol, akkor próbáld megtalálni az összes, a feltételeknek megfelelő lehetőséget. A kapott ábrák közös tulajdonsága, hogy összefüggők és nem tartalmaznak kört. Az ilyen gráfokat fának nevezzük. A fagráf egyik legismertebb alkalmazása a családfa.
Egy öttagú társaságot arról kérdeztek, hogy a másik négy ember közül hány ismerősük van a Facebookon. A következő válaszokat adták: 2, 3, 3, 1, 2. A válaszokat szemléltessük gráffal! A gráf csúcsai az emberek, az élei az ismeretségek. A próbálkozásaink nem vezettek eredményre. Lássuk, miért? Ha a csúcsok fokszámát összeadjuk, az élek számának a kétszeresét kapjuk, mert egy élhez két csúcs tartozik. Ebből következik, hogy a csúcsok fokszámának összege páros szám. A példában szereplő társaság valamelyik tagja rosszul emlékezett az ismerősei számára, hiszen az öt szám összege 11. Ezt az összefüggést sokféle feladatban alkalmazhatjuk, legyen szó ismeretségekről, kézfogásokról, sportmérkőzésekről vagy településeket összekötő utakról.
Az iskolai asztalitenisz bajnokság egyik csoportjába 6 lány került: Anna, Bea, Csilla, Dóri, Eszter és Flóra. A versenykiírás szerint mindenki mindenkivel egyszer játszik. Eddig Anna játszott Csillával, Dórival és Eszterrel, Bea Eszterrel és Flórával, Csilla Annán kívül Dórival. Flóra pedig Beán kívül Eszterrel. Hány mérkőzés van még hátra?
Ezt a feladatot gráfokkal nagyon egyszerűen meg lehet oldani. A gráf csúcsai a játékosok, élei a mérkőzések. Az ábráról le tudjuk olvasni, ki hány mérkőzést játszott és hány meccs volt eddig. A csúcsok fokszámának az összege 14, az élek száma ennek a fele, 7. Tehát eddig 7 mérkőzést játszottak a lányok. Ha mindenki mindenkivel játszik, minden versenyző 5 mérkőzést fog játszani. $6 \cdot 5 = 30$. A mérkőzések száma ennek a fele, 15. 7 meccs már volt, tehát 8 van még hátra.
Felmerült a feladatban, hogy összesen hány mérkőzés lesz a 6 lány között. Ezt a kérdést általánosíthatjuk: az n csúcsú teljes gráfnak hány éle van? Mivel minden csúcsból „en” mínusz egy él indul ki, ezeket összeszorozzuk a csúcsok számával. Így minden élt kétszer számoltunk, ezért osztani kell 2-vel.
Napjainkban a matematikában, az informatikában, a fizikában, a geográfiában, a kémiában, az orvostudományban és még számos területen használják a gráfokat mint modelleket, valamint a gráfelmélet különböző eredményeit a felmerülő kérdések, problémák megoldására.
A térképek színezése is gráfelméleti kérdésként vetődik fel. Célszerű minél kevesebb színt használni. Mennyi lehet a minimális szín, amellyel egy gömbön, vagy síkon lévő térkép kiszínezhető úgy, hogy ne legyen két azonos színű szomszédos régió. Azt sikerült bizonyítani, hogy öt szín mindig elegendő, de elég-e négy szín? Sokáig csak sejtés volt, hogy igen. Több hibás bizonyítás után a kérdésre 1976-ban végleges válasz született, a sejtésből tétel lett. Ez az első nevezetes tétel, amelyet számítógép segítségével bizonyítottak be.
Karinthy Frigyes elmélete szerint a Földön bárki kapcsolatba hozható bárkivel egy ismeretségi láncon keresztül, amelyben a két végpont között maximálisan öt elem van. Egy 2011-es vizsgálat szerint még ennél is kisebb ez a szám: a Facebookon bárki kapcsolatba kerülhet bárkivel úgy, hogy a két aktív facebook felhasználó között 4 egész 74 század, azaz 4 vagy 5 tagból álló ismeretségi lánc áll.
A gráfelméletben Kőnig Dénes után is számos magyar matematikus ért és ér el jelentős eredményeket: többek között Erdős Pál, Rényi Alfréd és Lovász László.