Ni Kruskal algorithm - ang konstruksiyon ng isang pinakamainam na balangkas

Sa unang bahagi ng ika-19 siglo geometrisyan Jakob Steiner mula sa Berlin itakda ang gawain ng kung paano ikonekta ang tatlong mga barangay upang ang kanilang haba ay ang pinakamaikling. Sa ibang pagkakataon, inisa-isa niya ang problema: ito ay kinakailangan upang mahanap ang isang punto sa eroplano, ang distansya mula sa mga ito sa n iba pang mga punto ay ang pinakamababang. Sa ika-20 siglo, ito ay patuloy na gagana sa paksang ito. Ito ay nagpasya na tumagal ng ilang mga puntos at ikonekta ang mga ito sa paraan na ang distansya sa pagitan ng mga ito ay ang pinakamaikling. Ito ang lahat ay isang espesyal na kaso ng problema pinag-aaralan.

"Matakaw" algorithm

ni Kruskal algorithm ay tumutukoy sa "sakim" algorithm (tinatawag din na gradient). Ang kakanyahan ng mga - ang pinakamataas na panalo sa bawat hakbang. Hindi palagi, "buwaya" algorithm magbigay ng pinakamahusay na solusyon sa problema. May ay isang teorya, na ipinapakita na sa kanilang mga aplikasyon sa mga tiyak na mga gawain bigyan sila ang pinakamainam na solusyon. Ito ang teorya ng matroids. ni Kruskal algorithm ay tumutukoy sa gayong mga problema.

Paghahanap ng isang minimum na timbang carcass

Tiningnan algorithm constructs isang optimal count frame. Ang problema sa mga ito ay tulad ng sumusunod. Dan undirected graph na walang parallel gilid at mga loop, at ang hanay ng mga gilid ay ibinigay ang bigat ng function w, na kung saan ay nagtatalaga ng bilang sa bawat gilid e - pagbaba ng rib - w (e). Ang bigat ng bawat subset ng mayorya ng mga buto-buto ay ang kabuuan ng mga timbang sa kanyang gilid. Kinakailangan upang mahanap ang balangkas ng isang maliit na timbang.

paglalarawan

ni Kruskal algorithm ay gumagana. Una, ang lahat ng mga gilid ng unang graph ay isinaayos sa pataas-sunod ng mga weights. Sa una, ang frame ay hindi naglalaman ng anumang mga buto-buto ngunit kasama ang lahat ng mga vertex. Matapos ang susunod na hakbang ng algorithm sa na constructed bahagi ng bangkay ng mga iyan, na isang sumasaklaw sa gubat, isang gilid ay idinagdag. Hindi ito pinili nagkataon. Ang lahat ng mga gilid ng graph, na hindi kasali sa frame, maaaring tinatawag na pula at berde. Ang tuktok ng bawat pulang gilid ay nasa parehong bahagi under construction forest pagkakakonekta, at ang green tops - naiiba. Samakatuwid, kung idagdag ka sa ang pulang gilid, doon ay isang cycle, at kung ang green - pati na natanggap matapos ang hakbang na kahoy konektado mga bahagi ay magiging mas mababa kaysa sa isa. Kaya, ang mga nagresultang konstruksiyon ay hindi maaaring magdagdag ng walang pulang gilid, ngunit ang anumang mga berdeng gilid ay maaaring idagdag upang makakuha ng kagubatan. At nagdadagdag ng isang green na gilid na may minimum na timbang. Ang resulta ay isang framework ng mga minimum na timbang.

pagsasagawa

Magpakilala ang kasalukuyang forest F. Ito divides ang hanay ng mga vertices sa larangan ng koneksyon (ang kanilang union form F, at sila ay magkahiwa-hiwalay). Sa parehong gilid ng pulang vertices magsinungaling sila sa isang piraso. Part (x) - ang function na para sa bawat tuktok x nagbabalik ng isang bahagi ng pangalan, ito ay kabilang x. Magkaisa (x, y) - isang pamamaraan na gagawa ng isang bagong dinding, na binubuo ng pinagsasama-sama mga bahagi ng x at y at lahat ng iba pang mga bahagi. Hayaan n - bilang ng mga gilid. Ang lahat ng mga konseptong ito ay kasama sa ni Kruskal algorithm. pagpapatupad:

