Նվազագույն ակնթարթային ծառ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
(Վերահղված է Minimum spanning treeից)
The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length.

Տրված է չկապակցված գրաֆ։ Մեկ գրաֆը կարող է ունենալ բազմաթիվ ճյուղավորված ծառեր։ Մենք կարող ենք տալ կշիռ յուրաքանչյուր եզրին, որը հանդիսանում է մի շարք՝ ներկայացնելով, թե ինչ անբարենպաստ այն կարող է լինել և օգտագործել այն , որպեսզի նշանակի կշիռ ճյուղավորված ծառին՝ հաշվարկելով այդ ճյուղավորված ծառի եզրերի կշիռների գումարը։ Նվազագույն ճյուղավորված ծառը (MST) կամ նվազագույն կշռով ճյուղավորված ծառը հանդիսանում է այն ճյուղավորված ծառը, որն ունի ցանկացած այլ ճյուղավորված ծառից նվազագույն կամ հավասար կշիռ։ Ընդհանուր առմամբ, ցանկացած չկապակցված գրաֆ, ունի նվազագույն ճյուղավորված անտառ, որը հանդիսանում է նվազագույն ճյուղավորված ծառերի միավորում։

Օրինակ կարող է ծառայել կաբելային հեռուստատեսության էլեկտրագծերը նոր ցանցում։ Եթե ստիպված տարվեր մալուխը միայն որոշակի ուղիներով, ապա չէր լինի գրաֆ՝ ներկայացնող,թե որ կետերն են կապված այդ ուղիներով։ Որոշ ուղիներ կարող են լինել ավելի թանկ, քանի որ դրանք ավելի երկար են և պահանջում են ավելի մեծ քանակությամբ մալուխ, որպեսզի ավելի խորը թաղեն. այս ուղիները կներկայացվեն ծանր կշիռ ունեցող եզրերով։ Ճյուղավորված ծառը, այդ գրաֆի համար կլինի ուղիների ենթաբազմություն, որը չի պարունակում ցիկլեր,սակայն կապում է յուրաքանչյուր տուն։ Կարող են լինել մի քանի հնարավոր ճյուղավորված ծառեր։ Նվազագույն ճյուղավորված ծառը կլինի ամենացածր ընդհանուր արժեքը։

Հատկություններ[խմբագրել]

Հնարավոր բազմազանությունը[խմբագրել]

This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.

