PROFILPELAJAR.COM

Példagráf, melyben a kétszeresen összefüggő komponensek meg vannak jelölve — Minden szín megfelel egy kétszeresen összefüggő komponensnek. A több színnel jelölt csúcsok az elvágó csúcsok, ezért több ilyen komponenshez (blokkhoz) tartoznak.

A matematika, azon belül a gráfelmélet területén egy kétszeresen összefüggő komponens (biconnected component), blokk (block) vagy 2-összefüggő komponens egy maximális kétszeresen összefüggő részgráf. Bármely összefüggő gráf felbontható kétszeresen összefüggő komponensek fájára, ami a gráfhoz tartozó blokk–vágás-fa (block-cut tree). Ezeket a blokkokat artikulációs pontok vagy elvágó pontok, elvágó csúcsok (cut vertices / articulation points) kötik össze. A gráf minden olyan csúcsa elvágó csúcs, melynek eltávolítása a gráf összefüggő komponenseinek számát növeli.

Algoritmusok

Lineáris idejű mélységi keresés

Az összefüggő irányítatlan gráfok kétszeresen összefüggő komponenseit megkereső klasszikus soros algoritmust John Hopcroft és Robert Tarjan (1973) alkották meg.^[1] Ez a lineáris idejű algoritmus mélységi keresésen alapszik, megjelenik az Introduction to Algorithms 2. és 3. kiadásában is, Problem 22-2 címszó alatt.

Az elképzelés lényege egy mélységi keresés futtatása, miközben a következő információkat jegyezzük fel:

minden meglátogatott csúcs mélysége a mélységi keresési fában;
minden v csúcshoz a mélységi keresési fában lévő leszármazottaihoz (magát a v csúcsot is beleértve) tartozó legnagyobb mélységet, nevezzük mélypontnak (lowpoint).

A mélység értékét jellemzően megtartjuk a mélységi keresés során. A v csúcs mélypontja v összes leszármazottjának meglátogatásával számítható ki (tehát épp mielőtt v-t kiemelnénk a mélységi keresés verméből) mint a minimális értékű a következők közül: v mélysége, v szülőjén kívüli összes szomszédjának mélysége és v gyermekeinek mélypontja.

Az algoritmus kulcsgondolata, hogy egy nem gyökér v csúcs pontosan akkor artikulációs pont, ha v-nek létezik olyan y gyermeke, melyre a mélypont(y) ≥ mélység(v). Ennek a tulajdonságnak az értéke azután vizsgálható, miután a mélységi keresés visszatért v minden gyermekéből (tehát épp mielőtt v-t kiemelnénk a veremből), és ha igaz, v a gráfot különböző kétszeresen összefüggő komponensekre választja szét. Ez realizálható minden ilyen y-hoz tartozó kétszeresen összefüggő komponens kiszámításával (egy olyan komponens, ami y-t tartalmazza, y részfáját plusz v-t is tartalmazza), majd a fából y részfájának törlésével.

A gyökér csúcsot külön kell kezelni: ez pontosan akkor artikulációs pont, ha legalább két gyereke van. Így elegendő egy komponenst építeni a gyökér minden egyes gyerek-részfájához (magát a gyökeret is beleértve).

Pszeudokód

GetArticulationPoints(i, d)
    visited[i] = true
    depth[i] = d
    low[i] = d
    childCount = 0
    isArticulation = false
    for each ni in adj[i]
        if not visited[ni]
            parent[ni] = i
            GetArticulationPoints(ni, d + 1)
            childCount = childCount + 1
            if low[ni] >= depth[i]
                isArticulation = true
            low[i] = Min(low[i], low[ni])
        else if ni <> parent[i]
            low[i] = Min(low[i], depth[ni])
    if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
        Output i as articulation point

A Tarjan-algoritmus demója. D jelöli a mélységet, L a mélypontot.

Egyéb algoritmusok

A fenti algoritmus egyszerű alternatívája láncfelbontásokat használ, amik a mélységi keresőfákon alapuló speciális fülfelbontások.^[2] A láncfelbontások lineáris időben számíthatók a következő áthaladási szabály alapján. Legyen C a G egy láncfelbontása. Ekkor G pontosan akkor 2-csúcsösszefüggő, ha G minimális fokszáma 2 és C₁ az egyetlen kör C-ben. Ezzel azonnal rendelkezésünkre áll egy lineáris idejű 2-összefüggőségi teszt, ami kiterjeszthető G artikulációs csúcsainak lineáris idejű listázására a következő állítás felhasználásával: egy 2 minimális fokszámú G gráfbeli v csúcs pontosan akkor artikulációs csúcs, ha v vagy egy elválasztó éllel szomszédos, vagy v az első csúcs C - C₁ egy körében. Az artikulációs csúcsok listája felhasználható G blokk-vágás-fájának lineáris idejű előállítására.

