Tidligere 19. århundrede Berlin geometer Jacob Steinersæt opgaven med, hvordan man forbinder tre landsbyer, så deres længde blev kortest. Derefter generaliserede han dette problem: det er nødvendigt at finde et punkt på flyet, så afstanden fra det til n andre punkter er den mindste. I det 20. århundrede fortsatte arbejdet med dette emne. Det blev besluttet at tage flere punkter og forbinde dem på en sådan måde, at afstanden mellem dem var den korteste. Alt dette er et specielt tilfælde af det undersøgte problem.
Grådige algoritmer
Kruskals algoritme tilhører de "grådige" algoritmer(de kaldes også gradient). Essensen af disse er den største gevinst ved hvert trin. Ikke altid "grådige" algoritmer giver den bedste løsning på problemet. Der er en teori, der viser, at når de anvendes til specifikke problemer, giver de en optimal løsning. Dette er teorien om matroider. Kruskals algoritme henviser til sådanne problemer.
At finde den mindste vægtramme
Den betragtede algoritme konstruerer det optimalewireframe graf. Problemet med det er som følger. Du får en ikke-rettet graf uden flere kanter og sløjfer, og på sættet med kanter gives en vægtfunktion w, som tildeler hver kant e et tal - kantens vægt - w (e). Vægten af hver delmængde fra kantsættet bestemmes af summen af vægten af dets kanter. Det er nødvendigt at finde rammen med den mindste vægt.
beskrivelse
Kruskals algoritme fungerer sådan.For det første er alle kanterne på den originale graf arrangeret i stigende rækkefølge efter vægte. Oprindeligt indeholder skelettet ingen kanter, men inkluderer alle hjørnerne i grafen. Efter det næste trin i algoritmen tilføjes en kant til den allerede konstruerede del af skeletet, som er en spændende skov. Det er ikke tilfældigt valgt. Alle kanter af grafen, der ikke hører til trådrammen, kan kaldes rød og grøn. Højdepunkterne på hver røde kant er i en tilsluttet komponent i skoven under opførelse, og hjørnerne på den grønne kant er i forskellige. Derfor, hvis vi tilføjer en rød kant der, vises en cyklus, og hvis den er grøn, vil tilslutningskomponenten i skoven opnået efter dette trin være en mindre. Således kan ingen rød kant føjes til den resulterende konstruktion, men enhver grøn kant kan tilføjes for at skabe en skov. Og en grøn kant med minimumsvægt tilføjes. Resultatet er den letteste ramme.
implementering
Lad os betegne den nuværende skov F.Det opdeler sættet af hjørner i grafen i forbundne områder (deres foreningsformularer F, og de krydser ikke parvis). De røde kanter har begge hjørner i samme del. Del (x) er en funktion, der for hvert toppunkt x returnerer navnet på den del, som x hører til. Unite (x, y) er en procedure, der bygger en ny partition, der består af foreningen af x- og y-delene og alle andre dele. Lad n være antallet af kanter i grafen. Alle disse begreber er inkluderet i Kruskals algoritme. Implementering:
Ordne alle kanter af grafen fra 1. til n. I stigende rækkefølge af vægte. (ai, bi er hjørnerne på kanten i).
for i = 1 til n do.
x: = del (ai).
y: = del (bi).
Hvis x ikke er lig med y, skal du forene (x, y), inkludere kant i i F.
Korrekthed
Lad T være skeletet til den oprindelige graf konstrueret ved hjælp af Kruskal-algoritmen, og S dens vilkårlige skelet. Vi er nødt til at bevise, at w (T) ikke overstiger w (S).
Lad M være kantsættet S, P være kantsættetT. Hvis S ikke er lig med T, så er der en kant et af rammen T, der ikke hører til S. Lad os slutte os til et til S. Der dannes en cyklus, lad os kalde den C. Vi fjerner fra C enhver kant, der tilhører S. Vi får en ny ramme, fordi kanterne, og der er lige så mange toppe i den. Dens vægt overstiger ikke w (S), da w (et) højst er w (e) i kraft af Kruskals algoritme. Vi gentager denne operation (udskiftning af kanterne S med kanterne T), indtil vi får T. Vægten af hver efterfølgende resulterende ramme er ikke større end vægten af den forrige, hvorfra det følger, at w (T) ikke er større end w (S).
Korrektheden af Kruskals algoritme følger også af Rado-Edmonds sætning på matroider.
Eksempler på brug af Kruskal-algoritmen
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). Ribvægte er vist i tabellen og figuren. Oprindeligt indeholder skoven F under opførelse alle hjørnerne i grafen og indeholder ingen kanter. Kruskals algoritme tilføjer først kanten (a, e), da den har den mindste vægt, og hjørnerne a og e er i forskellige tilsluttede komponenter i skoven F (kanten (a, e) er grøn), så er kanten (c, d) derfor at denne kant har den mindste vægt af kanterne på grafen, der ikke hører til F, og den er grøn, så tilføjes kanten (a, b) af de samme grunde. Men kanten (b, e) springes over, selvom den har den mindste vægt af de resterende kanter, fordi den er rød: hjørnerne b og e hører til den samme tilsluttede komponent i skoven F, dvs. hvis vi tilføjer en kant (b, e) til F, cyklus. Derefter tilføjes en grøn kant (b, c), en rød kant (c, e) springes over, og derefter d, e. Således tilføjes kanterne (a, e), (c, d), (a, b), (b, c) sekventielt. Det optimale skelet i den oprindelige graf består af dem. Sådan fungerer algoritmen i dette tilfælde Malet. Et eksempel har vist dette.
Figuren viser en graf bestående af to tilsluttede komponenter. De dristige linjer viser kanterne på den optimale trådramme (grøn) konstrueret ved hjælp af Kruskal-algoritmen.
Den øverste figur viser den originale graf, og den nederste viser den mindste vægt, der er konstrueret til det ved hjælp af den betragtede algoritme.
Sekvensen af tilføjede kanter: (1,6); (0.3), (2.6) eller (2.6), (0.3) - betyder ikke noget; (3.4); (0,1), (1,6) eller (1,6), (0,1) er ligeglad (5,6).
Kruskals algoritme finder praktisk anvendelse, for eksempel til at optimere kommunikation, veje i nye kvarterer i bosættelser i hvert land og også i andre tilfælde.
