5.3 Komponenter, 2-fargelegging og sykeldeteksjon

Prebetingelse: ingen. Postbetingelse: returverdien er antall
sammenhengende komponenter, og alle noder står med v.besokt = sant.

Procedure CountComponents(G)
  Input:  urettet graf G = (V, E) som nabolister
  Output: antall sammenhengende komponenter i G
  for hver node v i V:
      v.besokt = usant
  antall = 0
  for hver node v i V:
      if v.besokt er usant:
          antall = antall + 1
          DFSVisit(v)
  return antall

Procedure DFSVisit(v)
  v.besokt = sant
  for hver nabo u av v:
      if u.besokt er usant:
          DFSVisit(u)

Invarianten i én setning: etter at den ytre løkka har passert node $v$, er
alle noder i $v$-ens komponent markert som besøkt, og telleren er økt nøyaktig én
gang for den komponenten.

Kjøretid: $O(|V| + |E|)$. Initialiseringsløkka er $O(|V|)$. Den ytre løkka
går gjennom hver node én gang, men kaller DFSVisit bare for noder som ennå ikke
er besøkt — så på tvers av alle kallene besøkes hver node én gang og hver
kant ses på to ganger, én gang fra hver ende. Summen blir
$O(|V| + 2|E|)$, som forenkles til $O(|V| + |E|)$, der $|V|$ er antall noder og
$|E|$ antall kanter.

Merk hva den ytre løkka koster. Den er grunnen til at DFS-full er
$O(|V| + |E|)$ og ikke $O(|E|)$: også noder uten en eneste kant må innom. Å
oppgi $O(|E|)$ her er felle #6 — å forveksle DFS fra én node med DFS over
hele grafen.

Prebetingelse: ingen. Postbetingelse: returverdien er sant hvis og bare
hvis G er bipartitt. Er svaret sant, står hver node med en farge som er
motsatt av alle naboene sine.

Procedure TwoColor(G)
  Input:  urettet graf G = (V, E) som nabolister
  Output: sant hvis G er bipartitt, ellers usant
  for hver node v i V:
      v.farge = ingen
  for hver node s i V:
      if s.farge er ingen:
          s.farge = rod
          Ko = tom ko
          legg s bakerst i Ko
          while Ko er ikke tom:
              v = ta forrest ut av Ko
              for hver nabo u av v:
                  if u.farge er ingen:
                      u.farge = motsatt av v.farge
                      legg u bakerst i Ko
                  else if u.farge er lik v.farge:
                      return usant
  return sant

Grunnideen i én setning, og den er hele begrunnelsen: når startnoden først
har fått rødt, er hvert eneste senere fargevalg tvunget — en nabo av en rød
node kan bare bli blå — så finner algoritmen en konflikt, finnes det ingen gyldig
fargelegging i det hele tatt, ikke bare ingen som denne kjøringen fant.

Kjøretid: $O(|V| + |E|)$. Initialiseringen er $O(|V|)$; hver node legges i
køen høyst én gang, siden den får farge i samme øyeblikk, og hver kant ses på to
ganger — én gang fra hver ende.

Den ytre løkka over alle noder er ikke pynt. Uten den farger du bare
komponenten du startet i, og en ikke-bipartitt komponent lenger ute i grafen blir
aldri oppdaget.

En urettet graf er bipartitt hvis og bare hvis den ikke inneholder noen sykel
av oddetallslengde.

Hvorfor det er slik, i én setning hver vei. Går du rundt en sykel og veksler
farge for hvert steg, har du etter et partall steg samme farge som du startet
med — det går opp, og ringen kan farges. Etter et oddetall steg har du
motsatt farge av deg selv, og den siste kanten i sykelen forbinder to like
farger; det går ikke opp uansett hvor du begynner.

Slik brukes resultatet på eksamen. Det gir deg en øyeblikkelig test: finner
du en trekant, en femkant eller en hvilken som helst rundtur med et oddetall
kanter, er svaret «ikke bipartitt», og du trenger ikke kjøre algoritmen. Motsatt
er en graf uten sykel — et tre — alltid bipartitt.

Resultatet er kjent og kan brukes uten bevis; skisser gjerne argumentet over i én
setning, men bruk ikke eksamensminutter på mer enn det.

Prebetingelse: ingen. Postbetingelse: returverdien er sant hvis og bare
hvis G inneholder minst én sykel. Grafen er uendret.

Procedure HasCycle(G)
  Input:  urettet graf G = (V, E) som nabolister
  Output: sant hvis G inneholder minst en sykel, ellers usant
  for hver node v i V:
      v.besokt = usant
  for hver node v i V:
      if v.besokt er usant:
          if CycleVisit(v, ingen) er sant:
              return sant
  return usant

Procedure CycleVisit(v, forelder)
  v.besokt = sant
  for hver nabo u av v:
      if u.besokt er usant:
          if CycleVisit(u, v) er sant:
              return sant
      else if u er ulik forelder:
          return sant
  return usant

Invarianten i én setning: når CycleVisit(v, forelder) kalles, er v nådd
langs en sti fra en startnode, og hver besøkt nabo av v som ikke er
forelder, gir en andre vei tilbake til den stien — altså en sykel.

Kjøretid: $O(|V| + |E|)$. Hver node besøkes én gang, hver kant ses på to
ganger, og forelder-sammenligningen er $O(1)$.

Den ytre løkka er også her nødvendig. En sykel kan ligge i en komponent du
ikke startet i. Uten løkka over alle noder svarer algoritmen «ingen sykel» på en
graf som har én, bare et annet sted.

Avgrensning. Dette er sykeldeteksjon i urettede grafer. I en rettet graf
holder ikke forelder-regelen — der kan to noder peke på hverandre uten at det
utgjør en rundtur i vanlig forstand, og en besøkt node kan ligge i en helt annen
gren. Rettet sykeldeteksjon hører til Del 6, sammen med topologisk sortering, og
skal ikke brukes i dette kapitlet.