Kiel registrite je 20:13, 21 sep. 2008 redakti SieBot (diskuto \| kontribuoj) 168 505 redaktoj e roboto aldono de: sl:Minimalno vpeto drevo ← Iru al antaŭa ŝanĝo		Kiel registrite je 00:58, 16 jan. 2009 redakti malfari 70.58.169.61 (diskuto) Neniu resumo de redakto Iru al sekvanta ŝanĝo →
Linio 11: == Algoritmoj == La unua algoritmo por trovi minimuman branĉantan arbon estis ellaborita ~~far~~fare de Ĉeĥa sciencisto Otakar Borůvka en [[1926]] (vidu en [[algoritmo de Boruvka]]). Ĝia celo estis kompetenta elektrigo de [[Bohemio]]. Estas nun du algoritmoj kutime uzataj, l algoritmo de Prim kaj la algoritmo de Kruskal. Ĉiuj tri estas [[avara algoritmo\|avaraj algoritmoj]], kiuj ruliĝas en [[polinoma tempo]], do la problemo trovi tiajn arbojn estas en '''[[P (komplikeco)\|P]]'''. La plej rapida minimuma branĉanta arba algoritmo ĝis nun estis ellaborita ~~far~~fare de Bernard Chazelle, kaj bazita sur tiu de Borůvka. Ĝia [[rultempo]] estas ''[[Granda O skribmaniero\|O]]''(''m'' &α;(''m'',''n'')), kie ''m'' estas la kvanto de lateroj, ''n'' estas la nombro de verticoj kaj α estas la klasika funkcia inverso de la [[akermana funkcio]]. La funkcio α kreskas ege malfrue, tiel ke por ĉiuj praktikaj celoj ĝi povas esti konsiderata konstanto ne pli granda ol 4; tial la algoritmo de Chazelle prenas tre proksime al ''[[Granda O skribmaniero\|O]]''(''m'') tempon. Kiu estas la plej rapida ebla algoritmo por ĉi tiu problemo? Tio estas unu el la plej malnovaj malfermitaj demandoj en komputiko. Estas klare lineara suba baro, ĉar ni devas almenaŭ ekzameni ĉiujn pezojn. Se la latero-pezoj estas entjeroj kun barita bita longo, tiam [[determinismaj algoritmo]]j estas sciataj kun [[lineara rultempo]], ''O''(''m''). Por ĝeneralaj pezoj, [[hazardigita algoritmo\|hazardigitaj algoritmoj]] estas sciataj, kies atendita rultempo estas lineara. Linio 21: Pli ĵuse, esploro fokusas super solvi la minimuman branĉantan arban problemon en alte paraleligita maniero. Ekzemple, la pragmata ([[2003]]) papero "Rapida Komunigita-Memoro Algoritmoj por Komputi la Minimuman Generantan Arbaron de Sparse (Grafikaĵoj, Grafeoj)" per Davido A. pli malbona kaj Guojing Cong demonstracias algoritmon, kiu povas komputi MSTs 5-oble pli rapide sur 8 procesoroj ol (optimigis, optimumigita) (sekvenca vica algoritmo.[http://www.cs.unm.edu/~treport/tr/03-12/MST-bader.pdf] Tipe, paralelo algoritmoj estas bazitaj sur la algoritmo de Boruvka — la algoritmoj de Prim kaj aparte de Kruskal ne skalo kiel bone al aldonaj procesoroj. Aliaj specialigitaj algoritmoj jam estas (dizajnita, desegnita)j por komputi minimumajn generantajn arbojn de grafeo tiel grandaj, ke la plejparto el ili devas esti storita sur disko ajn tempoj. Ĉi tiuj ''[[ekstera memoro\|eksteraj memoraj]]'' algoritmoj, ekzemple kiel priskribitaj en "Inĝenierada Ekstera Memora Minimumo Branĉanta Arba Algoritmo" ~~far~~fare de Roma Dementiev k.a.,[http://citeseer.ist.psu.edu/dementiev04engineering.html] povas operacii tiel malgranda kiel 2 ĝis 5-oble pli malfrua ol tradicia en-memora algoritmo; ili pretendas, ke "problemoj de (masiva, peza) minimuma generanta arbo enspacanta kelkajn (fiksitaj diskoj, diskaparatoj)n povas esti solvitaj tranokte sur persona komputilo." Ili bezonas kompetentan eksteran memoran ordigan algoritmon kaj kuntirajn teknikojn sur grafeo por reduktanta la grafea amplekso kompetentajn. == MST sur plenaj grafeoj == Jam estas montrita ~~far~~fare de J. Michael Steele bazite sur laboro ~~far~~fare de A. M. Frieze, ke por donita [[plena grafeo]] sur ''n'' verticoj, kun latero-pezoj elektitaj de kontinua hazarda distribuo ''f'' tia, ke <math>f'(0) > 0</math>, kiam ''n'' proksimiĝas al [[malfinio]] la amplekso de la MST proksimiĝas al <math>\zeta(3)/f'(0)</math>, kie <math>\zeta</math> estas la [[rimana ζ funkcio]]. Por uniformaj hazardaj pezoj en <math>[0,1]</math>, la ĝusta atendita amplekso de la minimuma branĉanta arbo estas komputita por malgrandaj plenaj grafeoj.

Minimuma generanta arbo: Malsamoj inter versioj