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 / Dag topologikus rendezése

29. Dag topologikus rendezése

A címben szereplő DAG (mint egy angol eredetű mozaikszó) körmentes irányított gráfot jelent.

Operációs rendszerekben, adatbázis kezelő rendszerekben előfordulnak olyan esetek, hogy egyes folyamatok más folyamatokra várnak. Ilyen eset lehet egy nyomtatás várakoztatása, mert a nyomtatót egy másik folyamat használja, vagy egy adattáblán való művelet elvégzésének a várakoztatása, mert egy másik folyamat a táblát zárolta.

Építsünk fel egy úgy nevezett várakozási gráfot, ahol a gráf csúcsai a folyamatok, és egy u csúcsból vezessen él egy v csúcsba, ha az u folyamat a v folyamatra várakozik. Az említett várakozási reláció nem feltétlen szimmetrikus, tehát a gráfunk legyen irányított.

Ha a körbevárakozás esete lép fel, akkor a gráfban irányított kör keletkezik. Ha nem avatkoznánk közbe, akkor a folyamatok elvben akár végtelen ideig is várakozhatnának egymásra. A jelenséget a szakirodalom holtpontnak nevezi. Például a 29.1. ábrán az F1 folyamat várakozik F2-re, F2 várakozik F3-ra, és F3 várakozik F1-re.

Az irányított gráfok körmentessége (illetve, mint hibajelenség, a körök megjelenése) további jelentős szerepet kap az irányított gráfokkal leírható összetett folyamatok „linearizálása” terén. Például, az ételek elkészítése során bizonyos lépéseket előzetesen végrehajtandó tevékenységekhez, korábbi fázisok befejeződéséhez kötnek a receptek. Ezeket a függőségeket egy irányított gráffal lehet ábrázolni, amely – helyes recept esetén – nem tartalmaz kört. Komolyabb kiterjedésű gráfra példa lehet az autógyártásban, a szerelőcsarnok egy pontján elvégzett műveletek egymásutánjának a rendszere.

Mindkét példában fellép az az a feladat, hogy a gráf csúcsaiban szereplő tevékenységeket rendezzük szekvenciába úgy, hogy mire a sor hozzájuk ér, addigra már minden előzetesen végrehajtandó tevékenységen túljutottunk. A 29.2. ábrán szereplő gráf esetén egy ilyen felsorolás lehet például a következő: 1, 3, 2, 5, 4, 6. A csúcsoknak az ilyen alkalmas sorrendbe állítását nevezzük a körmentes irányított gráf topologikus rendezésének.

29.1. A topologikus rendezés jellemzői

Az egymásra épülő tevékenységeket akkor tudjuk végrehajtási sorba rendezni, ha a folyamatok egy irányított körmentes gráfban (directed acyclic graph, DAG) ábrázolhatók. Ennek megfelelően a fő feladatunk ellenőrizni, hogy irányított gráfunk teljesíti-e a körmentesség feltételét, másként a DAG tulajdonságot. A topologikus rendezés azután végezhető el.

A DAG tulajdonság ellenőrzése tehát nem más, mint irányított körök felderítése a gráfban. Ez a feladat pedig visszavezethető a 28. fejezetben ismertetett élosztályozásra. Például az előző fejezet 28.9. ábráján követhető az a lépés, amelyben a mélységi bejárás a gráfon detektált egy körre utaló visszaélt ((3,6) él).

Alább megfogalmazunk néhány olyan állítást, amelyek a körmentesség, a mélységi bejárás és a topologikus rendezés között teremtenek kapcsolatot.

Állítás. Legyen G=(V,E) irányított, véges gráf. Ha a G gráf mélységi bejárása során találunk visszaélt, akkor G nem DAG.

Bizonyítás. Tegyük fel, hogy egy visszaél, ekkor u leszármazottja v-nek a mélységi fában, azaz létezik irányított út. Ehhez hozzávéve élt egy irányított kör.

Állítás. Legyen irányított, véges gráf. Ha a G gráf nem DAG, akkor minden mélységi bejárás során találunk visszaélt.

Bizonyítás. G nem DAG, azaz van benne irányított kör, legyen egy irányított kör, és legyen v a mélységi bejárás során elsőnek elért csúcs. Ekkor a kör mentén a v kivételével minden csúcs fehér ebben a pillanatban. A kör mentén, vagy kis kerülő úton, de fehér csúcsok mentén eljutunk v -ből u-ba (ha van út, akkor van csupa fehér csúcsból álló út is), tehát visszaél lesz.

Arra a kedvező eredményre jutottunk, hogy egy gráfról idő alatt eldönthető, hogy DAG-e, a mélységi bejárás felhasználásával. Nem kell mást tenni, mint a mélységi keresés során figyelni az éltípusokat, ha nem találunk visszaélt, akkor a gráf DAG.

Definíció. Legyen G=(V,E) irányított, véges gráf, továbbá legyen . G csúcsainak egy felsorolása, G egy topologikus rendezése, ha él esetén a felsorolásban u előbb áll, mint w, azaz és esetén .

