Omvendt sletningsalgoritme

Tilbagesletningsalgoritmen  er en algoritme i grafteori , der bruges til at opnå et minimumspændingstræ fra en given forbundet linjevægtet graf . Algoritmen dukkede først op i Kruskals papir [1] , men må ikke forveksles med Kruskals algoritme , som dukkede op i samme papir. Hvis grafen ikke er forbundet, vil denne algoritme finde minimumspændingstræet for hver enkelt del af grafen. Sættet af disse minimumspændende træer kaldes minimumspændende skov, som indeholder alle hjørnerne af grafen.

Algoritmen er en grådig algoritme , der giver den bedste løsning. Det er det modsatte af Kruskals algoritme , som er en anden grådig minimumspændende træ-algoritme. Kruskals algoritme starter fra en tom graf og tilføjer kanter, mens den omvendte sletningsalgoritme starter fra den originale graf og fjerner kanter fra den. Algoritmen fungerer således:

Pseudokode

1 funktion ReverseDelete(kanter[] E ) 2 sorter E i faldende rækkefølge 3 Bestem indekset i ← 0 4 mens i < størrelse ( E ) 5 Definer en kant ← E [ i ] 6 fjern E [ i ] 7 , hvis grafen ikke er forbundet 8 E [ i ] ← kant 9 i ← i + 1 10 returkanter [] E

Eksempel

I det følgende eksempel søges de grønne kanter af algoritmen, og de røde kanter fjernes af algoritmen.

Dette er den originale graf. Tallene ved siden af ​​kanterne afspejler vægten af ​​kanterne.
Algoritmen starter med kanten med den maksimale vægt, i dette tilfælde kanten DE med vægten 15. Da fjernelse af kanten DE ikke resulterer i en afbrudt graf, fjernes kanten.
Den næste tungeste kant er FG , så algoritmen vil kontrollere, om fjernelse af kanten vil føre til afbrydelse af forbindelsen. Da fjernelse af en kant ikke gør grafen afbrudt, fjernes kanten.
Den næsttyngste kant er BD , så algoritmen kontrollerer, om fjernelse af kanten ville få den frakoblet og fjerne kanten.
Den næste kant at kontrollere er EG , som ikke kan fjernes, da dette vil føre til adskillelse af toppunktet G fra grafen. Derfor er den næste kant, der skal fjernes, BC .
Den næste tungeste kant er EF , så algoritmen vil tjekke denne kant og fjerne den.
Algoritmen kigger gennem de resterende kanter og finder ikke nogen egnet til fjernelse, så dette er den endelige graf, som algoritmen returnerer.

Åbningstider

Det kan vises, at algoritmen kører i tid ( "O" er stor og "o" er lille ), hvor E  er antallet af kanter og V  er antallet af hjørner. Denne grænse nås som følger:

Bevis for rigtighed

Det anbefales at læse beviset for Kruskals algoritme først .

Beviset består af to dele. For det første er det bevist, at de kanter, der er tilbage efter at have kørt algoritmen, har form af et spændingstræ. Så er det bevist, at dette spændtræ har en optimal vægt.

Spændende træ

Den resterende undergraf (g) opnået af algoritmen er forbundet, da algoritmen kontrollerer dette i linje 7. Undergrafen kan ikke indeholde en cyklus, for ellers kan du, når du bevæger dig langs cyklussen, finde kanten med den største vægt og fjerne den. Så skal g være et spændingstræ i hovedgrafen G.

Minimalitet

Vi vil vise ved induktion, at følgende udsagn P er sandt: Hvis F er det sæt af kanter, der er tilbage i slutningen af ​​cyklussen, så er der et minimumsspændingstræ, der (dets kanter) er en delmængde af F .

  1. Det er tydeligt, at P udføres før starten af ​​while -løkken . Da en vægtet forbundet graf altid har et minimum spændingstræ, og da F indeholder alle grafens kanter, skal dette minimum spændingstræ være en delmængde af F.
  2. Antag nu, at P er sandt for et mellemkantsæt F , og lad T være det mindste spændingstræ, der er indeholdt i F . Vi skal vise, at der efter fjernelse af kanten e i algoritmen eksisterer et (muligvis anderledes) spændingstræ T', der er en delmængde af F .
    1. hvis den næste fjernede kant e ikke hører til T, så er T=T' en delmængde af F og P er opfyldt.
    2. ellers, hvis kanten e tilhører i.ødelæggesT: bemærk først, at algoritmen kun fjerner kanter, der ikke forårsager, at forbindelsen af ​​F Antag, at e dekomponerer T i undergrafer t1 og t2. Da hele grafen forbliver forbundet efter at e er fjernet, skal der være en sti mellem t1 og t2 (bortset fra e ), så der skal være en cyklus C i F (før e fjernes ). Nu skal vi have en anden kant i denne cyklus (lad det være f), som ikke hører til T, men er i F (for hvis alle cyklussens kanter var i træet T, ville det ikke være et træ). Vi hævder nu, at T' = T - e + f er et minimumspændende træ, der er en delmængde af F.
    3. Vi beviser først, at T' er et spændingstræ . Vi ved, at sletning af en kant i et træ og tilføjelse af endnu en kant ikke skaber en cyklus, og vi får et andet træ med de samme hjørner. Da T var et spændingstræ, må T' også være et spændingstræ . Tilføjelse af "f" skaber ikke nogen cyklus, da "e" er fjernet (bemærk, at træet T indeholder alle toppunkterne i grafen).
    4. Vi beviser derefter, at T' er et minimumspændende træ. Vi har tre tilfælde for kanterne "e" og "f" defineret af vægtfunktionen wt.
      1. Tilfældet wt(f) < wt(e), hvilket er umuligt, fordi det antyder, at vægten af ​​T' er strengt taget mindre end T. Da T er et minimumspændende træ, er dette simpelthen ikke muligt.
      2. Tilfældet er wt(f) > wt(e), hvilket er umuligt, fordi når vi krydser kanterne i faldende rækkefølge af vægte, bør vi se "f" først. Da vi har C, fører fjernelse af "f" ikke til afbrydelse i F, så algoritmen ville være nødt til at fjerne en kant fra F tidligere. Det vil sige, "f" hører ikke til F, hvilket er umuligt (det beviste vi, at f gør i trin 4).
      3. Tilfælde wt(f) = wt(e), så T' er et minimumspændingstræ , så igen P er opfyldt.
  3. Så P udføres efter løkken ender (dvs. efter at alle kanter er blevet set på), og vi har bevist, at i slutningen bliver F et spændingstræ, og vi ved, at F har et minimum spændingstræ som en delmængde, så F skal selv være et minimum spændingstræ .

Se også

Noter

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

Links