Nåbarhet - Reachability

I grafteori , nåbarhet hänvisar till möjligheten att få från en vertex till en annan inom en graf. En toppunkt kan nå en toppunkt (och kan nås från ) om det finns en sekvens av intilliggande hörn (dvs. en väg ) som börjar med och slutar med . ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle t}$

I en oriktad graf kan räckvidd mellan alla hörnpar bestämmas genom att identifiera de anslutna komponenterna i grafen. Varje par hörn i en sådan graf kan nå varandra om och bara om de tillhör samma anslutna komponent; därför är nåbarheten i en sådan graf symmetrisk ( når iff når ). De anslutna komponenterna i en oriktad graf kan identifieras i linjär tid. Resten av den här artikeln fokuserar på det svårare problemet med att fastställa parvis nåbarhet i en riktad graf (som för övrigt inte behöver vara symmetrisk). ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$

Definition

För en riktad graf , med vertex set och kanten som , nåbarhets förhållande av är den transitiva stängningen av , det vill säga den uppsättning av alla ordnade par av hörn i för vilken det finns en sekvens av vertex så att kanten är i för allt . ${\ displaystyle G = (V, E)}$ ${\ displaystyle V}$ ${\ displaystyle E}$ ${\ displaystyle G}$ ${\ displaystyle E}$ ${\ displaystyle (s, t)}$ ${\ displaystyle V}$ ${\ displaystyle v_ {0} = s, v_ {1}, v_ {2}, ..., v_ {k} = t}$ ${\ displaystyle (v_ {i-1}, v_ {i})}$ ${\ displaystyle E}$ ${\ displaystyle 1 \ leq i \ leq k}$

Om det är acykliskt , är dess tillgänglighetsrelation en partiell ordning ; vilken partiell ordning som helst kan definieras på detta sätt, till exempel som förhållandet mellan dess transitiva reduktion . En anmärkningsvärd konsekvens av detta är att eftersom partiella order är antisymmetriska, om de kan nås , så vet vi att det inte kan nås . Intuitivt, om vi kunde resa från till och tillbaka till , skulle det innehålla en cykel som motsäger att den är acyklisk. Om den är riktad men inte acyklisk (dvs den innehåller minst en cykel), kommer dess tillgänglighetsrelation att motsvara en förbeställning istället för en delordning. ${\ displaystyle G}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle G}$ ${\ displaystyle G}$

Algoritmer

Algoritmer för att bestämma nåbarhet delas in i två klasser: de som kräver förbehandling och de som inte gör det.

Om du bara har en (eller några) frågor att göra kan det vara mer effektivt att avstå från användningen av mer komplexa datastrukturer och beräkna det önskade parets tillgänglighet direkt. Detta kan åstadkommas i linjär tid med hjälp av algoritmer som bredden första sökningen eller iterativ fördjupning djup-första sökning .

Om du kommer att göra många frågor kan en mer sofistikerad metod användas; det exakta metodvalet beror på arten av grafen som analyseras. I utbyte mot förbehandlingstid och lite extra lagringsutrymme kan vi skapa en datastruktur som sedan kan besvara tillgänglighetsfrågor på alla hörnpar på så låg tid som möjligt. Tre olika algoritmer och datastrukturer för tre olika, alltmer specialiserade situationer beskrivs nedan. ${\ displaystyle O (1)}$

Floyd-Warshall-algoritmen

Den Floyd-Warshall algoritm kan användas för att beräkna den transitiva stängningen av någon riktad graf, som ger upphov till nåbarhets förhållande som i definitionen ovan.

Algoritmen kräver tid och utrymme i värsta fall. Denna algoritm är inte enbart intresserad av nåbarhet eftersom den också beräknar det kortaste vägavståndet mellan alla hörnpar. För grafer som innehåller negativa cykler kan kortaste vägar vara odefinierade, men nåbarhet mellan par kan fortfarande noteras. ${\ displaystyle O (| V |^{3})}$ ${\ displaystyle O (| V |^{2})}$

Thorups algoritm

För plana grafer är en mycket snabbare metod tillgänglig, som beskrivs av Mikkel Thorup 2004. Denna metod kan svara på tillgänglighetsfrågor på en plan graf i tid efter att ha använt förbehandlingstid för att skapa en datastruktur av storlek. Denna algoritm kan också tillhandahålla ungefärliga kortaste vägavstånd, samt ruttinformation. ${\ displaystyle O (1)}$ ${\ displaystyle O (n \ log {n})}$ ${\ displaystyle O (n \ log {n})}$

