Vizualizare sursă pentru „Arbore minim de acoperire”

[[Fișier:Minimum_spanning_tree.svg|dreapta|miniatura|300x300px| Un [[graf planar]] și arborele său minim de acoperire. Fiecare muchie este etichetată cu ponderea sa, care aici este aproximativ proporțională cu lungimea sa.]]
Un '''arbore minim de acoperire''' sau un '''arbore de acoperire de pondere minimă''' este o [[submulțime]] a muchiilor unui graf neorientat [[conexitate (teoria grafurilor)|conex]] cu muchii ponderate, care toate [[nod (teoria grafurilor)|nodurile]] între ele, fără [[Ciclu (teoria grafurilor)|cicluri]] și cu ponderea totală a muchiilor minimă. Adică este un {{Ill-wd|Q831672|3=arbore de acoperire}} a cărui sumă a ponderilor muchiilor este cât mai mică posibil. Mai general, orice graf neorientat cu muchii ponderate (nu neapărat conex) are o '''pădure minimă de acoperire''', care este o reuniune a arborilor minimi de acoperire ai [[Componentă conexă|componentelor sale conexe]].

Există multe cazuri de utilizare pentru arborii minimi de acoperire. Un exemplu este o companie de telecomunicații care încearcă să întindă cabluri într-un cartier nou. Dacă este constrânsă să îngroape cablurile numai de-a lungul anumitor căi (de exemplu, străzi), atunci ar exista un graf care conține punctele (de exemplu, case) conectate de acele căi. Unele dintre căi ar putea fi mai costisitoare, deoarece sunt mai lungi sau necesită îngroparea cablului mai adânc; aceste căi ar fi reprezentate de muchii cu ponderi mai mari. Costul monetar este o unitate acceptabilă pentru ponderea muchiei{{Mdash}} nu este nevoie ca lungimile muchiilor să respecte regulile normale de [[geometrie]], cum ar fi [[inegalitatea triunghiului]]. Un ''arbore de acoperire'' pentru acel graf ar fi un subgrup al acelor căi care nu are cicluri, dar conectează totuși fiecare casă; ar putea exista mai mulți arbori de acoperire. Un ''arbore minim de acoperire'' ar fi unul cu cel mai mic cost total, reprezentând calea cea mai puțin costisitoare pentru așezarea cablurilor.

== Proprietăți ==

=== Posibilă multiplicitate ===
Dacă există {{Mvar|n}} noduri în graf, atunci fiecare arbore de acoperire are {{Math|''n'' − 1}} muchii.
[[Fișier:Multiple_minimum_spanning_trees.svg|miniatura| Această figură arată că poate exista mai mult de un singur arbore minim de acoperire într-un graf. În figură, cei doi arbori de sub graf sunt două variante de arbore minim de acoperire al grafului dat.]]
Pot exista mai mulți arbori minimi de acoperire cu aceeași pondere totală; în special, dacă toate ponderile muchiilor unui graf sunt aceleași, atunci toți arborii de acoperire ai grafului sunt și minimi.

=== Unicitate ===
''Dacă fiecare muchie are o pondere distinctă, atunci va exista un arbore minim de acoperire unic''. Acest lucru este adevărat în multe situații realiste, cum ar fi exemplul companiei de telecomunicații de mai sus, în care este puțin probabil ca două căi să aibă ''exact'' același cost. Acest lucru se generalizează și la păduri de acoperire.

Demonstrație:

# {{Ill-wd|Q184899|3=Să presupunem contrariul}}, că există doi AMA diferiți {{Math|''A''}} și {{Math|''B''}}''.''
# Deoarece {{Math|''A''}} și {{Math|''B''}} diferă, deși conțin aceleași noduri, există cel puțin o muchie care aparține unuia, dar nu celuilalt. Dintre astfel de muchii, fie {{Math|''e''<sub>1</sub>}} cea cu cea mai mică pondere; această alegere este unică, deoarece ponderile muchiilor sunt toate distincte. Fără pierderea generalității, să presupunem că {{Math|''e''<sub>1</sub>}} este în ''A.''
# Deoarece ''B'' este un AMA, {{Math|{ ''e''<sub>1</sub> } ∪ ''B''}} trebuie să conțină un ciclu {{Math|''C''}} avându-l pe {{Math|''e''<sub>1</sub>}}.
# Ca arbore, {{Math|''A''}} nu conține cicluri, prin urmare {{Math|''C''}} trebuie să aibă o muchie {{Math|''e''<sub>2</sub>}} care nu este în {{Math|''A''}}''.''
# Din moment ce {{Math|''e''<sub>1</sub>}} a fost aleasă ca muchia unică cu cea mai mică pondere printre cele care aparțin exact unuia dintre {{Math|''A''}} și {{Math|''B''}}'','' ponderea lui {{Math|''e''<sub>2</sub>}} trebuie să fie mai mare decât ponderea lui {{Math|''e''<sub>1</sub>}}<sub>.</sub>
# Deoarece {{Math|''e''<sub>1</sub>}} și {{Math|''e''<sub>2</sub>}} fac parte din ciclul {{Math|''C''}}, înlocuirea lui {{Math|''e''<sub>2</sub>}} cu {{Math|''e''<sub>1</sub>}} în {{Math|''B''}} produce un arbore de acoperire cu ponderea mai mică.
# Acest lucru contrazice presupunerea că {{Math|''B''}} este un AMA.

