Elérhetőségi reláció

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

A matematika, azon belül a gráfelmélet területén az elérhetőség (reachability) arra a lehetőségre utal, hogy a gráf egyik csúcsából el lehet jutni egy másik csúcsába. Az csúcsból elérhető a csúcs (avagy a csúcs elérhető az csúcsból), ha létezik szomszédos csúcsok sorozata (tehát egy séta), ami -sel kezdődik és -vel végződik.

Irányítatlan gráfban tetszőleges két csúcs közötti elérhetőség eldönthető a gráf összefüggő komponenseinek ismeretében. Két csúcs pontosan akkor elérhető egymásból, ha ugyanahhoz az összefüggő komponenshez tartoznak. Az irányítatlan gráf komponensekre bontása lineáris időben elvégezhető.

A szócikk további része az irányított gráfokkal foglalkozik, melyekben lényegesen nehezebb feladat a páronkénti elérhetőség megállapítása.

Definíció[szerkesztés]

Összefüggő, de nem erősen összefüggő gráf; az 1-gyel jelölt csúcs nem érhető el a többiből.

A csúcshalmazzal és élhalmazzal rendelkező irányított gráfban értelmezett elérhetőségi reláció alatt az tranzitív lezárását értjük, vagyis csúcsainak minden rendezett párját, melyre létezik olyan csúcssorozat úgy, hogy a él bármely -re része -nek.[1]

Ha körmentes, akkor elérhetőségi relációja egy részbenrendezés; bármely részbenrendezés meghatározható ezen a módon, például mint a tranzitív redukciójának elérhetőségi relációja.[2] Egy fontos következmény, hogy mivel a részbenrendezések antiszimmetrikusak, ha -ből elérhető , -ből nem érhető el . Ez könnyen látható abból, hogy ha -ből -be és vissza -be is el tudunk jutni, akkor kört tartalmazna, pedig abból indultunk ki, hogy körmentes. Ha irányított, de nem körmentes (tehát legalább egy kört tartalmaz), akkor elérhetőségi relációja részbenrendezés helyett előrendezésnek felel meg. [3]

Algoritmusok[szerkesztés]

Az elérhetőséget meghatározó algoritmusokat két csoportba oszthatjuk: vannak azok, melyek futásához szükség van előfeldolgozásra és azok, melyekhez nem.

Ha csak egyetlen, vagy néhány lekérdezést végezhetünk, hatékonyabb eltekinteni a komplex adatstruktúráktól és közvetlenül a kívánt csúcspár elérhetőségével számolni. Ez lineáris idejű algoritmusokkal elvégezhető, például szélességi bejárás vagy iteratívan mélyülő keresés segítségével.[4]

Ha több lekérdezést végezhetünk, kifinomultabb módszerek is alkalmazhatók; a használni kívánt módszer a szóba jövő gráf jellemzőitől függhet. Némi előfeldolgozási időért és extra tárterületért cserébe egy olyan adatszerkezet hozható létre, ami bármilyen csúcspár között felmerülő elérhetőségi kérdéseket akár időben megválaszolhat. Alább három különböző, egyre specializáltabb helyzetekre kiélezett algoritmust és hozzá tartozó adatstruktúrát vizsgálunk meg.

Floyd–Warshall-algoritmus[szerkesztés]

A Floyd–Warshall-algoritmus[5] bármely irányított gráf tranzitív lezárásának kiszámítására felhasználható, ami az elérhetőségi relációt a definíció szerint előállítja.

Az algoritmus a legrosszabb esetet figyelembe véve időben fut le és tárterületet vesz igénybe. A Floyd–Warshall-algoritmus nem csak az elérhetőséget számítja ki, hanem a csúcspárok közötti legrövidebb utak nagyságát is tárolja. A „negatív köröket” tartalmazó gráfoknál a legrövidebb utak definiálatlanok is lehetnek (hiszen még egy negatív körbejárással mindig tovább csökkenthető az út költsége), de a páronkénti elérhetőséget így is rögzíti.

Thorup-algoritmus[szerkesztés]

A síkbarajzolható irányított gráfok esetében létezik egy sokkal gyorsabb módszer, amit Mikkel Thorup írt le 2004-ben.[6] A módszer előkészítési idő alatt a síkbarajzolható gráfhoz létrehoz egy méretű adatstruktúrát; ezután idő alatt képes megválaszolni elérhetőségi kérdéseket. A Thorup-algoritmus képes közelítő legrövidebb utak számítására, valamit útválasztási információ megadására.

Az algoritmus nagy vonalakban úgy működik, hogy minden csúcshoz kis számú, úgynevezett elválasztó utat rendel oly módon, hogy egy csúcsból bármely másik csúcsba menő útnak keresztül kell menni vagy vagy egy szeparátorán. Az elérhetőséggel kapcsolatos rész vázlatos áttekintése következik.

