Komponent (grafteori)

En graf med tre komponenter

I grafteorin är en komponent i en oriktad graf en sammankopplad subgraf som inte är en del av någon större sammankopplad subgraf. Komponenterna i en graf delar upp dess hörn i disjunkta uppsättningar och är de inducerade subgraferna av dessa uppsättningar. En graf som själv är ansluten har exakt en komponent, bestående av hela grafen. Komponenter kallas ibland anslutna komponenter .

Antalet komponenter i en given graf är en viktig grafinvariant och är nära besläktad med invarianter av matroider , topologiska utrymmen och matriser . I slumpmässiga grafer är ett vanligt förekommande fenomen förekomsten av en gigantisk komponent , en komponent som är betydligt större än de andra; och av en perkolationströskel , en kantsannolikhet över vilken en gigantisk komponent existerar och under vilken den inte gör det.

Komponenterna i en graf kan konstrueras i linjär tid , och ett specialfall av problemet, märkning av anslutna komponenter , är en grundläggande teknik i bildanalys . Dynamiska anslutningsalgoritmer upprätthåller komponenter när kanter infogas eller tas bort i en graf, med kort tid per ändring. I beräkningskomplexitetsteori har anslutna komponenter använts för att studera algoritmer med begränsad rymdkomplexitet , och sublinjära tidsalgoritmer kan exakt uppskatta antalet komponenter.

Definitioner och exempel

En klustergraf med sju komponenter

En komponent i en given oriktad graf kan definieras som en ansluten subgraf som inte är en del av någon större ansluten subgraf. Till exempel har grafen som visas i den första illustrationen tre komponenter. Varje vertex $v$ i en graf tillhör en av grafens komponenter, som kan hittas som den inducerade subgrafen av uppsättningen av hörn som kan nås från $v$ . Varje graf är den osammanhängande föreningen av dess komponenter. Ytterligare exempel inkluderar följande specialfall:

I en tom graf bildar varje vertex en komponent med en vertex och nollkanter. Mer generellt bildas en komponent av denna typ för varje isolerad vertex i någon graf.
I en sammankopplad graf finns det exakt en komponent: hela grafen.
I en skog är varje komponent ett träd .
I en klustergraf är varje komponent en maximal klick . Dessa grafer kan produceras som de transitiva stängningarna av godtyckliga oriktade grafer, för vilka hitta den transitiva stängningen är en likvärdig formulering för att identifiera de anslutna komponenterna.

En annan definition av komponenter involverar ekvivalensklasserna för en ekvivalensrelation som definieras på grafens hörn. I en oriktad graf kan en vertex $v$ nås från en vertex $u$ om det finns en väg från $u$ till $v$ , eller motsvarande en promenad (a väg som tillåter upprepade hörn och kanter). Nåbarhet är en ekvivalensrelation, eftersom:

Det är reflexivt : Det finns en trivial bana med längden noll från vilken vertex som helst till sig själv.
Den är symmetrisk : Om det finns en bana från $u$ till $v$ , bildar samma kanter i omvänd ordning en bana från $v$ till $u$ .
Den är transitiv : Om det finns en sökväg från $u$ till $v$ och en sökväg från $v$ till $w$ , kan de två vägarna sammanfogas för att bilda en promenad från $u$ till $w$ .

Ekvivalensklasserna för denna relation delar upp grafens hörn i disjunkta uppsättningar , delmängder av hörn som alla kan nås från varandra, utan ytterligare nåbara par utanför någon av dessa delmängder . Varje vertex tillhör exakt en ekvivalensklass. Komponenterna är sedan de inducerade subgraferna som bildas av var och en av dessa ekvivalensklasser. Alternativt definierar vissa källor komponenter som uppsättningarna av hörn snarare än som de subgrafer de inducerar.

Liknande definitioner som involverar ekvivalensklasser har använts för att definiera komponenter för andra former av grafanslutning, inklusive de svaga komponenterna och starkt sammankopplade komponenterna i riktade grafer och de dubbelkopplade komponenterna i oriktade grafer.

Antal komponenter

Antalet komponenter i en given finit graf kan användas för att räkna antalet kanter i dess spännande skogar : I en graf med $n$ hörn och $c$ -komponenter kommer varje spännskog att ha exakt $nc$ kanter. Detta nummer $nc$ är den matroid -teoretiska rangordningen för grafen och rangordningen för dess grafiska matroid . Rangen för den dubbla kografiska matroiden är lika med grafens kretsrankning , det minsta antalet kanter som måste tas bort från grafen för att bryta alla dess cykler. I en graf med $m$ kanter, $n$ hörn och $c$ -komponenter är kretsrankningen $m-n+c$ .

