Gráf
Gráfnak tekintjük a pontok egy halmazát, és az azokat összekötő vonalakat. A pontokat gyakran csúcsnak, vagy csúcspontnak hívjuk, a vonalakat pedig éleknek hívjuk.
Számtalan programozási, matematikai és egyéb probléma, vagy struktúra (pl. folyamatleírások) jól kezelhető és ábrázolható gráfokkal.
A gráfban a csúcsok pontos helye és a vonalak alakja általában nem érdekes, adottnak tekintjük a gráfot, ha meg lehet őket különböztetni, és rögzített, hogy mely csúcsok között húzódik él.
Egy gráf megadható grafikusan (lerajzolva), a csúcsok és élek felsorolásával, vagy valamilyen matematikai jelöléssel.
Megkülönböztetünk irányított és irányítatlan gráfot. Előbbi esetben az élek iránya is adott, grafikus ábrázolásban ezt jellemzően nyílhegyekkel jelöljük.
Értelmezhető olyan él, ami egy csúcsból önmagába mutat, ezt hurokélnek hívjuk. Bizonyos esetekben megengedett, hogy egy csúcsból egy másikba több él is vezessen.
A csúcsok és élek egy végigjárható sorozatát a gráf egy útjának nevezzük. Ha egy gráf bármely két pontja között található út, akkor a gráfot összefüggőnek hívjuk. Körnek hívunk egy olyan utat a gráfban, ahol az út első és utolsó csúcsa megegyezik. Körmentesnek nevezzük a gráfot, ha nem található benne kör.
Ha egy gráf összefüggő, és körmentes, akkor felrajzolható úgy, hogy egy pontja fölé a szomszédait rajzoljuk, azok fölé azok szomszédait, stb. A kapott ábra általában egy bokorhoz hasonlít, ezért az ilyen gráfokat fának hívjuk.
Megvalósítások[szerkesztés]
Egy gráf számítógépes programban megvalósítható például mutatókkal, minden csúcsánál a csúcsból kiinduló élek végpontjainak nyilvántartásával.
Adatbáziskezelő rendszerekben a csúcsokat egy táblában tárolva egy másik táblában az egyes élek kiinduló és végpontjainak azonosítóját tárolhatjuk.
Ehhez hasonló struktúrában tömbökben is tárolhatunk gráfot, az éltömb elemei olyan rekordok lehetnek, amik a csúcstömb elemeinek két indexét tárolják.
Algoritmusok[szerkesztés]
Egy összefüggő gráf bejárható a Gráfkereső algoritmus segítségével.
Egy (irányítatlan) fa tetszőleges pontja elérhető egy másikból a Visszalépéses keresés algoritmussal.
Felhasználási területek[szerkesztés]
- Objektumorientált nyelvekben a memóriában levő objektumok és azok egymásra hivatkozásai felfoghatók gráfként.
- Bizonyos fájlrendszerekben megengedettek a mutatók (szimbolikus hivatkozások, parancsikonok). Ezekkel együtt a könyvtárszerkezet (ami általában fastruktúra) gráffá módosul.
- A láncolt listák gráfként is értelmezhetők.
- Szimulációkban és játékprogramokban a figurák mozgását gyakran útkereső algoritmusok segítik. Ezek lényegében gráfkereső algoritmusok.
- Egy programnyelv egy programja a belső hivatkozásokkal együtt szintén tekinthető gráfnak.
- A szakértői rendszereknél az információk és szabályok gráfot feszítenek ki.
- Egy adatbázisban levő rekordok a hivatkozásokkal együtt gráfot alkotnak.
