Kruskal algoritme - bygging av en optimal rammeverk

I begynnelsen av det 19. århundre geometer Jakob Steiner fra Berlin sette oppgaven med hvordan du kobler tre landsbyer slik at deres lengde var den korteste. Senere, han oppsummerte problemet: det er nødvendig for å finne et punkt i et fly, avstand fra det å n andre poeng var det laveste. I det 20. århundre, fortsetter det å jobbe med dette temaet. Det ble besluttet å ta noen poeng, og koble dem på en slik måte at avstanden mellom dem var den korteste. Alt dette er et spesielt tilfelle av problemet som studeres.

"Grådig" algoritme

Kruskal algoritme refererer til "grådig" algoritme (også kalt gradient). Essensen av dem - den høyeste gevinsten på hvert trinn. Ikke alltid, "grådige" algoritmer gi den beste løsningen på problemet. Det er en teori, som viser at i tilknyttet spesifikke oppgaver de gir en optimal løsning. Dette er teorien om matroids. Kruskal algoritme refererer til slike problemer.

Finne en minimum slaktevekt

Vist algoritme konstruerer en optimal bildenummer. Problemet med det er som følger. Dan-rettet grafe uten parallelle kanter og løkker, og settet av kantene er gitt vektfunksjonen w, som tildeler det nummer til hver kant e - vekt rib - w (e). Vekten av hver delmengde av flertallet av ribber er summen av vektene av dens kanter. Kreves for å finne skjelettet av en liten vekt.

beskrivelse

Kruskal algoritme fungerer. For det første er alle kanter av den første grafen ordnet i stigende rekkefølge av vektene. I utgangspunktet betyr rammen inneholder ingen ribber, men omfatter alle hjørnene. Etter det neste trinn i algoritmen til den allerede konstruerte del av skrotten, som er et spenner over skog, er en kant tilsatt. Det er ikke tilfeldig valgt. Alle kantene på grafen, som ikke hører til rammen, kan kalles rød og grønn. Toppen av hver røde kanter er i samme komponent under bygging skogen tilkobling, og de grønne topper - annerledes. Derfor, hvis du legger til den røde kanten, det er en syklus, og hvis den grønne - som mottas etter dette trinnet de tre koblet komponentene vil være mindre enn én. Dermed kan den resulterende byggingen ikke legge noen rød kant, men noen grønn kant kan legges for å få skogen. Og legger til en grønn kant med minimal vekt. Resultatet er et rammeverk med minimal vekt.

implementering

Betegne strøm skogen F. Det skiller settet med toppunkter i feltet av tilkoblings (deres forening formene F, og de er disjunkte). På begge sider av den røde toppunkter ligger de i ett stykke. En del (x) - funksjonen som for hver node x returnerer en del av navnet, tilhører den x. Forene (x, y) - en fremgangsmåte som bygger en ny partisjon, som består av å kombinere delene av x og y, og alle de andre delene. La n - antall kanter. Alle disse begrepene er inkludert i Kruskal algoritme. gjennomføring:

1. Ordne alle kanter av diagrammet fra den første til n-te stigende vekter. (Ai, bi - jeg med spiss kant nummer).

2. for i = 1 til n gjøre.

3. x: = Del (AI).

4. y: = Part (bi).

5. Hvis x er ikke lik y deretter forene (x, y), for å inkludere med kanten F i nummer.

korrekthet

La T - ramme av den opprinnelige diagrammet som er konstruert ved bruk av Kruskal-algoritmen og S - dens vilkårlig ramme. Vi må bevise at w (T) er ikke større enn w (S).

La M - flerhet av ribber S, P - et antall finner T. Hvis S ikke er lik T, så er det en ramme ribbe et T, som ikke hører til S. S. et henger sammen syklusen, er det som kalles C. C fjernes fra eventuelle kant es, tilhørighet S. Vi får en ny ramme, fordi kantene og hjørnene er det samme. Dens vekt ikke er større enn w (S), siden w (ET) ikke lenger w (r) i en kraft Kruskal-algoritme. Denne operasjon (substitutt T S ribber på ribbene) vil bli gjentatt så lenge som mottar T. Vekten av hver påfølgende mottatt ramme er ikke større enn den foregående vekt, noe som innebærer at w (t) ikke er større enn w (S).

Robustheten Kruskal algoritme følger av teorem av Rado-Edmonds på matroids.

Applikasjonseksempler Kruskal algoritmen

Dan graf med nodene a, b, c, d, e og ribber (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Vektene av kantene er vist i tabellen, og i figuren. I utgangspunktet inneholder konstruksjon skogen F alle punktene av grafen og inneholder ingen ribbeina. Algoritme Kruskal først legge ribbe (a, e), siden vekten hadde den laveste, og punktene A og E i ulike komponenter tømmer tilkobling F (rib (a, e) er grønt), deretter ribben (c, d), fordi at i det minste denne kant vekt på diagram kanter, som ikke hører til F, og det er grønt, da de samme grunner påløper kant (a, b). Men kanten (b, e) er passert, selv om han og minimumsvekten av de resterende kanter, fordi det er rødt: punktene b og e tilhører samme del av skogen tilkobling F, er at dersom vi legger til F kanten (b, e), er dannet syklus. Deretter tilsettes grønn kant (b, c), føres rød kant (c, e), og deretter d, e. Således er kantene tilsatt i rekkefølge (a, e), (c, d), (a, b), (b, c). Fra nihera optimal ramme og består av den opprinnelige grafen. Så i dette tilfellet virker det en algoritme Kruskal. Et eksempel er vist.

Figuren viser en grafisk fremstilling, som består av to sammenkoblede komponenter. De tykke linjer angir de optimale ramme ribbene (grønn) som er konstruert ved bruk av Kruskal-algoritmen.

Det øverste bildet viser den opprinnelige grafen, og bunnen - et skjelett av minimal vekt, bygget for ham ved hjelp av algoritmen.

Sekvensen av de tilsatte ribbene (1,6); (0,3), (2,6) eller (2,6), (0,3) - er ikke viktig; (3,4); (0,1), (1,6) eller (1,6), (0,1), også vare (5,6).

Kruskal algoritme finner praktisk anvendelse, for eksempel, for å optimalisere paknings kommunikasjon, veier i nye bolig lokaliteter i hvert land, så vel som i andre tilfeller.