Arborele minim de cuprindere
O serie de probleme din teoria grafurilor se numesc arborele minim de cuprindere. În teoria grafurilor, un arbore este o modalitate de conectare a tuturor vârfurilor între ele, astfel încât să existe exact o cale de la oricare dintre vertexuri la oricare alt vertex al arborelui. Dacă graful reprezintă un număr de orașe conectate prin drumuri, se poate selecta un număr de drumuri astfel încât fiecare oraș să poată fi accesat din fiecare oraș, dar să nu existe mai mult de o singură cale de deplasare de la un oraș la altul.
Un graf poate avea mai mult de un arbore de cuprindere, la fel cum pot exista mai multe moduri de a selecta drumurile dintre orașe.
De cele mai multe ori, graficele sunt ponderate; fiecare conexiune între două orașe are o pondere: poate costa ceva să călătorești pe un anumit drum sau o conexiune poate fi mai lungă decât cealaltă, ceea ce înseamnă că este nevoie de mai mult timp pentru a călători pe acea conexiune. În limbajul teoriei grafurilor, conexiunile se numesc muchii.
Un arbore de cuprindere minimă este un arbore. Acesta se deosebește de alți arbori prin faptul că minimizează totalul ponderilor atașate la muchii. În funcție de cum arată graficul, pot exista mai mulți arbori de cuprindere minimă. Într-un graf în care toate marginile au aceeași greutate, fiecare arbore este un arbore de cuprindere minimă. În cazul în care toate marginile au greutăți diferite (adică nu există două muchii cu aceeași greutate), există exact un singur arbore de cuprindere minimă.
Arborele minim de cuprindere al unui graf planar. Fiecare muchie este etichetată cu greutatea sa, care este aproximativ proporțională cu lungimea sa.
Găsirea arborelui 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.
Întrebări și răspunsuri
Î: Ce este un arbore de acoperire minimă în teoria grafurilor?
R: În teoria grafurilor, un arbore minim de cuprindere este un arbore care minimizează greutățile totale atașate marginilor.
Î: Ce este un arbore în teoria grafurilor?
R: În teoria grafurilor, un arbore este o modalitate de a conecta toate vârfurile între ele, astfel încât să existe o singură cale de acces de la orice vertex la orice alt vertex al arborelui.
Î: Care este scopul selectării drumurilor într-un scenariu de teoria grafurilor care reprezintă orașe?
R: Scopul selectării drumurilor într-un scenariu de teoria grafurilor care reprezintă orașe este de a permite ca fiecare oraș să fie accesibil din orice alt oraș, dar fără a exista mai mult de o singură cale posibilă de a călători de la un oraș la altul.
Î: Poate un graf să aibă mai mult de un arbore de acoperire?
R: Da, un graf poate avea mai mult de un arbore de cuprindere.
Î: Care este diferența dintre un arbore minim de cuprindere și alți arbori din teoria grafurilor?
R: Un arbore de cuprindere minimă minimizează greutatea totală atașată marginilor, în timp ce alți arbori nu au această caracteristică.
Î: Ce sunt marginile în teoria grafurilor?
R: În teoria grafurilor, marginile sunt conexiunile dintre două vârfuri.
Î: Pot exista mai mult de un arbore de cuprindere minimă într-un graf cu muchii cu ponderi diferite?
R: Da, în funcție de aspectul grafului, poate exista mai mult de un arbore minim de cuprindere.
