Komponent (grafteori) - Component (graph theory)

En graf med tre komponenter.

I grafteorin är en komponent i en icke-riktad graf en inducerad subgraf där två hörn är anslutna till varandra genom banor och som inte är anslutna till ytterligare hörn i resten av grafen. Till exempel har grafen som visas i illustrationen tre komponenter. Ett toppunkt utan infallande kanter är i sig en komponent. En graf som i sig är ansluten har exakt en komponent som består av hela grafen. Komponenter kallas ibland också anslutna komponenter .

En ekvivalensrelation

Ett alternativt sätt att definiera komponenter involverar ekvivalensklasserna för en ekvivalensrelation som definieras på kurvorna i diagrammet. I en oriktad graf, en spets v är nåbar från en vertex u om det finns en väg från u till v . I denna definition räknas ett enda toppunkt som en väg med längd noll, och samma toppunkt kan förekomma mer än en gång inom en väg. Reachability är en ekvivalensrelation , eftersom:

• Det är reflexivt : Det finns en trivial väg med längden noll från alla toppar till sig själv.
• Det är symmetriskt : Om det finns en väg från u till v , bildar samma kanter en väg från v till u .
• Det är övergående : Om det finns en väg från u till v och en väg från v till w , kan de två vägarna sammanfogas för att bilda en väg från u till w .

Komponenterna är sedan de inducerade underbilderna som bildas av ekvivalensklasserna för denna relation.

Antalet komponenter

Antalet komponenter är en viktig topologisk invariant i en graf. I topologisk grafteori kan den tolkas som grafens noll Betti-nummer . I algebraisk grafteori är det lika med mångfalden 0 som en egenvärde för den laplaciska matrisen i diagrammet. Det är också indexet för den första icke-nollkoefficienten för det kromatiska polynomet i en graf. Antal komponenter spelar en nyckelroll i Tutte-satsen som karaktäriserar grafer som har perfekta matchningar och i definitionen av grafens seghet .

Algoritmer

Det är enkelt att beräkna komponenterna i ett diagram i linjär tid (i termer av antalet hörn och kanter i diagrammet) med antingen bredd-första sökning eller djup-första sökning . I båda fallen kommer en sökning som börjar vid ett visst toppunkt v att hitta hela komponenten som innehåller v (och inte mer) innan den återvänder. För att hitta alla komponenter i en graf, gå igenom dess hörn, starta en ny bredd först eller djup första sökning när slingan når ett toppunkt som inte redan har inkluderats i en tidigare hittad komponent. Hopcroft & Tarjan (1973) beskriver i huvudsak denna algoritm och säger att den vid den tidpunkten var "välkänd".

Det finns också effektiva algoritmer för att dynamiskt spåra komponenterna i en graf när hörn och kanter läggs till, som en enkel tillämpning av ojämna datastrukturer . Dessa algoritmer kräver amorterad O ( α ( n )) -tid per operation, där addering av hörn och kanter och bestämning av komponenten i vilken ett toppunkt faller båda är operationer, och α ( n ) är en mycket långsamt växande invers av den mycket snabbt växande Ackermann-funktion . Ett relaterat problem är att spåra komponenter eftersom alla kanter raderas från en graf, en efter en; det finns en algoritm för att lösa detta med konstant tid per fråga och O (| V || E |) tid för att upprätthålla datastrukturen; detta är en upplupen kostnad på O (| V |) per kantradering. För skogar kan kostnaden sänkas till O ( q + | V | log | V |) , eller O (log | V |) amorterad kostnad per kantradering ( Shiloach & Even 1981 ).

Forskare har också studerat algoritmer för att hitta komponenter i mer begränsade beräkningsmodeller, till exempel program där arbetsminnet är begränsat till ett logaritmiskt antal bitar (definierat av komplexitetsklass L ). Lewis & Papadimitriou (1982) frågade om det är möjligt att testa i logspace om två hörn hör till samma komponent i en icke-riktad graf och definierade en komplexitetsklass SL av problem logspace-ekvivalent med anslutning. Slutligen lyckades Reingold (2008) hitta en algoritm för att lösa detta anslutningsproblem i logaritmiskt utrymme, vilket visar att L = SL .

Komponenter i slumpmässiga grafer

I slumpmässiga grafer ges storleken på komponenterna av en slumpmässig variabel, som i sin tur beror på den specifika modellen.

Den modellen har tre regioner med till synes olika beteenden: ${\ displaystyle G (n, p)}$

Subkritisk ${\ displaystyle np <1}$

Alla komponenter är enkla och mycket små, den största komponenten har storlek ;${\ displaystyle | C_ {1} | = O (\ log n)}$

Kritisk ${\ displaystyle np = 1}$

${\ displaystyle | C_ {1} | = O (n ^ {2/3})}$;

Superkritisk ${\ displaystyle np> 1}$

${\ displaystyle | C_ {1} | \ approx yn}$var är den positiva lösningen på ekvationen${\ displaystyle y = y (np)}$${\ displaystyle e ^ {- pny} = 1-y.}$

där respektive är de största respektive näst största komponenterna. Alla andra komponenter har storleksordningen${\ displaystyle C_ {1}}$${\ displaystyle C_ {2}}$${\ displaystyle O (\ log n).}$

Se även

• Jätte komponent
• Starkt ansluten komponent , ett relaterat koncept för riktade grafer
• Biconnected component
• Modulär sönderdelning för korrekt generalisering av komponenter på oriktade grafer
• Märkning av ansluten komponent , en grundläggande teknik i datorbildsanalys baserad på diagramkomponenter
• Perkolationsteori , en teori som beskriver komponenternas beteende i slumpmässiga underbilder av rutdiagram
• Centralitet
• Bridge (grafteori)

Referenser

• Hopcroft, J .; Tarjan, R. (1973), "Algoritm 447: effektiva algoritmer för grafmanipulation", Kommunikation av ACM , 16 (6): 372–378, doi : 10.1145 / 362248.362272
• Lewis, Harry R .; Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Teoretisk datavetenskap , 19 (2): 161–187, doi : 10.1016 / 0304-3975 (82) 90058-5
• Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM , 55 (4): Article 17, 24 pages, doi : 10.1145 / 1391289.1391291
• Shiloach, Yossi; Even, Shimon (1981), "Ett on-line edge-deletion problem", Journal of the ACM , 28 (1): 1–4, doi : 10.1145 / 322234.322235

externa länkar

• MATLAB-kod för att hitta komponenter i oriktade grafer , MATLAB File Exchange.
• Anslutna komponenter , Steven Skiena, The Stony Brook Algorithm Repository