Bikopplad komponent

Ej att förväxla med vertex cut .
An example graph with biconnected components marked
Varje färg motsvarar en dubbelkopplad komponent. Flerfärgade hörn är skurna hörn och tillhör således flera dubbelkopplade komponenter.

I grafteorin är en biansluten komponent (ibland känd som en 2-ansluten komponent ) en maximal biansluten subgraf . Alla anslutna grafer bryts ned till ett träd av dubbelkopplade komponenter som kallas grafens block-cut-träd . Blocken är fästa vid varandra vid delade hörn som kallas skurna hörn eller separerande hörn eller artikulationspunkter . Närmare bestämt är en skuren vertex vilken vertex som helst vars borttagning ökar antalet anslutna komponenter .

Algoritmer

Linjärt tidsdjup-första sökning

Den klassiska sekventiella algoritmen för att beräkna bikopplade komponenter i en ansluten oriktad graf beror på John Hopcroft och Robert Tarjan (1973). Den körs i linjär tid och är baserad på djup-först-sökning . Denna algoritm beskrivs också som uppgift 22-2 i Introduktion till algoritmer (både 2:a och 3:e upplagan).

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

  1. djupet för varje vertex i trädet för djup-först-sökning (när det väl har besökts), och
  2. för varje vertex v , det lägsta djupet av grannar av alla avkomlingar till v (inklusive v själv) i djupet-första-sökningsträdet, kallat lågpunkten .

Djupet är standard att upprätthålla under en djup-först-sökning. Den lägsta punkten för v kan beräknas efter att ha besökt alla avkomlingar till v (dvs. precis innan v hoppar av stapeln djup-först-sökning ) som minimum av djupet av v , djupet för alla grannar till v (annat än föräldern till v i djupet-första-sökningsträdet) och lågpunkten för alla barn till v i djupet-första-sökningsträdet.

Nyckelfaktumet är att en icke-rot vertex v är en skuren vertex (eller artikulationspunkt) som separerar två dubbelkopplade komponenter om och endast om det finns ett barn y av v så att lowpoint( y ) ≥ depth( v ) . Den här egenskapen kan testas när djupet-först-sökningen returneras från varje underordnad v (dvs. precis innan v tas bort från djup-först-sökning-stacken), och om sant , separerar v grafen i olika bianslutna komponenter. Detta kan representeras genom att beräkna en dubbelkopplad komponent av varje sådan y (en komponent som innehåller y kommer att innehålla underträdet av y , plus v ), och sedan radera underträdet av y från trädet.

Rotvertexet måste hanteras separat: det är ett avskuret vertex om och bara om det har minst två barn i DFS-trädet. Det räcker alltså att helt enkelt bygga en komponent av varje underträde till roten (inklusive roten).

Pseudokod 


    
            GetArticulationPoints(i, d)  visited[i] :=  sant  djup[i] := d low[i] := d childCount := 0 isArticulation :=  false  för varje  ni  i  adj[i]  gör  om  inte  besökt[ni]  sedan  förälder[ni] := i GetArticulationPoints(ni, d + 1) childCount := childCount + 1  om  låg[ni] ≥ djup[i]  då  ärArticulation :=  sant  låg[i] := Min (låg[i], låg[ni])  annars om  ni ≠ förälder[i]  sedan  låg[i] := Min (låg[i], djup[ni])  om  (förälder[i] ≠  null  och  isArticulation)  eller  (förälder[i] =  null  och  childCount > 1)  sedan  Output i som artikulationspunkt

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

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


Andra algoritmer

