Elérhetőségi reláció

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 ${\displaystyle s}$ csúcsból elérhető a ${\displaystyle t}$ csúcs (avagy a ${\displaystyle t}$ csúcs elérhető az ${\displaystyle s}$ csúcsból), ha létezik szomszédos csúcsok sorozata (tehát egy séta), ami ${\displaystyle s}$-sel kezdődik és ${\displaystyle t}$-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ó

Ö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 ${\displaystyle V}$ csúcshalmazzal és ${\displaystyle E}$ élhalmazzal rendelkező ${\displaystyle G=(V,E)}$ irányított gráfban értelmezett elérhetőségi reláció alatt az ${\displaystyle E}$ tranzitív lezárását értjük, vagyis ${\displaystyle V}$ csúcsainak minden ${\displaystyle (s,t)}$ rendezett párját, melyre létezik olyan ${\displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t}$ csúcssorozat úgy, hogy a ${\displaystyle (v_{i-1},v_{i})}$ él bármely ${\displaystyle 1\leq i\leq k}$-re része ${\displaystyle E}$-nek.^[1]

Ha ${\displaystyle G}$ 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 ${\displaystyle s}$-ből elérhető ${\displaystyle t}$, ${\displaystyle t}$-ből nem érhető el ${\displaystyle s}$. Ez könnyen látható abból, hogy ha ${\displaystyle s}$-ből ${\displaystyle t}$-be és vissza ${\displaystyle s}$-be is el tudunk jutni, akkor ${\displaystyle G}$ kört tartalmazna, pedig abból indultunk ki, hogy körmentes. Ha ${\displaystyle G}$ 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

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 ${\displaystyle O(1)}$ 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

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 ${\displaystyle O(|V|^{3})}$ időben fut le és ${\displaystyle O(|V|^{2})}$ 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

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 ${\displaystyle O(n\log {n})}$ előkészítési idő alatt a síkbarajzolható gráfhoz létrehoz egy ${\displaystyle O(n\log {n})}$ méretű adatstruktúrát; ezután ${\displaystyle O(1)}$ 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 ${\displaystyle v}$ csúcsból bármely másik ${\displaystyle w}$ csúcsba menő útnak keresztül kell menni vagy ${\displaystyle v}$ vagy ${\displaystyle w}$ egy szeparátorán. Az elérhetőséggel kapcsolatos rész vázlatos áttekintése következik.

Adott ${\displaystyle G}$ gráfon az algoritmus először a csúcsokat rétegekbe szervezi egy tetszőlegesen választott ${\displaystyle v_{0}}$ 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 ${\displaystyle v_{0}}$-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 ${\displaystyle G}$ minden irányított útja két szomszédos rétegen, ${\displaystyle L_{i}}$-n és ${\displaystyle L_{i+1}}$-en belül húzódik. Legyen ${\displaystyle k}$ az utoljára létrehozott réteg, tehát a ${\displaystyle \bigcup _{i=0}^{k}=V}$ kifejezésben ${\displaystyle k}$ legkisebb értéke.

Ezután a gráfot újraértelmezzük a ${\displaystyle G_{0},G_{1},\ldots ,G_{k-1}}$ irányított gráfok sorozataként, ahol minden egyes ${\displaystyle G_{i}=r_{i}\cup L_{i}\cup L_{i+1}}$, és ahol ${\displaystyle r_{i}}$ az összes korábbi ${\displaystyle L_{0}\ldots L_{i-1}}$ 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 ${\displaystyle G_{i}}$-t két egymást követő réteg alkot, ezért minden ${\displaystyle G}$-beli irányított út legalább egy ${\displaystyle G_{i}}$-ben (és legfeljebb kettőben) megjelenik.

Minden ${\displaystyle G_{i}}$-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 ${\displaystyle 1/2}$-részét tartalmazzák. Mivel ${\displaystyle G_{i}}$ 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 ${\displaystyle S}$ 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 ${\displaystyle Q\in S}$ irányított út esetében a ${\displaystyle Q}$ 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 ${\displaystyle G_{i}}$-beli ${\displaystyle v}$ csúcs esetében megkeressük ${\displaystyle Q}$-ban az első olyan csúcsot, ami ${\displaystyle v}$-ből elérhető, és az utolsót, ami eléri ${\displaystyle v}$-t. Más szavakkal, azt vizsgáljuk, hogy ${\displaystyle v}$-ből mennyire az elejére tudunk eljutni ${\displaystyle Q}$-nak, illetve, hogy milyen sokáig tudunk ${\displaystyle Q}$-ban maradni úgy, hogy vissza tudjunk jutni ${\displaystyle v}$-be. Ezt az információt minden ${\displaystyle v}$ csúcshoz eltároljuk. Ezután bármilyen ${\displaystyle u}$ és ${\displaystyle w}$ csúcspár esetén, ${\displaystyle u}$ akkor éri el a ${\displaystyle w}$ csúcsot ${\displaystyle Q}$-n keresztül, ha ${\displaystyle u}$ korábban kapcsolódik ${\displaystyle Q}$-hoz, mint ahogy ${\displaystyle Q}$ csatlakozik ${\displaystyle w}$-hez.

