Minimuma generanta arbo

La minimuma branĉanta arbo de ebena grafeo. Ĉiu branĉo estas etikedita kun ĝia pezo, kiu ĉi tie malfajne egalas sian longon.

Donita koneksa, sendirekta grafeo, branĉanta arbo de tiu grafeo estas subgrafeo kiu estas arbo kaj kunkonektas ĉiujn verticojn. Sola grafeo povas havi multajn malsamajn branĉantajn arbojn. On povas ankaŭ asigni pezon al ĉiu 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 grafeo prezentanta 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.

En la kazo se de egalpezo, povus esti kelkaj minimumaj branĉantaj arboj; precipe, se ĉiuj pezoj samas, ĉiu branĉanta arbo estas minimumo. Tamen, unu teoremo diras, ke se ĉiu branĉo havas klaran pezon, la minimuma branĉanta arbo estas unika. Tio estas vera en multaj realismaj situacioj, kiel tiu pli supre, kie estas malverŝajne ke iuj ajn du vojoj havas ĝuste la saman koston. Ĉi tiu ankaŭ ĝeneraliĝas al branĉantaj arbaroj.

Minimuma branĉanta arbo estas fakte la minimum-kostaj subgrafeaj trakonektantaj ĉiuj verticoj, ĉar subgrafeoj enhavantaj ciklojn necese havas pli tuteca pezo.

Algoritmoj

La unua algoritmo por trovi minimuman branĉantan arbon estis ellaborita 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 avaraj algoritmoj, kiuj ruliĝas en polinoma tempo, do la problemo trovi tiajn arbojn estas en P.

La plej rapida minimuma branĉanta arba algoritmo ĝis nun estis ellaborita fare de Bernard Chazelle, kaj bazita sur tiu de Borůvka. Ĝia rultempo estas 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 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 algoritmoj estas sciataj kun lineara rultempo, O(m). Por ĝeneralaj pezoj, hazardigitaj algoritmoj estas sciataj, kies atendita rultempo estas lineara.

Ĉu ekzistas determinisma algoritmo kun lineara rultempo por ĝeneralaj pezoj estas ankoraŭ malfermita demando. Tamen, Set Pettie kaj Vijaya Ramachandran havi fundamenti verŝajne optimalan determinisman minimuman branĉantan arban algoritmon, la komputa komplikeco de kiu estas nekonata. [1]

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.[2] 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 eksteraj memoraj algoritmoj, ekzemple kiel priskribitaj en "Inĝenierada Ekstera Memora Minimumo Branĉanta Arba Algoritmo" fare de Roma Dementiev k.a.,[3] Arkivigite je 2008-01-30 per la retarkivo Wayback Machine 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 fare de J. Michael Steele bazite sur laboro fare de A. M. Frieze, ke por donita plena grafeo sur n verticoj, kun latero-pezoj elektitaj de kontinua hazarda distribuo f tia, ke $f'(0)>0$, kiam n proksimiĝas al malfinio la amplekso de la MST proksimiĝas al $\zeta (3)/f'(0)$, kie $\zeta$ estas la rimana ζ funkcio.

Por uniformaj hazardaj pezoj en $[0,1]$, la ĝusta atendita amplekso de la minimuma branĉanta arbo estas komputita por malgrandaj plenaj grafeoj.

Verticoj	Atendita amplekso
2	1/2
3	3/4
4	31/35
5	893/924
6	278/273
7	30739/29172
8	199462271/184848378
9	126510063932/115228853025

Rilataj problemoj

Rilata grafeo estas la 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 eŭklida minimuma branĉanta arbo.

Referencoj

• Otakar Boruvka sur Minimumo Branĉanta Arba Problemo (traduko de la ambaŭ paperoj de 1926, komentoj, historio) (2000) Jaroslav Nesetril, Evo Milková, Helena Nesetrilová Arkivigite je 2008-05-04 per la retarkivo Wayback Machine (sekcio 7 donas lian algoritmon, kiu aspektas kiel mikso inter tiu de Prim kaj tiu de Kruskal)
• Minimuma Branĉanta Arba Algoritmo kun Inverso-Ackermann-a Tipa Komplekseco, Bernard Chazelle, 1999
• [4] Arkivigite je 2006-09-02 per la retarkivo Wayback Machine
• Tomaso H. Cormen, Karlo E. Leiserson, Ronald L. Rivest, kaj Clifford Stein. Enkonduko al Algoritmoj, Dua Redakto. MIT Press kaj McGraw-Hill, 2001. ISBN 0-262-03293-7. Ĉapitro 23: Minimumo Generantaj Arboj, pp.561–579.