Arbore minim de acoperire

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 conex cu muchii ponderate, care toate nodurile între ele, fără cicluri și cu ponderea totală a muchiilor minimă. Adică este un Format:Ill-wd 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 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 muchieiFormat: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ă Format:Mvar noduri în graf, atunci fiecare arbore de acoperire are Format:Math muchii.

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:

1. Format:Ill-wd, că există doi AMA diferiți Format:Math și Format:Math.
2. Deoarece Format:Math și Format:Math 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 Format:Math cea cu cea mai mică pondere; această alegere este unică, deoarece ponderile muchiilor sunt toate distincte. Fără pierderea generalității, să presupunem că Format:Math este în A.
3. Deoarece B este un AMA, Format:Math trebuie să conțină un ciclu Format:Math avându-l pe Format:Math.
4. Ca arbore, Format:Math nu conține cicluri, prin urmare Format:Math trebuie să aibă o muchie Format:Math care nu este în Format:Math.
5. Din moment ce Format:Math a fost aleasă ca muchia unică cu cea mai mică pondere printre cele care aparțin exact unuia dintre Format:Math și Format:Math, ponderea lui Format:Math trebuie să fie mai mare decât ponderea lui Format:Math_.
6. Deoarece Format:Math și Format:Math fac parte din ciclul Format:Math, înlocuirea lui Format:Math cu Format:Math în Format:Math produce un arbore de acoperire cu ponderea mai mică.
7. Acest lucru contrazice presupunerea că Format:Math 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.

Subgraful de cost minim

Dacă ponderile sunt pozitive, atunci un arbore minim de acoperire este de fapt un subgraf de cost minim care acoperă toate vârfurile, deoarece subgrafurile care conțin 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 Format:Math din graf, dacă ponderea unei muchii Format:Math lui Format:Math este mai mare decât ponderile individuale ale tuturor celorlalte muchii ale lui Format:Math, atunci această muchie nu poate aparține unui AMA.

Demonstrație: Format:Ill-wd, adică presupunem că Format:Math aparține unui AMA Format:Math . Atunci, ștergerea lui Format:Math va împărți Format:Math în doi subarbori cu două capete ale lui Format:Math aflate în subarbori diferiți. Restul de Format:Math reconectează subarborii, prin urmare există o muchie Format:Math a lui Format:Math cu capete în subarbori diferiți, adică ea reconectează subarborii într-un arbore Format:Math cu pondere mai mică decât cea a lui Format:Math, deoarece ponderea lui Format:Math este mai mică decât ponderea lui Format:Math.

Proprietatea de tăietură

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 Format:Ill-wd 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: 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' . Ș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.

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 Format:Ill-wd în 1926 (algoritmul lui Borůvka). Scopul său era o acoperire electrică eficientă a 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 Format:Tmath ca intrare la pasul următor. Aici, cu Format:Tmath 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).

Un al doilea algoritm este algoritmul lui Prim, care a fost inventat de Format:Ill-wd în 1930 și redescoperit de Format:Ill-wd în 1957 și 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 Format:Ill-wd, care este inversul algoritmului lui Kruskal. Timpul său de rulare este O(m log n (log log n)³).

Toți acești patru sunt algoritmi greedy. Deoarece rulează în timp polinomial, problema găsirii unor astfel de arbori este în clasa de complexitate FP și Format:Ill-wd 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.

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 Format:Ill-wd bazat pe o combinație între algoritmul lui Borůvka și algoritmul de ștergere inversă.

Cel mai rapid algoritm nerandomizat bazat pe comparații, cu complexitate cunoscută, al lui Format:Ill-wd, se bazează pe heap-ul soft, o coadă cu prioritate aproximativă. Durata sa de rulare este O(m α(m, n)), unde α este Format:Ill-wd. 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). 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 Format:Math, numărul de noduri rămase după o fază este cel mult Format:Math . Prin urmare, sunt necesare cel mult Format:Math faze, ceea ce oferă un timp de rulare liniar pentru grafuri dense.

Există și alți algoritmi care funcționează în timp liniar pe grafuri dense.

Ponderi întregi

Dacă ponderile muchiilor sunt numere întregi reprezentate în binar, atunci se cunosc algoritmi determiniști care rezolvă problema în O(m + n) operații cu întregi. 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 Format:Ill-wd (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 Format:Ill-wd. Această căutare se desfășoară în doi pași.

A. Generarea tuturor AD potențiali

• Sunt $2^{(\genfrac{}{}{0ex}{}{r}{2})}$ 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 Format:Math.
• Prin urmare, numărul de noduri interne într-un AD optim este mai mic decât $2^{r^2}$.
• Fiecare nod intern compară două muchii. Numărul muchiilor este cel mult Format:Math deci numărul diferit de comparații este cel mult Format:Math.
• Prin urmare, numărul AD-ilor potențiali este mai mic decât: ${(r^4)}^{(2^{r^2})}=r^{2^{(r^2+2)}}$ .

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 Format:Math.
• 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 Format:Math, deci timpul total necesar pentru verificarea tuturor permutărilor este cel mult $(r^2+1)!$.

Prin urmare, timpul total necesar pentru găsirea unui AD optim pentru toate grafurile cu r noduri este: $2^{(\genfrac{}{}{0ex}{}{r}{2})}\cdot r^{2^{(r^2+2)}}\cdot (r^2+1)!$, care este mai mic decât: $2^{2^{r^2+o(r)}}$.

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. Mai jos este o descriere simplificată a algoritmului.

1. Fie $r=\log \log \log n$, unde Format:Math 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).
2. Se împarte graful în componente cu cel mult r noduri în fiecare componentă. Această partiție folosește un Format:Ill-wd, care „corupe” un număr mic de muchii ale grafului.
3. Se utilizează arborii de decizie optimi pentru a găsi un AMA pentru subgraful necorupt din cadrul fiecărei componente.
4. 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.
5. 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 optimFormat: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 paraleli pentru problema arborelui minim. Cu un număr liniar de procesoare, se poate rezolva problema în timp Format:Math. 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.

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., 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 Format:Ill-wd eficiente și pe Format:Ill-wd pentru reducerea eficientă a dimensiunii graficului.