A ${\displaystyle G_{0}\ldots ,G_{k}}$-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 ${\displaystyle O(\log {n})}$ 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 ${\displaystyle Q}$-t kell találni. Az eredeti cikk a továbbiakban azzal foglalkozik, hogy a lekérdezés időigényét ${\displaystyle O(1)}$-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 ${\displaystyle O(1)}$ ideig kell foglalkozni. Az algoritmus szeparációs fázisa a gráfot az eredeti gráf méretének legfeljebb ${\displaystyle 1/2}$-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 ${\displaystyle O(n\log n)}$ előfeldolgozási idő, és ${\displaystyle O(\log {n})}$ plusz eltárolandó információ csúcsonként.

Kameda-algoritmus

Irányított gráf, melyre alkalmazható a Kameda-módszer; az ${\displaystyle s}$ és ${\displaystyle t}$ 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 ${\displaystyle G}$ rendelkezik ezekkel a tulajdonságokkal, akkor az előfeldolgozás mindössze ${\displaystyle O(n)}$ időt vesz igénybe, és az előző algoritmushoz hasonlóan mindössze ${\displaystyle O(\log {n})}$ bitet tárol el csúcsonként, az elérhetőség lekérésének ideje pedig ettől kezdve ${\displaystyle O(1)}$, egy egyszerű összehasonlítás.

Az előfeldolgozás a következő lépésekben történik. Hozzáadunk egy új ${\displaystyle s}$ csúcsot, melyből minden 0 befokú csúcshoz élt húzunk, valamint egy új ${\displaystyle t}$ csúcsot, melybe pedig minden 0 kifokú csúcstól húzunk élt. Vegyük észre, hogy ${\displaystyle G}$ 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 ${\displaystyle i=n+1}$ számlálót és ${\displaystyle 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 ${\displaystyle i}$ értékével, majd ${\displaystyle i}$-t dekrementáljuk. Vegyük észre, hogy ${\displaystyle t}$ címkéje mindig ${\displaystyle n+1}$, ${\displaystyle s}$ címkéje pedig ${\displaystyle 0}$. 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 ${\displaystyle s}$ és ${\displaystyle t}$ 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, ${\displaystyle 1}$-től ${\displaystyle n}$-ig terjedő értékekkel. Bármely két ${\displaystyle u}$ és ${\displaystyle v}$ csúcsot, illetve ${\displaystyle L(u)=(a_{1},a_{2})}$ és ${\displaystyle L(v)=(b_{1},b_{2})}$ címkéiket tekintve azt mondhatjuk, hogy ${\displaystyle L(u)<L(v)}$ pontosan akkor áll fenn, ha ${\displaystyle a_{1}\leq b_{1}}$, ${\displaystyle a_{2}\leq b_{2}}$, továbbá ${\displaystyle a_{1}}$ és ${\displaystyle a_{2}}$ közül legalább az egyik esetében a kisebb mint ${\displaystyle b_{1}}$, illetve ${\displaystyle b_{2}}$ reláció is fennáll.

A módszer végeredménye az az állítás, hogy ${\displaystyle v}$ pontosan akkor elérhető ${\displaystyle u}$-ból, ha ${\displaystyle L(u)<L(v)}$, ami ${\displaystyle O(1)}$ időben egyszerűen kiszámítható.

Kapcsolódó problémák

A gráfbeli elérhetőség területének másik problémája, hogy ${\displaystyle k}$ csúcs hibája esetén vizsgáljunk elérhetőségeket. Például: „Elérhető-e az ${\displaystyle u}$-ból a ${\displaystyle v}$ csúcs akkor is, ha az ${\displaystyle s_{1},s_{2},...,s_{k}}$ 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

• Gammoid
• st-elérhetőség

Jegyzetek

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

• Erősen összefüggő komponensek

Fordítá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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.