Kruskal an algairim - a 'togail an fhrèam reachdachadh

Anns na tràth san 19mh linn geometer Jakob Steiner a stèidheachadh bho Berlin an obair mar a tha a 'ceangal trì bailtean mar sin aca gun robh an fhaid a bh' as giorra. Às dèidh sin, thug e geàrr-chunntas air an trioblaid: tha feum air a lorg puing ann am plèana, an t-astar bhon e gu 'n puingean eile a bha an ìre as ìsle. Anns an 20mh linn, tha e fhathast ag obair air a 'chuspair seo. Chaidh co-dhùnadh a ghabhail beagan phuingean agus an ceangal riutha ann an leithid de dhòigh gu bheil an astar eadar na bha iad as giorra. Tha seo uile a tha sònraichte a 'chùis air an duilgheadas a' sgrùdadh.

"Greedy" algairim

Kruskal a 'buntainn ris an algairim "sanntach" algairim (ris an canar cuideachd caisead). Tha brìgh an fheadhainn - an ìre as àirde barr air gach ceum. Neo daonnan, "sanntach"-aontaran a 'toirt fuasgladh as fheàrr air an duilgheadas. Tha teòiridh, a 'sealltainn gu bheil ann an iarrtas aca gus na gnìomhan sònraichte a bheir iad a' fuasgladh as fheàrr. 'S e seo an teòiridh matroids. Kruskal algairim a 'toirt iomradh air a leithid de thrioblaidean.

A'faighinn a 'char as lugha chlosach cuideam

Sealladh algairim constructs an reachdachadh frèam chunntadh. Tha duilgheadas a tha e mar a leanas. Dan undirected graf gun co-shìnte oirean agus lùban, agus seata de oirean air a thoirt seachad an cuideam gnìomh w, a shònraicheas an àireamh do gach iomall S - cuideam asnaichean - W (e). Tha cuideam gach fo-sheata de na iomadalachd nan aisnichean 'S e an t-suim de na cuideaman a-oirean. A dhìth a lorg cnàimhneach de beag cuideam.

Tuairisgeul

Kruskal an algairim ag obair. Chiad, a h-uile oirean a 'chiad graf a chur air dòigh ann a' dìreadh òrdugh a 'cuideaman. An toiseach, an fhrèam anns nach eil ach sam bith aisnichean gabhail a-steach a h-uile vertices. Às dèidh an ath cheum air an algairim gu thogail mar-thà na pàirt de chlosach, a tha a 'spangachadh coille, aon an oir a tha air a chur ris. Chan eil e air a thaghadh arbitrarily. A h-uile oirean a 'ghraf, cha bhuineadh ri frèam, faodar an t-ainm dearg is uaine. Tha mullach gach oirean dearg anns an aon phàirt togail fo choille ceangal, agus uaine mullaich - eadar-dhealaichte. Uime sin, ma tha sibh ris an oir dhearg, tha cearcall, agus ma uaine - mar a gheibhear às dèidh a 'cheum seo a' choille co-cheangailte phàirtean bidh nas lugha na aon. Mar sin, thoradh air togail urrainn nach cuir sam bith oir dhearg, ach sam bith uaine oir faodar a chur ris a 'faighinn a' choille. Agus a 'cur uaine oir' char as lugha le cuideam. Tha seo a 'char as lugha frèam de chuideam.

buileachadh

Denote an-dràsta coille F. Tha e a 'sgaradh an t-seata de vertices ann an achadh Flash (aca aonadh F foirmean, agus tha iad disjoint). An dà chuid aig oirean dearg vertices iad na laighe ann an aon phìos. Pàirt (x) - a 'ghnìomh sin airson gach x Vertex a' tilleadh a cuibhrionn an ainm, buin e x. Unite (x, y) - modh-obrach ùr a 'togail balla-dealachaidh, le còmhla pàirtean de x agus y agus uile pàirtean eile. Leig n - uile-oirean. Sin uile bun-bheachdan a tha a 'gabhail a-steach ann an Kruskal an algairim. Gnìomhachadh:

1. A chur air dòigh a h-uile oirean na graf bhon 1mh gu-n mh dìridh cuideaman. (Ai, dà - i le faobhar uile APEX).

