Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a tananyag kezdőlapjára (P)Ugrás a tananyag előző oldalára (E)Ugrás a tananyag következő oldalára (V)Fogalom megjelenítés (nem elérhető funkció)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintése (D)Keresés az oldalon (nem elérhető funkció)Súgó megtekintése (S)

Algoritmusok és adatszerkezetek / Gráfok ábrázolása

22. Gráfok ábrázolása

A megoldandó feladatok, problémák modellezése során sokszor gráfokat alkalmazunk. A gráf fogalmát a matematikából ismertnek vehetjük. A modellezés során a gráfok több változata is szóba jöhet.

A különféle útkeresési problémák természetes módon vezetnek a gráfokhoz. Ha például Budapesten gyalogosan keresünk legrövidebb utat két pont között, akkor útszakaszokat irányítatlan éleknek tekinthetjük, súlyukat pedig lényegében az útszakasz hossza adja. Ha autóval szeretnék az utat megtenni, akkor a gráf éleit már irányítottnak kell tekintenünk. Szintén irányítás nélküliek az élek, ha néhány helység között szeretnénk minimális összköltségű vezetékrendszert létesíteni, valamilyen energiával való ellátás céljából. Az élekhez természetesen a létesítés költségét hozzárendeljük. Arra is tudunk példát mondani, hogy költségmentesek a modellben alkalmazott gráf élei. Ha egy termék előállításának egymáshoz illeszkedő, de többfelé ágazó (irányított élekkel ábrázolt) lépéseit szeretnénk linearizálni, akkor a költségeknek nincs alapvető szerepe. A párosítási feladatok irányítatlan élei is gyakran költség nélküliek.

Általánosabb megközelítés szerint bizonyos entitások, absztrakt objektumok közötti kapcsolatokat leíró bináris relációk (kapcsolatok) szemléletes leírásának egyik eszköze a gráf. A gráfokkal az ember számára könnyen "emészthető" formában lehet ábrázolni a relációk tulajdonságait (például szimmetria = irányítatlanság vagy kettő hosszú kör, reflexivitás = hurokél). A modell objektumainak megfeleltetjük a gráf csúcsait, a közöttük fennálló kapcsolatok leírására pedig a gráf éleit használjuk. Mivel egy olyan általános fogalom, mint a bináris reláció modellezésére használjuk, számos probléma megfogalmazható úgy, mint gráfelméleti feladat.

A gráfalgoritmusok című rész fejezeteiben néhány fontos, a gyakorlati életben is gyakran előforduló általános feladatot és a megoldásukra használható algoritmust ismertetünk.

22.1. Alapfogalmak, jelölések

A továbbiakban ismertnek feltételezzük az alapvető gráfelméleti fogalmakat, definíciókat és tételeket. Most nézzünk néhány fontosabb fogalmat kevésbé formálisan, inkább csak a felelevenítés szintjén.

A kép (nagyobb változata) külön ablakban is megtekinthető.22.1. ábra. Egy irányított gráf hurokéllel
A kép (nagyobb változata) külön ablakban is megtekinthető.22.2. ábra. Egy nem összefüggő gráf három komponenssel ( {1,2,5},{4},{3,6})

Vissza a tartalomjegyzékhez

22.2. Gráfok ábrázolása

A gráfok ábrázolására két, a gyakorlatban igen elterjedt adatszerkezetet adunk. Az egyik tisztán aritmetikai ábrázolású (szomszédsági mátrix), a másik vegyes, aritmetikai és láncolt ábrázolású (szomszédsági lista).

22.2.1. Szomszédsági mátrix

Legyen G = (V,E) véges gráf, és n a csúcsok száma. Ekkor a gráfot egy n x n-es mátrixban ábrázoljuk, ahol az oszlopokat és a sorokat rendre a csúcsokkal indexeljük (ez leggyakrabban 1,...,n). Egy mezőben akkor van 1-es, ha a hozzá tartozó oszlop által meghatározott csúcs szomszédja a sor által meghatározott csúcsnak.

