Kruskal algoritme - opførelse af en optimal ramme

I begyndelsen af det 19. århundrede geometer Jakob Steiner fra Berlin sæt opgaven med hvordan man kan forbinde tre landsbyer, så deres længde var kortest. Senere, han sammenfattet problemet: det er nødvendigt at finde et punkt i et plan, at afstanden fra det til n andre punkter var lavest. I det 20. århundrede, det fortsætter med at arbejde om dette emne. Det blev besluttet at tage et par punkter og forbinde dem på en sådan måde, at afstanden mellem dem var den korteste. Alt dette er et særligt tilfælde af problemet ved at blive undersøgt.

"Greedy" algoritme

Kruskal algoritme henviser til "grådige" algoritme (også kaldet gradient). Essensen af dem - den højeste gevinst på hvert trin. Ikke altid, "grådige" algoritmer giver den bedste løsning på problemet. Der er en teori, der viser, at i deres anvendelse på specifikke opgaver de giver den optimale løsning. Dette er teorien om matroider. Kruskal algoritme henviser til sådanne problemer.

At finde et minimum slagtevægt

Vist algoritme konstruerer en optimal ramme tæller. Problemet med det er, som følger. Dan ikke-styrede graf uden parallelle kanter og sløjfer, og sættet af kanter får vægtfunktion w, der tildeler nummeret til hver kant e - vægt ribben - w (e). Vægten af hver delmængde af flerheden af ribber er summen af vægten af dens kanter. Nødvendig for at finde skelettet af en lille vægt.

beskrivelse

Kruskal algoritme fungerer. Først bliver alle kanter af det oprindelige graf arrangeret i stigende rækkefølge af vægtene. I første omgang betyder rammen indeholder ingen ribben, men omfatter alle knuder. Efter det næste trin i algoritmen til den allerede konstruerede del af slagtekroppen, som er en spænder skov, tilføjes en kant. Det er ikke vilkårligt valgt. Alle kanterne af grafen, der ikke tilhører rammen, kan kaldes rød og grøn. Toppen af hver røde kanter er i samme komponent under opførelse skov-forbindelse, og de grønne toppe - anderledes. Derfor, hvis du føjer til den røde kant, der er en cyklus, og hvis det grønne - som modtages efter dette trin træ tilsluttet komponenter vil være mindre end én. Således kan den resulterende konstruktion ikke tilføje nogen rød kant, men enhver grøn kant kan tilføjes for at få skoven. Og tilføjer en grøn kant med minimal vægt. Resultatet er en ramme på minimum vægt.

implementering

Angiver det pågældende skov F. Det opdeler sæt af knudepunkter inden for tilslutningsmuligheder (deres union formularer F, og de er disjunkte). På begge kanter af de røde knuder de ligger i et stykke. Del (x) - funktionen, som for hver top x returnerer en del af navnet, det tilhører x. Unite (x, y) - en procedure, der bygger en ny partition, der består af at kombinere dele af x og y og alle de andre dele. Lad n - antal kanter. Alle disse begreber er inkluderet i Kruskal algoritme. Implementering:

1. Arrangere alle kanterne af grafen fra 1. til n-th opstigende vægte. (Ai, bi - i med spidsen kant nummer).

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

3. x: = Del (ai).

4. y: = Del (bi).

5. Hvis x ikke er lig med y derefter Unite (x, y), til at omfatte med kanten Fj nummer.

korrekthed

Lad T - ramme af den oprindelige graf konstrueret under anvendelse af Kruskal-algoritmen og S - dets vilkårlige ramme. Vi skal bevise, at w (T) ikke er større end w (S).

Lad M - flerhed af finner S, P - en flerhed af finner T. Hvis S ikke er lig med T, så er der en ramme ribbe et T, som ikke tilhører S. S. et støder cyklussen, kaldes det C. C fjerne fra enhver kant es, der tilhører S. Vi får en ny ramme, fordi de kanter og hjørner er den samme. Dens vægt ikke er større end w (S), idet w (et) ikke længere w (r) i en strøm Kruskal algoritme. Denne operation (substitutionsprodukter T S ribber på ribben) vil blive gentaget så længe modtage T. Vægten af hver efterfølgende modtagne ramme ikke er større end den foregående vægt, hvilket indebærer, at w (T) ikke er større end w (S).

Robustheden af Kruskal algoritme følger af sætning af Rado-Edmonds på matroider.

Anvendelseseksempler Kruskal algoritme

Dan graf med knudepunkter a, b, c, d, e og ribber (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Vægten af kanter er vist i tabellen og i figuren. I første omgang, byggeri skov F indeholder alle knuder i grafen og indeholder ingen ribben. Algoritme Kruskal først tilføje ribben (a, e), da vægten havde den laveste, og de hjørner en og e er i forskellige komponenter tømmer tilslutningsmuligheder F (ribben (a, e) er grøn), så ribben (c, d), fordi at i det mindste denne kant vægt af grafens kanter, der ikke tilhører F, og det er grøn, af de samme grunde tilfalder kant (a, b). Men kanten (b, e) er passeret, selv om han og den mindste vægt af de resterende kanter, fordi den er rød: de hjørner B og E tilhører samme komponent i skov tilslutningsmuligheder F, det vil sige, hvis vi tilføjer til F kanten (B, E), der dannes cyklus. Så tilføjede grøn kant (b, c), er gået rød kant (c, e), og derefter d, e. Således er kanter successivt tilsat (a, e), (c, d), (a, b), (b, c). Fra nihera optimal ramme og består af den oprindelige graf. Så i dette tilfælde er det driver en algoritme Kruskal. Et eksempel er vist.

Figuren viser en graf, som består af to tilsluttede komponenter. De fede linjer angiver de optimale spanterne (grøn) konstrueret under anvendelse af Kruskal-algoritmen.

Det øverste billede viser den oprindelige graf, og bunden - et skelet af minimal vægt, bygget til ham ved hjælp af algoritmen.

Sekvensen af de tilsatte ribber (1.6); (0,3), (2,6) eller (2,6), (0,3) - er ikke vigtigt; (3,4); (0,1), (1,6) eller (1,6), (0,1), også pleje (5,6).

Kruskal algoritme finder praktisk anvendelse, for eksempel til at optimere pakningen kommunikation, veje i nye boligområder lokaliteter i de enkelte lande, samt i andre tilfælde.