graph

graph (tsz. graphs)

1. (informatika) gráf
2. grafikon

A gráf (angolul graph) a diszkrét matematika egyik központi fogalma. A gráfelmélet azokat a struktúrákat vizsgálja, ahol objektumok (csomópontok, pontok vagy csúcsok) között kapcsolatok (élek) vannak. A gráfok segítségével modellezhetünk sokféle valós és elméleti rendszert, például közösségi hálózatokat, útvonalhálózatokat, számítógép-hálózatokat vagy akár logikai összefüggéseket.

Egy gráf egy csúcsokból és élekből álló halmaz:

• Csúcs (vertex, többes száma: vertices): az elemek, amelyeket össze akarunk kötni.
• Él (edge): a kapcsolat két csúcs között.

Egy gráf formálisan:

$${\displaystyle G=(V,E)}$$

ahol:

• ${\textstyle V}$: a csúcsok halmaza,
• ${\textstyle E\subseteq \{\{u,v\}\mid u,v\in V,u\neq v\}}$: az élek halmaza, ha a gráf nem irányított,
• vagy ${\textstyle E\subseteq \{(u,v)\mid u,v\in V,u\neq v\}}$: ha a gráf irányított.

• Nem irányított gráf: az élek nem hordoznak irányt (pl. ${\textstyle \{A,B\}}$).
• Irányított gráf (digráf): az élek irányítottak (pl. ${\textstyle (A,B)}$ ≠ ${\textstyle (B,A)}$).

• Súlyozatlan gráf: minden él egyenrangú.
• Súlyozott gráf: az élekhez súly (számérték) tartozik, pl. távolság, költség, idő.

• Egyszerű gráf: nincs hurok (önmaga felé mutató él) és nincs két csúcs között több él.
• Többszörös gráf: lehet több él ugyanazon csúcspár között.
• Hurokgráf: lehetnek hurokélek, pl. ${\textstyle (A,A)}$.

• Teljes gráf (Kₙ): minden csúcs össze van kötve minden másikkal.
• Fa: ciklusmentes, összefüggő gráf.
• Kör (cycle): zárt, egyszerű lánc, pl. A → B → C → A.
• Páros gráf: a csúcsok két részhalmazra oszthatók, úgy, hogy minden él két különböző halmazból való csúcsot köt össze.

Egy ${\textstyle n\times n}$-es mátrix, ahol az ${\textstyle i}$-edik sor és ${\textstyle j}$-edik oszlop eleme 1 (vagy a súly), ha van él az ${\textstyle i}$ és ${\textstyle j}$ csúcs között.

Példa nem irányított gráfra:

   A B C
A  0 1 1
B  1 0 0
C  1 0 0

Minden csúcshoz felsoroljuk a szomszédait.

Példa:

A: B, C
B: A
C: A

Ez memóriahatékonyabb ritka gráfok esetén.

• Fokszám (degree): egy csúcsból kiinduló (vagy belépő) élek száma.
  • Nem irányított gráfnál: egyszerűen a kapcsolatok száma.
  • Irányított gráfnál: in-degree, out-degree.
• Út (path): csúcsok sorozata, amelyben minden egymást követő pár össze van kötve.
• Egyszerű út: nem ismétlődik benne csúcs.
• Ciklus: olyan út, ahol az első és utolsó csúcs megegyezik.
• Összefüggő gráf: bármely két csúcs között van út.
• Komponens: összefüggő részgráf.

• DFS – Mélységi keresés (Depth-First Search): rekurzívan vagy veremmel bejárja az elérhető csúcsokat.
• BFS – Szélességi keresés (Breadth-First Search): sorban haladva látogatja a szinteket.

• Dijkstra algoritmus: pozitív súlyú gráfban legrövidebb utak.
• Bellman–Ford algoritmus: negatív súlyokat is kezel.
• Floyd–Warshall algoritmus: minden csúcspárra legrövidebb utak.

• Kruskal algoritmus: élek növekvő sorrendje alapján.
• Prim algoritmus: kezdőcsúcsból építkezik.

Irányított, ciklusmentes gráf (DAG) csúcsainak olyan sorrendje, ahol minden él előrefelé mutat.

• Közlekedési hálózatok – városok és utak modellezése.
• Társadalmi hálózatok – emberek és kapcsolataik.
• Web – weblapok (csúcs), linkek (él).
• Hálózatbiztonság – tűzfal- vagy támadási gráfok.
• Programozás – vezérlési gráfok, állapotgépek.
• Kémia – molekulák atomi szerkezete.

• Gráf színezés: Hányféleképp színezhető a csúcsok úgy, hogy szomszédosak különbözők legyenek?
• Hamilton-út: olyan út, amely minden csúcsot egyszer érint.
• Euler-út: olyan út, amely minden élt egyszer érint.
• Kör problémák: pl. a híres Königsbergi hidak problémája (Euler által megoldva, ez indította el a gráfelméletet).

• Izomorf gráfok: különböző elnevezésű, de szerkezetileg azonos gráfok.
• Komplementer gráf: egy adott gráfnak az a változata, ahol pont azok az élek hiányoznak, amelyek az eredetiben megvoltak.
• Planáris gráf: síkban lerajzolható úgy, hogy az élek nem metszik egymást.
• Gráf spektruma: a szomszédsági mátrix sajátértékei – fontos a kvantumgráfelméletben is.

• Véletlen gráfok (pl. Erdős–Rényi modell)
• Hipergráfok: ahol egy él több mint két csúcsot is összeköthet.
• Dinamikus gráfok: időben változó struktúrák (pl. hálózati forgalom).
• Gráfok gépi tanulásban: pl. gráfalapú neurális hálózatok (GNN).

A gráf egy univerzális modellező eszköz, amelynek fogalma és elmélete mindenhol megjelenik az informatika, a hálózatok, a mesterséges intelligencia, az operációkutatás és a biológia területén is. Az algoritmikus kezelésük kulcsfontosságú a hatékony problémamegoldáshoz.

• graph - Szótár.net (en-hu)
• graph - Sztaki (en-hu)
• graph - Merriam–Webster
• graph - Cambridge
• graph - WordNet
• graph - Яндекс (en-ru)
• graph - Google (en-hu)
• graph - Wikidata
• graph - Wikipédia (angol)