Det övergripande tillvägagångssättet är att associera till varje hörn en relativt liten uppsättning så kallade separatorvägar så att varje väg från en toppunkt till någon annan toppunkt måste gå igenom minst en av separatorerna som är associerade med eller . En översikt över de tillgänglighetsrelaterade avsnitten följer. ${\ displaystyle v}$ ${\ displaystyle w}$ ${\ displaystyle v}$ ${\ displaystyle w}$

Med tanke på en graf börjar algoritmen med att organisera hörnen i lager med utgångspunkt från en godtycklig topp . Skikten byggs i alternerande steg genom att först betrakta alla hörn som kan nås från föregående steg (börjar med bara ) och sedan alla hörn som når till föregående steg tills alla hörn har tilldelats ett lager. Genom konstruktion av lagren uppträder varje toppunkt högst två lager, och varje riktad väg , eller dipat, i finns i två intilliggande lager och . Låt vara det sista lagret som skapades, det vill säga det lägsta värdet för sådant . ${\ displaystyle G}$ ${\ displaystyle v_ {0}}$ ${\ displaystyle v_ {0}}$ ${\ displaystyle G}$ ${\ displaystyle L_ {i}}$ ${\ displaystyle L_ {i+1}}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle \ bigcup _ {i = 0}^{k} L_ {i} = V}$

Diagrammet uttrycks sedan igen som en serie digrafer där varje och var är sammandragningen av alla tidigare nivåer till en enda toppunkt. Eftersom varje dipat förekommer i högst två på varandra följande lager, och eftersom varje bildas av två på varandra följande lager, visas varje dipat i sin helhet i minst ett (och inte mer än 2 på varandra följande grafer) ${\ displaystyle G_ {0}, G_ {1}, \ ldots, G_ {k-1}}$ ${\ displaystyle G_ {i} = r_ {i} \ cup L_ {i} \ cup L_ {i+1}}$ ${\ displaystyle r_ {i}}$ ${\ displaystyle L_ {0} \ ldots L_ {i-1}}$ ${\ displaystyle G_ {i}}$ ${\ displaystyle G}$ ${\ displaystyle G_ {i}}$

För varje identifieras tre separatorer som, när de tas bort, bryter grafen i tre komponenter som var och en innehåller högst hörn av originalet. Eftersom den är byggd av två lager av motsatta dipater kan varje separator bestå av upp till 2 dipater, totalt upp till 6 dipater över alla separatorerna. Låt vara denna uppsättning dipater. Beviset för att sådana separatorer alltid kan hittas är relaterat till Planar Separator Theorem of Lipton och Tarjan, och dessa separatorer kan lokaliseras i linjär tid. ${\ displaystyle G_ {i}}$ ${\ displaystyle 1/2}$ ${\ displaystyle G_ {i}}$ ${\ displaystyle S}$

För var och en ger den naturliga riktningen en naturlig indexering av dess hörn från början till slutet av vägen. För varje hörn i , lokaliserar vi den första hörn som kan nås av , och den sista hörn i den når till . Det vill säga, vi tittar på hur tidigt vi kan komma ifrån , och hur långt vi kan stanna kvar och fortfarande komma tillbaka till . Denna information lagras med varje . Sedan för varje par av hörn och , kan nå via om ansluter till tidigare än ansluter från . ${\ displaystyle Q \ i S}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle G_ {i}}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle w}$ ${\ displaystyle u}$ ${\ displaystyle w}$ ${\ displaystyle Q}$ ${\ displaystyle u}$ ${\ displaystyle Q}$ ${\ displaystyle w}$ ${\ displaystyle Q}$

Varje hörn är märkt som ovan för varje steg i rekursionen som bygger . Eftersom denna rekursion har logaritmiskt djup lagras totalt extra information per toppunkt. Från denna punkt är en logaritmisk tidsfråga för tillgänglighet lika enkel som att titta över varje etikettpar för en gemensam, lämplig . Det ursprungliga papperet arbetar sedan med att ställa in frågetiden till . ${\ displaystyle G_ {0} \ ldots, G_ {k}}$ ${\ displaystyle O (\ log {n})}$ ${\ displaystyle Q}$ ${\ displaystyle O (1)}$

För att sammanfatta analysen av denna metod, först betrakta att skiktning tillvägagångssätt skiljer hörnen så att varje hörn anses bara gånger. Algoritmens separatorfas bryter grafen till komponenter som högst är storleken på det ursprungliga diagrammet, vilket resulterar i ett logaritmiskt rekursionsdjup. På varje nivå av rekursionen behövs endast linjärt arbete för att identifiera separatorerna såväl som möjliga kopplingar mellan hörn. Det övergripande resultatet är förbehandlingstid med endast ytterligare information lagrad för varje toppunkt. ${\ displaystyle O (1)}$ ${\ displaystyle 1/2}$ ${\ displaystyle O (n \ log n)}$ ${\ displaystyle O (\ log {n})}$

