Erősen összefüggő komponens
A matematika, azon belül a gráfelmélet területén egy irányított gráf akkor erősen összefüggő (strongly connected vagy diconnected), ha bármely csúcs bármely másik csúcsból elérhető. Egy irányított gráf erősen összefüggő komponensei, röviden erős komponensei (strongly connected components vagy diconnected components) a gráf olyan részgráfokra való felbontását adják, mely részgráfok maguk is erősen összefüggőek. Egy gráf erős összefüggőségének tesztelése, illetve erősen összefüggő komponenseinek megkeresése lineáris időben elvégezhető feladat.
Definíciók
[szerkesztés]Egy irányított gráf erősen összefüggő, ha bármely két csúcsa között mindkét irányban létezik (irányított) út. A G irányított gráfban, még ha nem is erősen összefüggő, ha u és v csúcsok között mindkét irányban létezik út, akkor a két csúcs erősen összefügg egymással.
Az erős összefüggőség bináris relációja egy ekvivalenciareláció, melynek ekvivalenciaosztályai által meghatározott feszített részgráfok neve erősen összefüggő komponensek. Ezzel ekvivalens megfogalmazás, hogy egy G irányított gráf erősen összefüggő komponense olyan részgráf, mely erősen összefüggő, és a következő tulajdonság szerint maximális: G bármely további csúcsának vagy élének hozzáadásával megszűnne az erős összefüggősége. Az erősen összefüggő komponensek G csúcshalmazának felbontását alkotják.
Ha minden erősen összefüggő komponenst összehúzunk egy-egy csúcsba, az eredményül kapott irányított körmentes gráfot a G gráf kondenzációjának nevezzük. Egy irányított gráf pontosan akkor körmentes, ha nincsenek egynél több csúcsból álló erősen összefüggő részgráfjai – hiszen egy irányított kör erősen összefüggő, és minden nemtriviális erősen összefüggő komponens legalább egy irányított kört tartalmaz.
Algoritmusok
[szerkesztés]Számos algoritmus létezik az erősen összefüggő komponensek lineáris időben történő azonosítására.
- A Kosaraju-algoritmus két menetben futtat mélységi keresést. Az első menet az eredeti gráfon fut annak meghatározására, hogy a második mélységi keresés külső ciklusa milyen sorrendben vizsgálja meg a csúcsokat, hogy járt-e már ott, és rekurzív vizsgálatba kezdjen, ha még nem. A második mélységi keresés az eredeti gráf transzponáltján (megfordításán) történik, és minden rekurzív keresési lépésben egy új erősen összefüggő komponenst tár fel.[1] Nevét S. Rao Kosarajuról kapta, aki 1978-ban leírta (de nem publikálta eredményeit); ezt 1981-ben Micha Sharir tette meg.[2]
- A Tarjan-algoritmus, amit 1972-ben Robert Tarjan publikált,[3] egyetlen menetben végez mélységi keresést. Egy veremben tárolja azokat a csúcsokat, melyekhez még nem lett komponens hozzárendelve, és minden csúcshoz kiszámítja a hozzá tartozó „alacsony számot” (low number) – a csúcs egy leszármazottjából elérhető legmagasabb ősének indexe –, melyet annak eldöntésére használ, hogy csúcsok egy halmazát mikor kell elővennie a veremből és elhelyezni egy új komponensben.
- Az útalapú erős komponens-algoritmus Tarjan algoritmusához hasonlóan egyetlen mélységi keresést végez, de két vermet használ. Az egyik verem tartja számon a komponenshez még nem rendelt csúcsokat, a másik pedig a mélységi keresés aktuális útját. Ennek az algoritmusnak az első lineáris idejű változatát Edsger W. Dijkstra publikálta 1976-ban.[4]
Bár Kosaraju algoritmusa egyszerűbben megérthető, a Tarjan-féle és az útalapú algoritmus kettő helyett csak egy mélységi keresést igényel.
Alkalmazásai
[szerkesztés]
Az erősen összefüggő komponenseket megtaláló algoritmusokkal meg lehet oldani 2-kielégíthetőségi (2-SAT) problémákat is (ezek Boole-változók olyan rendszerei, melyekben változópárokat együtt vizsgálunk): ahogy (Aspvall, Plass & Tarjan 1979) megmutatta, egy 2-kielégíthetőségi probléma pontosan akkor nem oldható meg, ha létezik olyan v változó, amire v és komplementere is a probléma következtetési gráfjának ugyanabban az erősen összefüggő komponensében található.[5]
Az erősen összefüggő komponensek felhasználhatók a Dulmage–Mendelsohn-felbontás kiszámításában, ez a páros gráf éleinek osztályozása aszerint, hogy szerepelnek-e a gráf valamely teljes párosításában.[6]
Kapcsolódó eredmények
[szerkesztés]Egy irányított gráf pontosan akkor erősen összefüggő, ha létezik fülfelbontása, tehát élei particionálhatók irányított utak és körök olyan sorozatába, hogy a sorozat első részgráfja egy kör, és minden rákövetkező részgráf vagy egy olyan kör, ami egy csúcsában közös a megelőző részgráfokkal, vagy olyan út, ami két végpontjában közös a megelőző részgráfokkal.
A Robbins-tétel szerint egy irányítatlan gráfnak pontosan akkor létezik azt erősen összefüggővé tevő irányítása, ha 2-szeresen élösszefüggő. Ennek az egyik bizonyítása szerint meg kell keresni az eredeti irányítatlan gráf egy fülfelbontását, és minden fület konzisztensen kell irányítani.[7]
Kapcsolódó szócikkek
[szerkesztés]Jegyzetek
[szerkesztés]- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.
- ↑ Micha Sharir. A strong connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 7(1):67–72, 1981.
- ↑ Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160, DOI 10.1137/0201010
- ↑ Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.
- ↑ Aspvall, Bengt; Plass, Michael F. & Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8 (3): 121–123, DOI 10.1016/0020-0190(79)90002-4.
- ↑ Dulmage, A. L. & Mendelsohn, N. S. (1958), "Coverings of bipartite graphs", Canad. J. Math. 10: 517–534, DOI 10.4153/cjm-1958-052-0.
- ↑ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly 46: 281–283, DOI 10.2307/2303897.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Strongly connected component 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.
További információk
[szerkesztés]- Java implementation for computation of strongly connected components in the jBPT library (see StronglyConnectedComponents class).
- C++ implementation of Strongly Connected Components