1 Formularea problemei
Fie G un grafic ne-orientat conectat [math] G = (V, E) [/ math] cu greutăți de margine [math] f (e) [/ math]. Un subgraf care este un copac și trece prin toate vârfurile [math] G [/ math]. se numește arborele principal. Un copac spanning este numit minim. Dacă greutatea totală a marginilor sale este minimă între toți copacii care se întind.
2 variante de sarcini
În cazul în care graficul inițial G [/ math] este deconectat, atunci setul de arbori care se întind pe minim pentru toate componentele de conectivitate se numește Forest Minimum Spanning (MSF).
Pentru un grafic cu scale întregi, este posibil să se utilizeze metode speciale, cum ar fi sortarea biturilor. ceea ce duce la algoritmi care rezolvă problema în timp liniar.
Într-o problemă distribuită, poate exista o cerință suplimentară că schimbul de date are loc numai de-a lungul marginilor graficului.
3 Proprietăți sarcini
Greutate. Soluția problemei nu depinde de valorile greutăților, ci de ordinea lor. Astfel, în loc de a stabili greutăți, putem specifica ordinea - predicatul "mai mic sau egal cu" pe setul de perechi de margini ale graficului. Din acest motiv, fără pierderea generalității, se poate presupune că toate greutățile marginilor sunt diferite - în acest scop, marginile trebuie mai întâi să fie ordonate în funcție de greutate și apoi de număr. În plus, orice funcție de creștere poate fi aplicată greutăților inițiale și nu va duce la o modificare a soluției. În consecință, putem presupune că toate greutățile sunt într-un anumit interval, de exemplu, [math] [0, 1] [/ math].
Existența și unicitatea. O pădure minimă de referință există întotdeauna și dacă toate greutățile marginilor sunt diferite, atunci este singura. După cum sa menționat deja, este întotdeauna posibil ca greutățile marginilor să fie diferite. Dacă condiția diferitelor greutăți nu este satisfăcută, este ușor să se construiască un exemplu în care vor exista mai mult de un arbore minim de spanning.
Slamming de fragmente. Fie [matematica] F [/ math] fragmentul copacului minim al grafului [math] G [/ math]. iar graficul [math] G [/ math] este obținut din [math] G [/ math] prin lipirea vârfurilor aparținând [math] F [/ math]. Apoi uniunea [matematica] F [/ matematica] și arborele minim se întinde a graficului [matematica] G „[/ math] dă arborele minim se întinde a graficului de pornire [matematică] G [/ matematica].
Latura minimă a fragmentului. Să [math] F [/ math] - fragment și minimum se întinde copac [matematică] e_F [/ math] - rib cel greutate care provin de la [matematică] F [/ math] (adică exact un capăt este vârful [matematică] F [/ math]). Dacă marginea [math] e_F [/ math] este unică, atunci ea aparține arborelui minim de spanning. Pe această proprietate se bazează algoritmul Borovka și algoritmul Prima.
Marginea minimă a graficului. Dacă [math] e ^ * [/ math] este singura margine a unui grafic cu o greutate minimă, atunci el aparține arborelui minim de spanning. Pe această proprietate se bazează algoritmul Kruskal.
Asociativitatea de-a lungul marginilor. Fie ca MSF (E) [/ math] să fie pădurea minimă care acoperă un grafic cu marginile [math] E [/ math]. atunci
[Math] MSF (E_1 \ ceașcă E_2 \ ceașcă \ dots \ cup E_k) = MSF (MSF (E_1) \ cup MSF (E_2) \ cup \ dots \ cup MSF (E_k)). [/ math]
Numărul de nervuri care acoperă pădure pentru graful cu [matematică] n [/ matematică] vârfuri și [matematică] c [/ matematică] componente conectate este egal cu [matematica] n-c [/ math]. Această proprietate poate fi utilizată pentru a finaliza rapid activitatea algoritmilor dacă numărul componentelor de conectivitate este cunoscut în prealabil.
4 Descrierea datelor de intrare și ieșire
Datele de intrare. Grafic ponderat [matematică] (V, E, W) [/ math] ([matematică] n [/ math] noduri [matematica] v_i [/ matematică] și [matematică] m [/ math] coaste [matematica] e_j = ( v ^, v ^ _) [/ math] cu greutatea [math] f_j [/ math]).
Cantitatea de date introduse. [math] O (m + n) [/ math].
Datele de ieșire. lista de margini ale arborelui minim de spanning (pentru un grafic disjunctiv - o listă cu arbori de extindere minimă pentru toate componentele conectate).
Valoarea producției. [matematică] O (n) [/ matematică].
5 Algoritmi pentru rezolvarea problemei
Există trei abordări clasice pentru rezolvarea problemei:
În toate cazurile, complexitatea secvențială a algoritmului [math] O (m \ ln m) [/ math] atunci când se utilizează structuri de date convenționale. (Notă: [math] m [/ math] este numărul de margini, [math] n [/ math] este numărul de noduri.)
Toți ceilalți algoritmi, de regulă, sunt o variație pe tema uneia dintre cele trei enumerate sau o combinație a acestora.
- Algoritmul GHS (Gallager, Humblet, Spira) [6] și versiunile sale ulterioare [7] [8] sunt o versiune distribuită a algoritmului Borovka. Acest algoritm este utilizat de obicei pentru construirea automată distribuită a unui arbore spanning de către o rețea de switch-uri.
- Algoritmul lui Gabov și alții [9] utilizează heapul Fibonacci pentru ordonarea marginilor în algoritmul Borovka. Complexitate [math] O (m \ ln \ beta (m, n)) [/ math].
- Algoritmul Fredman și Willard [10] este destinat grafurilor cu greutăți întregi și are o estimare de complexitate liniară [math] O (m) [/ math]. Algoritmul Prima este utilizat împreună cu un algoritm de heap special dezvoltat (AF-heap).
- Algoritmul lui Karger și alții [11] rezolvă problema în medie în timp liniar [math] O (m) [/ math]. (Existența unui algoritm determinist cu o estimare complexă liniară este o întrebare deschisă.)
Trebuie notat faptul că algoritmii cu complexitate asimptotică sunt mai buni decât [math] O (m \ nn n) [/ math]. ca regulă, în practică acestea funcționează mai lent decât algoritmii clasici: constanta în estimare este atât de mare încât câștigul de la cele mai bune asimptotice va fi vizibil numai pe grafice de dimensiuni foarte mari.
6 Resurse de concurs
- Proprietățile fragmentelor de colaps și marginea minimă a fragmentului permit separarea fragmentelor de prelucrare. Pe baza acestor proprietăți, algoritmul Borovka are cea mai mare resursă de paralelism dintre cei trei algoritmi clasici.
- Asociativitatea de-a lungul marginilor poate fi folosită pentru a paralela algoritmele Kruskal și Prima, care sunt, în esență, consecvente.
- Utilizarea algoritmilor paraleli pentru sortarea marginilor unui grafic sau sortarea paralelă a marginilor în fiecare vârf sau în fiecare fragment.
Trimiteți-le prietenilor: