Rêbaza Kruskal da - ji bo avakirina çarçoveyeke herî maqule

Di destpêka salên geometer sedsala 19'an Jakob Steiner ji Berlin set ya ku karê wê çawa to connect sê gundên, da ku length wan kêmtirîn bû. Piştre, ew bi kurtî pirsgirêka: ev pêwîst e ku xaleke di balafirê de, ji dûr ve ji bo n xalên din jî herî erzan bûn. Di sedsala 20mîn de, ew berdewam bi xebata li ser vê mijarê. Ev ji bo ku çend xalên û girêdanê wan bi vî awayî, ku ji dûr ve di navbera wan de kêmtirîn bû, biryar hate dayîn. Ev hemû dosyayek taybet li ser pirsgirêka ku xwendiye e.

"Greedy" Cureyê

Rêbaza Kruskal ya li algorithm "çavbirçî" (bi navê rengên sade) dide. Karê kesên - bilind win li ser her gav. Ne her tim, ji algorîtmayan "çavbirçî" ya herî baş bo çareseriya pirsgirêka ne. e, a teoriyê de heye, nîşandana ku di serlêdana xwe ji bo karên taybetî ew bidin çareseriya optimum. Ev teoriya matroids e. Rêbaza Kruskal ya ji bo van pirsgirêkan, behsa.

Tespîtkirin, herî kêm weight carcass

Rêbaza Viewed kareyan an count frame aşitixwaz. Pirsgirêka ku ev wiha ye. Dan graph birêvebirin bê keviya paralel û xelek, û set ji keviyan function weight w, ku diyarkirina hejmara bo her qiraxa e bê dayîn - rib weight - w (e). Ya bi giraniya her binkomeka, pirejimarî ji parsûyê sercem ji pîvan ji kevîyên wê ye. Pêwîst ji bo peyda hestî yên a weight biçûk.

description

Rêbaza Kruskal de dixebite. Yekem, hemû keviya ji graph destpêkê de bi li derdikevim fermana pîvan sazkirin. Di destpêkê de, di çarçoveya nade ti şikadin ne, lê di nav de hemû vertices. Piştî gava li pêş yên algorithm ji beşa berê çêkirî yên be, ku daristan Bahoz, yek ji devê added ye. Ev keyfî bijartî ne. Hemû ji keviyan ji graph, ku mensûbê çarçovê de ne, dikare bê kesk û sor û gazî. Jor li ser hev keviya sor li ser pêkhênanê ku heman di bin re girêdayîbûna bi daristanê avakirina in, û li tops kesk - cuda. Îcar, eger tu bi xwe li rêşiyên sor lê zêde bike, e xelekekê de heye, û eger kesk - ku piştî vê gavê qebûl pêkhateyên dar ve girêdayî ya kêmtir ji yek dê bibe. Bi vî awayî, ji bo avakirina wê encamê dikarin no qiraxa sor lê zêde ne, lê ti qiraxa kesk dikare got to get daristanê. Û wiha xemlên kesk bi kêmtirîn weight. Di encama vê çarçoveyê de ji herî kêm weight e.

pêkanîna

Eznûmên me daristanê niha F. Ev parçebûyî set of vertices di warê pêwendîdariya (Tewandin yekîtiya xwe F, û ew disjoint in). Li herdu keviya ji vertices sor ew in one piece derewan dikin. Part (x) - function ku ji bo her Vertex x beşek ji navê vedigere, ev nivîs aîdê x. Unite (x, y) - prosedureke ku ava dike partîsiyonê ya nû, ku ji yekbûneke parçeyên x û y û hemû parçeyên din. Bila n - hejmara keviya. Hemû van têgehan bi rêbazeke Kruskal ya di nav de. sepandina:

1. Saz hemû keviya ji graph ji 1ê ji bo pîvan asîman n-th. (Ai, bi - i bi hejmara qiraxa apex).

2. ji bo i = 1 to n do.

3. x: = Part (ai).

4. y: = Part (bi).

5. Eger x nizane y wekhev paşê Unite (x, y) ne, ji nav bi hejmara qiraxa F i.

duristîya

Bila T - frame ji graph original çêkirin bikaranîna algorithm Kruskal û S - frame kêfî xwe. Em îspat bikin ku w (T) ne di ser w (S).

Bila M - pirejimarî ji perik S, P - pirrengîyeke yên havîngehan T. Eger S e ji bo T wekhev ne, îdî a et frame rib T, ku mensûbê S. S. et ne adjoin di dewra, ku bi navê C. C jê ji ti es qiraxa, ku mensûbê hene S. Em bidestxistina çarçoveyeke nû, ji ber ku ji keviyan û vertices heman e. giranîya xwe ne mezintir w (S), ji ber ku w (et), êdî tu w (es) li rêbazeke Kruskal desthilatê. Ev operasyona (wekîl de şikadin T S li parsûyê) dê bên dubarekirin heta ku qebûl T. The giraniya her çarçovê de girtiye pişt re e ne mezintir giraniya berê, ku tê wateya ku w (T) ne di ser w (S).

The geflekirin ji algorithm Kruskal ya wiha ji theorem ji Rado-Edmonds li matroids.

Nimûne Application algorithm Kruskal

graph Dan bi hucûma a, b, c, d, e û şikadin (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). The pîvan ji keviyan bi li ser sifrê û li hejmara nîşandan. Di destpêkê de, daristan avakirina F dihewîne hemû vertices ji graph û ne ti şikadin ne. Algorithm Kruskal pêşî lê zêde bike rib (a, e), ji ber ku giraniya wê ya herî erzan kiribû, û li vertices a û e bi cuda bi hev re girêdayîbûna pêkhateyên timber F located (rib (a, e) kesk e), piştre rib (c, d), ji ber ku ku ev weight qet nebe ji devê keviya graph, ku mensûbê ne bi F, û kesk e, hingê ji ber heman sedemên paşarojê de qiraxa (a, b). Lê belê, ji devê (b, e) re derbas dibe, tevî ku ew û herî kêm giraniya keviya mayî, ji ber ku ew sor e: vertices de b û e ji ber ku component heman pêwendîdariya daristanê F, ku ev e, eger em ji bo F lê zêde bike ji devê (b, e), avakirin cycle. Hingê added qiraxa kesk (b, c) qiraxa sor, re derbas dibe (c, e), û paşê d, e. sequentially Bi vî awayî, keviya added bi (a, e), (c, d), (a, b), (b, c). Ji nihera frame aşitixwaz û ji van graph original. Bi vî awayî di vê rewşê de binasin an algorithm Kruskal. An mînak, tê nîşandan.

Ev jimar nîşan dide graph, ku ji du pêkhateyên ve girêdayî ye. Xetên qalind re nîşan didin ji parsûyê frame aşitixwaz (kesk) bikaranîna algorithm Kruskal çêkirin.

The picture top dide graph original, û li jêr - a hestî yên mînîmal weight, ava ji bo wî bi bikaranîna algorithm.

Bûyer ji parsûyê added (1.6); (0,3), (2,6) an jî (2,6), (0,3) - e ne giring e; (3,4); (0,1), (1,6) an jî (1,6), (0,1), bi xema (5,6).

Rêbaza Kruskal da serlêdana pratîk dibîne, bo nimûne, ji bo optimize bi berateyên gasket, rê li nû mehelên ku li sîteyên xanî li her welat, her wiha di rewşên din de.