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

Ha $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. Egy fontos következmény, hogy mivel a részbenrendezések antiszimmetrikusak, ha $s$-ből elérhető $t$, $t$-ből nem érhető el $s$. Ez könnyen látható abból, hogy ha $s$-ből $t$-be és vissza $s$-be is el tudunk jutni, akkor $G$ kört tartalmazna, pedig abból indultunk ki, hogy körmentes. Ha $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.

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.

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

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

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

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

A $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 $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 $Q$-t kell találni. Az eredeti cikk a továbbiakban azzal foglalkozik, hogy a lekérdezés időigényét $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 $O(1)$ ideig kell foglalkozni. Az algoritmus szeparációs fázisa a gráfot az eredeti gráf méretének legfeljebb $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 $O(n\log n)$ előfeldolgozási idő, és $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 $s$ és $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. 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 $G$ rendelkezik ezekkel a tulajdonságokkal, akkor az előfeldolgozás mindössze $O(n)$ időt vesz igénybe, és az előző algoritmushoz hasonlóan mindössze $O(\log {n})$ bitet tárol el csúcsonként, az elérhetőség lekérésének ideje pedig ettől kezdve $O(1)$, egy egyszerű összehasonlítás.

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

A módszer végeredménye az az állítás, hogy $v$ pontosan akkor elérhető $u$-ból, ha $L(u)<L(v)$, ami $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 $k$ csúcs hibája esetén vizsgáljunk elérhetőségeket. Például: „Elérhető-e az $u$-ból a $v$ csúcs akkor is, ha az $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.

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

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.