Kamedas algoritm

En lämplig digraph för Kamedas metod med och tillsatt.

{\ displaystyle s}

{\ displaystyle t}

Samma graf som ovan efter att Kamedas algoritm har körts och visar DFS -etiketterna för varje toppunkt

En ännu snabbare metod för förbehandling, på grund av T. Kameda 1975, kan användas om grafen är plan , acyklisk och även uppvisar följande ytterligare egenskaper: alla 0- oavgränsade och alla 0-utgrader hörn visas på samma ansikte (antas ofta vara det yttre ansiktet), och det är möjligt att dela gränsen för det ansiktet i två delar så att alla 0-hängiga hörn visas på ena delen och alla 0-utegrads hörn visas på den andra (dvs. två typer av hörn växlar inte).

Om uppvisar dessa egenskaper kan vi förbehandla grafen på bara tid och lagra endast extra bitar per toppunkt, svara på tillgänglighetsfrågor för alla hörnpar i tid med en enkel jämförelse. ${\ displaystyle G}$ ${\ displaystyle O (n)}$ ${\ displaystyle O (\ log {n})}$ ${\ displaystyle O (1)}$

Förbehandlingen utför följande steg. Vi lägger till en ny toppunkt som har en kant till varje 0-oavgränsad hörnpunkt, och en annan ny hörnpunkt med kanter från varje 0-utegrad-toppunkt. Observera att egenskaperna tillåter oss att göra det samtidigt som vi behåller planariteten, det vill säga att det fortfarande inte kommer att finnas några kantkorsningar efter dessa tillägg. För varje toppunkt lagrar vi listan över adjacenser (utkanter) i ordning efter diagrammets planitet (till exempel medurs med avseende på grafens inbäddning). Vi initierar sedan en räknare och börjar en djup-första genomgång från . Under denna traversal besöks adjacenslistan för varje toppunkt från vänster till höger efter behov. När hörnen dyker upp från traversalens stapel, märks de med värdet och minskas sedan. Observera att det alltid är märkt med värdet och alltid är märkt med . Den första djupgående genomgången upprepas sedan, men den här gången besöks adjacenslistan för varje hörn från höger till vänster. ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle G}$ ${\ displaystyle i = n+1}$ ${\ displaystyle s}$ ${\ displaystyle i}$ ${\ displaystyle i}$ ${\ displaystyle t}$ ${\ displaystyle n+1}$ ${\ displaystyle s}$ ${\ displaystyle 0}$

När de är klara, och , och deras infallande kanter, tas bort. Varje kvarvarande hörn lagrar en 2-dimensionell etikett med värden från till . Med tanke på två hörn och och deras etiketter och vi säger att om och endast om , och det finns åtminstone en komponent eller som är strikt mindre än eller respektive. ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle 1}$ ${\ displaystyle n}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle L (u) = (a_ {1}, a_ {2})}$ ${\ displaystyle L (v) = (b_ {1}, b_ {2})}$ ${\ displaystyle L (u) <L (v)}$ ${\ displaystyle a_ {1} \ leq b_ {1}}$ ${\ displaystyle a_ {2} \ leq b_ {2}}$ ${\ displaystyle a_ {1}}$ ${\ displaystyle a_ {2}}$ ${\ displaystyle b_ {1}}$ ${\ displaystyle b_ {2}}$

Huvudresultatet av denna metod anger sedan att den kan nås från om och bara om , vilket enkelt kan beräknas i tid. ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle L (u) <L (v)}$ ${\ displaystyle O (1)}$

Relaterade problem

Ett relaterat problem är att lösa tillgänglighetsfrågor med ett antal vertexfel. Till exempel: "Kan vertex fortfarande nå toppunkt trots att hörn har misslyckats och inte längre kan användas?" Ett liknande problem kan överväga kantfel snarare än toppunktsfel eller en blandning av de två. Den bredaste första söktekniken fungerar lika bra på sådana frågor, men att konstruera ett effektivt orakel är mer utmanande. ${\ displaystyle k}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle s_ {1}, s_ {2}, ..., s_ {k}}$

Ett annat problem relaterat till tillgänglighetsfrågor är att snabbt omberäkna ändringar i tillgänglighetsrelationer när någon del av diagrammet ändras. Till exempel är detta en relevant fråga för sophämtning som måste balansera återvinningen av minnet (så att det kan omfördelas) med prestandaproblemen för den körande applikationen.

Languages

In other projects