Üdvözlöm, Ön a graph theory szó jelentését keresi. A DICTIOUS-ban nem csak a graph theory szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a graph theory szót egyes és többes számban mondani. Minden, amit a graph theory szóról tudni kell, itt található. A graph theory szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Agraph theory és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
A gráfelmélet a diszkrét matematika egyik ága, amely pontok (csúcsok) és azok kapcsolatainak (élek) vizsgálatával foglalkozik. Alkalmazzák számítógépes hálózatokban, közlekedésben, közösségi hálózatokban, optimalizálási feladatokban, adatstruktúrákban és mesterséges intelligenciában.
🧱 Alapfogalmak
Gráf (G): két halmazból áll: G = (V, E) ahol:
V: csúcsok (pontok, “vertices”) halmaza
E: élek (kapcsolatok, “edges”) halmaza
📌 Típusok
1. Irányítatlan gráf
Az élek kétirányúak (pl. barátság)
2. Irányított gráf (digraph)
Az élek irányítottak (pl. követés, hivatkozás)
3. Súlyozott gráf
Minden élhez számérték (súly, pl. távolság) tartozik
4. Teljes gráf
Minden csúcs össze van kötve minden másikkal
5. Fa (Tree)
Olyan gráf, amely összefüggő és nincs benne kör
🔄 Gráf reprezentációk számítógépen
Módszer
Leírás
Szomszédsági mátrix
n×n mátrix, 1 ha él van
Szomszédsági lista
Minden csúcshoz lista, hogy mivel van összekötve
Éllista
Élek listája: (u, v) párok
📏 Gráf jellemzők
Fokszám (degree): hány él indul ki a csúcsból
Út (path): csúcsok sorozata, melyek éllel vannak összekötve
Kör (cycle): zárt út, ahol az első és utolsó csúcs megegyezik
Összefüggő gráf: minden csúcsból elérhető bármely másik
🔍 Fontos algoritmusok
1. Gráf bejárása
Algoritmus
Módszer
Alkalmazás
DFS (mélységi keresés)
rekurzív / verem
kör keresés, komponensek
BFS (szélességi keresés)
soros
legrövidebb út nem súlyozott gráfban
2. Legrövidebb út keresése
Algoritmus
Működés
Használható
Dijkstra
nem negatív súlyok
útvonaltervezés
Bellman-Ford
lehet negatív súly is
pénzügyi modellek
Floyd–Warshall
minden csúcs–csúcs út
kis gráfokra
3. Minimális feszítőfa
Olyan fa, amely minden csúcsot összeköt minimális összsúllyal