Arborele minim de cuprindere

O primă încercare

Poate fi foarte simplu să se creeze un algoritm care să descopere un arbore minim de cuprindere:

 funcția MST(G,W):     T = {} în timp ce T nu formează un arbore de cuprindere: se găsește muchia ponderată minimă din E care este sigură pentru T T T = T union {(u,v)} return T

În acest caz, "sigur" înseamnă că includerea muchiei nu formează un ciclu în graf. Un ciclu înseamnă să începi de la un vârf, să călătorești spre un număr de alte vârfuri și să ajungi din nou la punctul de plecare fără a folosi aceeași muchie de două ori.

Istorie

Omul de știință ceh Otakar Borůvka a dezvoltat în 1926 primul algoritm cunoscut pentru găsirea unui arbore de cuprindere minimă. El a dorit să rezolve problema găsirii unei acoperiri eficiente a Moraviei cu energie electrică. Astăzi, acest algoritm este cunoscut sub numele de algoritmul lui Borůvka. Alți doi algoritmi sunt utilizați în mod obișnuit în prezent. Unul dintre ei a fost dezvoltat de Vojtěch Jarník în 1930 și pus în practică de Robert Clay Prim în 1957. Edsger Wybe Dijkstra l-a redescoperit în 1959 și l-a numit algoritmul lui Prim. Celălalt algoritm se numește algoritmul lui Kruskal și a fost pus la punct de Joseph Kruskal în 1956. Toți cei trei algoritmi sunt lacomi și se execută în timp polinomial.

Cel mai rapid algoritm de arbore minim de cuprindere de până acum a fost dezvoltat de Bernard Chazelle. Algoritmul se bazează pe soft heap, o coadă de prioritate aproximativă. Timpul său de execuție este O(m α(m,n)), unde m este numărul de muchii, n este numărul de vârfuri și α este 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 are un timp foarte apropiat de cel liniar.

Care este cel mai rapid algoritm posibil pentru această problemă? Aceasta este una dintre cele mai vechi întrebări deschise din domeniul informaticii. Există în mod clar o limită inferioară liniară, deoarece trebuie să examinăm cel puțin toate ponderile. Dacă greutățile marginilor sunt numere întregi cu o lungime de bit limitată, atunci se cunosc algoritmi deterministici cu timp de execuție liniar. Pentru ponderi generale, există algoritmi aleatori al căror timp de execuție așteptat este liniar.

Problema poate fi abordată, de asemenea, într-o manieră distribuită. În cazul în care fiecare nod este considerat un computer și niciun nod nu cunoaște nimic în afară de propriile legături conectate, se poate calcula totuși arborele minim distribuit.