Grafalgoritmer: Dispositioner (fem eksamensspørgsmål) ***************************************************** Generelt -------- For hvert af de fem spørgsmål (numrene 6-10 i fortegnelsen på hjemmesiden) dækkende kursusafsnittet om grafalgoritmer bringes her forslag til en disposition svarende til en fremlæggelse af ca. 15-20 minutters varighed. Mere får de gode eksaminander sædvanligvis ikke, idet resten af den halve time da forløber med tillægsspørgsmål i hele pensum. Uanset det trukne spørgsmål bør der indledes med en kort præcisering af problemstillingen. Sædvanligvis sætter såvel censorer som eksaminatorer pris på at alle grafalgoritmer tager afsæt i et matematisk problem og at tiden ikke spildes med mere eller mindre eksotiske anvendelser af den pågældende model. 6. Strongly connected components ******************************** "En stærkt-sammenhængende komponent (SCC) af en orienteret graf er en delgraf induceret af maksimal delmængde af knuder således at der i delgrafen findes en vej mellem ethvert par af disse. For en given graf kan dens stærkt-sammenhængende komponenter findes ved to dybde-først søgninger (DFS), dels på grafen G, dels på den transponere- de graf G^T. Formålet er, at flere grafproblemer med fordel kan løses ved dekomponering af grafen i dens SCC'er.". Introducer d[u], f[u]. Håndkør et lille eksempel på DFS. Vis herunder hvordan kanter kan klassificeres (tree, back, forward, cross) og at slut- facit bliver en dybde-først skov samt f[u] for alle knuder. Fortsæt med eksemplet, nu DFS på den transponerede graf G^T og med startknuderne valgt efter aftagende f[u]. Knuderne i hvert træ i dybde- først skoven kan nu vises at inducere en SCC. Et centralt begreb i korrekthedsbeviset er den orienterede, acykliske komponentgraf. Redegør for hovedlinien i beviset. Argumenter for tidskompleksiteten theta(V+E). Vær bekendt med begrebet topologisk sortering som et andet eksempel på DFS. 7. Single-source shortest paths: Bellman-Ford's algorithm ********************************************************* "For en orienteret, vægtet graf ønskes bestemt en korteste vej fra en given knude til alle øvrige knuder". Introducer G=(V,E) repræsenteret ved nabolister. Introducer s, w (her: kantvægte kan være negative), delta(s,v). Korteste veje er simple -> højst |V|-1 kanter. Nævn optimal delstruktur; bevis behøves ikke. Introducer d[v], beskriv relaksation, herunder forgænger, forgængerdelgraf, korteste-veje træ. Bellman-Ford: ------------- Det er ikke nødvendigt at opskrive selve algoritmen (tager for lang tid), men håndkør et lille eksempel og fortæl herunder om initialisering, |V|-1 gennemløb med relaksering af alle kanter (rækkefølge underordnet), check for kredse med negativ vægt der kan nås fra s. Begrund tidskompleksiteten O(VE). Gennemfør det tredelte korrekthedsbevis: 1) ingen negative kredse kan nås fra s -> d[v]=delta(s,v) 2) stadig ingen negative kredse: 1) -> B-F returnerer TRUE 3) negative kredse kan nås fra s: -> B-F returnerer FALSE 8. Single-source shortest paths: Dijkstra's algorithm ***************************************************** "For en orienteret, vægtet graf ønskes bestemt en korteste vej fra en given knude til alle øvrige knuder". Introducer G=(V,E) repræsenteret ved nabolister. Introducer s, w (her: alle kantvægte er ikke-negative), delta(s,v). Korteste veje er simple -> højst |V|-1 kanter. Nævn optimal delstruktur; bevis behøves ikke. Introducer d[v], beskriv relaksation, herunder forgænger, forgængerdelgraf, korteste-veje træ. Dijkstra: --------- Det er ikke nødvendigt at opskrive selve algoritmen (tager for lang tid), men håndkør et lille eksempel og fortæl herunder om initialisering, kø af samtlige knuder styret af d[v] EXTRACT-MIN: relakser alle kanter der udgår fra den udtagne knude. Fortsæt indtil køen er tom: while-løkken gennemløbes således |V| gange og alle kanter relakseres netop 1 gang. Tidskompleksiteten bestemmes af implementeringen af prioritetskøen Q. Angiv denne for hver af de tre tilfælde (lineært array, binær hob, Fibo- nacci hob). Noter forbedringen, hvis G er tynd. Gennemfør korrekthedsbeviset. Det vanskelige punkt er ofte at indse at delta(s,y)=d[y]. Hvis tiden tillader: Dijkstra giver ikke nødvendigvis et ukorrekt svar selv om der er kanter med negative vægte. Illustrer evt. med lille eksem- pel (minimum 4 knuder og 4 kanter). 9. All-pairs shortest paths *************************** "For en orienteret, vægtet graf uden negative kredse ønskes bestemt en korteste vej fra enhver knude til alle øvrige knuder". Introducer G = (V,E) repræsenteret som en matrix. Forklar hvordan for- gængermatricen er organiseret. Resten handler om _dynamisk programmering_. Beskriv strukturen af en optimal løsning. Vis (kortfattet) den rekursive O(n^4) løsning og forbed- bedringen til O(n^3lgn) ved _repeated squaring_. Referer (til sammenlig- ning) til almindelig matrixmultiplikation. Vægten skal imidlertid lægges på _Floyd-Warshall_, som er den centrale del af spørgsmålet. Redegør nøje for den rekursive definition (udtryk (25.5)), "bottom up"-beregningen af delta(i,j) samt algoritmens sidelø- bende opdatering af forgængermatricen. Kend begrebet _transitiv afslutning_ (transitive closure) og redegør kort for den tilsvarende simplifikation af Floyd-Warshall. Hvis grafen ikke har negative vægte og er tilpas tynd, vil Dijkstra (implementeret med binære hobe eller Fibonaccihobe og anvendt med hver knude som kilde) være hurtigere end Floyd-Warshall. Selv en _maksimal plan_ graf med 3n-6 kanter er tyndere end "tilpas tynd". 10. Maximum flow **************** "Et flownetværk er en orienteret, vægtet og sammenhængende graf med de ikke-negative kantvægte opfattet som kapaciteter. Desuden er givet to forskellige knuder, s og t, som er hhv. kilde og terminal. Flow kan u- formelt beskrives som den hastighed, hvormed materiale under opfyldelse af visse betingelser kan transporteres mellem et knudepar. Værdien af flow er den totale udstrømning fra s. Max flow problemet er at finde et flow af maksimal værdi fra s til t.". Indfør G=(V,E), c(u,v); opskriv den formelle definition af flow (husk VxV) og |f|. Redefiner fx. |f| som eksempel på den implicitte sumnotation. Definer residualkapacitet, residualgraf, strømforøgende vej, snit, snit- kapacitet (husk at kanter orienteret fra T mod S _ikke_ bidrager til sidst- nævnte). Nævn Ford-Fulkersons metode/algoritme. Vær helt sikker på de tre ækvi- valente udsagn i Max-flow min-cut sætningen samt beviserne 1->2 (simpelt), 2->3 (det vigtigste) og 3->1 (også simpelt). Vær klar over at Ford-Fulkerson med kompleksiteten O(E|f*|) er _ekspo- nentiel_ (der skal fx. ca. 20 bits til at repræsentere 10^6) men ikke der- for nødvendigvis dårlig hvis |f*| er lille som fx. ved todelt parring (bi- partite matching). Beskriv Edmonds-Karp O(VE^2)-algoritme og hovedideerne i køretidsbevi- set: en kant kan blive kritisk højst O(V) gange og afstanden til s (målt i antal kanter) øges med mindst 2 pr. gang. Todelt parring kan formuleres og løses som et max-flow problem ved ud- videlse af den todelte graf til et flownetværk, hvor alle kanter har ka- paciteten 1. Pointen er, at |f(u,v)| vil være 0 eller 1. Det er næppe realistisk, at man kan nå at sige noget væsentligt om både Edmonds-Karp og push-relabel algoritmer. Vælger man at starte med sidst- nævnte, må man formelt definere preflow, excess flow, height function og eventuelt også admissible edge og admissible network som indledning til en beskrivelse af de to operationer (push, relabel). Køretiden for RELABEL- FRONT er O(V^3); korrekthedsbevis kræves ikke.