1. Ayusin ang lahat ng mga gilid ng graph mula sa ika-1 hanggang n-th pataas na weights. (Ai, bi - i sa tugatog number gilid).

2. para i = 1 sa n gawin.

3. x: = Part (Ai).

4. y: = Part (bi).

5. Kung x ay hindi katumbas ng y at pagkatapos ay Unite (x, y), upang isama sa ang bilang edge F i.

kawastuhan

Hayaan T - frame ng orihinal na graph constructed gamit ang Kruskal algorithm at S - nito arbitrary frame. Mayroon kaming upang patunayan na w (T) ay hindi mas malaki kaysa sa w (S).

Hayaan M - mayorya ng mga palikpik S, P - isang mayorya ng mga palikpik T. Kung S ay hindi katumbas ng T, at pagkatapos ay doon ay isang frame rib et T, na hindi kasali sa S. S. et makapiling cycle, ito ay tinatawag C. C-alis mula sa anumang es gilid, na pagmamay-ari S. makakuha kami ng isang bagong frame, dahil ang mga gilid at vertices ay pareho. Bigat nito ay hindi mas malaki kaysa sa w (S), dahil w (et) Hindi na w (es) sa isang power Kruskal algorithm. Ang operasyon na ito (kapalit T S buto-buto sa buto-buto) ay mauulit hangga't makatanggap T. Ang bigat ng bawat kasunod na natanggap frame ay hindi mas malaki kaysa sa nakaraang grado, na nagpapahiwatig na ang w (T) ay hindi mas malaki kaysa sa w (S).

Ang bulas ng Kruskal algorithm ay sumusunod mula sa ang teorama ng Rado-Edmonds sa matroids.

Application halimbawa Kruskal algorithm

Dan graph na may nodes a, b, c, d, e at mga buto-buto (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Ang mga timbang ng mga gilid ay ipinapakita sa talahanayan at sa pigura. Sa una, konstruksiyon kagubatan F naglalaman ng lahat ng vertices ng graph at ay hindi naglalaman ng anumang mga buto-buto. Algorithm Kruskal idagdag muna rib (a, e), dahil ang bigat ay nagkaroon ang pinakamababang at ang vertices ng isang at e ay nasa iba't ibang mga bahagi timber pagkakakonekta F (rib (a, e) ay berde), pagkatapos ay ang rib (c, d), dahil na hindi bababa sa ito edge bigat ng graph gilid, na hindi kasali sa F, at ito ay berde, at pagkatapos ay para sa parehong mga dahilan makaipon gilid (a, b). Ngunit sa gilid (b, e) ay lumipas, kahit na siya at ang minimum na timbang ng ang mga natitirang mga gilid, dahil ito ay pula: ang vertices b at e nabibilang sa parehong bahagi ng kagubatan pagkakakonekta F, iyon ay, kung idagdag namin na F gilid (b, e), ay binuo cycle. Pagkatapos ay idinagdag berdeng gilid (b, c), Lumipas pulang gilid (c, e), at pagkatapos ay d, e. Kaya, ang mga gilid ay idinagdag nang sunud-sunod (a, e), (c, d), (a, b), (b, c). Mula nihera optimal frame at binubuo ng orihinal na graph. Kaya sa kasong ito ito ay nagpapatakbo ng isang algorithm Kruskal. Ang isang halimbawa ay ipinapakita.

Ang figure na nagpapakita ng isang graph, na kung saan ay binubuo ng dalawang konektado mga bahagi. Ang naka-bold linya ipahiwatig ang pinakamainam na frame buto-buto (berde) constructed gamit ang Kruskal algorithm.

Ang tuktok na larawan ay nagpapakita ng mga orihinal na graph, at ibaba - isang balangkas ng minimal na timbang, na binuo para sa kanya sa pamamagitan ng paggamit ng mga algorithm.

Ang pagkakasunod-sunod ng dagdag buto-buto (1.6); (0,3), (2,6) o (2,6), (0,3) - ay hindi mahalaga; (3,4); (0,1), (1,6) o (1,6), (0,1), din-aalaga (5,6).

ni Kruskal algorithm hahanap praktikal na application, halimbawa, upang i-optimize ang sapin ng komunikasyon, mga kalsada sa mga bagong pabahay Estates lokalidad sa bawat bansa, pati na rin sa ibang mga kaso.