Például vegyük a 29.2. ábrán látható körmentes gráfot. A gráf egy topologikus rendezése 1,2,3,4,5,6 (ez most egy másik rendezés, mint amely előzőleg szerepelt).

Állítás. Ha G=(V,E) irányított gráf DAG, akkor csúcs, amelybe nem fut él.

Bizonyítás. Indirekt tegyük fel, hogy nem létezik ilyen csúcs. Ekkor vegyünk egy csúcsot, és egyik befutó élén hátráljunk (lépjünk vissza a megelőző csúcsra). Azonban minden csúcsnak van befutó éle, így a hátrálást korlátlanul végrehajthatjuk, vagyis kört kapunk, ami ellentmondás.

Állítás. A G=(V,E) gráfnak létezik topologikus rendezése akkor, és csak akkor, ha G DAG.

Bizonyítás.

: G-nek létezik topologikus rendezése, és indirekt tegyük fel, hogy G nem DAG, azaz van benne irányított kör, ami ellentmondás, mivel a kör mentén nem lehet alkalmas sorrendet definiálni.

: Konstruktív bizonyítást adunk a csúcsok száma szerinti teljes indukcióval. Az egyetlen pontból álló gráfra utaló esetén az állítás triviális módon igaz. Tegyük fel, hogy pontú DAG-okra igaz az állítás. Legyen csúcsból álló DAG, ekkor csúcs, amelyben nem megy él. Töröljük a gráfból u-t és a belőle kimenő éleket, így megkapjuk csúcsból álló DAG-ot. Ekkor az indukciós feltevés szerint -nek létezik topologikus rendezése, legyen ez . Ekkor egy topologikus rendezése lesz -nek.

Például legyen a 28.2. ábra gráfja. Ekkor az 1-es csúcs törlésével megkapjuk a gráfot (28.3. ábra), ami az indukciós feltétel szerint DAG, így létezik topologikus rendezése: 2,3,4,5,6. Tehát -nek topologikus rendezése az 1,2,3,4,5,6 sorozat, mivel nem megy él az 1-es csúcsba, így az 1-es csúcsot tehetjük a sorozat elejére.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej29_03_full.png29.3. ábra. Az 1-es csúcs és éleinek elhagyása a gráfból

Vissza a tartalomjegyzékhez

29.2. A topologikus rendezés algoritmusa

A topologikus rendezés előállítását többféle módon is megközelíthetjük.

1. Q -ba berakjuk azon csúcsokat, amelybe nem megy él.

2.Ha Q üres, akkor készen vagyunk.

3.Vegyük ki Q -ból az első elemet, és írjuk ki, legyen ez u.

4.Töröljük G-ből éleket csúcsra. Ha v-be most már nem megy él, akkor helyezzük v-t a sor végére.

5.Folytassuk a 2. lépéssel.

Állítás. Az eljárás G=(V,E) DAG egy topologikus rendezését állítja elő.

Bizonyítás. Azt kell belátni, hogy amennyiben , akkor
. Amikor élt vizsgáljuk, akkor v fehér vagy fekete (szürke esetén visszaél lenne, de G DAG). Ha v fehér, akkor v leszármazottja u-nak, tehát . Ha v fekete, akkor v -t már megvizsgáltuk és elhagytuk, míg u-t még nem, tehát . Azaz minden esetre fennáll az állítás.

Mivel a mélységi bejárás műveletigénye , és a veremműveletek száma a csúcsok számával arányos, azaz , .

Vissza a tartalomjegyzékhez

29.3. A topologikus rendezés szemléltetése

Nézzük meg a mélységi bejárás alapú algoritmus működését a 29.4. ábrán.

A mélységi bejárással elindulunk az 1-es csúcsból, majd néhány lépés után eljutunk a 6-os csúcsba, miközben csupa faéleket azonosítunk.

Elsőként a 6-os csúcs bejárását fejezzük be, tehát a 6-ost bedobjuk a V verembe, így . A következő lépésben a 4-es csúcsot fejezzük be. . Majd a 2-es csúcsból ellátogatunk az 5-ös csúcsba, miközben a verem változatlan marad. Az 5-ös csúcsból kimenő élt keresztélként azonosítjuk. Befejezzük az 5-ös csúcs bejárását is, tehát a verembe dobjuk: . Következőnek befejezzük a 2-es csúcsot is, és a vermet a 2-essel bővítjük: . Az 1-es csúcsból elérjük a 3-as csúcsot, és újabb keresztélt azonosítunk: . Befejezzük a 3-as csúcs bejárását is. Befejezzük a 3-as csúcs bejárását is. . Végezetül a bejárás utolsó csúcsaként elhagyjuk az 1-es csúcsot is. A veremben van a gráf összes csúcsa a befejezésük szerint: . Menet közben nem találtunk visszaélt, tehát a DAG tulajdonságot rendben találtuk. Végül a verem tartalmát kiírjuk: 1,3,2,5,4,6, amellyel megkapjuk a G egy topologikus rendezését.

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.