Az ábrázolás eszközeként alkalmazott mátrixot nevezzük szomszédsági mátrixnak. (Találkozni lehet még az adjacencia mátrix, illetve csúcsmátrix elnevezésekkel is.)

Tekintsünk két példát a 22.3. ábrán. Figyeljük meg, hogy az irányítatlan gráf esetén a mátrix szemmetrikus.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej22_s1_full.png22.3. ábra. Egy irányított és egy irányítatlan gráf szomszédsági mátrixa
A kép (nagyobb változata) külön ablakban is megtekinthető.fej22_s2_full.png22.3. ábra. Egy irányított és egy irányítatlan gráf szomszédsági mátrixa

Ha súlyozott a gráf, akkor az élsúlyokat (élköltségeket) is el kell tárolni. Ezt is a mátrixon belül oldjuk meg. A súly valós számokat vehet fel. Természetesen adódik, hogy ahol előzőleg 1-est írtunk, azaz létezett az illető él, oda most írjuk be az él költségét.

Két további eset maradt, a mátrix főátlója, és az olyan mezők, amelyek esetén nem létezik él. Vezessük be a végtelen (végtelen) élsúlyt, és a nem létező élek esetén a mátrix megfelelő helyére írjunk végtelen-t. Egy ilyen "élen" csak végtelen nagy költséggel tudunk végighaladni (tehát nem tudunk).

A mátrix főátlójába kerülnének a hurokélek költségei, de ilyen értékeket nem alkalmazunk, mivel a továbbiakban a legtöbb gyakorlati probléma leírására alkalmas egyszerű gráfokra korlátozzuk a tárgyalást. Az egyszerű gráfok nem tartalmaznak hurokéleket (valamint többszörös éleket sem).

Élsúlyozott gráf esetén a szomszédsági mátrix kitöltését a következő megállapodás szerint végezzük:

A mátrixos ábrázolás helyfoglalása mindig ugyanakkora, független az élek számától, a mátrix méretével n2-tel arányos. (Az n pontú teljes gráfnak is ekkora a helyfoglalása.) A mátrixos reprezentációt sűrű gráfok esetén érdemes használni, hogy ne legyen túl nagy a helypazarlás.

22.2.2. Éllistás ábrázolás

Ebben a reprezentációban a gráf minden csúcsához egy listát rendelünk. Ezen listában tartjuk nyilván az adott csúcsból kimenő éleket.

Legyen G = (V,E) véges gráf, és n a csúcsok száma. Vegyünk fel egy mutatókat tartalmazó Adj[1...n] tömböt (a csúcsokkal indexeljük a tömböt). A tömbben lévő mutatók mutatnak az éllistákra (más néven a szomszédsági listákra). Az éllisták lehetnek egy- vagy kétirányú, fejelemes vagy fejelem nélküli listák, ez most nem lényeges a gráf szempontjából.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej22_s3_full.png22.4. ábra. Egy irányított gráf éllistás ábrázolása
A kép (nagyobb változata) külön ablakban is megtekinthető.fej22_s4_full.png22.5. ábra. Egy irányítatlan gráf éllistás ábrázolása

Az éllistás ábrázolás helyfoglalása irányítatlan gráfok esetén a csúcsok számával (Adj tömb), illetve az élek számával (éllista-elemek száma) arányos. Az elfoglalt memória méretének nagyságrendje (n + e). Irányított gráfok esetén az élek számának duplájával kell számolnunk, így (n + 2e)-vel arányos helyfoglaláshoz jutunk.

Mivel a memóriaigény az élek számával arányos, ezért az éllistás ábrázolást ritka, illetve nem-sűrű (mondhatnánk „normál”) gráfok () esetén szokták használni, ugyanis sűrű gráf esetén a szomszédsági mátrixhoz képest itt jelentkezik a listák láncolásából származó helyfoglalás is, a mutatók tárolása révén.

Vissza a tartalomjegyzékhez

Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.

A tananyag az ELTE - PPKE informatika tananyagfejlesztési projekt (TÁMOP-4.1.2.A/1-11/1-2011-0052) keretében valósult meg.
A tananyag elkészítéséhez az ELTESCORM keretrendszert használtuk.