nätkomponenter

Nätkomponenter är inom grafteori de maximalt sammanhängande mängderna av noder i ett nätverk där varje nod är nåbar från varje annan nod i samma komponent. I en oredigerad (o riktad) graf motsvarar dessa komponenter ofta begreppet sammanhängande komponenter. För riktade grafer finns olika varianter: starkt sammanhängande komponenter där varje nod kan nås från varje annan nod via riktade vägar, och svagt sammanhängande komponenter som uppstår när man ignorerar riktningar i kanten.

Formellt utgörs ett graf G=(V,E) av nodmängden V och kantmängden E. En delmängd C⊆V är en nätkomponent om för varje u,v∈C finns en stig mellan u och v i G, och C är maximal med denna egenskap. I en riktad graf gäller istället att en starkt sammanhängande komponent är en maximal delmängd C där varje par u,v∈C har vägar i båda riktningarna (u→v och v→u). En svagt sammanhängande komponent uppnås när man betraktar riktningarna som obetydliga och kräver att varje par i C är kopplat av en stig i någon riktning.

Egenskaper: Antalet nätkomponenter i en graf är ett mått på hur uppdelad grafen är; komponenterna bildar en partition av nodmängden. Storlekarna på komponenterna kan vara olika och speglar ofta strukturens modularitet och isolering. Nätkomponenter används för att bedöma robusthet, felverk och kommunikation i olika nätverkstyper.

Beräkningar: För oänd av riktade och o riktade grafer används effektiva algoritmer. I o riktade grafer kan man med DFS eller BFS identifiera alla komponenter i O(V+E). För starkt sammanhängande komponenter används algoritmer som Kosaraju, Tarjan eller Gabow med samma linearitet O(V+E). Dynamisk anslutning kan hanteras med fusionsstrukturer (Union-Find) i vissa tillämpningar.