Svag komponent

I grafteorin delar de svaga komponenterna i en riktad graf upp grafens hörn i delmängder som är helt ordnade efter nåbarhet . De bildar den finaste partitionen av uppsättningen av hörn som är helt ordnad på detta sätt.

Definition

De svaga komponenterna definierades i en artikel från 1972 av Ronald Graham , Donald Knuth och (postumt) Theodore Motzkin , analogt med de starkt sammankopplade komponenterna i en riktad graf, som bildar den finaste möjliga uppdelningen av grafens hörn i delmängder som är delvis ordnade efter tillgänglighet. Istället definierade de de svaga komponenterna till att vara den finaste uppdelningen av hörnen i delmängder som är helt ordnade efter tillgänglighet.

Mer detaljerat definierar Knuth (2022) de svaga komponenterna genom en kombination av fyra symmetriska relationer på hörnen av valfri riktad graf, här betecknad som ${\displaystyle \Leftrightarrow } ,$ ∥ $\displaystyle \parallel }$ , $\approx$ , och $\asymp$ :

• För två valfria hörn $u$ och $v$ i grafen, $u\Leftrightarrow v$ om och endast om varje vertex kan nås från den andra: det finns vägar i grafen från $u$ till $v$ och från $v$ till $u$ . Relationen $\Leftrightarrow$ är en ekvivalensrelation och dess ekvivalensklasser används för att definiera de starkt sammankopplade komponenterna i grafen.
• För två valfria hörn $u$ och $v$ i grafen, $u\parallel v$ om och endast om ingen av hörn är nåbar från den andra: det finns inga vägar i grafen i endera riktningen mellan $u$ och $v$ .
• För två valfria hörn $u$ och $v$ i grafen, $u\approx v$ om och endast om antingen $u\Leftrightarrow v$ eller $u\parallel v$ . Det vill säga, det kan finnas en tvåvägsförbindelse mellan dessa hörn, eller så kan de vara ömsesidigt oåtkomliga, men de kanske inte har en enkelriktad anslutning.
• Relationen $\asymp$ definieras som den transitiva stängningen av $\approx$ . Det vill säga $u\asymp v$ när det finns en sekvens $u\approx \cdots \approx v$ av hörn, som börjar med $u$ och slutar med $v$ , så att varje på varandra följande par i sekvensen är relaterat till $\approx$ .

Då är $\asymp$ en ekvivalensrelation : varje vertex är relaterat till sig själv med $\asymp$ (eftersom det kan nå sig själv i båda riktningarna med banor med längden noll), vilka två hörn som helst som är relaterade till $\asymp$ kan bytas mot varandra utan att ändra denna relation (eftersom $\asymp$ är byggd ur de symmetriska relationerna $\Leftrightarrow$ och $\parallel$ ), och $\asymp$ är en transitiv relation (eftersom den är en transitiv stängning av en annan relation). Som med alla ekvivalensrelationer kan den användas för att dela upp grafens hörn i ekvivalensklasser , delmängder av hörnen så att två hörn är relaterade med $\asymp$ om och endast om de tillhör samma ekvivalensklass . Dessa ekvivalensklasser är de svaga komponenterna i den givna grafen.

Den ursprungliga definitionen av Graham, Knuth och Motzkin är likvärdig men formulerad något annorlunda. Givet en riktad graf $G$ displaystyle konstruerar de först en annan graf ${\hat {G}}$ som komplementgrafen för den transitiva stängningen av $G}$ . Som Tarjan (1974) beskriver representerar kanterna i ${\hat {G}}$ icke-banor , par av hörn som inte är förbundna med en bana i $G$ . Sedan hör två hörn till samma svaga komponent när de antingen tillhör samma starkt anslutna komponent av $G$ eller av ${\hat {G}}$ . Som Graham, Knuth och Motzkin bevisar, definierar detta villkor en ekvivalensrelation, samma som definierats ovan som $\asymp$ .

Motsvarande dessa definitioner kallas en riktad graf svagt kopplad om den har exakt en svag komponent. Detta betyder att dess hörn inte kan delas upp i två delmängder, så att alla hörn i den första delmängden kan nå alla hörn i den andra delmängden, men så att ingen av hörnen i den andra delmängden kan nå någon av hörnen i den första delmängden. Det skiljer sig från andra föreställningar om svag anslutning i litteraturen, såsom anslutning och komponenter i den underliggande oanslutna grafen, för vilka Knuth föreslår den alternativa terminologin oriktade komponenterna .