En graf kan tolkas som ett topologiskt utrymme på flera sätt, till exempel genom att placera dess hörn som punkter i allmän position i det tredimensionella euklidiska rummet och representera dess kanter som linjesegment mellan dessa punkter. Komponenterna i en graf kan generaliseras genom dessa tolkningar som de topologiskt sammankopplade komponenterna i motsvarande utrymme; dessa är ekvivalensklasser av punkter som inte kan separeras med par av disjunkta slutna uppsättningar. Precis som antalet sammankopplade komponenter i ett topologiskt utrymme är en viktig topologisk invariant , det nollte Betti-talet , är antalet komponenter i en graf en viktig grafinvariant , och i topologisk grafteori kan det tolkas som det nollte Betti-talet av grafen.

Antalet komponenter uppstår på andra sätt även i grafteorin. I algebraisk grafteori är det lika med multipliciteten av 0 som ett egenvärde för den laplaciska matrisen för en finit graf. Det är också indexet för den första koefficienten som inte är noll för grafens kromatiska polynom , och det kromatiska polynomet för hela grafen kan erhållas som produkten av polynomen av dess komponenter. Antal komponenter spelar en nyckelroll i Tutte-satsen som karakteriserar finita grafer som har perfekta matchningar och den tillhörande Tutte–Berge-formeln för storleken på en maximal matchning och i definitionen av grafens seghet .

Algoritmer

Det är enkelt att beräkna komponenterna i en ändlig graf i linjär tid (i termer av antalet hörn och kanter på grafen) med antingen bredd- först-sökning eller djup-först-sökning . I båda fallen kommer en sökning som börjar vid någon speciell vertex $v$ att hitta hela komponenten som innehåller $v$ (och inte mer) innan den returneras. Alla komponenter i en graf kan hittas genom att loopa genom dess hörn och starta en ny sökning med bredd-först eller djup-först när slingan når en vertex som inte redan har inkluderats i en tidigare hittad komponent. Hopcroft & Tarjan (1973) beskriver i huvudsak denna algoritm och konstaterar att den redan var "välkänd".

Märkning av anslutna komponenter , en grundläggande teknik inom datorbildanalys, innebär att man bygger en graf från bilden och en komponentanalys på grafen. Hörnen är delmängden av bildens pixlar , valda som varande av intresse eller som sannolikt är en del av avbildade objekt. Kanter förbinder angränsande pixlar , med angränsning definierad antingen ortogonalt enligt Von Neumann-området , eller både ortogonalt och diagonalt enligt Moore-området . Att identifiera de anslutna komponenterna i denna graf möjliggör ytterligare bearbetning för att hitta mer struktur i dessa delar av bilden eller identifiera vilken typ av objekt som avbildas. Forskare har utvecklat algoritmer för att hitta komponenter som är specialiserade för den här typen av grafer, vilket gör det möjligt att bearbeta den i pixelordning snarare än i den mer spridda ordning som skulle genereras av sökning med bredd-först eller djup-först. Detta kan vara användbart i situationer där sekventiell åtkomst till pixlarna är effektivare än direktåtkomst, antingen för att bilden representeras på ett hierarkiskt sätt som inte tillåter snabb direktåtkomst eller för att sekventiell åtkomst ger bättre minnesåtkomstmönster .

Det finns också effektiva algoritmer för att dynamiskt spåra komponenterna i en graf när hörn och kanter läggs till, genom att använda en disjunkt-uppsättning datastruktur för att hålla reda på uppdelningen av hörnen i ekvivalensklasser, vilket ersätter två valfria klasser med deras förening när en kant som förbinder dem läggs till. Dessa algoritmer tar amorterad tid $O(\alpha (n))$ per operation, där addering av hörn och kanter och bestämning av den komponent i vilken en vertex faller är båda operationer, och $\alpha$ är en mycket långsamt växande invers av den mycket snabbt växande Ackermann - funktionen . En tillämpning av denna typ av inkrementell anslutningsalgoritm är i Kruskals algoritm för minsta spännträd , som lägger till kanter till en graf i sorterad ordning efter längd och inkluderar en kant i det minsta spännträdet endast när den kopplar samman två olika komponenter i det tidigare tillagda subgraf. När både kantinsättningar och kantborttagningar är tillåtna, dynamiska anslutningsalgoritmer fortfarande behålla samma information, i amorterad tid $O(\log ^{2}n/\ log \log n)$ per ändring och tid $O(\log n/\log \log n)$ per anslutningsfråga, eller i nästan logaritmisk randomiserad förväntad tid .

