Նվազագույն ակնթարթային ծառ
Տրված է չկապակցված գրաֆ:Մեկ գրաֆը կարող է ունենալ բազմաթիվ ճյուղավորված ծառեր: Մենք կարող ենք տալ կշիռ յուրաքանչյուր եզրին, որը հանդիսանում է մի շարք` ներկայացնելով, թե ինչ անբարենպաստ այն կարող է լինել և օգտագործել այն , որպեսզի նշանակի կշիռ ճյուղավորված ծառին` հաշվարկելով այդ ճյուղավորված ծառի եզրերի կշիռների գումարը: Նվազագույն ճյուղավորված ծառը (MST) կամ նվազագույն կշռով ճյուղավորված ծառը հանդիսանում է այն ճյուղավորված ծառը, որն ունի ցանկացած այլ ճյուղավորված ծառից նվազագույն կամ հավասար կշիռ: Ընդհանուր առմամբ, ցանկացած չկապակցված գրաֆ, ունի նվազագույն ճյուղավորված անտառ, որը հանդիսանում է նվազագույն ճյուղավորված ծառերի միավորում:
Օրինակ կարող է ծառայել կաբելային հեռուստատեսության էլեկտրագծերը նոր ցանցում: Եթե ստիպված տարվեր մալուխը միայն որոշակի ուղիներով, ապա չէր լինի գրաֆ` ներկայացնող,թե որ կետերն են կապված այդ ուղիներով: Որոշ ուղիներ կարող են լինել ավելի թանկ, քանի որ դրանք ավելի երկար են և պահանջում են ավելի մեծ քանակությամբ մալուխ, որպեսզի ավելի խորը թաղեն. այս ուղիները կներկայացվեն ծանր կշիռ ունեցող եզրերով: Ճյուղավորված ծառը, այդ գրաֆի համար կլինի ուղիների ենթաբազմություն, որը չի պարունակում ցիկլեր,սակայն կապում է յուրաքանչյուր տուն: Կարող են լինել մի քանի հնարավոր ճյուղավորված ծառեր: Նվազագույն ճյուղավորված ծառը կլինի ամենացածր ընդհանուր արժեքը:
Բովանդակություն |
Հատկություններ [խմբագրել]
Հնարավոր բազմազանությունը [խմբագրել]
Կարող են լինել մի քանի նվազագույն ճյուղավորված ծառեր` նույն կշիռն ունեցող; մասնավորապես, եթե տվյալ գրաֆի բոլոր եզրերը նույնն են, ապա տվյալ գրաֆի յուրաքանչյուր ճյուղավորված ծառը նվազագույնն է : Եթե գրաֆում կան n բարձրություններ, ապա յուրաքանչյուր երրորդը ունի n-1 եզրեր:
Եզակիությունը [խմբագրել]
Եթե ամեն եզրն ունի հստակ կշիռ, ապա կլինի միայն մեկ - միակ նվազագույն ճյուղավորված ծառ: Սա կարող է ապացուցվել ինդուկցիայի մեթոդով:Սա ճիշտ է շատ պրակտիկ իրավիճակներում, ինչպիսիք են կաբելային հեռուստաընկերության օրինակը, որտեղ քիչ հավանական է, որ ցանկացած երկու ուղիներ ունեն հենց նույն արժեքը: Հակասությունների յուրահատկության ապացույցը կայանում է հետևյալում`[1]
- Ենթադրենք, մենք ունենք MST ալգորիթմ, (որը մենք կանվանենք A),հիմնված գրաֆի կառուցվածքի վրա:
- Ենթադրենք MST A եզակի չէ:
- Կա ևս մեկ ճյուղավորված ծառ,հավասար կշռով, որը կանվանենք MST B:
- Թող e1 լինի եզր, որը գտնվում է Aբայց ոչ B:
- Ինչպես B MST է, այնպես էլ {e1}
Bպետք է պարունակի Cցիկլ: - Այնուհետև B պետք է ներառի առնվազն e2-ի մեկ եզր, որը A-ի մեջ չէ, այլ պատկանում է C:
- Ենթադրենք, որ e1 կշիռը ավելի փոքր է, քան e2-ինը:
- Փոխարինենք e2-ը e1-ի հետ, B-ն հանգեցնում է {e1} B - {e2} շրջանակին, որն ունի նվազագույն կշիռ B-ի համեմատ:
- Հակասություն: Ինչպես մենք ենթադրեցինք B-ն հանդիսանում է MST, բայց դա այդպես չէ:
Եթե e1-ի կշիռը ավելի մեծ է, քան e2, համանման արգումենտը ներառում է {e2} 
A - {e1} նույնպես հանգեցնում է հակասությունների: Այսպիսով, գալիս ենք այն եզրակացությանը, որ այն ենթադրությունը, թե այնտեղ կարող է լինել երկրորդ MST,սխալ է:
Նվազագույն արժեքով ենթագրաֆ [խմբագրել]
Եթե կշիռը դրական է, ապա նվազագույն ճյուղավորված ծառը իրականում նվազագույն արժեքով ենթագրաֆ է կապող բոլոր բարձրությունները,այնպես, որ ցիկլեր պարունակող ենթագրաֆները միշտ ունենում են ավելի մեծ ընդհանուր կշիռ:
Ցիկլի հատկությունը [խմբագրել]
Ցանկացած ցիկլ C գրաֆում, եթե C-ի e եզրի կշիռը ավելի մեծ է, քան C-ի մյուս եզրերի կշիռները, ապա այդ եզրը չի կարող պատկանել MST-ին: Ենթադրելով հակառակը, որ e-ն պատկանում է MST T1-ին, ապա ջնջելով e-ն T1-ը բաժանվում է երկու ենթածառերի: C-ի մնացած մասը միանում է ենթածառերին, հետևաբար, գոյություն ունի C-ի f եզր տարբեր ենթածառերով, այսինքն այն միացնում է ենթածառերը 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-ը բարձրությունների քանակն է, a-ն Ackermann գործառույթի դասական ֆունկցիոնալ հավանականությունն է: α ֆունկցիան աճում է շատ դանդաղ, այնպես որ, բոլոր գործնական նպատակների համար կարելի է համարել հաստատուն,ոչ մեծ 4-ից: Seth Pettie և Vijaya Ramachandran գտան օպտիմալ դետերմինացված համեմատություն` հիմնված նվազագույն ճյուղաորված ծառի ալգորիթմի վրա, որը անհայտ հաշվողական բարդություն է:[7]
Ուսումնասիրությունները նաև համարվում են զուգահեռ ալգորիթմներ, նվազագույն ճյուղաորված ծառի խնդրի համար: Պրոցեսորների մի շարք գծային վերամշակման խնդիրը կարելի է որոշել 
բանաձևով:[8][9] Կաղապար:Harvtxt [10]
Այլ մասնագիտացված ալգորիթմները մշակվել են նվազագույն ճյուղաորված ծառիհաշվարկելու համար,այդ գրաֆը այնքան մեծ է, որ դրանցից շատերը, խետք է պահպանվեն սկավառակի վրա`ցանկացած ժամանակ: Այս արտաքին հիշողության ալգորիթմները, օրինակ ինչպես նկարագրված է "Ճարտարագիտական արտաքին հիշողության նվազագույն ճյուղաորված ծառի ալգորիթմում" Roman Dementiev կողմից,[11] հեղինակների պնդումներով կարող են աշխատել երկուսից հինգ անգամ դանդաղ, քան սովորական հիշողության ալգորիթմները:
Խնդիրը կարելի է նաև դիտարկել բաշխված ձևով:
MST-ն ամբողջական գրաֆներում [խմբագրել]
Alan M. Frieze-ը ցույց տվեց, որ հաշվի առնելով ամբողջական գրաֆը n բարձրություններում, որոնք անկախ են F ֆունկցիայից, բավարարում են 
satisfying 
պայմանինն, ապաn-ը մոտենում է +∞, MST-ի ակնկալվող կշիռն է 
, որտեղ 
-ն Riemann-ի ֆունկցիայի գործառույթն է: Համաձայն լրացուցիչ սահմանապակ շեղումների Alan M. Frieze նաև ապացուցեց կոնվերգենցիայի հավանականությունը: Հետագայում J. Michael Steele ցույց տվեց, որ փոփոխության ենթադրությունը, կարող է նվազել:
Ավելի ուշSvante Janson իր աշխատանքում սահմանեց կենտորնական սահմանաչափի թեորեմը MST-ի կշռի համար:
Պատահական ![[0,1]](http://upload.wikimedia.org/math/c/c/f/ccfcd347d0bf65dc77afe01a3306a96b.png)
միջակայքի համար, նվազագույն ճյուղավորված ծառի ճշգրիտ սպասվող մեծությունը նախատեսվել էր փոքր ամբողջական գրաֆների համար:[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-նվազագույն ճյուղավորված ծառին):
Էվկլիդյան նվազագույն ճյուղավորված ծառը, գրաֆի ճյուղավորված ծառ է, եզրի կշիռներին համապատասխան, ինչպես նաև Էվկլիդյան հեռավորություն բարձրությունների միջև,որոնք տարածքի միավորներ են:
Ուղագծային նվազագույն ճյուղավորված ծառը, գրաֆի ճյուղավորված ծառ է, եզրի կշիռներին համապատասխան,ինչպես նաև ուղագծային հեռավորություն բարձրությունների միջև, որոնք տարածքի միավորներ են:
Տես նաև [խմբագրել]
- Reverse-Delete algorithm
- Dijkstra's algorithm
- Spanning tree protocol, used in switched networks
- Minimum spanning tree-based image segmentation
- Edmonds's algorithm
- Distributed minimum spanning tree
- Prim's algorithm
- Kruskal's algorithm
- Steiner tree
- Borůvka's algorithm
Հղումներ [խմբագրել]
- ↑ 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:.
- ↑ 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:.
- ↑ 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:
- ↑ 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.
- ↑ Chazelle, Bernard (2000), «A minimum spanning tree algorithm with inverse-Ackermann type complexity», Journal of the Association for Computing Machinery 47 (6), doi:.
- ↑ Chazelle, Bernard (2000), «The soft heap: an approximate priority queue with optimal error rate», Journal of the Association for Computing Machinery 47 (6), doi:.
- ↑ Pettie, Seth; Ramachandran, Vijaya (2002), «An optimal minimum spanning tree algorithm», Journal of the Association for Computing Machinery 49 (1), doi:.
- ↑ 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:.
- ↑ 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:.
- ↑ 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:.
- ↑ 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.
- ↑ Steele, J. Michael (2002), «Minimal spanning trees for graphs with random edge lengths», Mathematics and computer science, II (Versailles, 2002), Basel: Birkhäuser
- ↑ Gabow, Harold N. (1977), «Two algorithms for generating weighted spanning trees in order», SIAM Journal on Computing 6 (1).
- ↑ Eppstein, David (1992), «Finding the k smallest spanning trees», BIT 32 (2), doi:.
- ↑ Frederickson, Greg N. (1997), «Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees», SIAM Journal on Computing 26 (2), doi:.
Հավելյալ նյութեր [խմբագրել]
- Graham, R. L.; Hell, Pavol (1985), «On the history of the minimum spanning tree problem», Annals of the History of Computing 7 (1), doi:.
- Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová. (Section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's.)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp. 561–579.
- Eisner, Jason (1997). State-of-the-art algorithms for minimum spanning trees: A tutorial discussion. Manuscript, University of Pennsylvania, April. 78 pp.
- Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Using minimum spanning tree as method of demographic analysis of ethnic diversity across the United States).