Adott gráfon az algoritmus először a csúcsokat rétegekbe szervezi egy tetszőlegesen választott csúcstól kezdve. A rétegek felépítésekor először az előző lépésből elérhető csúcsokat vesszük figyelembe (az egyetlen -ból kiindulva), majd az előző lépésbe elérő csúcsokat tekintjük, amíg csak minden csúcsot hozzá nem rendelünk valamely réteghez. A rétegek felépítése során egy csúcs legfeljebb két rétegben jelenik meg, és minden irányított útja két szomszédos rétegen, -n és -en belül húzódik. Legyen az utoljára létrehozott réteg, tehát a kifejezésben legkisebb értéke.

Ezután a gráfot újraértelmezzük a irányított gráfok sorozataként, ahol minden egyes , és ahol az összes korábbi szint egyetlen csúccsá történő összehúzása. Mivel minden irányított út legfeljebb két egymást követő rétegben jelentkezik, és mivel minden -t két egymást követő réteg alkot, ezért minden -beli irányított út legalább egy -ben (és legfeljebb kettőben) megjelenik.

Minden -re azonosítunk három olyan szeparátort, melyek eltávolításával a gráf három komponensre esik szét, melyek egyenként az eredeti gráf csúcsainak legfeljebb -részét tartalmazzák. Mivel két réteg ellentétes irányítású útból van felépítve, minden szeparátor legfeljebb két irányított utat tartalmazhat, tehát a szeparátorok összesen 6 irányított utat. Legyen ezen irányított utak halmaza. Annak bizonyítását, hogy mindig lehet találni ilyen szeparátorokat Lipton és Tarjan síkgráf-elválasztási tétele tartalmazza; ezek a szeparátorok ráadásul lineáris időben megtalálhatók.

Bármely irányított út esetében a irányítottságából adódik a csúcsok egy természetes indexelése az út elejétől a végéig. Minden -beli csúcs esetében megkeressük -ban az első olyan csúcsot, ami -ből elérhető, és az utolsót, ami eléri -t. Más szavakkal, azt vizsgáljuk, hogy -ből mennyire az elejére tudunk eljutni -nak, illetve, hogy milyen sokáig tudunk -ban maradni úgy, hogy vissza tudjunk jutni -be. Ezt az információt minden csúcshoz eltároljuk. Ezután bármilyen és csúcspár esetén, akkor éri el a csúcsot -n keresztül, ha korábban kapcsolódik -hoz, mint ahogy csatlakozik -hez.

A -t felépítő egyes rekurziós lépések során minden csúcs címkézésre kerül. Mivel a rekurzió logaritmikus mélységű, csúcsonként összesen extra információ tárolására kerül sor. Innen nézve a logaritmikus idejű elérhetőségi lekérdezés egyszerűen annyiból áll, hogy a csúcspár címkéi közül egy megfelelő közös -t kell találni. Az eredeti cikk a továbbiakban azzal foglalkozik, hogy a lekérdezés időigényét -ig tuningolja.

A módszer analízisének összefoglalásaként először láthatjuk, hogy a réteges megközelítés úgy particionálja a csúcsokat, hogy egy-egy csúccsal csak ideig kell foglalkozni. Az algoritmus szeparációs fázisa a gráfot az eredeti gráf méretének legfeljebb -e méretű komponensekre bontja, ami logaritmikus rekurziós mélységet eredményez. A rekurzió minden szintjén csak lineáris idejű munkát igényel a szeparátorok megkeresése és a csúcsok közti lehetséges kapcsolatok feltárása. A végeredmény előfeldolgozási idő, és plusz eltárolandó információ csúcsonként.

Kameda-algoritmus[szerkesztés]

Irányított gráf, melyre alkalmazható a Kameda-módszer; az és hozzáadva.
A fentivel megegyező gráf a Kameda-algoritmus futása után. Láthatók a csúcsokhoz tartozó mélységi keresési (DFS-) címkék

Az előfeldolgozás még gyorsabb módszerét T. Kameda ötlötte ki 1975-ben.[7] Kameda módszere kizárólag olyan irányított gráfokra alkalmazható, melyek síkba rajzolhatók, körmentesek és a következő tulajdonságokkal is rendelkeznek: az összes, 0 befokú, illetve 0 kifokú csúcsnak a lerajzolás ugyanazon tartományán kell lennie (ez a feltételezés szerint általában a külső tartomány), és a tartomány határa kettéparticionálható oly módon, hogy az összes 0 befokú csúcs az egyik részben és az összes 0 kifokú csúcs a másik partícióban jelenik meg (tehát ez a kétfajta csúcs nem váltakozik).

