gráftípusok

Gráftípusok a gráfok különböző osztályait jelentik, amelyeket a kapcsolatok és a szerkezet alapján szokás meghatározni. Egy gráf alapvető elemei a csúcsok (pontok) és az élek (kapcsolatok). Az élek irányultsága alapján beszélhetünk irányított (direkciós) és irányítatlan gráfról. Az élek súlyai szerint pedig súlyozott és súlyozatlan gráfokat különítünk el.

Az alapvető osztályozás közé tartozik, hogy egyszerű-e a gráf: egyszerű gráfban nincsenek többé élek vagy csomóponti hurkok (ön- vagy párhuzamos él nélkül). Ezzel szemben multigráf több élt is tartalmazhat ugyanazon a pár csúcs között, pszeudográf pedig csomóponti hurkokat is enged.

További fontos kategóriák a gráfok összekapcsoltsága és a ciklusosság alapján. Összekapcsolt gráfban minden csúcs elérhető a gráf bármely másik csúcsáról; ha nem, akkor külön részekből álló, összefüggő összetevőkre oszlik. Acyclikus gráf egy vagy több összetevője nem tartalmaz köröket, és ezekhez kapcsolódóan a fa és az erdő fogalmak kapcsolódnak: fa egy összekapcsolt, aciklikus gráf; erdő pedig aciklikus gráfok összessége. Kör vagy ciklus egy zárt út, ahol a kezdő és végpont megegyezik.

Más típusok közé tartozik a teljes gráf K_n, ahol minden csúcs minden egyes másik csúccsal kapcsolódik, és a bipartit gráf, amelyben a csúcsok két részhalmazra oszthatók úgy, hogy az élek csak a két rész között húzódjanak. Planáris gráf olyan, amelyik síkban úgy ábrázolható, hogy az élek esetleg kereszteződés nélkül futnak. Reguláris gráfban minden csúcs ugyanannyi élt érint, például k-reguláris gráf.

A gráfok reprezentációjára gyakran használják az adjacency mátrixot és az adjacency listát. Fontos invariánsok közé tartozik a rend (csúcsok száma), a méret (élek száma), a fokszám-sorozat, a dúr: átfogó tulajdonságok, például a diaméter, girth és a kromatikus szám. A gráftípusok fogalmai alapvető eszközök a kombinatorikában, hálózatkutatásban és informatikai problémák modellezésében.