Kruskal-algoritmus - az építési optimális keret

A 19. század elején geométert Jakob Steiner Berlin a feladatot, hogyan lehet csatlakozni a három falut, hogy hosszuk volt a legrövidebb. Később össze a problémát: ez szükséges, hogy talál egy pontot a síkon, a távolság, hogy n többi pont volt a legalacsonyabb. A 20. században, továbbra is dolgozik ebben a témában. Úgy döntöttek, hogy néhány pontot, és csatlakoztassa őket oly módon, hogy a köztük lévő távolság volt a legrövidebb. Mindez egy speciális esete a probléma is vizsgálták.

„Mohó” algoritmus

Kruskal-algoritmus utal, hogy a „mohó” algoritmus (más néven gradiens). A lényege az, - a legmagasabb win minden lépésre. Nem mindig, „mohó” algoritmus biztosítja a legjobb megoldást a problémára. Van egy elmélet, amely igazolja, hogy azok alkalmazása konkrét feladatokat adnak az optimális megoldást. Ez az elmélet a matroidok. Kruskal-algoritmus kifejezés az ilyen problémákat.

Találjanak minimális hasított súly

Megtekintett algoritmus létrehoz egy optimális keretszám. A probléma az, hogy a következő. Dan irányítatlan gráf nélkül párhuzamos élek és hurkok, és a beállított élek adják a súlyfüggvényt w, amely kijelöli a számot minden e éléhez - tömeg borda - W (E). A tömeg minden részhalmazában a bordák az összege a súlyok széle. Szükséges, hogy megtalálják a csontváz egy kis súlyt.

leírás

Kruskal-algoritmus működik. Először is, az összes szélei a kezdeti gráf vannak elrendezve növekvő sorrendben a súlyok. Kezdetben a keret nem tartalmaz olyan bordákat, hanem magában foglalja az összes csúcsot. Miután a következő lépés az algoritmus a már megépített része a szövetváz, amely egy áthidaló erdőben, az egyik szélén adunk hozzá. Ez nem önkényesen választottuk. Minden a széleit a grafikon, amely nem tartozik a kerethez, nevezhetjük vörös és zöld. A tetején minden piros élek ugyanabban a komponens alatt erdő kapcsolat, és a zöld tetők - más. Ezért, ha hozzá a vörös él, van egy ciklus, és ha a zöld - a beérkezett lépés után a fa csatlakoztatott készülékek kevesebb lesz, mint egy. Tehát a keletkező építési nem lehet hozzáadni nem piros él, de a zöld széle adhatunk, hogy az erdőben. És hozzáteszi, zöld széle és minimális súly. Az eredmény egy olyan keret minimális súlyát.

végrehajtás

Jelöljük a jelenlegi erdő F. megosztja a csúcsok halmaza terén kapcsolat (szakszervezeti formák F, és ezek diszjunkt). Mindkét élén a piros csúcsok fekszenek egy darabban. Rész (x) - ez a funkció, hogy minden x csúcs visszatér egy részét a nevét, tartozik x. Unite (x, y) - olyan eljárás, amely épít egy új partíció, amely egyesíti részei x, y és az összes többi része. Legyen n - élek számát. Mindezek a fogalmak szerepelnek Kruskal-algoritmus. Megvalósítás:

1. Gondoskodjon az összes széleit a grafikon az 1-től n-edik emelkedő súlyokkal. (Ai, bi - i amelynek csúcsa szélén szám).

2. i = 1-től n do.

3. X: = rész (ai).

4. y: = rész (bi).

5. Ha x nem egyenlő y, majd Unite (x, y), hogy tartalmazza a szélén F i száma.

helyességét

Legyen T - keret az eredeti, diagram épített a Kruskal algoritmus és S - annak önkényes képkocka. Azt kell bizonyítani, hogy w (T) nem nagyobb, mint w (S).

Legyen M - több bordával S, P - több bordát T. Ha S nem egyenlő T, akkor van egy keret borda et T, nem tartozó S. S. és szomszédosak a ciklus, ez az úgynevezett C. C eltávolítására bármely szélétől es tartozó S. kapunk egy új képkockát, mert az élek és csúcsok ugyanaz. A súlya nem nagyobb, mint w (S), mivel w (et) már nem w (ek) a teljesítmény Kruskal algoritmus. Ez a művelet (helyettesítő T S bordák bordák) meg kell ismételni, amíg megkapja T. A tömeg minden ezt követő vett keret nem nagyobb, mint az előző tömeg, ami azt jelenti, hogy a w (t) nem nagyobb, mint w (S).

A robusztus Kruskal-algoritmus következik a tétel a Rado-Edmonds on matroidok.

Alkalmazási példák Kruskal algoritmus

Dan gráf csomópontok a, b, c, d, e és a bordák (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). A súlyok élek megjelennek a táblázatban, és az ábrán. Kezdetben építési erdő F minden a gráf és nem tartalmaz semmilyen bordák. Algoritmus Kruskal először hozzá borda (a, e), mivel a súlya volt a legalacsonyabb, és a csúcsok A és E jelentése a különböző alkotóelemek fűrészárut kapcsolat F (borda (a, e) zölden), akkor a borda (c, d), mert hogy legalább ez az él súlya gráf élek, nem tartoznak a F, és ez a zöld, majd ugyanezen okokból felhalmozni széle (a, b). De az él (b, e) vezetünk, bár ő és a minimális súlya a fennmaradó élek, mert piros: a csúcsok b és e tartoznak azonos összetevője erdő kapcsolat F, azaz, ha ehhez hozzátesszük, hogy az F szélén (b, e), van kialakítva ciklust. Ezután hozzáadunk zöld széle (b, c), vezetünk piros él (c, e), majd D, E. Így élek egymást követően adjuk (a, e), (c, d), (a, b), (b, c). Tól nihera optimális keret áll, és az eredeti gráf. Tehát ebben az esetben működik egy algoritmus Kruskal. Egy példa látható.

Az ábrán egy grafikon, amely két csatlakoztatott komponensek. A vastag vonalak jelzik az optimális keret bordák (zöld) épített a Kruskal algoritmus.

A felső képen az eredeti gráf, és az alsó - a csontváz minimális tömegű, épített neki segítségével az algoritmus.

A szekvenciát a hozzáadott bordák (1.6); (0,3), (2,6), vagy (2,6), (0,3) - nem fontos; (3,4); (0,1), (1,6), vagy (1,6), (0,1), továbbá érdekel (5,6).

Kruskal-algoritmus megállapítja gyakorlati alkalmazása, például, hogy optimalizálja a tömítés kommunikáció, utak új lakótelepek hely az egyes országok, valamint más esetekben.