Det tidiga 1800-talets Berlingeometer Jacob Steinersatte uppgiften att koppla samman tre byar så att deras längd var som kortast. Därefter generaliserade han detta problem: det krävs att hitta en punkt på planet så att avståndet från det till n andra punkter är det minsta. Under 1900-talet fortsatte arbetet med detta ämne. Man beslutade att ta flera punkter och koppla ihop dem på ett sådant sätt att avståndet mellan dem var som kortast. Allt detta är ett specialfall av problemet som studeras.
giriga algoritmer
Kruskals algoritm tillhör de "giriga" algoritmerna(de kallas också gradient). Kärnan i dessa är den största vinsten vid varje steg. Giriga algoritmer ger inte alltid den bästa lösningen på problemet. Det finns en teori som visar att när de tillämpas på specifika problem ger de en optimal lösning. Detta är teorin om matroider. Kruskals algoritm hör till sådana problem.
Att hitta ram med lägsta vikt
Den övervägda algoritmen konstruerar det optimalawireframe graf. Problemet med det är som följer. Du får en oriktad graf utan flera kanter och slingor, och på uppsättningen av dess kanter ges en viktfunktion w, som tilldelar varje kant e ett nummer - kantens vikt - w (e). Vikten av varje delmängd från uppsättningen av kanter bestäms av summan av vikterna av dess kanter. Det krävs att man hittar ramen med den minsta vikten.
beskrivning
Kruskals algoritm fungerar så här.Först är alla kanter på den ursprungliga grafen ordnade i stigande viktordning. Inledningsvis innehåller skelettet inga kanter utan inkluderar alla hörn i grafen. Efter nästa steg i algoritmen läggs en kant till den redan konstruerade delen av skelettet, som är en spännskog. Det är inte vald godtyckligt. Alla kanter på grafen som inte hör till trådramen kan kallas röda och gröna. Topparna på varje röd kant är i samma anslutningskomponent i skogen som är under uppbyggnad, och spetsarna på den gröna kanten är i olika. Därför, om du lägger till en röd kant där, visas en cykel, och om den är grön kommer kopplingskomponenten i skogen som erhålls efter detta steg att vara en mindre. Således kan ingen röd kant läggas till den resulterande konstruktionen, utan vilken grön kant som helst kan läggas till för att skapa en skog. Och en grön kant med minimal vikt läggs till. Resultatet är den lättaste ramen.
Genomförande
Låt oss beteckna den nuvarande skogen F.Den delar upp uppsättningen av hörn i grafen i anslutningsområden (deras förening bildar F, och de skärs inte i par). De röda kanterna har båda hörnen i samma del. Del (x) är en funktion som, för varje vertex x, returnerar namnet på den del som x tillhör. Unite (x, y) är en procedur som bygger en ny partition, bestående av föreningen av x- och y-delarna och alla andra delar. Låt n vara antalet kanter i grafen. Alla dessa begrepp ingår i Kruskals algoritm. Genomförande:
Ordna alla kanter på grafen från 1:a till n:e i stigande viktordning. (ai, bi är hörn av kanten med nummer i).
för i = 1 till n do.
x: = Del (ai).
y: = Del (bi).
Om x inte är lika med y så förena (x, y), inkludera kant i i F.
Rätthet
Låt T vara skelettet för den ursprungliga grafen konstruerad med Kruskal-algoritmen, och S dess godtyckliga skelett. Vi måste bevisa att w (T) inte överstiger w (S).
Låt M vara uppsättningen av kanter S, P vara uppsättningen av kanterT. Om S inte är lika med T, så finns det en kant et på ramen T som inte tillhör S. Vi fäster et till S. En cykel bildas, låt oss kalla den C. Vi tar bort från C alla kant es tillhör S. Vi får en ny ram, eftersom kanterna, och det är lika många toppar i den. Dess vikt överstiger inte w(S), eftersom w(et) som mest är w(es) på grund av Kruskals algoritm. Vi kommer att upprepa denna operation (ersätter kanterna S med kanterna T) tills vi får T. Vikten av varje efterföljande resulterande ram är inte större än vikten av den föregående, varför det följer att w (T) inte är större än w (S).
Dessutom följer riktigheten av Kruskals algoritm från Rado-Edmonds sats om matroider.
Exempel på tillämpning av Kruskal-algoritmen
Givet en graf med hörn a, b, c, d, e och kanter (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Revbenens vikter visas i tabellen och i figuren. Inledningsvis innehåller skogen F under uppbyggnad alla hörn i grafen och innehåller inga kanter. Kruskals algoritm lägger först till kanten (a, e), eftersom den har den minsta vikten, och hörnen a och e är i olika sammankopplade komponenter i skogen F (kanten (a, e) är grön), sedan kanten (c, d), därför att denna kant har minst vikt av kanterna på grafen som inte tillhör F, och den är grön, så läggs kanten (a, b) till av samma skäl. Men kanten (b, e) hoppas över, även om den har den minsta vikten av de återstående kanterna, eftersom den är röd: hörnen b och e tillhör samma sammankopplade komponent i skogen F, det vill säga om vi lägger till kanten (b, e) till F, den bildar cykel. Sedan läggs en grön kant (b, c) till, en röd kant (c, e) hoppas över och sedan d, e. Således läggs kanterna (a, e), (c, d), (a, b), (b, c) till sekventiellt. Det optimala skelettet i den initiala grafen består av dem. Så här fungerar algoritmen i det här fallet Målad. Ett exempel har visat detta.
Figuren visar en graf som består av två sammankopplade komponenter. De feta linjerna visar kanterna på den optimala trådramen (grön) konstruerad med Kruskal-algoritmen.
Den övre figuren visar den ursprungliga grafen, och den nedre visar ramverket för minimivikt som konstruerats för det med den övervägda algoritmen.
Sekvensen av tillagda kanter: (1,6); (0.3), (2.6) eller (2.6), (0.3) - spelar ingen roll; (3,4); (0,1), (1,6) eller (1,6), (0,1) är också likgiltigt (5,6).
Kruskals algoritm finner praktisk tillämpning, till exempel för att optimera läggningen av kommunikationer, vägar i nya stadsdelar av bosättningar i varje land, såväl som i andra fall.