2. airson i = 1 gu n dhèanamh.

3. x: = Pàirt (ai).

4. y: = Pàirt (dà thuras).

5. Ma x chan eil co-ionnan y uair sin Unite (x, y), a-steach le faobhar F i àireamh.

ceart

Leig T - frèam a 'chiad graf a thogail a' cleachdadh an algairim agus Kruskal S - a tràighte cèis. Feumaidh sinn a dhearbhadh gun w (T) nach eil nas motha na w (S).

Leig M - iomadalachd nan itean S, D - ioma-ghnèitheachd de itean T. Ma S nach eil co-ionnan ri T, an uair sin tha frèam-asnaichean et T, nach bhuineadh don S. S. et adjoin a 'chearcall,' se C. C thoirt air falbh bho sam bith oir es, a bhuineas S. sinn fhaighinn frèam ùr, oir na h-oirean agus vertices an aon rud. Tha cuideam nach eil nas motha na w (S), bho w (et) eil w (es) ann an cumhachd Kruskal algairim. Obrachadh seo (S ionaid T-aisnichean air aisnichean) a-rithist cho fada 'sa gheibh T. Tha cuideam às dèidh sin fhuair gach frèam nach eil nas motha na an cuideam roimhe, a tha a' ciallachadh gum w (T) nach eil nas motha na w (S).

Tha an gainnead de Kruskal an algairim a leanas bho Theorem de Rado-Edmonds air matroids.

Iarrtas Eisimpleirean Kruskal algairim

Dan graf le àiteachan a, b, c, d, e agus aisnichean (a, b), (a, e), (b, c), (b, d), (c, d), (c, d) , (d, e). Tha cuideaman de oirean air an sealltainn anns a 'chlàr agus ann an àireamh. An toiseach, togail coille F anns a h-uile vertices an graf agus anns nach eil sam bith aisnichean. Algorithm Kruskal chiad Cuir asnaichean (a, e), bho chaidh a 'chuideam a bha an ìre ab' ìsle, agus na vertices a agus e a tha ann an diofar phàirtean fiodh ceangal F (asnaichean (a, e) tha uaine), an uair sin asnaichean (c, d), a chionn gu bheil co-dhiù seo oir cuideam graf-oirean, nach bhuineadh don F, agus tha e uaine, an uair sin airson na h-aon adhbharan 'tàrmachadh oir (a, b). Ach an iomall (b, e) a tha a 'dol seachad, ged a bha e fhèin agus a' char as lugha cudthrom air fhàgail oirean, oir tha e dearg: an vertices b agus post buin an aon phàirt den choille ceangal F, 'se sin, ma tha sinn ris F faobhar (b, e), a chruthachadh rothaireachd. An sin a chur ris uaine oir (b, c), ga thoirt seachad oir dhearg (c, d), agus an uair sin d, e. Mar sin, oirean air an cur an òrdugh (a, e), (c, d), (a, b), (b, c). Bho nihera reachdachadh frèam agus tha a 'chiad ghraf. Mar sin, sa chùis seo tha e ag obrachadh an algairim Kruskal. Tha eisimpleir a shealltainn.

Tha an ìomhaigh seo a 'sealltainn graf, a tha air a dhèanamh suas de dhà co-cheangailte phàirtean. Tha dàna lines sealltainn na reachdachadh frèam-aisnichean (uaine) a thogail a 'cleachdadh an Kruskal algairim.

Tha mullach an dealbh a 'sealltainn graf tùsail, agus a' bhonn - cnàimhneach glè bheag de chuideam, a chaidh a thogail dha le bhith a 'cleachdadh an algairim.

Tha an sreath de chur ris aisnichean (1.6); (0,3), (2,6) no (2,6), (0,3) - chan eil e cudromach; (3,4); (0,1), (1,6) no (1,6), (0,1), cuideachd a 'gabhail cùram (5,6).

Kruskal an algairim lorgas practaigeach iarrtais, mar eisimpleir, gus an fheum as fheàrr gasket conaltraidh, rathaidean ann an taigheadas ùr oighreachdan sgìrean anns gach dùthaich, a thuilleadh air ann an cùisean eile.