Omvänd raderingsalgoritm

Algoritmen för tillbakaradering  är en algoritm i grafteori som används för att erhålla ett minsta spännträd från en given ansluten linjeviktad graf . Algoritmen dök först upp i Kruskals tidning [1] , men bör inte förväxlas med Kruskals algoritm , som förekom i samma tidning. Om grafen inte är ansluten, kommer denna algoritm att hitta det minsta spännträdet för varje enskild del av grafen. Uppsättningen av dessa minimumspännande träd kallas den minsta spännande skogen, som innehåller alla hörn i grafen.

Algoritmen är en girig algoritm som ger den bästa lösningen. Det är motsatsen till Kruskals algoritm , som är en annan girig algoritm för minsta spännträd. Kruskals algoritm utgår från en tom graf och lägger till kanter, medan den omvända raderingsalgoritmen startar från den ursprungliga grafen och tar bort kanter från den. Algoritmen fungerar så här:

Pseudokod

1 funktion ReverseDelete(kanter[] E ) 2 sortera E i fallande ordning 3 Bestäm indexet i ← 0 4 medan i < storlek ( E ) 5 Definiera en kant ← E [ i ] 6 ta bort E [ i ] 7 om grafen inte är ansluten 8 E [ i ] ← kant 9 i ← i + 1 10 returkanter [] E

Exempel

I följande exempel söks de gröna kanterna av algoritmen och de röda kanterna tas bort av algoritmen.

Detta är den ursprungliga grafen. Siffrorna bredvid kanterna reflekterar vikten av kanterna.
Algoritmen börjar med kanten med maximal vikt, i detta fall kanten DE med vikt 15. Eftersom borttagning av kanten DE inte resulterar i en bortkopplad graf tas kanten bort.
Den näst tyngsta kanten är FG , så algoritmen kommer att kontrollera om borttagning av kanten skulle leda till frånkoppling. Eftersom borttagning av en kant inte gör att grafen kopplas bort, tas kanten bort.
Den näst tyngsta kanten är BD , så algoritmen kontrollerar om kanten skulle kopplas bort och ta bort kanten.
Nästa kant att kontrollera är EG , som inte kan tas bort, eftersom detta kommer att leda till separering av vertex G från grafen. Därför är nästa kant att ta bort BC .
Den näst tyngsta kanten är EF , så algoritmen kommer att kontrollera denna kant och ta bort den.
Algoritmen tittar igenom de återstående kanterna och hittar ingen lämplig för borttagning, så detta är den sista grafen som algoritmen returnerar.

Öppettider

Det kan visas att algoritmen går i tid ( "O" är stor och "o" är liten ), där E  är antalet kanter och V  är antalet hörn. Denna gräns nås enligt följande:

Bevis på riktighet

Det rekommenderas att läsa beviset för Kruskals algoritm först .

Beviset består av två delar. För det första är det bevisat att kanterna som finns kvar efter att ha kört algoritmen har formen av ett spännträd. Då är det bevisat att detta spännträd har en optimal vikt.

Spännande träd

Den återstående subgrafen (g) som erhålls av algoritmen är kopplad, eftersom algoritmen kontrollerar detta på rad 7. Subgrafen kan inte innehålla en cykel, eftersom du annars, när du rör dig längs cykeln, kan hitta kanten med den största vikten och ta bort den. Då måste g vara ett spännträd i huvudgrafen G.

Minimalitet

Vi kommer att visa genom induktion att följande påstående P är sant: Om F är uppsättningen av kanter som finns kvar i slutet av cykeln, så finns det något minsta spännträd som (dess kanter) är en delmängd av F .

  1. Det är tydligt att P exekveras innan while -loopen börjar . Eftersom en viktad sammankopplad graf alltid har ett minsta spännträd, och eftersom F innehåller alla grafens kanter, måste detta minsta spännträd vara en delmängd av F.
  2. Antag nu att P är sant för någon mellankantmängd F och låt T vara det minsta spännträdet som finns i F . Vi måste visa att efter borttagandet av kanten e i algoritmen finns det något (möjligen olika) spännträd T' som är en delmängd av F .
    1. om nästa borttagna kant e inte tillhör T, då är T=T' en delmängd av F och P är uppfylld.
    2. annars, om kanten e tillhör i.förstörsT: observera först att algoritmen bara tar bort kanter som inte gör att anslutningen av F Antag att e bryter ner T i subgraferna t1 och t2. Eftersom hela grafen förblir sammankopplad efter att e tagits bort måste det finnas en väg mellan t1 och t2 (annat än e ), så det måste finnas en cykel C i F (innan e tas bort ). Nu måste vi ha ytterligare en kant i denna cykel (låt det vara f) som inte tillhör T utan är i F (för om alla cykelns kanter var i trädet T skulle det inte vara ett träd). Vi hävdar nu att T' = T - e + f är ett minimumspännande träd som är en delmängd av F.
    3. Vi bevisar först att T' är ett spännträd . Vi vet att ta bort en kant i ett träd och lägga till ytterligare en kant inte skapar en cykel och vi får ett annat träd med samma hörn. Eftersom T var ett spännträd måste T' också vara ett spännträd . Att sedan lägga till "f" skapar ingen cykel, eftersom "e" tas bort (observera att trädet T innehåller alla hörn i grafen).
    4. Vi bevisar då att T' är ett minimumspännande träd. Vi har tre fall för kanterna "e" och "f" definierade av viktfunktionen wt.
      1. Fallet wt(f) < wt(e), vilket är omöjligt eftersom det antyder att vikten av T' är strikt mindre än T. Eftersom T är ett minsta spännträd är detta helt enkelt inte möjligt.
      2. Fallet är wt(f) > wt(e), vilket är omöjligt eftersom när vi korsar kanterna i fallande viktordning bör vi se "f" först. Eftersom vi har C, leder inte borttagning av "f" till frånkoppling i F, så algoritmen måste ta bort en kant från F tidigare. Det vill säga "f" tillhör inte F, vilket är omöjligt (vi bevisade att f gör det i steg 4).
      3. Fall wt(f) = wt(e), så T' är ett minsta spännträd, så återigen P är uppfyllt.
  3. Så P exekveras efter att slingan slutar (d.v.s. efter att alla kanter har tittats på) och vi har bevisat att F i slutet blir ett spännträd och vi vet att F har ett minsta spännträd som en delmängd, så F måste själv vara ett minimum spännträd .

Se även

Anteckningar

  1. ↑ Kruskal, 1956 .
  2. ↑ Thorup, 2000 .

Länkar