Կարող են լինել մի քանի նվազագույն ճյուղավորված ծառեր` նույն կշիռն ունեցող; մասնավորապես, եթե տվյալ գրաֆի բոլոր եզրերը նույնն են, ապա տվյալ գրաֆի յուրաքանչյուր ճյուղավորված ծառը նվազագույնն է։ Եթե գրաֆում կան n բարձրություններ, ապա յուրաքանչյուր երրորդը ունի n-1 եզրեր։

Եզակիությունը[խմբագրել]

Եթե ամեն եզրն ունի հստակ կշիռ, ապա կլինի միայն մեկ - միակ նվազագույն ճյուղավորված ծառ։ Սա կարող է ապացուցվել ինդուկցիայի մեթոդով։ Սա ճիշտ է շատ պրակտիկ իրավիճակներում, ինչպիսիք են կաբելային հեռուստաընկերության օրինակը, որտեղ քիչ հավանական է, որ ցանկացած երկու ուղիներ ունեն հենց նույն արժեքը։ Հակասությունների յուրահատկության ապացույցը կայանում է հետևյալում՝[1]

  1. Ենթադրենք, մենք ունենք MST ալգորիթմ, (որը մենք կանվանենք A),հիմնված գրաֆի կառուցվածքի վրա։
  2. Ենթադրենք MST A եզակի չէ։
  3. Կա ևս մեկ ճյուղավորված ծառ,հավասար կշռով, որը կանվանենք MST B։
  4. Թող e1 լինի եզր, որը գտնվում է Aբայց ոչ B։
  5. Ինչպես B MST է, այնպես էլ {e1} \cup Bպետք է պարունակի Cցիկլ։
  6. Այնուհետև B պետք է ներառի առնվազն e2-ի մեկ եզր, որը A-ի մեջ չէ, այլ պատկանում է C։
  7. Ենթադրենք, որ e1 կշիռը ավելի փոքր է, քան e2-ինը։
  8. Փոխարինենք e2e1-ի հետ, B-ն հանգեցնում է {e1} \cup B - {e2} շրջանակին, որն ունի նվազագույն կշիռ B-ի համեմատ։
  9. Հակասություն։ Ինչպես մենք ենթադրեցինք B-ն հանդիսանում է MST, բայց դա այդպես չէ։

Եթե e1-ի կշիռը ավելի մեծ է, քան e2, համանման արգումենտը ներառում է {e2} \cup A - {e1} նույնպես հանգեցնում է հակասությունների։ Այսպիսով, գալիս ենք այն եզրակացությանը, որ այն ենթադրությունը, թե այնտեղ կարող է լինել երկրորդ MST,սխալ է։

Նվազագույն արժեքով ենթագրաֆ[խմբագրել]

Եթե կշիռը դրական է, ապա նվազագույն ճյուղավորված ծառը իրականում նվազագույն արժեքով ենթագրաֆ է կապող բոլոր բարձրությունները,այնպես, որ ցիկլեր պարունակող ենթագրաֆները միշտ ունենում են ավելի մեծ ընդհանուր կշիռ։

Ցիկլի հատկությունը[խմբագրել]

Ցանկացած ցիկլ C գրաֆում, եթե C e եզրի կշիռը ավելի մեծ է, քան C-ի մյուս եզրերի կշիռները, ապա այդ եզրը չի կարող պատկանել MST-ին: Ենթադրելով հակառակը, որ e-ն պատկանում է MST T1-ին, ապա ջնջելով e-ն T1-ը բաժանվում է երկու ենթածառերի։ C-ի մնացած մասը միանում է ենթածառերին, հետևաբար, գոյություն ունի Cf եզր տարբեր ենթածառերով, այսինքն այն միացնում է ենթածառերը T2 ծառի մեջ,ավելի քիչ կշռով, քան T1-ինն է, որովհետև f-ի կշիռը ավելի փոքր է, քան e-ի կշիռը։

Ալգորիթմները[խմբագրել]

Նվազագույն ճյուղավորված ծառը գտնելու համար առաջին ալգորիթմը մշակել է Չեխիայի գիտնական Otakar Borůvka 1926 թվականին(տես՝ Borůvka's algorithm)։ Նրա նպատակն էր Moravia-ի արդյունավետ էլեկտրական լուսաբանումը։ Սովորաբար օգտագործվում են այս երկու ալգորիթմները՝ Prim-ի ալգորիթմ և Kruskal-ի ալգորիթմ։ Բոլոր երեք ագահ ալգորիթմները, որոնք աշխատում են պոլինոմ ժամանակահատվածում, այնպես որ FP-ում նման ծառերի գտնելու խնդիրը և նրանց հետ կապված խնդիրների որոշումը, ինչպիսիք են, օրինակ որոշելու, թե արդյոք տվյալ եզրը MST-ում է կամ ,թե արդյոք նվազագույն ընդհանուր կշիռը գերազանցում է որոշակի արժեք P-ում։

Եթե եզրի կշիռները ամբողջ թվեր են, ապա դետերմինացված ալգորիթմները, ինչպես հայտնի է, որոշում են այդ խնդիրը O(m + n[2][3][4] Ամենաարագ ոչ-randomized համեմատությունը գործող ալգորիթմի համար, ըստ Bernard Chazelle-ի, հիմնված է փափուկ կույտի վրա։ [5][6] Նրա աշխատանքի ժամանակահատվածն է O(m α(m,n)),որտեղ՝ m-ը եզրերի քանակն է, n-ը բարձրությունների քանակն է, aAckermann գործառույթի դասական ֆունկցիոնալ հավանականությունն է։ α ֆունկցիան աճում է շատ դանդաղ, այնպես որ, բոլոր գործնական նպատակների համար կարելի է համարել հաստատուն,ոչ մեծ 4-ից։ Seth Pettie և Vijaya Ramachandran գտան օպտիմալ դետերմինացված համեմատություն՝ հիմնված նվազագույն ճյուղաորված ծառի ալգորիթմի վրա, որը անհայտ հաշվողական բարդություն է։[7]

Ուսումնասիրությունները նաև համարվում են զուգահեռ ալգորիթմներ, նվազագույն ճյուղաորված ծառի խնդրի համար։ Պրոցեսորների մի շարք գծային վերամշակման խնդիրը կարելի է որոշել O(\log n) բանաձևով։[8][9] Կաղապար:Harvtxt [10]

Այլ մասնագիտացված ալգորիթմները մշակվել են նվազագույն ճյուղաորված ծառիհաշվարկելու համար,այդ գրաֆը այնքան մեծ է, որ դրանցից շատերը, խետք է պահպանվեն սկավառակի վրա՝ցանկացած ժամանակ։ Այս արտաքին հիշողության ալգորիթմները, օրինակ ինչպես նկարագրված է "Ճարտարագիտական արտաքին հիշողության նվազագույն ճյուղաորված ծառի ալգորիթմում" Roman Dementiev կողմից,[11] հեղինակների պնդումներով կարող են աշխատել երկուսից հինգ անգամ դանդաղ, քան սովորական հիշողության ալգորիթմները։

Խնդիրը կարելի է նաև դիտարկել բաշխված ձևով։

MST-ն ամբողջական գրաֆներում[խմբագրել]

Alan M. Frieze-ը ցույց տվեց, որ հաշվի առնելով ամբողջական գրաֆը n բարձրություններում, որոնք անկախ են F ֆունկցիայից, բավարարում են F satisfying F'(0) > 0 պայմանինն, ապաn-ը մոտենում է +∞, MST-ի ակնկալվող կշիռն է \zeta(3)/F'(0), որտեղ \zetaRiemann-ի ֆունկցիայի գործառույթն է։ Համաձայն լրացուցիչ սահմանապակ շեղումների Alan M. Frieze նաև ապացուցեց կոնվերգենցիայի հավանականությունը։ Հետագայում J. Michael Steele ցույց տվեց, որ փոփոխության ենթադրությունը, կարող է նվազել։

Ավելի ուշSvante Janson իր աշխատանքում սահմանեց կենտորնական սահմանաչափի թեորեմը MST-ի կշռի համար։

Պատահական [0,1] միջակայքի համար, նվազագույն ճյուղավորված ծառի ճշգրիտ սպասվող մեծությունը նախատեսվել էր փոքր ամբողջական գրաֆների համար։[12]

Բարձրություն Ակնկալվող չափ Մոտավոր ակնկալվող չափ
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

Նմանատիպ խնդիրներ[խմբագրել]

Սրա հետ կապված խնդիրը կայանում է k-նվազագույն ճյուղավորված ծառի հետ (k-MST), որը հանդիսանում է ծառ և ներառում է k բարձրության մի քանի բնագավառներ, նվազագույն կշռով գրաֆում։

k-նվազագույն ճյուղավորված ծառերի A փաթեթը , k ճյուղավորված ծառերի մի ենթաբազմություն է (դուրս է բոլոր հնարավոր ճյուղավորված ծառերից), այնպես որ ոչ մի ճյուղավորված ծառ՝ ենթաբազմությունից դուրս, չունի փոքր կշիռ,[13][14][15] (Նշենք, որ այս պրոբլեմը չի վերաբերվում k-նվազագույն ճյուղավորված ծառին)։

Էվկլիդյան նվազագույն ճյուղավորված ծառը, գրաֆի ճյուղավորված ծառ է, եզրի կշիռներին համապատասխան, ինչպես նաև Էվկլիդյան հեռավորություն բարձրությունների միջև,որոնք տարածքի միավորներ են։

Ուղագծային նվազագույն ճյուղավորված ծառը, գրաֆի ճյուղավորված ծառ է, եզրի կշիռներին համապատասխան,ինչպես նաև ուղագծային հեռավորություն բարձրությունների միջև, որոնք տարածքի միավորներ են։

Տես նաև[խմբագրել]

Հղումներ[խմբագրել]

  1. Gallager, R. G.; Humblet, P. A.; Spira, P. M. (January 1983), «A distributed algorithm for minimum-weight spanning trees», ACM Transactions on Programming Languages and Systems 5 (1), doi:10.1145/357195.357200 .
  2. Fredman, M. L.; Willard, D. E. (1994), «Trans-dichotomous algorithms for minimum spanning trees and shortest paths», Journal of Computer and System Sciences 48 (3), doi:10.1016/S0022-0000(05)80064-9 .
  3. Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), «A randomized linear-time algorithm to find minimum spanning trees», Journal of the Association for Computing Machinery 42 (2), doi:10.1145/201019.201022 
  4. Pettie, Seth; Ramachandran, Vijaya (2002), «Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms», Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, http://portal.acm.org/citation.cfm?id=545477 .
  5. Chazelle, Bernard (2000), «A minimum spanning tree algorithm with inverse-Ackermann type complexity», Journal of the Association for Computing Machinery 47 (6), doi:10.1145/355541.355562 .
  6. Chazelle, Bernard (2000), «The soft heap: an approximate priority queue with optimal error rate», Journal of the Association for Computing Machinery 47 (6), doi:10.1145/355541.355554 .
  7. Pettie, Seth; Ramachandran, Vijaya (2002), «An optimal minimum spanning tree algorithm», Journal of the Association for Computing Machinery 49 (1), doi:10.1145/505241.505243 .
  8. Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), «Concurrent threads and optimal parallel minimum spanning trees algorithm», Journal of the Association for Computing Machinery 48 (2), doi:10.1145/375827.375847 .
  9. Pettie, Seth; Ramachandran, Vijaya (2002), «A randomized time-work optimal parallel algorithm for finding a minimum spanning forest», SIAM Journal on Computing 31 (6), doi:10.1137/S0097539700371065 .
  10. Bader, David A.; Cong, Guojing (2006), «Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs», Journal of Parallel and Distributed Computing 66 (11), doi:10.1016/j.jpdc.2006.06.001 .
  11. Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), «Engineering an external memory minimum spanning tree algorithm», Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004), http://algo2.iti.kit.edu/dementiev/files/emst.pdf .
  12. Steele, J. Michael (2002), «Minimal spanning trees for graphs with random edge lengths», Mathematics and computer science, II (Versailles, 2002), Basel: Birkhäuser 
  13. Gabow, Harold N. (1977), «Two algorithms for generating weighted spanning trees in order», SIAM Journal on Computing 6 (1) .
  14. Eppstein, David (1992), «Finding the k smallest spanning trees», BIT 32 (2), doi:10.1007/BF01994879 .
  15. Frederickson, Greg N. (1997), «Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees», SIAM Journal on Computing 26 (2), doi:10.1137/S0097539792226825 .

Հավելյալ նյութեր[խմբագրել]

Արտաքին հղումներ[խմբագրել]