Starkt ansluten komponent

En riktad graf (digraf) kallas starkt sammankopplad om två av dess hörn s och t är starkt sammankopplade, det vill säga om det finns en riktad väg från till  och en samtidigt riktad väg från till

De starkt sammankopplade komponenterna i en digraf är dess inklusionsmaximala starkt sammankopplade subgrafer. En starkt ansluten region är en uppsättning hörn av starkt anslutna komponenter.

Definitioner

En digraf som inte tillhör klassen av starkt sammankopplade grafer innehåller en uppsättning starkt sammankopplade komponenter och en uppsättning riktade kanter som går från en komponent till en annan.

Varje hörn av en digraf är starkt kopplad till sig själv.

Algoritmer

Den enklaste algoritmen för att lösa problemet med att hitta starkt anslutna komponenter i en digraf fungerar enligt följande:

  1. Med transitiv stängning kontrollerar vi om den är nåbar från och från för alla par och
  2. Sedan definierar vi en sådan oriktad graf , som innehåller en kant för varje sådant par.
  3. Sökandet efter anslutna komponenter i en sådan oriktad graf ger starkt anslutna komponenter i digrafen.

Uppenbarligen är den huvudsakliga körtiden för denna algoritm upptagen av en transitiv stängning.

Det finns också tre algoritmer som löser detta problem i linjär tid, det vill säga V gånger snabbare än ovanstående algoritm. Dessa är Kosarajus algoritmer , sök efter starkt anslutna komponenter med två stackar och Tarjan .

Exempel

Figuren visar en digraf för vilken alla tre starkt sammankopplade komponenterna visas (skuggade områden med en streckad linje).

Se även

Litteratur