hu hu hu hu hu hu hu hu hu hu hu ca hu en da fi hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu en hu hu en en en en en en en en en hu hu hu hu hu sk hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu de hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu en ko pl pt ru hu hu hu hu hu hu hu hu hu hu
A Wikipédiából, a szabad enciklopédiából
Ez a közzétett változat, ellenőrizve: 2018. október 9.
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 s {\displaystyle s} csúcsból elérhető a t {\displaystyle t} csúcs (avagy a t {\displaystyle t} csúcs elérhető az s {\displaystyle s} csúcsból), ha létezik szomszédos csúcsok sorozata (tehát egy séta), ami s {\displaystyle s} -sel kezdődik és t {\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.
Ö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 {\displaystyle V} csúcshalmazzal és E {\displaystyle E} élhalmazzal rendelkező G = ( V , E ) {\displaystyle G=(V,E)} irányított gráfban értelmezett elérhetőségi reláció alatt az E {\displaystyle E} tranzitív lezárását értjük, vagyis V {\displaystyle V} csúcsainak minden ( s , t ) {\displaystyle (s,t)} rendezett párját, melyre létezik olyan v 0 = s , v 1 , v 2 , . . . , v k = t {\displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t} csúcssorozat úgy, hogy a ( v i − 1 , v i ) {\displaystyle (v_{i-1},v_{i})} él bármely 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} -re része E {\displaystyle E} -nek.[1]
Ha G {\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 s {\displaystyle s} -ből elérhető t {\displaystyle t} , t {\displaystyle t} -ből nem érhető el s {\displaystyle s} . Ez könnyen látható abból, hogy ha s {\displaystyle s} -ből t {\displaystyle t} -be és vissza s {\displaystyle s} -be is el tudunk jutni, akkor G {\displaystyle G} kört tartalmazna, pedig abból indultunk ki, hogy körmentes. Ha G {\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]
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 O ( 1 ) {\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.
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 O ( | V | 3 ) {\displaystyle O(|V|^{3})} időben fut le és O ( | V | 2 ) {\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.
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 O ( n log ⁡ n ) {\displaystyle O(n\log {n})} előkészítési idő alatt a síkbarajzolható gráfhoz létrehoz egy O ( n log ⁡ n ) {\displaystyle O(n\log {n})} méretű adatstruktúrát; ezután O ( 1 ) {\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 v {\displaystyle v} csúcsból bármely másik w {\displaystyle w} csúcsba menő útnak keresztül kell menni vagy v {\displaystyle v} vagy w {\displaystyle w} egy szeparátorán. Az elérhetőséggel kapcsolatos rész vázlatos áttekintése következik.
Adott G {\displaystyle G} gráfon az algoritmus először a csúcsokat rétegekbe szervezi egy tetszőlegesen választott v 0 {\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 v 0 {\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 G {\displaystyle G} minden irányított útja két szomszédos rétegen, L i {\displaystyle L_{i}} -n és L i + 1 {\displaystyle L_{i+1}} -en belül húzódik. Legyen k {\displaystyle k} az utoljára létrehozott réteg, tehát a ⋃ i = 0 k = V {\displaystyle \bigcup _{i=0}^{k}=V} kifejezésben k {\displaystyle k} legkisebb értéke.
Ezután a gráfot újraértelmezzük a G 0 , G 1 , … , G k − 1 {\displaystyle G_{0},G_{1},\ldots ,G_{k-1}} irányított gráfok sorozataként, ahol minden egyes G i = r i ∪ L i ∪ L i + 1 {\displaystyle G_{i}=r_{i}\cup L_{i}\cup L_{i+1}} , és ahol r i {\displaystyle r_{i}} az összes korábbi L 0 … L i − 1 {\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 G i {\displaystyle G_{i}} -t két egymást követő réteg alkot, ezért minden G {\displaystyle G} -beli irányított út legalább egy G i {\displaystyle G_{i}} -ben (és legfeljebb kettőben) megjelenik.
Minden G i {\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 1 / 2 {\displaystyle 1/2} -részét tartalmazzák. Mivel G i {\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 S {\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 Q ∈ S {\displaystyle Q\in S} irányított út esetében a Q {\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 G i {\displaystyle G_{i}} -beli v {\displaystyle v} csúcs esetében megkeressük Q {\displaystyle Q} -ban az első olyan csúcsot, ami v {\displaystyle v} -ből elérhető, és az utolsót, ami eléri v {\displaystyle v} -t. Más szavakkal, azt vizsgáljuk, hogy v {\displaystyle v} -ből mennyire az elejére tudunk eljutni Q {\displaystyle Q} -nak, illetve, hogy milyen sokáig tudunk Q {\displaystyle Q} -ban maradni úgy, hogy vissza tudjunk jutni v {\displaystyle v} -be. Ezt az információt minden v {\displaystyle v} csúcshoz eltároljuk. Ezután bármilyen u {\displaystyle u} és w {\displaystyle w} csúcspár esetén, u {\displaystyle u} akkor éri el a w {\displaystyle w} csúcsot Q {\displaystyle Q} -n keresztül, ha u {\displaystyle u} korábban kapcsolódik Q {\displaystyle Q} -hoz, mint ahogy Q {\displaystyle Q} csatlakozik w {\displaystyle w} -hez.
A G 0 … , G k {\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 O ( log ⁡ n ) {\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 Q {\displaystyle Q} -t kell találni. Az eredeti cikk a továbbiakban azzal foglalkozik, hogy a lekérdezés időigényét O ( 1 ) {\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 O ( 1 ) {\displaystyle 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 {\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 O ( n log ⁡ n ) {\displaystyle O(n\log n)} előfeldolgozási idő, és O ( log ⁡ n ) {\displaystyle O(\log {n})} plusz eltárolandó információ csúcsonként.
Irányított gráf, melyre alkalmazható a Kameda-módszer; az s {\displaystyle s} és t {\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 G {\displaystyle G} rendelkezik ezekkel a tulajdonságokkal, akkor az előfeldolgozás mindössze O ( n ) {\displaystyle O(n)} időt vesz igénybe, és az előző algoritmushoz hasonlóan mindössze O ( log ⁡ n ) {\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 O ( 1 ) {\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 s {\displaystyle s} csúcsot, melyből minden 0 befokú csúcshoz élt húzunk, valamint egy új t {\displaystyle t} csúcsot, melybe pedig minden 0 kifokú csúcstól húzunk élt. Vegyük észre, hogy G {\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 i = n + 1 {\displaystyle i=n+1} számlálót és 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 i {\displaystyle i} értékével, majd i {\displaystyle i} -t dekrementáljuk. Vegyük észre, hogy t {\displaystyle t} címkéje mindig n + 1 {\displaystyle n+1} , s {\displaystyle s} címkéje pedig 0 {\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 s {\displaystyle s} és t {\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, 1 {\displaystyle 1} -től n {\displaystyle n} -ig terjedő értékekkel. Bármely két u {\displaystyle u} és v {\displaystyle v} csúcsot, illetve L ( u ) = ( a 1 , a 2 ) {\displaystyle L(u)=(a_{1},a_{2})} és L ( v ) = ( b 1 , b 2 ) {\displaystyle L(v)=(b_{1},b_{2})} címkéiket tekintve azt mondhatjuk, hogy L ( u ) < L ( v ) {\displaystyle L(u)<L(v)} pontosan akkor áll fenn, ha a 1 ≤ b 1 {\displaystyle a_{1}\leq b_{1}} , a 2 ≤ b 2 {\displaystyle a_{2}\leq b_{2}} , továbbá a 1 {\displaystyle a_{1}} és a 2 {\displaystyle a_{2}} közül legalább az egyik esetében a kisebb mint b 1 {\displaystyle b_{1}} , illetve b 2 {\displaystyle b_{2}} reláció is fennáll.
A módszer végeredménye az az állítás, hogy v {\displaystyle v} pontosan akkor elérhető u {\displaystyle u} -ból, ha L ( u ) < L ( v ) {\displaystyle L(u)<L(v)} , ami O ( 1 ) {\displaystyle O(1)} időben egyszerűen kiszámítható.
A gráfbeli elérhetőség területének másik problémája, hogy k {\displaystyle k} csúcs hibája esetén vizsgáljunk elérhetőségeket. Például: „Elérhető-e az u {\displaystyle u} -ból a v {\displaystyle v} csúcs akkor is, ha az s 1 , s 2 , . . . , s k {\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.
↑ Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698,  .
↑ Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878,  .
↑ Schmidt, Gunther (2010), Relational Mathematics, vol. 132, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, p. 77, ISBN 9780521762687,  .
↑ Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647,  .
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ Halftermeyer, Pierre, Connectivity in Networks and Compact Labeling Schemes for Emergency Planning, Universite de Bordeaux,  .
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.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Elérhetőségi_reláció&oldid=20499927”
Hivatkozás erre a változatra
Hogyan hivatkozz erre a lapra?
A lap utolsó módosítása: 2018. október 9., 15:33
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.