Biconnected component - Biconnected component

Ett exempel på en graf med två anslutna komponenter markerade
Varje färg motsvarar en sammankopplad komponent. Flerfärgade hörn är skurna hörn och tillhör därmed flera bikopplade komponenter.

I grafteorin är en dubbelkopplad komponent (ibland känd som en 2-ansluten komponent ) en maximal dubbelkopplad subgraf . Varje ansluten graf bryts ned till ett träd av tvåkopplade komponenter som kallas blockets klippträd i grafen. Blocken är fästa vid varandra vid delade hörn som kallas klippta hörn eller separerar hörn eller ledpunkter . Specifikt är en skuren vertex varje vertex vars avlägsnande ökar antalet anslutna komponenter .

Algoritmer

Linjär tidsdjup-första sökning

Den klassiska sekventiella algoritmen för att beräkna tvåkopplade komponenter i en ansluten ostyrd graf beror på John Hopcroft och Robert Tarjan (1973). Den körs i linjär tid och är baserad på djup-första sökning . Denna algoritm beskrivs också som Problem 22-2 i Introduction to Algorithms (både andra och tredje upplagan).

Tanken är att köra en djup-första sökning samtidigt som du behåller följande information:

  1. djupet för varje hörn i djupet-första-sökningsträdet (när det får besök), och
  2. för varje toppunkt v , det lägsta djupet av grannar av alla ättlingar till v (inklusive v själv) i djupet-först-sökningsträdet, kallat lågpunkten .

Djupet är standard att bibehålla under en djup-första sökning. Lågpunkten för v kan beräknas efter att ha besökt alla ättlingar till v (dvs precis innan v hoppar av stacken för första djup-sökningen ) som minimum av djupet av v , djupet av alla grannar till v (andra än förälder till v i trädet för djup-första-sökning) och lågpunkten för alla barn till v i trädet för djup-första-sökning.

Det viktigaste faktum är att en nonroot -vertex v är en cut -vertex (eller artikulationspunkt) som separerar två bikopplade komponenter om och bara om det finns ett barn y till v så att lågpunkt ( y ) ≥ djup ( v ). Den här egenskapen kan testas när den första djup-sökningen returneras från varje barn till v (dvs precis innan v plockas av stacken först-djup-sökning), och om det är sant , separerar v grafen i olika sammankopplade komponenter. Detta kan representeras genom att beräkna en dubbelkopplad komponent av varje sådant y (en komponent som innehåller y kommer att innehålla delträdet till y , plus v ) och sedan radera delträdet till y från trädet.

Rotpunkten måste hanteras separat: det är en avskuren toppunkt om och bara om den har minst två barn i DFS -trädet. Således räcker det med att helt enkelt bygga en komponent av varje barns subtree i roten (inklusive roten).

Pseudokod

GetArticulationPoints(i, d)
    visited[i] := true
    depth[i] := d
    low[i] := d
    childCount := 0
    isArticulation := false

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

Observera att termerna barn och förälder betecknar relationerna i DFS -trädet, inte det ursprungliga diagrammet.

En demo av Tarjans algoritm för att hitta snittade hörn. D betecknar djup och L betecknar lågpunkt.


Andra algoritmer

Ett enkelt alternativ till ovanstående algoritm använder kedjesönderdelningar , som är speciella öronnedbrytningar beroende på DFS -träd. Kedjesönderfall kan beräknas linjärt med denna korsningsregel . Låt C vara en kedja sönderdelning av G . Då G är 2-vertex-anslutas om och endast om G har minimal grad 2 och C 1 är den enda cykeln i C . Detta ger omedelbart ett 2-anslutningstest med linjär tid och kan utökas till att lista alla klippta hörn av G i linjär tid med hjälp av följande uttalande: En toppunkt v i en ansluten graf G (med minsta grad 2) är en avskuren toppunkt om och bara om v är infallande mot en bro eller v är den första hörnpunkten i en cykel i C - C 1 . Listan över klippta hörn kan användas för att skapa det blockklippta trädet i G i linjär tid.

I onlineversionen av problemet läggs hörn och kanter till (men tas inte bort) dynamiskt, och en datastruktur måste behålla de två anslutna komponenterna. Jeffery Westbrook och Robert Tarjan (1992) utvecklade en effektiv datastruktur för detta problem baserat på osammanhängande datastrukturer . Specifikt behandlar den n toppunktstillägg och m -kanttillägg i O ( m  α ( m ,  n )) total tid, där α är den inversa Ackermann -funktionen . Denna tidsgräns har visat sig vara optimal.

