gráfelmélet

Magyar

gráfelmélet

(matematika, kombinatorika, gráfelmélet) A gráfelmélet a matematika és az informatika egyik ága, amely a gráfok tulajdonságait és alkalmazásait vizsgálja. A gráf egy olyan struktúra, amely csúcsokból (pontokból) és élekből (vonalakból) áll, és gyakran használják kapcsolati rendszerek, hálózatok modellezésére.

Csúcsok (V): A gráf alapelemei, amelyeket pontokként ábrázolunk.
Élek (E): A csúcsokat összekötő vonalak vagy kapcsolatok.
Irányítatlan gráf: Az élek nem irányítottak, tehát az ( (u, v) ) él azonos ( (v, u) )-val.
Irányított gráf: Az éleknek iránya van, tehát az ( (u, v) ) él különbözik ( (v, u) )-tól.
Súlyozott gráf: Az élekhez egy érték (súly) van rendelve, például távolság vagy költség.
Ciklikus gráf: Olyan gráf, amely tartalmaz kört.
Aciklikus gráf: Olyan gráf, amely nem tartalmaz kört.
Összefüggő gráf: Bármely két csúcs között létezik út.

Legkisebb feszítőfa: Hogyan lehet a gráf összes csúcsát összekötni úgy, hogy az élek súlyainak összege minimális legyen? (Pl. Kruskal- vagy Prim-algoritmus)
Legrövidebb út: Hogyan található meg a legkisebb súlyú út két csúcs között? (Pl. Dijkstra-algoritmus)
Maximális folyam: Mi a maximális érték, amit egy forrásból egy célig lehet eljuttatni egy hálózaton? (Pl. Ford-Fulkerson-algoritmus)
Színezés: Hogyan lehet a gráf csúcsait a lehető legkevesebb színnel kiszínezni úgy, hogy két szomszédos csúcs ne legyen azonos színű?
Euler-út és kör: Létezik-e olyan út, amely minden élen pontosan egyszer halad át? (Euler-út)
Hamilton-út és kör: Létezik-e olyan út, amely minden csúcson pontosan egyszer halad át? (Hamilton-út)