Kruskals algoritme - de bouw van een optimaal kader

In het begin van de 19e eeuw meetkundige Jakob Steiner uit Berlijn de taak van hoe de drie dorpen verbinden zodat hun lengte was de kortste. Later, vatte hij het probleem: het nodig is om een punt in een vliegtuig te vinden, de afstand van het aan n andere punten waren het laagst. In de 20e eeuw, het blijft werken aan dit onderwerp. Er werd besloten om een paar punten te pakken en sluit ze op een zodanige wijze dat de afstand tussen hen was de kortste. Dit alles is een speciaal geval van het probleem bestudeerd.

"Greedy" algoritme

Kruskals algoritme verwijst naar de "greedy" algoritme (ook wel gradiënt). De essentie van deze - de hoogste winst op elke stap. Niet altijd, "greedy" algoritmen bieden de beste oplossing voor het probleem. Er is een theorie, blijkt dat de toepassing van specifieke taken zij de optimale oplossing. Dit is de theorie van matroids. Kruskals algoritme verwijst naar dergelijke problemen.

Het vinden van een minimum karkas gewicht

Bekeken algoritme construeert een optimale rastertelling. Het probleem daarvan is als volgt. Dan ongerichte graaf zonder parallelle randen en lussen, en het stel randen krijgt de gewichtsfunctie w, waarbij het aantal toekent aan elke rand e - gewicht rib - w (e). Het gewicht van elke deelverzameling van het veelvoud van ribben is de som van de gewichten van de randen. Die nodig is om het skelet van een kleine gewicht te vinden.

beschrijving

Kruskals algoritme werkt. Eerst worden alle randen van de initiële grafiek zijn gerangschikt in oplopende volgorde van de gewichten. Aanvankelijk het frame geen ribben bevatten, maar omvat alle vertices. Na de volgende stap van het algoritme om de reeds gebouwde deel van het karkas, een bos overspannen, wordt een rand toegevoegd. Het is niet willekeurig gekozen. Alle randen van de grafiek, die niet behoren tot het frame kan worden rood en groen genoemd. De bovenkant van elke rode randen in dezelfde component in aanbouw bos connectiviteit, en de groene toppen - anders. Daarom, als u toe te voegen aan de rode rand, is er een cyclus, en als de groene - als zodanig, nadat deze stap zal het hout aangesloten componenten minder dan één zijn. Zo kan de resulterende constructie niet toevoegen geen rode rand, maar enige groene rand kan worden toegevoegd aan het bos te krijgen. En voegt een groene rand met een minimaal gewicht. Het resultaat is een raamwerk van minimumgewicht.

uitvoering

Noem het huidige bos F. Het verdeelt de set van hoekpunten op het gebied van connectiviteit (hun vakbond vormen F, en ze zijn disjunct). Aan beide kanten van de rode hoekpunten liggen ze in een stuk. Deel (x) - de functie die voor elk hoekpunt Xa deel van de naam geeft, behoort x. Verenigen (x, y) - een procedure die een nieuwe verdeling bouwt, bestaande uit het combineren van delen van x en y en alle andere onderdelen. Zij n - aantal zijden. Al deze concepten zijn opgenomen in kruskals algoritme. uitvoering:

1. Schik alle randen van de grafiek van de 1e tot en met n-de oplopende gewichten. (Ai, Bi - i met toprand nummer).

2. voor i = 1 tot n doen.

3. x: = Part (ai).

4. y: = Part (bi).

5. Als x niet gelijk y dan verenigt (x, y), met de rand Fi getal te nemen.

juistheid

Zij T - frame van de oorspronkelijke grafiek geconstrueerd met behulp van de Kruskal algoritme en S - een willekeurig frame. We moeten bewijzen dat w (t) niet groter dan wi (S).

Laat M - aantal vinnen S, P - meerdere vinnen T. Indien S niet gelijk is aan T, dan is er een frame rib et T, niet behorend tot S. S. et grenzen aan de cyclus, het heet C C verwijderen van een rand es, behoren S. We krijgen een nieuw frame, omdat de randen en hoekpunten is hetzelfde. Zijn gewicht niet groter dan wi (S), aangezien w (et) niet langer w (n) in een stroom Kruskal algoritme. Deze bewerking (plaatsvervanger Ts ribben op ribben) worden herhaald zolang ontvangt T. Het gewicht van elke volgende ontvangen frame niet groter is dan de vorige gewicht, hetgeen betekent dat w (t) niet groter dan wi (S).

De robuustheid van kruskals algoritme volgt uit de stelling van Rado-Edmonds op matroids.

Toepassingsvoorbeelden Kruskal algoritme

Dan grafiek met knooppunten a, b, c, d, e en ribben (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) (d, e). De gewichten van randen in de tabel en de figuur. Aanvankelijk bos bouw F bevat alle hoekpunten van de grafiek en geen ribben bevat. Algoritme Kruskal eerst toevoegen rib (a, e), aangezien het gewicht had de laagste en de hoekpunten a en e zijn in verschillende componenten hout verbinding F (rib (a, e) groen) en de ribbe (c, d), omdat dat althans deze rand gewicht van de grafiek randen, niet behorend tot F, en het is groen, dan om dezelfde redenen toekomen rand (a, b). Maar de rand (b, e) wordt aangenomen, hoewel hij en het minimumgewicht van de resterende randen, omdat het rood: de hoekpunten b en e behoren tot dezelfde component van het bos connectiviteit F, dat wil zeggen, als we toe te voegen aan F de rand (b, e), wordt gevormd cyclus. Vervolgens voegde groene rand (b, c), wordt geleid rode rand (c, e) en d, e. Aldus worden de randen achtereenvolgens (a, e), (c, d), (a, b), (b, c). Van nihera optimale frame en bestaat uit de oorspronkelijke graaf. Dus in dit geval werkt een algoritme Kruskal. Een voorbeeld is getoond.

De figuur toont een grafiek, die uit twee verbonden componenten. De dikke lijnen geven de optimale gestel ribben (groen) uitgevoerd met de Kruskal-algoritme.

Het bovenste beeld toont de oorspronkelijke grafiek en de bodem - een skelet van minimaal gewicht, voor hem gebouwd met behulp van de algoritme.

De sequentie van de toegevoegde ribben (1,6); (0,3), (2,6) of (2,6), (0,3) - is niet belangrijk; (3,4); (0,1), (1,6) of (1,6), (0,1), ook zorg (5,6).

Kruskals algoritme vindt praktische toepassing, bijvoorbeeld om de pakking communicatie wegen in nieuwbouw plaatsen in elk land, en in andere gevallen te optimaliseren.