Tidlig 19. århundre Berlin geometer Jacob Steinersette oppgaven med å koble sammen tre landsbyer slik at lengden ble kortest. Deretter generaliserte han dette problemet: det kreves å finne et punkt på flyet slik at avstanden fra det til n andre punkter er den minste. I det 20. århundre fortsatte arbeidet med dette emnet. Det ble besluttet å ta flere punkter og koble dem på en slik måte at avstanden mellom dem var kortest. Alt dette er et spesielt tilfelle av problemet som studeres.
Grådige algoritmer
Kruskals algoritme tilhører de "grådige" algoritmene(de kalles også gradient). Essensen av disse er den største gevinsten på hvert trinn. Grådige algoritmer gir ikke alltid den beste løsningen på problemet. Det er en teori som viser at når de brukes på spesifikke problemer, gir de en optimal løsning. Dette er teorien om matroider. Kruskals algoritme tilhører slike problemer.
Finne minimum vekt ramme
Den vurderte algoritmen konstruerer det optimaletrådrammediagram. Problemet med det er som følger. Du får en ikke-rettet graf uten flere kanter og løkker, og på settet med kanter er det gitt en vektfunksjon w, som tildeler hver kant e et tall - kantens vekt - w (e). Vekten av hvert delmengde fra kantsettet bestemmes av summen av vekten av kantene. Det er nødvendig å finne rammen med den minste vekten.
beskrivelse
Kruskals algoritme fungerer slik.Først er alle kantene på den originale grafen ordnet i stigende rekkefølge etter vekter. Opprinnelig inneholder skjelettet ingen kanter, men inkluderer alle hjørnene i grafen. Etter neste trinn i algoritmen legges den ene kanten til den allerede konstruerte delen av skjelettet, som er en spennende skog. Det er ikke valgt vilkårlig. Alle kantene på grafen som ikke tilhører trådrammen kan kalles rød og grønn. Hjørnene til hver røde kant er i samme tilkoblingsdel av skogen under konstruksjon, og hjørnene til den grønne kanten er forskjellige. Derfor, hvis du legger til en rød kant der, vises en syklus, og hvis den er grønn, vil tilkoblingskomponenten i skogen oppnådd etter dette trinnet være en mindre. Dermed kan ingen rød kant legges til den resulterende konstruksjonen, men en hvilken som helst grønn kant kan legges til for å skape en skog. Og en grønn kant med minimal vekt tilsettes. Resultatet er den letteste rammen.
Gjennomføring
La oss betegne den nåværende skogen F.Det deler settet med hjørner i grafen i områder med tilkobling (deres foreningsformer F, og de krysser ikke parvis). De røde kantene har begge hjørner i samme del. Del (x) er en funksjon som for hvert toppunkt x returnerer navnet på delen som x tilhører. Unite (x, y) er en prosedyre som bygger en ny partisjon, som består av foreningen av x- og y-delene og alle andre deler. La n være antall kanter i grafen. Alle disse konseptene er inkludert i Kruskals algoritme. Gjennomføring:
Ordne alle kantene av grafen fra 1. til 9. i stigende rekkefølge av vekter. (ai, bi er kantene på kanten med tallet i).
for jeg = 1 til n gjør.
x: = Del (ai).
y: = Del (bi).
Hvis x ikke er lik y, forenes (x, y), inkluder kant i i F.
Korrekthet
La T være skjelettet til den opprinnelige grafen konstruert ved hjelp av Kruskal-algoritmen, og S dens vilkårlige skjelett. Vi må bevise at w (T) ikke overstiger w (S).
La M være settet med kanter S, P være sett med kanterT. Hvis S ikke er lik T, så er det en kant et av rammen T som ikke tilhører S. La oss bli med et til S. En syklus blir dannet, la oss kalle det C. Vi fjerner en kant fra C es tilhører S. Vi får en ny ramme, fordi kantene, og det er like mange topper i den. Dens vekt overstiger ikke w (S), siden w (et) maksimalt er w (e) i kraft av Kruskals algoritme. Vi vil gjenta denne operasjonen (erstatte kantene S med kantene T) til vi får T. Vekten til hver påfølgende resulterende ramme er ikke større enn vekten til den forrige, hvorfra det følger at w (T) ikke er større enn w (S).
Korrektheten til Kruskals algoritme følger også av Rado-Edmonds-teoremet på matroider.
Eksempler på anvendelse av Kruskal-algoritmen
Gitt en graf med hjørner a, b, c, d, e og kanter (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Ribbevekter er vist i tabellen og figuren. Opprinnelig inneholder skogen F under konstruksjon alle hjørnene i grafen og inneholder ingen kanter. Kruskals algoritme legger først til kanten (a, e), siden den har den minste vekten, og toppunktene a og e er i forskjellige sammenkoblede komponenter i skogen F (kanten (a, e) er grønn), deretter kanten ( c, d), derfor at denne kanten har minst vekt på kantene på grafen som ikke tilhører F, og den er grønn, så blir kanten (a, b) lagt til av samme grunner. Men kanten (b, e) hoppes over, selv om den har den minste vekten av de gjenværende kantene, fordi den er rød: toppunktene b og e tilhører den samme tilkoblede komponenten i skogen F, det vil si hvis vi legger til kanten (b, e) til F, får vi syklus. Deretter tilsettes en grønn kant (b, c), en rød kant (c, e) hoppes over, og deretter d, e. Dermed blir kantene (a, e), (c, d), (a, b), (b, c) tilsatt sekvensielt. Det optimale skjelettet til den opprinnelige grafen består av dem. Slik fungerer algoritmen i dette tilfellet Malt. Et eksempel har vist dette.
Figuren viser en graf som består av to tilkoblede komponenter. De dristige linjene viser kantene til den optimale trådrammen (grønn) konstruert ved hjelp av Kruskal-algoritmen.
Den øvre figuren viser den originale grafen, og den nedre viser rammeverket for minimumsvekt konstruert for den ved hjelp av den vurderte algoritmen.
Sekvensen av tilføyde kanter: (1,6); (0.3), (2.6) eller (2.6), (0.3) - betyr ikke noe; (3.4); (0.1), (1.6) eller (1.6), (0.1) er også likegyldig (5.6).
Kruskals algoritme finner praktisk anvendelse, for eksempel for å optimalisere kommunikasjon, veier i nye nabolag i bosetningene i hvert land, så vel som i andre tilfeller.
