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

Տրված է չկապակցված գրաֆ։ Մեկ գրաֆը կարող է ունենալ բազմաթիվ ճյուղավորված ծառեր։ Մենք կարող ենք տալ կշիռ յուրաքանչյուր եզրին, որը հանդիսանում է մի շարք՝ ներկայացնելով, թե ինչ անբարենպաստ այն կարող է լինել և օգտագործել այն, որպեսզի նշանակի կշիռ ճյուղավորված ծառին՝ հաշվարկելով այդ ճյուղավորված ծառի եզրերի կշիռների գումարը։ Նվազագույն ճյուղավորված ծառը (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]՝

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

Եթե e1-ի կշիռը ավելի մեծ է, քան e2, համանման արգումենտը ներառում է {e2} $\cup$ 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]։

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

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

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

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

Alan M. Frieze-ը ցույց տվեց, որ հաշվի առնելով ամբողջական գրաֆը n բարձրություններում, որոնք անկախ են F ֆունկցիայից, բավարարում են $F$ satisfying $F'(0)>0$ պայմանինն, ապաn-ը մոտենում է +∞, MST-ի ակնկալվող կշիռն է $\zeta (3)/F'(0)$ , որտեղ $\zeta$ -ն Riemann-ի ֆունկցիայի գործառույթն է։ Համաձայն լրացուցիչ սահմանապակ շեղումների 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-նվազագույն ճյուղավորված ծառին)։

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

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

Տես նաև[խմբագրել | խմբագրել կոդը]

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. (1983 թ․ հունվար), «A distributed algorithm for minimum-weight spanning trees», ACM Transactions on Programming Languages and Systems, 5 (1): 66–77, doi:10.1145/357195.357200.
↑ 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): 533–55, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.
↑ 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): 321–328, doi:10.1145/201019.201022, MR 1409738
↑ 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, էջեր 713–722{{citation}}: CS1 սպաս․ location missing publisher (link).
↑ Chazelle, Bernard (2000), «A minimum spanning tree algorithm with inverse-Ackermann type complexity», Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456.
↑ Chazelle, Bernard (2000), «The soft heap: an approximate priority queue with optimal error rate», Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455.
↑ Pettie, Seth; Ramachandran, Vijaya (2002), «An optimal minimum spanning tree algorithm», Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431.
↑ 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): 297–323, doi:10.1145/375827.375847, MR 1868718.
↑ Pettie, Seth; Ramachandran, Vijaya (2002), «A randomized time-work optimal parallel algorithm for finding a minimum spanning forest», SIAM Journal on Computing, 31 (6): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.
↑ 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): 1366–1378, doi:10.1016/j.jpdc.2006.06.001.
↑ 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) (PDF), էջեր 195–208, Արխիվացված է օրիգինալից (PDF) 2011 թ․ օգոստոսի 9-ին, Վերցված է 2012 թ․ մայիսի 30-ին.
↑ Steele, J. Michael (2002), «Minimal spanning trees for graphs with random edge lengths», Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, էջեր 223–245, MR 1940139
↑ Gabow, Harold N. (1977), «Two algorithms for generating weighted spanning trees in order», SIAM Journal on Computing, 6 (1): 139–150, MR 0441784.
↑ Eppstein, David (1992), «Finding the k smallest spanning trees», BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188.
↑ Frederickson, Greg N. (1997), «Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees», SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.

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

Graham, R. L.; Hell, Pavol (1985), «On the history of the minimum spanning tree problem», Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/MAHC.1985.10011, MR 0783327.
Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Արխիվացված 2008-05-04 Wayback Machine 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).

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

Jeff Erickson's MST lecture notes Արխիվացված 2012-03-07 Wayback Machine
Implemented in BGL, the Boost Graph Library
The Stony Brook Algorithm Repository - Minimum Spanning Tree codes
Implemented in QuickGraph for .Net

[1] Gallager, R. G.; Humblet, P. A.; Spira, P. M. (1983 թ․ հունվար), «A distributed algorithm for minimum-weight spanning trees», ACM Transactions on Programming Languages and Systems, 5 (1): 66–77, 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): 533–55, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.

[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): 321–328, doi:10.1145/201019.201022, MR 1409738

[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, էջեր 713–722{{citation}}: CS1 սպաս․ location missing publisher (link).

[5] Chazelle, Bernard (2000), «A minimum spanning tree algorithm with inverse-Ackermann type complexity», Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456.

[6] Chazelle, Bernard (2000), «The soft heap: an approximate priority queue with optimal error rate», Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455.

[7] Pettie, Seth; Ramachandran, Vijaya (2002), «An optimal minimum spanning tree algorithm», Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431.

[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): 297–323, doi:10.1145/375827.375847, MR 1868718.

[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): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.

[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): 1366–1378, 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) (PDF), էջեր 195–208, Արխիվացված է օրիգինալից (PDF) 2011 թ․ օգոստոսի 9-ին, Վերցված է 2012 թ․ մայիսի 30-ին.

[12] Steele, J. Michael (2002), «Minimal spanning trees for graphs with random edge lengths», Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, էջեր 223–245, MR 1940139

[13] Gabow, Harold N. (1977), «Two algorithms for generating weighted spanning trees in order», SIAM Journal on Computing, 6 (1): 139–150, MR 0441784.

[14] Eppstein, David (1992), «Finding the k smallest spanning trees», BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188.

[15] Frederickson, Greg N. (1997), «Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees», SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]