A probléma online változatában a gráfhoz dinamikusan csúcsokat és éleket adhatunk hozzá (de el nem vehetünk), és egy adatstruktúrában fenn kell tartani a kétszeresen összefüggő komponensek listáját. Jeffery Westbrook és Robert Tarjan (1992)^[3] hatékony adatstruktúrát fejlesztett ki erre a feladatra, ami a diszjunkt halmaz-adatstruktúrán alapul. Módszerük n csúcs hozzáadását, illetve m él hozzáadását O(m α(m, n)) időben kezeli, ahol α az inverz Ackermann-függvény. Ez az időkorlát bizonyítottan optimális.

Az Uzi Vishkin és Robert Tarjan (1985)^[4] által kidolgozott, PRAM-on futó párhuzamos algoritmus O(log n) idejű, n + m processzort felhasználva. Guojing Cong és David A. Bader (2005)^[5] kifejlesztett egy algoritmust, ami ötszörös gyorsulást ér el 12 processzoros SMP rendszeren. Az eredeti Tarjan–Vishkin-algoritmuson alapuló több mint harmincszoros gyorsítást ért el James A. Edwards és Uzi Vishkin (2012).^[6]

Kapcsolódó struktúrák

Ekvivalenciareláció

Tetszőleges irányítatlan gráf élein definiálható egy bináris reláció, melyben az e és f élek pontosan akkor vannak relációban, ha vagy e = f, vagy a gráf tartalmaz e-n és f-en is keresztülmenő egyszerű kört. Minden él relációban van saját magával, és az e él pontosan akkor van relációban az f éllel, ha ugyanúgy f is relációban van e-vel. Kevésbé nyilvánvaló módon ez egy tranzitív reláció: ha létezik egyszerű kör, ami tartalmazza az e és f éleket, egy másik egyszerű kör pedig az f és g éleket, akkor a két kör kombinálásával található egyszerű kör, ami eljut e-től g-ig. Éppen ezért ez egy ekvivalenciareláció, aminek segítségével tehát az élek ekvivalenciaosztályokba particionálhatók: élek olyan részhalmazaiba, melyekben két él akkor van relációban egymással, ha ugyanabba az ekvivalenciaosztályba tartoznak. Az egyes ekvivalenciaosztályok élei által alkotott részgráfok éppen az adott gráf kétszeresen összefüggő komponensei. Így tehát a kétszeresen összefüggő komponensek particionálják a gráf éleit; azonban ezeknek a csoportoknak lehetnek egymással közös csúcsaik.^[7]

Blokkgráf

Egy G gráf blokkgráfja alatt blokkjainak metszetgráfja értendő. Ennek minden csúcsa G egy blokkjának felel meg, és két csúcs akkor van éllel összekötve, ha a megfelelő blokkoknak van közös csúcsuk. Egy H gráf akkor a blokkgráfja valamilyen G gráfnak, ha H blokkjai teljes részgráfok. Az ilyen tulajdonságú H gráfokat blokkgráfoknak nevezzük.^[8]

Blokk-vágás fa

Egy G gráf elvágó pontja, artikulációs pontja vagy artikulációs csúcsa olyan csúcs, ami két vagy több blokk közös csúcsa. Egy összefüggő gráf váltakozó blokkokból, illetve artikulációs csúcsokból álló szerkezetét fával lehet leírni, amit blokk-vágás fának (block-cut tree, BC-tree) neveznek. A blokk-vágás fának minden csúcsa egy-egy blokknak vagy artikulációs csúcsnak felel meg, két csúcs között pedig akkor húzódik él, ha az egyik csúcs egy blokkban, a másik pedig a blokkhoz tartozó artikulációs csúcsnak felel meg.^[9]

Kapcsolódó szócikkek

Fordítás

Ez a szócikk részben vagy egészben a Biconnected 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.

Jegyzetek

↑ (1973) „Algorithm 447: efficient algorithms for graph manipulation”. Communications of the ACM 16 (6), 372–378. o. DOI:10.1145/362248.362272.
↑ Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters 113 (7): 241–244, DOI 10.1016/j.ipl.2013.01.016.
↑ (1992) „Maintaining bridge-connected and biconnected components on-line”. Algorithmica 7, 433–464. o. DOI:10.1007/BF01758773.
↑ (1985) „An Efficient Parallel Biconnectivity Algorithm”. SIAM J. Comput. 14 (4), 862–874. o. DOI:10.1137/0214061.
↑ Guojing Cong and David A. Bader, (2005). „An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)”. Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium: 45b. doi:10.1109/IPDPS.2005.100.
↑ Better speedups using simpler parallel programming for graph connectivity and biconnectivity, Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores - PMAM '12, 103. o.. DOI: 10.1145/2141702.2141714 (2012). ISBN 9781450312110
↑ (Tarjan & Vishkin 1985) az ekvivalenciareláció definícióját (Harary 1969)-nek tulajdonítják; Harary azonban nem írta azt le explicit módon.
↑ Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
↑ (Harary 1969), p. 36.

Eugene C. Freuder (1985). „A Sufficient Condition for Backtrack-Bounded Search”. Journal of the Association for Computing Machinery 32 (4), 755–761. o. DOI:10.1145/4221.4225.