Egenskaper

Om $X$ och $Y$ är två svaga komponenter i en riktad graf, så kan antingen alla hörn i $X$ nå alla hörn i $Y$ med sökvägar i grafen , eller alla hörn i $Y$ kan nå alla hörn i $X$ . Det kan dock inte existera nåbarhetsrelationer i båda riktningarna mellan dessa två komponenter. Därför kan vi definiera en ordning på de svaga komponenterna, enligt vilken $X<Y$ när alla hörn i $X$ kan nå alla hörn i $Y$ . Per definition, $X\nless X$ . Detta är en asymmetrisk relation (två element kan bara relateras i en riktning, inte den andra) och det ärver egenskapen att vara en transitiv relation från transitiviteten för nåbarhet. Därför definierar den en total ordning på de svaga komponenterna. Det är den finaste möjliga uppdelningen av hörnen i en helt ordnad uppsättning av hörn som överensstämmer med nåbarhet.

Denna ordning på de svaga komponenterna kan alternativt tolkas som en svag ordning på själva hörnen, med egenskapen att när $u<v$ i den svaga ordningen, så finns det nödvändigtvis en väg från $u$ till $v$ , men inte från $v$ till $u$ . Detta är dock inte en fullständig karaktärisering av denna svaga ordning, eftersom två hörn $u$ och $v$ skulle kunna ha samma nåbarhetsordning samtidigt som de tillhör samma svaga komponent som varandra .

Varje svag komponent är en förening av starkt sammankopplade komponenter. Om de starkt anslutna komponenterna i en given graf dras samman till enstaka hörn, vilket ger en riktad acyklisk graf ( kondensationen av den givna grafen), och sedan denna kondensation sorteras topologiskt , så visas varje svag komponent nödvändigtvis som en konsekutiv undersekvens av den topologiska ordning på de starka komponenterna.

Algoritmer

En algoritm för att beräkna de svaga komponenterna i en given riktad graf i linjär tid beskrevs av Pacault (1974) , och förenklades därefter av Tarjan (1974) och Knuth (2022) . Som Tarjan observerar, kommer Tarjans starkt anslutna komponenters algoritm baserad på djup-först-sökning att mata ut de starkt anslutna komponenterna i (omvändningen av) en topologiskt sorterad ordning. Algoritmen för svaga komponenter genererar de starkt anslutna komponenterna i denna ordning, och upprätthåller en partition av komponenterna som har genererats hittills i de svaga komponenterna i deras inducerade subgraf . När alla komponenter har genererats kommer denna partition att beskriva de svaga komponenterna i hela grafen.

Det är bekvämt att behålla den nuvarande partitionen i svaga komponenter i en stack , där varje svag komponent bibehåller en lista över dess källor , starkt anslutna komponenter som inte har några inkommande kanter från andra starkt anslutna komponenter i samma svaga komponent, med den senaste genererad källa först. Varje nyligen genererad starkt ansluten komponent kan bilda en ny svag komponent på egen hand, eller kan hamna samman med några av de tidigare konstruerade svaga komponenterna nära toppen av stacken, de för vilka den inte kan nå alla källor .

Således utför algoritmen följande steg:

• Initiera en tom hög med svaga komponenter, var och en associerad med en lista över dess källkomponenter.
• Använd Tarjans starkt anslutna komponenters algoritm för att generera de starkt anslutna komponenterna i den givna grafen i omvänd topologisk ordning. När varje starkt ansluten komponent $S$ genereras, utför följande steg med den:
  • Medan högen inte är tom och $S$ inte har några kanter till den översta svaga komponenten i högen, skjuter du upp den komponenten från högen.
  • Om stacken fortfarande inte är tom, och vissa källor till dess svaga toppkomponent inte träffas av kanter från $S$ , skjuter du återigen upp den komponenten från stacken.
  • Konstruera en ny svag komponent $W$ , som innehåller som källor $S$ och alla källor som inte har träffats från den översta komponenten som poppades, och tryck $W$ på stacken.

Varje test för om några kanter från $S$ träffar en svag komponent kan utföras i konstant tid när vi hittar en kant från $S$ till den senast genererade tidigare starkt anslutna komponenten, genom att jämföra målkomponenten av den kanten till den första källan för den andra-till-översta komponenten på stapeln.