grafelméleti

A grafelmélet olyan matematika ág, amely gráfokkal foglalkozik. A gráf egy absztrakt struktúra, amely csúcsokból (pontokból) és azokat összekötő élekből áll. Lehetnek egyszerű gráfok, multigráfok, súlyozott gráfok vagy irányított gráfok. A hagyományos jelölés szerint G=(V,E) a gráf, ahol V a csúcsok halmaza, E pedig az élek halmaza.

Historikusan Euler Königsbergi hídproblémája indította a kutatást; a 20. században a grafelmélet önálló tudományág lett. Kulcsfogalmak között találhatók a kapcsolhatóság, út, ciklus, fa és a planaritás; később a színezés, a párosítás és a hálózati folyamatok kerültek előtérbe.

Fő fogalmak közé tartozik a kapcsolhatóság és az összefüggő komponensek felismerése, az út és a ciklus, a fa szerkezete, a gráf színezése (minimális színek száma), a párosítás, valamint a hálózati folyamatok (pl. maximális áramlás). A grafelméletet több ágra osztják: szerkezeti grafelmélet, algoritmikus grafelmélet, probabilisztikus grafelmélet és spektrális grafelmélet.

Algoritmusok és módszertan: gyakran használt eszközök közé tartozik a BFS és a DFS bejárás, a rövid út keresése (Dijkstra, Bellman–Ford), a minimális feszítőfa keresése (Kruskal, Prim) és a hálózati problémák megoldása (Ford–Fulkerson/Edmonds–Karp). Sok probléma kombinatorikus és számításszerű nehézséggel bír.

Alkalmazások: a grafelmélet alapot ad informatikai hálózatokhoz, közösségi hálózatokhoz, biológiai és kémiai szerkezetekhez, logisztikához, ütemezéshez és tervezéshez. Emellett elméleti területekben is központi szerepet játszik.

Jelölés és kapcsolódó területek: G=(V,E) a hagyományos jelölés, irányított gráfoknál pedig az élek irányossága szembetűnő. A grafelmélet szoros kapcsolatban áll a diszkrét matematikával, a számítástudománnyal és a kombinatorikával.