Uzi Vishkin och Robert Tarjan (1985) utformade en parallell algoritm på CRCW PRAM som körs i O (log  n ) -tid med n  +  m -processorer. Guojing Cong och David A. Bader (2005) utvecklade en algoritm som uppnår en hastighet på 5 med 12 processorer på SMP . Hastigheter som överstiger 30 baserat på den ursprungliga Tarjan-Vishkin-algoritmen rapporterades av James A. Edwards och Uzi Vishkin (2012).

Relaterade strukturer

Ekvivalensrelation

Man kan definiera en binär relation på kanterna på en godtycklig oriktad graf, enligt vilken två kanter e och f är relaterade om och bara om antingen e  =  f eller grafen innehåller en enkel cykel genom både e och f . Varje kant är relaterad till sig själv, och en kant e är relaterad till en annan kant f om och bara om f är relaterad på samma sätt till e . Mindre uppenbart är detta en transitiv relation : om det finns en enkel cykel som innehåller kanterna e och f , och en annan enkel cykel som innehåller kanterna f och g , kan man kombinera dessa två cykler för att hitta en enkel cykel genom e och g . Därför är detta en ekvivalensrelation , och den kan användas för att dela upp kanterna i ekvivalensklasser, delmängder av kanter med egenskapen att två kanter är relaterade till varandra om och bara om de tillhör samma ekvivalensklass. Subgraferna som bildas av kanterna i varje ekvivalensklass är de bikopplade komponenterna i den givna grafen. Således delar de tvåkopplade komponenterna kanterna på grafen; de kan dock dela hörn med varandra.

Blockera diagram

Det blocket graf av en given graf G är skärnings grafen av dess block. Således har den en toppunkt för varje block av G och en kant mellan två hörn när motsvarande två block delar en toppunkt. En graf H är blockdiagrammet för en annan graf G exakt när alla block av H är kompletta undergrafer. Graferna H med denna egenskap är kända som blockgraferna .

Blockklippt träd

En S-spets , skuren vertex , eller ledpunkt av en graf G är en vertex som delas av två eller flera block. Strukturen för blocken och skärpunkterna för en ansluten graf kan beskrivas av ett träd som kallas det blockklippta trädet eller BC-trädet . Detta träd har ett toppunkt för varje block och för varje ledpunkt i den angivna grafen. Det finns en kant i det blockklippta trädet för varje par av ett block och en artikulationspunkt som tillhör det blocket.

En graf och dess blockklippta träd.
Blocken är: b 1 = [1,2], b 2 = [2,3,4], b 3 = [2,5,6,7], b 4 = [7,8,9,10,11 ], b 5 = [8,12,13,14,15], b 6 = [10,16] och b 7 = [10,17,18];
skärpunkter är: c 1 = 2, c 2 = 7, c 3 = 8 och c 4 = 10.

Se även

Anteckningar

  1. ^ Hopcroft, J .; Tarjan, R. (1973). "Algoritm 447: effektiva algoritmer för grafmanipulation". Kommunikation av ACM . 16 (6): 372–378. doi : 10.1145/362248.362272 .
  2. ^ Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters , 113 (7): 241-244, arXiv : 1209.0700 , doi : 10.1016 / j. ipl.2013.01.016.
  3. ^ Westbrook, J .; Tarjan, RE (1992). "Underhålla brygganslutna och dubbelkopplade komponenter online". Algoritmik . 7 (1–6): 433–464. doi : 10.1007 / BF01758773 .
  4. ^ Tarjan, R .; Vishkin, U. (1985). "En effektiv parallellbikonnektivitetsalgoritm". SIAM J. Comput. 14 (4): 862–874. CiteSeerX  10.1.1.465.8898 . doi : 10.1137/0214061 .
  5. ^ Guojing Cong och David A. Bader (2005). "En experimentell studie av parallellkopplade komponentalgoritmer på symmetriska multiprocessorer (SMP)". Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium . s. 45b. doi : 10.1109/IPDPS.2005.100 .
  6. ^ Edwards, JA; Vishkin, U. (2012). "Bättre hastigheter med enklare parallellprogrammering för grafanslutning och bikonnektivitet". Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores - PMAM '12 . sid. 103. doi : 10.1145 / 2141702.2141714 . ISBN 9781450312110.
  7. ^ Tarjan & Vishkin (1985) krediterar definitionen av denna likvärdighetsrelation till Harary (1969) ; dock verkar Harary inte beskriva det i uttryckliga termer.
  8. ^ Harary, Frank (1969), Graph Theory , Addison-Wesley, sid. 29.
  9. ^ Harary (1969) , sid. 36.

Referenser

externa länkar