Ett enkelt alternativ till ovanstående algoritm använder kedjesönderdelning , som är speciella öronnedbrytningar beroende på DFS -träd. Kedjesönderdelning kan beräknas i linjär tid genom denna korsningsregel . Låt C vara en kedjesönderdelning av G . Då G 2-vertexkopplad om och endast om G har minsta grad 2 och C 1 är den enda cykeln i C . Detta ger omedelbart ett linjär-tid 2-anslutningstest och kan utökas till att lista alla skära hörn av G i linjär tid med hjälp av följande påstående: En vertex v i en sammankopplad graf G (med minsta grad 2) är en cut vertex om och endast om v faller in mot en bro eller v är den första spetsen i en cykel i C – C 1 . Listan över avskurna hörn kan användas för att skapa det blockklippta trädet för 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 underhålla de bianslutna komponenterna. Jeffery Westbrook och Robert Tarjan (1992) utvecklade en effektiv datastruktur för detta problem baserad på disjunkta datastrukturer . Specifikt behandlar den n vertexadditioner och m kantadditioner i O ( m α ( m , n )) total tid, där α är den omvända Ackermann-funktionen . Denna tidsbundna har visat sig vara optimal.

Uzi Vishkin och Robert Tarjan (1985) designade en parallell algoritm på CRCW PRAM som körs i O (log n ) tid med n + m processorer.

Relaterade strukturer

Ekvivalensförhållande

Man kan definiera en binär relation på kanterna av en godtycklig oriktad graf, enligt vilken två kanter e och f är relaterade om och endast 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 endast 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 , då 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 endast om de tillhör samma ekvivalensklass. Subgraferna som bildas av kanterna i varje ekvivalensklass är de bikopplade komponenterna i den givna grafen. De tvåkopplade komponenterna delar alltså upp kanterna på grafen; dock kan de dela hörn med varandra.

Blockdiagram

Blockdiagrammet för en given graf G är skärningsdiagrammet för dess block . Således har den en vertex för varje block av G och en kant mellan två hörn närhelst de motsvarande två blocken delar en vertex. En graf H är blockgrafen för en annan graf G exakt när alla block av H är kompletta subgrafer. Graferna H med den här egenskapen kallas blockgraferna .

Blockhugget träd

En cutpoint , cut vertex , eller artikulationspunkt för en graf G är en vertex som delas av två eller flera block. Strukturen av blocken och skärpunkterna i en sammankopplad graf kan beskrivas av ett träd som kallas block-cut tree eller BC-tree . Detta träd har en vertex för varje block och för varje artikulationspunkt i den givna grafen. Det finns en kant i det blockskurna trädet för varje par av ett block och en artikulationspunkt som hör till det blocket.














En graf och dess blockskurna träd. Block : 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] b 7 = [10,17,18] Cutpoints: c 1 = 2 c 2 = 7 c 3 = 8 c 4 = 10

Se även

Anteckningar

  1. ^    AL-TAIE, MOHAMMED ZUHAIR. KADRY, SEIFEDINE (2019). "3. Grafteori". PYTHON FÖR GRAF- OCH NÄTVERKSANALYS . SPRINGER. ISBN 3-319-85037-7 . OCLC 1047552679 . En cut-vertex är en vertex som om den tas bort ökar antalet nätverkskomponenter.
  2. ^ Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: effektiva algoritmer för grafmanipulation" . Kommunikation från ACM . 16 (6): 372–378. doi : 10.1145/362248.362272 .
  3. ^ 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 .
  4. ^ Westbrook, J.; Tarjan, RE (1992). "Underhåll av broanslutna och dubbelkopplade komponenter online". Algoritmik . 7 (1–6): 433–464. doi : 10.1007/BF01758773 .
  5. ^   Tarjan, R.; Vishkin, U. (1985). "En effektiv parallell biconnectivity-algoritm". SIAM J. Comput. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . doi : 10.1137/0214061 .
  6. ^ Tarjan & Vishkin (1985) krediterar definitionen av denna likvärdighetsrelation till Harary (1969) ; Harary verkar dock inte beskriva det i explicita termer.
  7. ^ Harary, Frank (1969), Graph Theory , Addison-Wesley, s. 29 .
  8. ^ Harary (1969) , sid. 36.
  • Eugene C. Freuder (1985). "A Tillräckligt villkor för Backtrack-Bounded Search". Journal of the Association for Computing Machinery . 32 (4): 755–761. doi : 10.1145/4221.4225 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Biconnected_component&oldid=1136281926 "