Ha rendelkezik ezekkel a tulajdonságokkal, akkor az előfeldolgozás mindössze időt vesz igénybe, és az előző algoritmushoz hasonlóan mindössze bitet tárol el csúcsonként, az elérhetőség lekérésének ideje pedig ettől kezdve , egy egyszerű összehasonlítás.

Az előfeldolgozás a következő lépésekben történik. Hozzáadunk egy új csúcsot, melyből minden 0 befokú csúcshoz élt húzunk, valamint egy új csúcsot, melybe pedig minden 0 kifokú csúcstól húzunk élt. Vegyük észre, hogy tulajdonságai megengedik ezt a síkbarajzolhatóság megszűnése nélkül, tehát a hozzáadott csúcsok új élei sem fogják keresztezni a többit. Minden csúcshoz eltároljuk a szomszédok (a kimenő élek) listáját, a síkba rajzolás által meghatározott valamely sorrend szerint (például a gráf lerajzolása szerint az óramutató járásával megegyező irányban). Ekkor inicializálunk egy számlálót és -től indulva mélységi bejárást kezdünk meg. A bejárás során minden csúcs szomszédsági listája balról jobbra haladva meglátogatásra kerül szükség szerint. Ahogy a csúcsokat elővesszük a bejárásnál használt veremből, megcímkézzük őket értékével, majd -t dekrementáljuk. Vegyük észre, hogy címkéje mindig , címkéje pedig . Ezután megismételjük a mélységi bejárást, de ezúttal a szomszédsági lista jobbról balra kerül látogatásra.

A bejárások végeztével az és csúcsokat, valamint a hozzájuk tartozó éleket eltávolítjuk. A megmaradt csúcsok mindegyikének címkéje egy-egy kételemű lista, -től -ig terjedő értékekkel. Bármely két és csúcsot, illetve és címkéiket tekintve azt mondhatjuk, hogy pontosan akkor áll fenn, ha , , továbbá és közül legalább az egyik esetében a kisebb mint , illetve reláció is fennáll.

A módszer végeredménye az az állítás, hogy pontosan akkor elérhető -ból, ha , ami időben egyszerűen kiszámítható.

Kapcsolódó problémák[szerkesztés]

A gráfbeli elérhetőség területének másik problémája, hogy csúcs hibája esetén vizsgáljunk elérhetőségeket. Például: „Elérhető-e az -ból a csúcs akkor is, ha az csúcsok hibásak és nem érinthetjük őket?” Egy kapcsolódó probléma az élek hibáját, vagy a kettő keverékét vizsgálja. A szélességi keresési technikák ilyen lekérdezéseknél is működnek, de a hatékony orákulum konstrukciója ilyenkor nehezebb lehet.[8][9]

Az elérhetőségi lekérdezésekkel kapcsolatos másik probléma, hogy miként lehet gyorsan újraszámolni az elérhetőségi kapcsolatokat, ha a gráf egyes részei megváltoznak. Ez a kérdés előkerül például a szemétgyűjtés során, amikor egyensúlyozni kell a memória felszabadítása (hogy újra kiosztható legyen) és a futó alkalmazás teljesítményigénye között.

Kapcsolódó szócikkek[szerkesztés]

Jegyzetek[szerkesztés]

  1. Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698, <https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA495>.
  2. Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878, <https://books.google.com/books?id=VESm0MJOiDQC&pg=PA17>.
  3. Schmidt, Gunther (2010), Relational Mathematics, vol. 132, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, p. 77, ISBN 9780521762687, <https://books.google.com/books?id=E4dREBTs5WsC&pg=PA559&lpg=PA77>.
  4. Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647, <https://books.google.com/books?id=lvAo3AeJikQC&pg=PA519>.
  5. Cormen, Thomas H.; Leiserson, Charles E. & Rivest, Ronald L. et al. (2001), "Transitive closure of a directed graph", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 632–634, ISBN 0-262-03293-7.
  6. Thorup, Mikkel (2004), "Compact oracles for reachability and approximate distances in planar digraphs", Journal of the ACM 51 (6): 993–1024, DOI 10.1145/1039488.1039493.
  7. Kameda, T (1975), "On the vector representation of the reachability in planar directed graphs", Information Processing Letters 3 (3): 75–77, DOI 10.1016/0020-0190(75)90019-8.
  8. Demetrescu, Camil; Thorup, Mikkel & Chowdhury, Rezaul Alam et al. (2008), "Oracles for distances avoiding a failed node or link", SIAM Journal on Computing 37 (5): 1299–1318, DOI 10.1137/S0097539705429847.
  9. Halftermeyer, Pierre, Connectivity in Networks and Compact Labeling Schemes for Emergency Planning, Universite de Bordeaux, <https://tel.archives-ouvertes.fr/tel-01110316/document>.

További információk[szerkesztés]


Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Reachability című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.