Kruskals algoritm - byggandet av en optimal ram

I början av 19-talet geometer Jakob Steiner från Berlin ställa uppgiften att hur man kopplar tre byar så att deras längd var kortast. Senare sammanfattade han problemet: det är nödvändigt att hitta en punkt i ett plan, avståndet från det till n andra punkter var den lägsta. På 20-talet, fortsätter att arbeta med detta ämne. Det beslutades att ta några poäng och anslut dem på ett sådant sätt att avståndet mellan dem var kortast. Allt detta är ett specialfall av problemet som studeras.

"Greedy" algoritm

Kruskals algoritm hänvisar till "giriga" algoritm (även kallad gradient). Kärnan i de - den högsta vinsten på varje steg. Inte alltid, "giriga" algoritmer ger den bästa lösningen på problemet. Det finns en teori, som visar att i sin ansökan till specifika uppgifter som de ger den optimala lösningen. Detta är teorin om matroids. Kruskals algoritm hänvisar till sådana problem.

Att hitta en minimal slaktvikt

Tittade algoritm konstruerar en optimal ramsumman. Problemet med det är som följer. Dan oriktad graf utan parallella kanter och loopar, och uppsättningen av kanter ges viktfunktion w, som tilldelar nummer till varje kant e - vikt resår - w (e). Vikten av varje undergrupp av nämnda flertal ribbor är summan av vikterna av dess kanter. Krävs för att hitta skelettet av en liten vikt.

beskrivning

Kruskals algoritm fungerar. Först, är alla kanter på den initiala grafen arrangerade i stigande ordning av vikterna. Inledningsvis inte ramen innehåller inga revben utan omfattar alla hörn. Efter nästa steg av algoritmen till den redan byggda delen av slaktkroppen, som är en som spänner över skog, är en kant sattes. Det är inte godtyckligt valda. Alla kanter grafen inte hör till ramen, kan kallas rött och grönt. Toppen av varje röda kanter är i samma komponent under konstruktion skog anslutning och de gröna toppar - olika. Därför, om du lägger till den röda kanten, det finns en cykel, och om den gröna - som inkommer efter detta steg trä anslutna komponenterna kommer att vara mindre än ett. Således kan den resulterande konstruktionen inte lägga någon röd kant, men någon grön kant kan läggas att få skogen. Och lägger till en grön kant med minimal vikt. Resultatet är ett ramverk av minimal vikt.

genomförandet

Anger det aktuella skogen F. Den delar uppsättningen hörn inom konnektivitet (deras fackliga former F, och de är disjunkta). Vid båda kanterna av röda hörn de ligger i ett stycke. Del (x) - den funktion som för varje vertex x returnerar en del av namnet, tillhör det x. Unite (x, y) - ett förfarande som bygger en ny partition, som består av att kombinera delar av x och y och alla andra delar. Låt n - antal kanter. Alla dessa begrepp ingår i kruskals algoritm. genomförande:

1. Ordna alla kanterna på grafen från 1: a till n: te uppstigande vikter. (Ai, bi - i med apex kantnummer).

2. för i = 1 till n göra.

3. x: = Del (ai).

4. y: = Del (bi).

5. Om x inte är lika med y sedan Unite (x, y), för att inkludera med kant Fj nummer.

korrekthet

Låt T - ram av den ursprungliga grafen konstrueras med användning av Kruskal-algoritmen och S - dess godtycklig ram. Vi måste bevisa att w (T) inte är större än w (S).

Låt M - flertal fenor S, P - ett flertal fenor T. Om S inte är lika med T, då finns det en spantet et T, som inte hör till S. S. et gränsar cykeln, det kallas C. C ta bort från eventuella kant es, som tillhör S. Vi får en ny ram, eftersom kanterna och hörnen är densamma. Dess vikt är inte större än w (S), eftersom w (et) inte längre w (er) i en kraft Kruskal algoritm. Denna operation (substitut T S ribbor på ribbor) kommer att upprepas så länge som mottar T. Vikten av varje efterföljande mottagna ramen inte är större än den tidigare vikt, vilket innebär att w (T) inte är större än w (S).

Robustheten kruskals algoritm följer satsen av Rado-Edmonds på matroids.

Applikationsexempel Kruskal algoritm

Dan graf med noder a, b, c, d, e och revben (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Vikterna av kanterna visas i tabellen och i figuren. Inledningsvis konstruktion skog F innehåller alla hörn av grafen och inte innehåller några revben. Algoritm Kruskal först lägga ribba (a, e), eftersom vikten hade den lägsta, och hörnen A och E är i olika komponenter timmer anslutning F (ribba (a, e) är grön), därefter ribban (c, d), eftersom att åtminstone denna kant vikt av graf kanter, som inte tillhör F, och det är grön, därefter av samma skäl falla kanten (a, b). Men kanten (b, e) passeras, även om han och minimal vikt av de återstående kanterna, eftersom det är röd: hörn B och E tillhör samma komponent av skogs anslutning F, det vill säga om vi lägger till F kanten (b, e), bildas cykeln. Sattes därefter grön kant (b, c), får passera röd kant (c, e), och sedan d, e. Således är kanter sätts sekventiellt (a, e), (c, d), (a, b), (b, c). Från nihera optimal ram och består av den ursprungliga grafen. Så i detta fall driver en algoritm Kruskal. Ett exempel visas.

Figuren visar ett diagram, som består av två anslutna komponenter. De feta linjerna indikerar de optimala spant (grön) konstruerade med användning av Kruskal-algoritmen.

Den översta bilden visar den ursprungliga grafen och botten - ett skelett av minimal vikt, byggd för honom genom att använda algoritmen.

Sekvensen av de tillsatta ribbor (1,6); (0,3), (2,6) eller (2,6), (0,3) - är inte viktigt; (3,4); (0,1), (1,6) eller (1,6), (0,1), även bryr (5,6).

Kruskals algoritm finner praktisk tillämpning, till exempel för att optimera packnings kommunikation, vägar i nya bostadsområden orter i varje land, liksom i andra fall.