Problema poate fi abordată și într-o 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 Format:Ill-wd.

AMA pe grafuri complete

Format:Ill-wd a demonstrat că, dat fiind un grafic complet de n noduri, cu muchiile având ca ponderi variabile aleatoare independente distribuite identic, având funcția de distribuție Format:Math cu proprietatea că Format:Math, apoi pe măsură ce n se apropie de Format:Ill-wd, se apropie de ponderea așteptată a AMA $\zeta (3)/F^{\prime }(0)$, Unde $\zeta$ este funcția zeta Riemann (mai exact este $\zeta (3)$ Format:Ill-wd). Frieze și Format:Ill-wd au demonstrat și convergența probabilității. Format:Ill-wd a demonstrat o Format:Ill-wd pentru ponderea AMA.

Pentru ponderi aleatorii uniforme în intervalul $[0,1]$, dimensiunea exactă așteptată a arborelui minim de acoperire a fost calculată pentru grafuri complete mici.

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țelelor de calculatoare, Format:Ill-wd, Format:Ill-wd, Format:Ill-wd și rețele electrice (pentru care au fost inventate pentru prima dată, așa cum s-a menționat mai sus). Ele sunt invocate ca subrutine în algoritmi pentru alte probleme, inclusiv în algoritmul Christofides pentru aproximarea problemei comis-voiajorului, aproximând problema decupării minime multi-terminal (care este echivalentă în cazul unui singur terminal cu Format:Ill-wd), și pentru aproximarea cuplajului perfect ponderat de cost minim.

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

• Taxonomia.
• Analiza de cluster: clustere de puncte în plan, clustering o singură legătură (o metodă de clusterizare ierarhică), clustering graf-teoretic, și clusteringul datelor de exprimare genetică.
• Construirea arborilor pentru broadcast în rețele de calculatoare.
• Înregistrarea și segmentarea imaginilor.
• Extragerea caracteristicilor curbilinii în vederea computerizată.
• Recunoașterea scrisului de mână cu expresii matematice.
• Proiectarea circuitelor: implementarea eficientă a multiplicărilor constante multiple, așa cum se utilizează în filtrele de răspuns finit la impuls.
• Regionalizarea zonelor socio-geografice, gruparea zonelor în regiuni omogene, contigue.
• Compararea datelor ecotoxicologice.
• Observabilitate topologică în sistemele de alimentare.
• Măsurarea omogenității materialelor bidimensionale.
• Controlul procesului Minimax.
• Arborii minimi pot fi folosiți și pentru a descrie piețele financiare. 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

Format:Regular polygon minimum spanning tree.svgSe cunoaște că problema găsirii Format:Ill-wd al unei submulțimi a nodurilor, adică a unui arbore minim care acoperă submulțimea dată, este NP-completă.

O problemă asociată este Format:Ill-wd (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ă. (Această problemă nu are legătură cu k-arborele minim de acoperire.)

Format:Ill-wd 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).

Format:Ill-wd este un arbore de acoperire al unui graf, ale cărui muchii au ponderile corespunzătoare distanței rectilinii între nodurile care sunt puncte în plan (sau spațiu).

În 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 Format:Ill-wd. Definiția matematică a problemei este aceeași, dar există diferite abordări pentru o soluție.

Format:Ill-wd 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, dar euristicile bune, cum ar fi Esau-Williams și Sharma, produc soluții aproape de optim în timp polinomial.

Format:Ill-wd 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 = 2 este un caz special al problemei comis-voiajorului, astfel încât arborele minim de acoperire cu constrângere de grad este în general NP-hard.

Pentru grafuri orientate, problema arborelui minim de acoperire se numește Format:Ill-wd și poate fi rezolvată în timp pătratic folosind Format:Ill-wd.

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 Format:Ill-wd din graf între cele două puncte finale: dintre toate drumurile posibile, maximizează ponderea muchiei cu pondere minimă. Arborii maximi de acoperire găsesc aplicații în algoritmi de parsare a limbajelor naturale și în algoritmi de instruire pentru Format:Ill-wd.

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.

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.

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.

Lecturi suplimentare

• 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.)
• Format:Ill-wd, Format:Ill-wd, Ronald L. Rivest și Format:Ill-wd . Format:Ill-wd, ediția a doua. MIT Press și McGraw-Hill, 2001.Format:ISBNISBN 0-262-03293-7. Capitolul 23: Arbori minimi de acoperire, pp. 561–579.
• Eisner, Jason (1997). 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

• Implementat în BGL, Boost Graph Library
• Stony Brook Algorithm Repository - cod pentru arbori minimi de acoperire
• Implementat în QuickGraph pentru .Net