Komponenter i grafer har använts i beräkningskomplexitetsteori för att studera kraften hos Turing-maskiner som har ett arbetsminne begränsat till ett logaritmiskt antal bitar, med den mycket större ingången tillgänglig endast genom läsåtkomst snarare än att vara modifierbar. De problem som kan lösas av maskiner som begränsas på detta sätt definierar komplexitetsklassen L . Det var under många år oklart om anslutna komponenter kunde hittas i denna modell, när den formaliserades som ett beslutsproblem för att testa om två hörn hör till samma komponent, och 1982 definierades en relaterad komplexitetsklass, SL , för att inkludera detta anslutningsproblem och alla andra problem som motsvarar det under logaritmiska rymdreduktioner . Det bevisades slutligen 2008 att detta anslutningsproblem kan lösas i logaritmiskt utrymme, och därför att SL = L.

I en graf representerad som en närliggande lista , med slumpmässig åtkomst till dess hörn, är det möjligt att uppskatta antalet anslutna komponenter, med konstant sannolikhet att erhålla additivt (absolut) fel som mest $\varepsilon n$ , i sublinjär tid $O(\varepsilon ^{-2}\log \varepsilon ^{-1})$ .

I slumpmässiga grafer

En Erdős–Rényi–Gilbert slumpmässig graf med 1000 hörn med kantsannolikhet

p=1/(n-1)

(i det kritiska området), som visar en stor komponent och många små ettor

I slumpmässiga grafer ges storleken på komponenterna av en slumpvariabel , som i sin tur beror på den specifika modellen för hur slumpmässiga grafer väljs. I ${\displaystyle G(n,p)}-$ versionen av Erdős–Rényi–Gilbert-modellen genereras en graf på ${\displaystyle n} hörn genom att välja slumpmässigt och oberoende för varje par av hörn$ om man ska inkludera en kant som förbinder det paret, med sannolikheten $p$ för att inkludera en kant och sannolikheten $1-p$ för att lämna dessa två hörn utan en kant som förbinder dem. Den här modellens anslutningsmöjligheter beror på $p$ , och det finns tre olika intervall av $p$ med mycket olika beteende från varandra. I analysen nedan inträffar alla utfall med hög sannolikhet , vilket innebär att sannolikheten för utfallet är godtyckligt nära ett för tillräckligt stora värden på $n$ . Analysen beror på en parameter $\varepsilon$ , en positiv konstant oberoende av $n$ som kan vara godtyckligt nära noll.

Subkritisk $p<(1-\varepsilon )/n$: I detta intervall av $p$ är alla komponenter enkla och mycket små. Den största komponenten har logaritmisk storlek. Grafen är en pseudoskog . De flesta av dess komponenter är träd: antalet hörn i komponenter som har cykler växer långsammare än någon obegränsad funktion av antalet hörn. Varje träd av fast storlek förekommer linjärt många gånger.
Kritisk $p\approx 1/n$: Den största anslutna komponenten har ett antal hörn som är proportionella mot $n^{2/3}$ . Det kan finnas flera andra stora komponenter; dock är det totala antalet hörn i icke-trädkomponenter återigen proportionellt mot $n^{2/3}$ .
Superkritisk $p>(1+\varepsilon )/n$: Det finns en enda gigantisk komponent som innehåller ett linjärt antal hörn. För stora värden på $p$ närmar sig dess storlek hela grafen: $|C_{1}|\approx yn$ där $y$ är den positiva lösningen till ekvationen $e^{-pny}=1 -y$ . De återstående komponenterna är små, med logaritmisk storlek.

I samma modell av slumpmässiga grafer kommer det att finnas flera sammankopplade komponenter med hög sannolikhet för värden på $p$ under en betydligt högre tröskel, $p <(1-\varepsilon )(\log n)/n$ , och en enda ansluten komponent för värden över tröskeln, $p>(1+\ varepsilon )(\log n)/n$ . Detta fenomen är nära besläktat med kupongsamlarens problem : för att kunna anslutas behöver en slumpmässig graf tillräckligt med kanter för att varje vertex ska falla in mot åtminstone en kant. Närmare bestämt, om slumpmässiga kanter läggs till en efter en till en graf, kommer med hög sannolikhet den första kanten vars addition förbinder hela grafen att vidröra den sista isolerade vertexen.

För olika modeller, inklusive de slumpmässiga subgraferna av rutnätsdiagram, beskrivs de anslutna komponenterna av perkolationsteori . En nyckelfråga i denna teori är förekomsten av en perkolationströskel , en kritisk sannolikhet över vilken en gigantisk komponent (eller oändlig komponent) existerar och under vilken den inte gör det.

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