Mai general, dacă ponderile muchiilor nu sunt toate distincte, atunci doar (multi-)mulțimea ponderilor din arborele minim de acoperire este cu siguranță unică; la fel pentru toți arborii minimi de acoperire.<ref>{{Citat web|url=https://cs.stackexchange.com/q/2204|titlu=Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?|accessdate=4 April 2018|lucrare=cs.stackexchange.com}}</ref>

=== Subgraful de cost minim ===
Dacă ponderile sunt ''pozitive'', atunci un arbore minim de acoperire este de fapt un [[Glosar de teoria grafurilor|subgraf]] de cost minim care acoperă toate vârfurile, deoarece subgrafurile care conțin [[Drum (teoria grafurilor)|cicluri]] au obligatoriu o pondere totală mai mare decât un arbore. În schimb, dacă există ponderi negative, atunci un ciclu conținând o muchie de pondere negativă poate reduce ponderea totală a subgrafului de acoperire, și îl poate astfel face să aibă cost mai mic decât AMA.

=== Proprietatea de ciclu ===
''Pentru orice ciclu {{Math|C}} din graf, dacă ponderea unei muchii {{Math|e}} lui {{Math|C}} este mai mare decât ponderile individuale ale tuturor celorlalte muchii ale lui {{Math|C}}, atunci această muchie nu poate aparține unui AMA.''

Demonstrație: {{Ill-wd|Q184899|3=presupunem contrariul}}, adică presupunem că {{Math|e}} aparține unui AMA {{Math|T<sub>1</sub>}} . Atunci, ștergerea lui {{Math|e}} va împărți {{Math|T<sub>1</sub>}} în doi subarbori cu două capete ale lui {{Math|e}} aflate în subarbori diferiți. Restul de {{Math|C}} reconectează subarborii, prin urmare există o muchie {{Math|f}} a lui {{Math|C}} cu capete în subarbori diferiți, adică ea reconectează subarborii într-un arbore {{Math|T<sub>2</sub>}} cu pondere mai mică decât cea a lui {{Math|T<sub>1</sub>}}, deoarece ponderea lui {{Math|f}} este mai mică decât ponderea lui {{Math|e}}.

=== Proprietatea de tăietură ===
[[Fișier:Msp-the-cut-correct.svg|miniatura|400x400px| Această figură arată proprietatea de tăietură a AMA-urilor. T este singurul AMA al grafului dat. Dacă S = {A, B, D, E}, deci VS = {C, F}, atunci există 3 posibilități ale muchiei de-a lungul tăierii (S, V-S), anume muchiile BC, EC, EF ale grafului originar. Atunci, e este una dintre muchiile de pondere minimă pentru tăiere, prin urmare S ∪ {e} face parte din AMA T.]]
''Pentru orice {{Ill-wd|Q1626444|3=tăietură}}'' C ''a grafului, dacă ponderea unei muchii'' e ''în mulțimea tăieturilor lui'' C ''este strict mai mică decât ponderile tuturor celorlalte muchii din mulțimea de tăieturi ale lui'' C'', atunci această muchie aparține tuturor AMA-urilor grafului.''

Demonstrație: [[Argumentum ad absurdum|Presupunem]] că există un AMA ''T'' care nu conține ''e''. Adăugarea lui ''e'' la ''T'' va produce deci un ciclu care traversează tăietura o dată în ''e'' și se întoarce la o altă muchie ''e'<nowiki/>'' . Ștergând ''e''' obținem un arbore de acoperire ''T∖{e'} ∪ {e}'' cu pondere strict mai mică decât ''T.'' Acest lucru contrazice presupunerea că ''T'' este un AMA.

Printr-un argument similar, dacă mai mult de o margine are ponderea minimă pe o tăietură, atunci fiecare astfel de muchie este conținută într-un arbore minim de acoperire.

=== Muchia de cost minim ===
''Dacă muchia de cost minim'' e ''a unui graf este unică, atunci această muchie este inclusă în orice AMA.''

Demonstrație: dacă ''e'' nu ar fi inclus în AMA, eliminarea oricăror muchii (cu costuri mai mari) din ciclul format după adăugarea lui ''e'' la AMA, ar produce un arbore cu pondere mai mică.

=== Contracția ===
''Dacă T este un arbore de muchii din AMA, atunci putem'' contracta ''T într-un singur nod, menținând în același timp invariantul că AMA al grafului contractat plus T dă AMA pentru graful dinainte de contracție.<ref name="PettieRamachandran2002"/>''

== Algoritmi ==
În toți algoritmii de mai jos, ''m'' este numărul de muchii din graf și ''n'' este numărul de noduri.

=== Algoritmi clasici ===
Primul algoritm pentru găsirea unui arbore minim de acoperire a fost dezvoltat de omul de știință ceh {{Ill-wd|Q725806|3=Otakar Borůvka}} în 1926 ([[algoritmul lui Borůvka]]). Scopul său era o acoperire electrică eficientă a [[Moravia|Moraviei]]. Algoritmul se derulează într-o succesiune de etape. În fiecare etapă, numită ''pas Boruvka'', el identifică o pădure ''F'' constând din muchia de pondere minimă incidentă fiecărui nod din graful ''G'', apoi formează graful {{Tmath|1=G_1=G\setminus F}} ca intrare la pasul următor. Aici, cu {{Tmath|G\setminus F}} se notează graful derivat din ''G'' prin contractarea muchiilor din ''F'' (prin proprietatea de tăiere, aceste muchii aparțin AMA). Fiecare pas Boruvka necesită timp liniar. Deoarece numărul de muchii este redus cu cel puțin jumătate la fiecare pas, algoritmul lui Boruvka are complexitatea în timp O(''m'' log ''n'').<ref name="PettieRamachandran2002"/>

Un al doilea algoritm este [[algoritmul lui Prim]], care a fost inventat de {{Ill-wd|Q730209|3=Vojtěch Jarník}} în 1930 și redescoperit de {{Ill-wd|Q92939|3=Prim}} în 1957 și [[Edsger Dijkstra|Dijkstra]] în 1959. Practic, el crește AMA (''T'') muchie cu muchie. Inițial, ''T'' conține un nod arbitrar. În fiecare etapă, ''T'' este mărit cu o muchie cu cea mai mică pondere (''x'', ''y'') astfel încât ''x'' este în ''T'' și ''y'' nu este încă în ''T.'' Prin proprietatea de tăiere, toate muchiile adăugate la ''T'' se află în AMA. Durata sa de rulare este fie O (''m'' log ''n''), fie O (''m'' + ''n'' log ''n''), în funcție de structurile de date utilizate.

Un al treilea algoritm utilizat în mod obișnuit este [[algoritmul lui Kruskal]], care rulează tot în timp O(''m'' log ''n'').

Un al patrulea algoritm, nu la fel de frecvent utilizat, este {{Ill-wd|Q4925151|3=algoritmul de ștergere inversă}}, care este inversul algoritmului lui Kruskal. Timpul său de rulare este O(''m'' log ''n'' (log log ''n'')<sup>3</sup>).

Toți acești patru sunt [[Algoritm greedy|algoritmi greedy]]. Deoarece rulează în timp polinomial, problema găsirii unor astfel de arbori este în clasa de complexitate '''[[FP (clasă de complexitate)|FP]]''' și {{Ill-wd|Q3262192|3=problemele de decizie}} conexe, cum ar fi determinarea dacă o anumită muchie este în AMA sau determinarea dacă ponderea totală minimă depășește o anumită valoare sunt în '''[[P (teoria complexității)|P]].'''

=== Algoritmi mai rapizi ===
Mai mulți cercetători au încercat să găsească algoritmi mai eficienți din punct de vedere al calculului.

Într-un model comparativ, în care singurele operații permise pe ponderile muchiilor sunt comparațiile în perechi, Karger, Klein & Tarjan (1995) au găsit un {{Ill-wd|Q5420845|3=algoritm randomizat în timp liniar}} bazat pe o combinație între algoritmul lui Borůvka și algoritmul de ștergere inversă.<ref>{{Citation|last=Karger|first=David R.|title=A randomized linear-time algorithm to find minimum spanning trees|volume=42|issue=2|pages=321–328|year=1995|periodical={{Ill-wd|Q1709878|3=Journal of the Association for Computing Machinery}}|doi=10.1145/201019.201022|mr=1409738|last2=Klein|first2=Philip N.|last3=Tarjan|first3=Robert E.|author-link=David Karger|author-link3=Robert Tarjan}}</ref><ref>{{Citation|last=Pettie|first=Seth|title=Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02)|url=http://portal.acm.org/citation.cfm?id=545477|pages=713–722|year=2002|contribution=Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms|place=San Francisco, California|last2=Ramachandran|first2=Vijaya|author-link2=Vijaya Ramachandran}}.</ref>

Cel mai rapid algoritm nerandomizat bazat pe comparații, cu complexitate cunoscută, al lui {{Ill-wd|Q892115|3=Bernard Chazelle}}, se bazează pe [[Heap moale|heap-ul soft]], o coadă cu prioritate aproximativă.<ref name="Chazelle2000">{{Citation|last=Chazelle|first=Bernard|title=A minimum spanning tree algorithm with inverse-Ackermann type complexity|volume=47|issue=6|pages=1028–1047|year=2000|periodical={{Ill-wd|Q1709878|3=Journal of the Association for Computing Machinery}}|doi=10.1145/355541.355562|mr=1866456|author-link=Bernard Chazelle}}.</ref><ref>{{Citation|last=Chazelle|first=Bernard|title=The soft heap: an approximate priority queue with optimal error rate|url=http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf|volume=47|issue=6|pages=1012–1027|year=2000|periodical={{Ill-wd|Q1709878|3=Journal of the Association for Computing Machinery}}|doi=10.1145/355541.355554|mr=1866455|author-link=Bernard Chazelle|access-date=2021-10-15|archive-date=2017-08-08|archive-url=https://web.archive.org/web/20170808100539/http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf|dead-url=yes}}.</ref> Durata sa de rulare este ''[[Notația Big O|O]]''(''m''&nbsp;α(''m'', ''n'')), unde α este {{Ill-wd|Q341835|3=inversul funcțional clasic al funcției Ackermann}}. Funcția α crește extrem de lent, astfel încât, în toate scopurile practice, poate fi considerată o constantă nu mai mare de 4; astfel, algoritmul lui Chazelle rulează foarte aproape de timpul liniar.

=== Algoritmi în timp liniar pentru cazuri speciale ===

==== Grafuri dense ====
Dacă graful este dens (adică ''m'' / ''n'' ≥ log log log ''n''), atunci un algoritm determinist conceput de Fredman și Tarjan găsește AMA într-un timp O(''m'').<ref>{{Citat revistă|nume=Fredman|nume2=Tarjan|prenume=M. L.|prenume2=R. E.|an=1987|titlu=Fibonacci heaps and their uses in improved network optimization algorithms|journal=Journal of the ACM|volum=34|număr=3|pagini=596|doi=10.1145/28869.28874}}</ref> Algoritmul execută o serie de faze. Fiecare fază execută [[algoritmul lui Prim]] de multe ori, de fiecare dată pentru un număr limitat de pași. Durata fiecărei faze este O(''m''+''n''). Dacă numărul de vârfuri înainte de o fază este {{Math|''n&#39;''}}, numărul de noduri rămase după o fază este cel mult {{Math|''m&#39; / 2<sup>m/n&#39;</sup>''}} . Prin urmare, sunt necesare cel mult {{Math|log* ''n''}} faze, ceea ce oferă un timp de rulare liniar pentru grafuri dense.<ref name="PettieRamachandran2002">{{Citation|last=Pettie|first=Seth|title=An optimal minimum spanning tree algorithm|url=https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf|volume=49|issue=1|pages=16–34|year=2002|periodical={{Ill-wd|Q1709878|3=Journal of the Association for Computing Machinery}}|doi=10.1145/505241.505243|mr=2148431|last2=Ramachandran|first2=Vijaya}}.</ref>

Există și alți algoritmi care funcționează în timp liniar pe grafuri dense.<ref name="Chazelle2000"/><ref>{{Citat revistă|nume=Gabow|nume2=Galil|nume3=Spencer|nume4=Tarjan|prenume=H. N.|prenume2=Z.|prenume3=T.|prenume4=R. E.|legătură-autor=Harold N. Gabow|an=1986|titlu=Efficient algorithms for finding minimum spanning trees in undirected and directed graphs|journal=Combinatorica|volum=6|număr=2|pagini=109|doi=10.1007/bf02579168}}</ref>

==== Ponderi întregi ====
Dacă ponderile muchiilor sunt numere întregi reprezentate în binar, atunci se cunosc algoritmi determiniști care rezolvă problema în ''O''(''m''&nbsp;+&nbsp;''n'') operații cu întregi.<ref>{{Citation|last=Fredman|first=M. L.|title=Trans-dichotomous algorithms for minimum spanning trees and shortest paths|volume=48|issue=3|pages=533–551|year=1994|periodical={{Ill-wd|Q6295014|3=Journal of Computer and System Sciences}}|doi=10.1016/S0022-0000(05)80064-9|mr=1279413|last2=Willard|first2=D. E.|author-link=Michael Fredman|author-link2=Dan Willard}}.</ref> Rămâne deschisă întrebarea dacă problema poate fi rezolvată ''determinist'' pentru un ''graf general'' în ''timp liniar'' printr-un algoritm bazat pe comparații.

=== Arborii de decizie ===
Dat fiind graful ''G'' în care nodurile și muchiile sunt fixe, dar ponderile sunt necunoscute, este posibil să se construiască un {{Ill-wd|Q831366|3=arbore de decizie}} (AD) binar pentru calcularea AMA pentru orice permutare a ponderilor. Fiecare nod intern din AD conține o comparație între două muchii, de exemplu „ponderea muchiei dintre ''x'' și ''y'' este mai mare decât ponderea muchiei dintre ''w'' și ''z'' ?”. Cei doi copii ai nodului corespund celor două posibile răspunsuri „da” sau „nu”. În fiecare frunză din AD, există o listă de muchii din ''G'' care corespund unui AMA. Complexitatea de rulare a unui AD este cel mai mare număr de interogări necesare pentru a găsi AMA, care este doar adâncimea AD. Un AD pentru un graf ''G'' se numește ''optim'' dacă are cea mai mică adâncime dintre toate AD-urile corecte pentru ''G.''

Oricare ar fi un număr întreg ''r'', se pot găsi arbori de decizie optimi pentru toate grafurile pe ''r'' muchii prin {{Ill-wd|Q850362|3=căutarea cu forță brută}}. Această căutare se desfășoară în doi pași.

'''A. Generarea tuturor AD potențiali'''

* Sunt <math>2^{r \choose 2}</math> grafuri diferite pe ''r'' noduri''.''
* Pentru orice graf, un AMA poate fi întotdeauna găsit folosind ''r''(''r−''1), de exemplu, prin [[algoritmul lui Prim]].
* Prin urmare, adâncimea unui AD optim este mai mică decât {{Math|''r<sup>2</sup>''}}.
* Prin urmare, numărul de noduri interne într-un AD optim este mai mic decât <math>2^{r^2}</math>.
* Fiecare nod intern compară două muchii. Numărul muchiilor este cel mult {{Math|''r<sup>2</sup>''}} deci numărul diferit de comparații este cel mult {{Math|''r<sup>4</sup>''}}.
* Prin urmare, numărul AD-ilor potențiali este mai mic decât: <math>{(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}</math> .

'''B. Identificarea AD-ilor corecți'''. Pentru a verifica dacă un AD este corect, trebuie verificat pe toate permutările posibile ale ponderilor muchiilor.

* Numărul acestor permutări este cel mult {{Math|(''r<sup>2</sup>'')!}}.
* Pentru fiecare permutare, se rezolvă problema AMA pe graful dat folosind orice algoritm existent și se compară rezultatul cu răspunsul dat de AD.
* Timpul de funcționare al oricărui algoritm AMA este cel mult {{Math|''r<sup>2</sup>''}}, deci timpul total necesar pentru verificarea tuturor permutărilor este cel mult <math>(r^2+1)!</math>.

Prin urmare, timpul total necesar pentru găsirea unui AD optim pentru ''toate'' grafurile cu ''r'' noduri este: <math>2^{r \choose 2} \cdot r^{2^{(r^2+2)}} \cdot (r^2+1)!</math>, care este mai mic decât: <math>2^{2^{r^2+o(r)}}</math>.<ref name="PettieRamachandran2002"/>

=== Algoritm optim ===
Seth Pettie și Vijaya Ramachandran au găsit un algoritm determinist, demonstrabil optim, pe bază de comparații, pentru arborele minim de acoperire.<ref name="PettieRamachandran2002"/> Mai jos este o descriere simplificată a algoritmului.

# Fie <math>r = \log \log \log n</math>, unde {{Math|''n''}} este numărul de noduri. Se găsesc toți arborii de decizie optimi pe ''r'' noduri''.'' Acest lucru se poate face în timp O(''n'').
# Se împarte graful în componente cu cel mult ''r'' noduri în fiecare componentă. Această partiție folosește un {{Ill-wd|Q7553986|3=heap soft}}, care „corupe” un număr mic de muchii ale grafului.
# Se utilizează arborii de decizie optimi pentru a găsi un AMA pentru subgraful necorupt din cadrul fiecărei componente.
# Se contractă fiecare componentă conectată parcursă de AMA la un singur nod și se aplică orice algoritm care funcționează pe grafuri dense în timp O(''m'') asupra contracției subgrafului necorupt.
# Se adaugă înapoi muchiile corupte în pădurea rezultată pentru a forma un subgraf garantat să conțină arborele minim de acoperire și mai mic cu un factor constant decât graful de pornire. Se aplică algoritmul optim recursiv pe acest graf.

Timpul de rulare al tuturor pașilor din algoritm este O(''m''), ''cu excepția pasului de utilizare a arborilor de decizie''. Timpul de rulare al acestui pas este necunoscut, dar s-a dovedit că este optim{{Mdash}} niciun algoritm nu poate performa mai bine decât arborele decizional optim. Astfel, acest algoritm are proprietatea particulară că este în ''demonstrabil optim,'' deși complexitatea sa de rulare este ''necunoscută''.

=== Algoritmi paraleli și distribuiți ===
Cercetările au luat în considerare și [[Algoritmi de calcul paralel|algoritmi paraleli]] pentru problema arborelui minim. Cu un număr liniar de procesoare, se poate rezolva problema în timp {{Math|''O''(log ''n'')}}.<ref>{{Citation|last=Chong|first=Ka Wong|title=Concurrent threads and optimal parallel minimum spanning trees algorithm|volume=48|issue=2|pages=297–323|year=2001|periodical={{Ill-wd|Q1709878|3=Journal of the Association for Computing Machinery}}|doi=10.1145/375827.375847|mr=1868718|last2=Han|first2=Yijie|last3=Lam|first3=Tak Wah}}.</ref><ref>{{Citation|last=Pettie|first=Seth|title=A randomized time-work optimal parallel algorithm for finding a minimum spanning forest|url=http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf|volume=31|issue=6|pages=1879–1895|year=2002|periodical={{Ill-wd|Q7390263|3=SIAM Journal on Computing}}|doi=10.1137/S0097539700371065|mr=1954882|last2=Ramachandran|first2=Vijaya}}.</ref> Bader & Cong (2006) demonstrează un algoritm care poate calcula AMA de 5 ori mai rapid pe 8 procesoare decât un algoritm secvențial optimizat.<ref>{{Citation|last=Bader|first=David A.|title=Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs|volume=66|issue=11|pages=1366–1378|year=2006|periodical=Journal of Parallel and Distributed Computing|doi=10.1016/j.jpdc.2006.06.001|last2=Cong|first2=Guojing|author-link=David A. Bader}}.</ref>

Alți algoritmi specializați au fost proiectați pentru calcularea arborilor minimi de acoperire ai unui graf atât de mare încât majoritatea acestuia trebuie stocată pe disc în orice moment. Acești ''algoritmi de stocare externă'', de exemplu, așa cum sunt descriși în „Engineering an External Memory Minimum Spanning Tree Algorithm” de Roman, Dementiev și colab.,<ref>{{Citation|last=Dementiev|first=Roman|title=Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004)|url=http://algo2.iti.kit.edu/dementiev/files/emst.pdf|pages=195–208|year=2004|contribution=Engineering an external memory minimum spanning tree algorithm|last2=Sanders|first2=Peter|last3=Schultes|first3=Dominik|last4=Sibeyn|first4=Jop F.|access-date=2021-10-15|archive-date=2011-08-09|archive-url=https://web.archive.org/web/20110809075049/http://algo2.iti.kit.edu/dementiev/files/emst.pdf|dead-url=yes}}.</ref> pot funcționa, conform afirmațiilor autorilor, de doar 2 până la 5 ori mai lent decât un tradițional algoritm în memorie. Se bazează pe {{Ill-wd|Q209687|3=algoritmi de sortare a stocării externe}} eficiente și pe {{Ill-wd|Q1397646|3=tehnici de contracție a graurilor}} pentru reducerea eficientă a dimensiunii graficului.

Problema poate fi abordată și într-o [[Calcul distribuit|manieră distribuită]]. Dacă fiecare nod este considerat un computer și niciun nod nu știe nimic în afară de propriile legături conectate, se poate calcula totuși {{Ill-wd|Q5283163|3=arborele minim de acoperire distribuit}}.

== AMA pe grafuri complete ==
{{Ill-wd|Q4707185|3=Alan M. Frieze}} a demonstrat că, dat fiind un [[Graf complet|grafic complet]] de ''n'' noduri, cu muchiile având ca ponderi variabile aleatoare independente distribuite identic, având funcția de distribuție {{Math|''F''}} cu proprietatea că {{Math|''F&#39;''(0) > 0}}, apoi pe măsură ce ''n se'' apropie de {{Ill-wd|Q2039387|3=+ ∞}}, se apropie de ponderea așteptată a AMA <math>\zeta(3)/F'(0)</math>, Unde <math>\zeta</math> este [[funcția zeta Riemann]] (mai exact este <math>\zeta(3)</math> {{Ill-wd|Q622682|3=Constanta lui Apéry}}). Frieze și {{Ill-wd|Q11104994|3=Steele}} au demonstrat și convergența probabilității. {{Ill-wd|Q4181206|3=Svante Janson}} a demonstrat o {{Ill-wd|Q190391|3=teoremă limită centrală}} pentru ponderea AMA.

Pentru ponderi aleatorii uniforme în intervalul <math>[0,1]</math>, dimensiunea exactă așteptată a arborelui minim de acoperire a fost calculată pentru grafuri complete mici. <ref>{{Citation|last=Steele|first=J. Michael|title=Mathematics and computer science, II (Versailles, 2002)|pages=223–245|year=2002|series=Trends Math.|contribution=Minimal spanning trees for graphs with random edge lengths|place=Basel|publisher=Birkhäuser|mr=1940139|author-link=J. Michael Steele}}</ref>
{| class="wikitable"
!Noduri
! Dimensiunea așteptată
! Dimensiunea estimată aproximativă
|-
| 2
| 1/2
| 0,5
|-
| 3
| 3/4
| 0,75
|-
| 4
| 31/35
| 0,8857143
|-
| 5
| 893/924
| 0,9664502
|-
| 6
| 278/273
| 1.0183151
|-
| 7
| 30739/29172
| 1,053716
|-
| 8
| 199462271/184848378
| 1.0790588
|-
| 9
| 126510063932/115228853025
| 1.0979027
|}

== Aplicații ==
Arborii minimi de acoperire au aplicații directe în proiectarea rețelelor, inclusiv a [[Rețea de calculatoare|rețelelor de calculatoare]], {{Ill-wd|Q1068715|3=de telecomunicații}}, {{Ill-wd|Q924286|3=de transport}}, {{Ill-wd|Q625083|3=de alimentare cu apă}} și [[Rețea electrică|rețele electrice]] (pentru care au fost inventate pentru prima dată, așa cum s-a menționat mai sus).<ref>{{Citation|last=Graham|first=R. L.|title=On the history of the minimum spanning tree problem|volume=7|issue=1|pages=43–57|year=1985|periodical=Annals of the History of Computing|doi=10.1109/MAHC.1985.10011|mr=783327|last2=Hell|first2=Pavol|author-link=Ronald Graham|author-link2=Pavol Hell}}</ref> Ele sunt invocate ca subrutine în algoritmi pentru alte probleme, inclusiv în [[algoritmul Christofides]] pentru aproximarea [[Problema comis-voiajorului|problemei comis-voiajorului]],<ref>[[Nicos Christofides]], [https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf Worst-case analysis of a new heuristic for the travelling salesman problem] {{Webarchive|url=https://web.archive.org/web/20190721172134/https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|date=2019-07-21}}, Report 388, Graduate School of Industrial Administration, CMU, 1976.</ref> aproximând problema decupării minime multi-terminal (care este echivalentă în cazul unui singur terminal cu {{Ill-wd|Q2585642|3=problema fluxului maxim}}),<ref>{{Citat revistă|nume=Dahlhaus|nume2=Johnson|nume3=Papadimitriou|nume4=Seymour|nume5=Yannakakis|prenume=E.|prenume2=D. S.|prenume3=C. H.|prenume4=P. D.|prenume5=M.|legătură-autor2=David S. Johnson|legătură-autor3=Christos Papadimitriou|legătură-autor4=Paul Seymour (mathematician)|legătură-autor5=Mihalis Yannakakis|dată=August 1994|titlu=The complexity of multiterminal cuts|urlarhivă=https://web.archive.org/web/20040824184059/http://akpublic.research.att.com/~dsj/papers/3way.pdf|url=http://akpublic.research.att.com/~dsj/papers/3way.pdf|journal={{Ill-wd|Q7390263|3=SIAM Journal on Computing}}|volum=23|număr=4|pagini=864–894|doi=10.1137/S0097539792225297|access-date=17 December 2012|archive-date=24 August 2004}}</ref> și pentru aproximarea cuplajului perfect ponderat de cost minim.<ref>{{Cite conference|last=Supowit|last2=Plaisted|last3=Reingold|given=Kenneth J.|first2=David A.|first3=Edward M.|year=1980|conference=12th Annual ACM Symposium on Theory of Computing (STOC '80)|pages=398–419|title=Heuristics for weighted perfect matching|url=http://dl.acm.org/citation.cfm?id=804689|location=New York, NY, USA|publisher=ACM|doi=10.1145/800141.804689}}</ref>

Printre alte aplicații practice bazate pe arbori minimi de acoperire se numără:

* [[Taxonomie|Taxonomia]].<ref>{{Citat revistă|nume=Sneath|prenume=P. H. A.|dată=1 August 1957|titlu=The Application of Computers to Taxonomy|journal=Journal of General Microbiology|volum=17|număr=1|pagini=201–226|pmid=13475686|doi=10.1099/00221287-17-1-201}}</ref>
* Analiza de cluster: clustere de puncte în plan,<ref>{{Cite conference|last=Asano|last2=Bhattacharya|last3=Keil|last4=Yao|given=T.|first2=B.|first3=M.|first4=F.|author-link=Tetsuo Asano|author4-link=Frances Yao|year=1988|conference=Fourth Annual Symposium on Computational Geometry (SCG '88)|volume=1|pages=252–257|title=Clustering algorithms based on minimum and maximum spanning trees|doi=10.1145/73393.73419}}</ref> clustering o singură legătură (o metodă de clusterizare ierarhică),<ref>{{Citat revistă|nume=Gower|nume2=Ross|prenume=J. C.|prenume2=G. J. S.|an=1969|titlu=Minimum Spanning Trees and Single Linkage Cluster Analysis|serie=C (Applied Statistics)|journal=Journal of the Royal Statistical Society|volum=18|număr=1|pagini=54–64|jstor=2346439|doi=10.2307/2346439}}</ref> clustering graf-teoretic, <ref>{{Citat revistă|nume=Päivinen|prenume=Niina|dată=1 May 2005|titlu=Clustering with a minimum spanning tree of scale-free-like structure|journal=Pattern Recognition Letters|volum=26|număr=7|pagini=921–930|doi=10.1016/j.patrec.2004.09.039}}</ref> și clusteringul datelor de [[exprimare genetică]].<ref>{{Citat revistă|nume=Xu|nume2=Olman|nume3=Xu|prenume=Y.|prenume2=V.|prenume3=D.|dată=1 April 2002|titlu=Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees|journal=Bioinformatics|volum=18|număr=4|pagini=536–545|pmid=12016051|doi=10.1093/bioinformatics/18.4.536}}</ref>
* Construirea arborilor pentru broadcast în rețele de calculatoare.<ref>{{Citat revistă|nume=Dalal|nume2=Metcalfe|prenume=Yogen K.|prenume2=Robert M.|dată=1 December 1978|titlu=Reverse path forwarding of broadcast packets|journal=Communications of the ACM|volum=21|număr=12|pagini=1040–1048|doi=10.1145/359657.359665}}</ref>
* Înregistrarea <ref>{{Cite conference|last=Ma|last2=Hero|last3=Gorman|last4=Michel|given=B.|first2=A.|first3=J.|first4=O.|year=2000|conference=International Conference on Image Processing|volume=1|pages=481–484|title=Image registration with minimum spanning tree algorithm|url=http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf|doi=10.1109/ICIP.2000.901000}}</ref> și segmentarea imaginilor<ref>P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)</ref>.
* Extragerea caracteristicilor curbilinii în vederea computerizată.<ref>{{Citat revistă|nume=Suk|nume2=Song|prenume=Minsoo|prenume2=Ohyoung|dată=1 June 1984|titlu=Curvilinear feature extraction using minimum spanning trees|journal=Computer Vision, Graphics, and Image Processing|volum=26|număr=3|pagini=400–411|doi=10.1016/0734-189X(84)90221-4}}</ref>
* Recunoașterea scrisului de mână cu expresii matematice.<ref>{{Citat carte|nume=Tapia|prenume=Ernesto|nume2=Rojas|prenume2=Raúl|titlu=Graphics Recognition. Recent Advances and Perspectives|serie=Lecture Notes in Computer Science|volum=3088|an=2004|editură=Springer-Verlag|capitol=Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance|locul-publicării=Berlin Heidelberg|isbn=978-3540224785|pagini=329–340|url-capitol=http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf}}</ref>
* Proiectarea circuitelor: implementarea eficientă a multiplicărilor constante multiple, așa cum se utilizează în filtrele de răspuns finit la impuls.<ref>{{Cite conference|last=Ohlsson|given=H.|year=2004|conference=12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004)|volume=1|pages=261–264|title=Implementation of low complexity FIR filters using a minimum spanning tree|doi=10.1109/MELCON.2004.1346826}}</ref>
* Regionalizarea zonelor socio-geografice, gruparea zonelor în regiuni omogene, contigue.<ref>{{Citat revistă|nume=Assunção|nume2=M. C. Neves|nume3=G. Câmara|nume4=C. Da Costa Freitas|prenume=R. M.|an=2006|titlu=Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees|url=https://zenodo.org/record/3832352|journal=International Journal of Geographical Information Science|volum=20|număr=7|pagini=797–811|doi=10.1080/13658810600665111}}</ref>
* Compararea datelor [[Ecotoxicologie|ecotoxicologice]].<ref>{{Citat revistă|nume=Devillers|nume2=Dore|prenume=J.|prenume2=J.C.|dată=1 April 1989|titlu=Heuristic potency of the minimum spanning tree (MST) method in toxicology|journal=Ecotoxicology and Environmental Safety|volum=17|număr=2|pagini=227–235|pmid=2737116|doi=10.1016/0147-6513(89)90042-0}}</ref>
* Observabilitate topologică în sistemele de alimentare.<ref>{{Citat revistă|nume=Mori|nume2=Tsuzuki|prenume=H.|prenume2=S.|dată=1 May 1991|titlu=A fast method for topological observability analysis using a minimum spanning tree technique|journal=IEEE Transactions on Power Systems|volum=6|număr=2|pagini=491–500|bibcode=1991ITPSy...6..491M|doi=10.1109/59.76691}}</ref>
* Măsurarea omogenității materialelor bidimensionale.<ref>{{Citat revistă|nume=Filliben|nume2=Kafadar|nume3=Shier|prenume=James J.|prenume2=Karen|prenume3=Douglas R.|legătură-autor2=Karen Kafadar|dată=1 January 1983|titlu=Testing for homogeneity of two-dimensional surfaces|journal=Mathematical Modelling|volum=4|număr=2|pagini=167–189|doi=10.1016/0270-0255(83)90026-X}}</ref>
* Controlul procesului Minimax.<ref>{{Citation|last=Kalaba|first=Robert E.|title=Graph Theory and Automatic Control|url=http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf|year=1963|access-date=2021-10-15|archive-date=2017-02-18|archive-url=https://web.archive.org/web/20170218011615/http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf|dead-url=yes}}</ref>
* Arborii minimi pot fi folosiți și pentru a descrie piețele financiare.<ref>Mantegna, R. N. (1999). [[arxiv:cond-mat/9802256|Hierarchical structure in financial markets]]. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193-197.</ref><ref>Djauhari, M., & Gan, S. (2015). [https://www.researchgate.net/profile/Maman_Djauhari3/publication/277250327_Optimality_problem_of_network_topology_in_stocks_market_analysis/links/59ebdb7d4585151983cb7795/Optimality-problem-of-network-topology-in-stocks-market-analysis.pdf Optimality problem of network topology in stocks market analysis]. Physica A: Statistical Mechanics and Its Applications, 419, 108-114.</ref> O matrice de corelație poate fi creată prin calcularea unui coeficient de corelație între oricare două acțiuni. Această matrice poate fi reprezentată topologic ca o rețea complexă și se poate construi un arbore minim care să vizualizeze relațiile.

== Probleme conexe ==
{{regular_polygon_minimum_spanning_tree.svg}}Se cunoaște că problema găsirii {{Ill-wd|Q1764144|3=arborelui Steiner}} al unei submulțimi a nodurilor, adică a unui arbore minim care acoperă submulțimea dată, este [[NP-completitudine|NP-completă]].

O problemă asociată este {{Ill-wd|Q6322849|3=''k-''arborele minim de acoperire}} (''k-''AMA), care este arborele care acoperă o submulțime de ''k'' noduri din graf cu pondere minimă.

O mulțime de ''k-arbori minimi de acoperire'' este o submulțime de ''k'' arbori de acoperire (dintre toți arborii de acoperire posibili), astfel încât niciun arbore de acoperire din afara submulțimii să nu aibă o pondere mai mică.<ref>{{Citation|last=Gabow|first=Harold N.|title=Two algorithms for generating weighted spanning trees in order|volume=6|issue=1|pages=139–150|year=1977|periodical={{Ill-wd|Q7390263|3=SIAM Journal on Computing}}|doi=10.1137/0206011|mr=0441784|author-link=Harold N. Gabow}}.</ref><ref>{{Citation|last=Eppstein|first=David|title=Finding the ''k'' smallest spanning trees|volume=32|issue=2|pages=237–248|year=1992|periodical=BIT|doi=10.1007/BF01994879|mr=1172188|author-link=David Eppstein}}.</ref><ref>{{Citation|last=Frederickson|first=Greg N.|title=Ambivalent data structures for dynamic 2-edge-connectivity and ''k'' smallest spanning trees|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1888&context=cstech|volume=26|issue=2|pages=484–538|year=1997|periodical={{Ill-wd|Q7390263|3=SIAM Journal on Computing}}|doi=10.1137/S0097539792226825|mr=1438526}}.</ref> (Această problemă nu are legătură cu ''k-''arborele minim de acoperire''.'')

{{Ill-wd|Q4454941|3=Arborele minim de acoperire euclidian}} este un arbore de acoperire al unui graf, ale cărui muchii au ponderi ce corespund distanței euclidiene între nodurile care sunt puncte în plan (sau spațiu).

{{Ill-wd|Q7303185|3=Arborele de întindere minim rectiliniu}} este un arbore de acoperire al unui graf, ale cărui muchii au ponderile corespunzătoare [[Distanță Manhattan|distanței rectilinii]] între nodurile care sunt puncte în plan (sau spațiu).

În [[Calcul distribuit|modelul distribuit]], unde fiecare nod este considerat un computer și niciun nod nu știe nimic în afară de propriile legături conectate, se poate lua în considerare {{Ill-wd|Q5283163|3=arborele minim de acoperire distribuit}}. Definiția matematică a problemei este aceeași, dar există diferite abordări pentru o soluție.

{{Ill-wd|Q5034477|3=Arborele minim de acoperire capacitat}} este un arbore care are un nod marcat (origine sau rădăcină) și fiecare dintre subarborii atașați nodului conține nu mai mult de un număr ''c'' de noduri''.'' Numărul ''c'' se numește ''capacitatea arborelui''. Rezolvarea optimă a acestei probleme este [[NP-hard]],<ref>{{Citation|last=Jothi|first=Raja|title=Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design|volume=1|issue=2|pages=265–282|year=2005|periodical=ACM Trans. Algorithms|doi=10.1145/1103963.1103967|last2=Raghavachari|first2=Balaji}}</ref> dar euristicile bune, cum ar fi Esau-Williams și Sharma, produc soluții aproape de optim în timp polinomial.

{{Ill-wd|Q5251832|3=Arborele minim de acoperire cu constrângere de grad}} este un arbore minim de acoperire în care fiecare nod este conectat la cel mult ''d'' alte noduri, pentru un anumit număr ''d''. Cazul ''d''&nbsp;=&nbsp;2 este un caz special al [[Problema comis-voiajorului|problemei comis-voiajorului]], astfel încât arborele minim de acoperire cu constrângere de grad este în general [[NP-hard]].

Pentru [[Graf orientat|grafuri orientate]], problema arborelui minim de acoperire se numește {{Ill-wd|Q1520825|3=problema arborescenței}} și poate fi rezolvată în timp pătratic folosind {{Ill-wd|Q1752324|3=algoritmul Chu–Liu/Edmonds}}.

Un arbore maxim de acoperire este un arbore cu pondere totală mai mare sau egală cu a oricărui alt arbore de acoperire. Un astfel de arbore poate fi găsit cu algoritmi precum Prim sau Kruskal după înmulțirea cu -1 a ponderilor muchiilor și rezolvarea problemei AMA pe noul graf. Un drum în arborele maxim de acoperire este {{Ill-wd|Q7998708|3=cel mai larg drum}} din graf între cele două puncte finale: dintre toate drumurile posibile, maximizează ponderea muchiei cu pondere minimă.<ref>{{Citation|last=Hu|first=T. C.|title=The maximum capacity route problem|volume=9|issue=6|pages=898–900|year=1961|periodical=Operations Research|doi=10.1287/opre.9.6.898|jstor=167055}}.</ref> Arborii maximi de acoperire găsesc aplicații în algoritmi de [[parsare]] a [[Prelucrarea limbajului natural|limbajelor naturale]]<ref>{{Cite conference|last=McDonald|last2=Pereira|last3=Ribarov|last4=Hajič|given=Ryan|first2=Fernando|first3=Kiril|first4=Jan|year=2005|booktitle=Proc. HLT/EMNLP|title=Non-projective dependency parsing using spanning tree algorithms|url=http://www.seas.upenn.edu/~strctlrn/bib/PDF/nonprojectiveHLT-EMNLP2005.pdf|access-date=2021-10-15|archive-date=2020-10-01|archive-url=https://web.archive.org/web/20201001165843/https://www.seas.upenn.edu/~strctlrn/bib/PDF/nonprojectiveHLT-EMNLP2005.pdf|dead-url=yes}}</ref> și în algoritmi de instruire pentru {{Ill-wd|Q1124538|3=câmpuri aleatorii condiționale}}.

Problema '''AMA dinamic''' se referă la actualizarea unui AMA calculat anterior după o schimbare a ponderii muchiilor în graful originar sau inserarea/ștergerea unui nod.<ref>{{Citation|last=Spira|first=P. M.|title=On finding and updating spanning trees and shortest paths|url=http://www.ics.forth.gr/~lourakis/10.1137.0204032.pdf|volume=4|issue=3|pages=375–380|year=1975|periodical=SIAM Journal on Computing|doi=10.1137/0204032|mr=0378466|last2=Pan|first2=A.}}.</ref><ref>{{Citation|last=Holm|first=Jacob|title=Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity|volume=48|issue=4|pages=723–760|year=2001|periodical={{Ill-wd|Q1709878|3=Journal of the Association for Computing Machinery}}|doi=10.1145/502090.502095|mr=2144928|last2=de Lichtenberg|first2=Kristian|last3=Thorup|first3=Mikkel|author-link3=Mikkel Thorup}}.</ref><ref>{{Citation|last=Chin|first=F.|title=Algorithms for updating minimal spanning trees|volume=16|issue=3|pages=333–344|year=1978|periodical={{Ill-wd|Q6295014|3=Journal of Computer and System Sciences}}|doi=10.1016/0022-0000(78)90022-3|last2=Houck|first2=D.}}.</ref>

Problema arborelui minim de acoperire cu etichete este de a găsi un arbore de acoperire cu numărul minim de tipuri de etichete dacă fiecare muchie dintr-un graf este asociată cu o etichetă dintr-o mulțime finită de etichete, în loc de pondere.<ref>{{Citation|last=Chang|first=R.S.|title=The minimum labeling spanning trees|volume=63|issue=5|pages=277–282|year=1997|periodical={{Ill-wd|Q129239|3=Information Processing Letters}}|doi=10.1016/s0020-0190(97)00127-0|last2=Leu|first2=S.J.}}.</ref>

O muchie critică este muchia cu cea mai mar epondere dintr-un arbore de acoperire. Un arbore de acoperire este '''arbore minim critic de acoperire''' dacă graful nu conține un arbore de acoperire cu pondere mai mică a unei muchii critice. Un AMA este neapărat și un arbore minim critic de acoperire (fapt demonstrabil prin proprietatea tăieturii), dar nu și invers.<ref>{{Citat web|url=http://flashing-thoughts.blogspot.ru/2010/06/everything-about-bottleneck-spanning.html|titlu=Everything about Bottleneck Spanning Tree|accessdate=4 April 2018|lucrare=flashing-thoughts.blogspot.ru}}</ref><ref>{{Citation |publisher=pages.cpsc.ucalgary.ca |title=Wayback Machine |url=http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf}}</ref>

== Note ==
<references/>

== Lecturi suplimentare ==

* [http://citeseer.ist.psu.edu/nesetril00otakar.html Otakar Boruvka despre problema arborelui minim de acoperire (traducerea ambelor lucrări din 1926, comentarii, istorie) (2000)] Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Secțiunea 7 oferă algoritmul său, care arată ca o încrucișare între Prim și Kruskal.)
* {{Ill-wd|Q2524992|3=Thomas H. Cormen}}, {{Ill-wd|Q93028|3=Charles E. Leiserson}}, [[Ronald Rivest|Ronald L. Rivest]] și {{Ill-wd|Q2024396|3=Clifford Stein}} . ''{{Ill-wd|Q1141518|3=Introduction to Algorithms}}'', ediția a doua. [[Massachusetts Institute of Technology|MIT]] Press și McGraw-Hill, 2001.{{ISBN|0-262-03293-7}}[[International Standard Book Number|ISBN]]&nbsp;[[Special:BookSources/0-262-03293-7|0-262-03293-7]]. Capitolul 23: Arbori minimi de acoperire, pp.&nbsp;561–579.
* Eisner, Jason (1997). [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf State-of-the-art algorithms for minimum spanning trees: A tutorial discussion] . Manuscris, [[Universitatea din Pennsylvania]], aprilie. 78 pp.
* Kromkowski, John David. „Still Unmelted after All These Years”, în Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Folosirea arborelui minim de acoperire ca metodă de analiză demografică a diversității etnice din Statele Unite).

== Legături externe ==

* [http://www.boost.org/libs/graph/doc/table_of_contents.html Implementat în BGL, Boost Graph Library]
* [http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml Stony Brook Algorithm Repository - cod pentru arbori minimi de acoperire]
* [https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph Implementat în QuickGraph pentru .Net]

[[Categorie:Teoria grafurilor]]