Ugrás a tartalomhoz

graph theory

A Wikiszótárból, a nyitott szótárból

Angol

Főnév

graph theory (tsz. graph theories)

  1. (matematika, informatika) gráfelmélet

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

  • Prim algoritmus
  • Kruskal algoritmus

4. Topologikus rendezés

  • Irányított körmentes gráf (DAG) sorrendbe állítása
  • Pl. feladatok ütemezése

5. Gráf színezése

  • Cél: szomszédos csúcsok ne kapjanak azonos színt
  • Pl. térképszínezés, ütemezés, register allocation


📊 Példák az életből

Terület Gráf jelentése
Hálózatok számítógépek (csúcs), kábelek (élek)
Közlekedés városok (csúcs), utak (élek, súly: távolság/idő)
Szociális háló emberek (csúcs), kapcsolatok (élek)
Web oldalak (csúcs), linkek (irányított élek)


📚 Kombinatorikus gráfelmélet

Gráfelmélet sok kombinatorikus problémával foglalkozik:

  • Hamilton-kör: minden csúcsot egyszer meglátogat
  • Euler-kör: minden élt egyszer jár be
  • Kötött pontszámú gráf: adott fokszámú csúcsokból épített gráf
  • Gráf izomorfizmus: két gráf szerkezetileg azonos-e?


🔐 Haladó témák

  • Gráfkomponensek és erősen összefüggő komponensek (SCC)
  • Áramlás gráfokban (pl. Ford–Fulkerson, hálózati áramlás)
  • Random gráfok, Erdős–Rényi modellek
  • Gráf-alapú gépi tanulás (pl. GNN – Graph Neural Networks)


🧪 Példa: Dijkstra algoritmus lépései

  1. Kezdeti csúcs súlya 0, a többi ∞
  2. Minden szomszédot frissít a minimális értékre
  3. Kiválasztja a legkisebb súlyút, azt véglegesíti
  4. Ismétlés, amíg minden csúcsot be nem járt

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=graph_theory&oldid=3495926”