Minimuma generanta arbo: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
Maksim (diskuto | kontribuoj) Neniu resumo de redakto |
Maksim (diskuto | kontribuoj) Neniu resumo de redakto |
||
Linio 1:
{{polurinda}}
[[Dosiero:Minimum spanning tree.svg|thumb|300px|right|La minimuma branĉanta arbo de ebena grafeo. Ĉiu branĉo estas etikedita kun ĝia pezo, kiu
Donita koneksa, sendirekta grafeo, [[generanta arbo|branĉanta arbo]] de tiu [[grafeo]] estas [[subgrafeo]] kiu estas arbo kaj kunkonektas ĉiujn [[vertico (grafeo)|verticojn]]. Sola grafeo povas havi multajn malsamajn branĉantajn arbojn. On povas ankaŭ asigni ''pezon'' al ĉiu [[latero (grafeo)|latero]], kiu estas nombro prezentanta kiel malfavora ĝi estas, kaj uzi tion por asigni pezon al branĉanta arbo per komputi la sumon de la pezoj de la branĉoj en tiu branĉanta arbo. '''Minimuma branĉanta arbo''' aŭ '''minimum-peza branĉanta arbo''' estas tiam branĉanta arbo kun pezo malpli ol aŭ egala al la pezo de ĉiu alia branĉanta arbo. Pli ĝenerale, iu ajn sendirekta grafeo havas '''minimuman branĉantan arbaron'''.
Unu ekzemplo estus kabla televid-kompanio demetanta kablon al nova najbarejo. Se ĝi estas limigita subterigi la kablon nur laŭ certaj vojoj, tiam devus esti (grafikaĵo, grafeo)n prezentantan tion kiuj punktoj estas koneksaj per tiuj vojoj. Iuj el tiuj vojoj povus esti pli multekostaj, ĉar ili estas pli longaj, aŭ postuli la kablon esti enfosita pli profunde; ĉi tiuj vojoj devus esti prezentitaj per randoj kun pli grandaj pezoj. ''Branĉanta arbo'' por tiu grafeo devus esti subaro de tiuj vojoj, kiuj havas neniujn ciklojn sed ankoraŭ trakonektas al ĉiu domo. Tie povus esti kelkaj branĉantaj arboj eblaj. ''Minimuma branĉanta arbo'' devus esti unu kun la plej malalta tuteca kosto.
Linio 11:
== Algoritmoj ==
La unua algoritmo por trovi minimuman branĉantan arbon estis ellaborita far Ĉ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 [[
La plej rapida minimuma branĉanta arba algoritmo ĝis nun estis ellaborita far Bernard Chazelle, kaj bazita sur tiu de
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
Ĉu ekzistas
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.
Linio 25:
== MST sur plenaj grafeoj ==
Jam estas montrita far J.
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.
Linio 62:
Rilata grafeo estas la [[K-minimuma branĉanta arbo|''k''-minimuma generanta arbo]] (''k''-MST) kiu estas la arbo kiu generas iun subaron de ''k'' verticoj en la grafeo kun minimuma pezo.
Geometrie rilata problemo estas la
== Referencoj ==
* [http://citeseer.ist.psu.edu/nesetril00otakar.html Otakar Boruvka sur Minimumo Branĉanta Arba Problemo (traduko de la ambaŭ paperoj de 1926, komentoj, historio) (2000) Jaroslav Nesetril, Evo Milková, Helena Nesetrilová] (sekcio 7 donas lian algoritmon, kiu aspektas kiel mikso inter tiu de Prim kaj tiu de Kruskal)
| |||