Մասնակից:Teni Tadevosyan/Սևագրություն

Էվկլիդյան նվազագույն ճյուղավորված ծառ'-ն կամ EMST-ը minimum spanning treeէ հարթության վրա մի շարք n կետերից (կամ ընդհանրապես ℝ^d),որտեղ գագաթի կշիռը յուրաքանչյուր զույգ միավորների միջև հեռավորությունն է այդ երկեւ կետերի միջև.Այդ տեսանկյունից պարզ է որ EMST-ը կետերը իրար է միացնում գծերի միջոցով և ցանկացած կետ կարող է հասնել մեկ ուրիշին հետևելով այդ գծերին.

Հարթության վրա EMST-ը կարող է հանդես գալ Θ(n log n)այն ժամանակ երբ O(n)-ը տարածություն է algebraic decision tree հաշվարկի մոդել-ում. բարդությունների ավելի արագ randomized algorithms-ները O(n log log n)հայտնի են որպես հաշվարկի ավելի հզոր մոդելներ,որոնք ավելի ճշգրիտ մոդելներ են իրենց համակարգչային իրական կարողություններով.^[1]

Բարձրագույն հարթություններում գտնելով օպտիմալ ալգորիթմներ մնում է (d ≥ 3) open problem.

Պարտավորվածության իջեցում[խմբագրել | խմբագրել կոդը]

Ասիմտոտ իջեցված սահմանը Ω(n log n)-ի համար time complexity -ի է .որը կարող է լուծել EMST-ի պրոբլեմները սահմանափակված մոդելների հաշվարկում,ինչպիսիք են algebraic decision tree -ն և algebraic computation tree մոդելները, որտեղ ալգորիթմը ունի ներդրված միավորներ միայն որոշակի սահմանափակված պրիմիտիվներով ,որոնք կատարում են պարզ հանրահաշվական հաշվարկներ իրենց կոորդինատներում:այս մոդելում , closest pair of points problem պահանջվում է Ω(n log n)ժամանակ, բայց ամենամոտ զույգը անհրաժեշտ է EMST-ի եզրին, ուստի EMST-ը նույնպես պահանջում է շատ ժամանակ .^[2] Ինչևէ ,եթե ներմուծված միավորները ունեն ամբողջական թիվ համակարգում և bitwise operation-ը և [Random access|table indexing]] գորշողությունները թույլատրվում է օգտագործել այդ համակարգում այնուհետև ավելի արագ են ալգորիթմները դառնում հնարավոր .^[1]

Ալգորիթմներ,որոնք հաշվում են EMST-ը երկու հարթություններում[խմբագրել | խմբագրել կոդը]

Ամենապարզ ալգորիթմը գտնել EMST-ը երկու հարթություններում ,տալով n միավորը,իրականում կառուցել complete graph n-ի վրա,որը n(n-1)/2 գագաթն է,հաշվել յուրաքանչյուր գագաթի կշիռը գտնելով հեռավորությունը ցանկացած զույգ միավորների միջև և հետո նոր ստեղծել standard minimum spanning tree-ի ալգորիթմ (ինչպիսին է Prim's algorithm-ի վերսիան կամ Kruskal's algorithm).Քանի որ այդ գրաֆիկն ունի Θ(n²)տեսքը, գագաթ n կետով, կառուցելը առդեն պահանջում է Ω(n²) ժամանակ. Այս որոշումը հաճախ պահանջում է Ω(n²) տարածություն պահելու բոլոր գագաթները.

Լավագույն մոտեցումը EMST-ը հարթության վրա գտնելու, դա նշելն է թե ինչպես յուրաքանչյուր գրաֆիկ Delaunay triangulation n կետից, ավելի է փոքրացնում գագաթների շարքը:

Հաշվել Delaunay triangulation-ը O(n log n) ժամանակ և O(n)տարածությունում.Որովհետև Delaunay triangulation-ը դաplanar graph է,և այնտեղ չկա ավելի քան երեք անգամ ավելի շատ գագաթներ քան ուրիշ գրաֆիկներում,դա առաջացնում է միայն O(n) գագաթներ.
Պիտակավորել յուրաքնչյուր գագաթը իր երկարությամբ
Ստեղծել գրաֆիկ նվազագույն ճյուղավորված ծառ ալգորիթմով և այդ գրաֆիկի վրա գտնել նվազագույն ճյուղավորված ծառ -ը. Քանի որ այնտեղ O(n)-ը գագաթներն են,անհրաժեշտ է O(n log n) կայուն նվազագույն ճյուղավորված ծառ ալգորիթմներ ինչպիսին են Borůvka's algorithm-ը, Prim's algorithm-ը, կամ Kruskal's algorithm-ը.

Վերջնական առդյունքը հանդիսանում է ալգորիթմը O(n log n) ժամանակով և O(n) տարածությամբ.

Եթե շահույթը կորդինացված ամբողջ թիվ է և կարող է օգտագործվել array indices-ում,ավելի արագ ալգորիթմները դառնում են հնարավոր: Delaunay triangulation-ը կարող է կառուցվել randomized algorithm-ով O(n log log n) ակնկալված ժամանակ.^[1] Բացի այդ,քանի որ Delaunay triangulation-ը planar graph է,դրա նվազագույն ճյուղավորված ծառ-ը կարելի է գտնել linear time-ում Borůvka's ալգորիթմի տարբերակով,որը հեռացնում է բոլորը բայց ամենաէժան եզրը տարրերի ցանկացած զույգի միջև ալգորիթմի ամեն մի փուլից հետո.^[3] Հետևաբար ընդհանուր ակնկալվող ժամանակը ալգորիթմի համար դա O(n log log n).^[1]

Բարձրագույն մեծություններ[խմբագրել | խմբագրել կոդը]

Խնդիրը հաճախ կարող է լինել ընդհանրացված n կետից մինչև d-ծավալային տարածք ℝ^d.Բարձրագույն մեծություններում փոխկապակցվածությունը որոշվում է Delaunay triangulation-ով (որը, նմանապես, բաժանմունք է convex hull d-տարածական simplices) ,որը պառունակում է minimum spanning tree-ն ; ինչևէ, triangulation -ը պետք է պարունակի ամբողջ գրաֆիկը.^[4] Հետևաբար, գտնելով որ Euclidean minimum spanning tree-ն ամբողջական գրաֆիկի spanning tree է կամ Delaunay triangulation-ի spanning tree երկուսն ել տանւմ են O(dn²)ժամանակի.Երեք մեծությունների համար հնարավոր է գտնել minimum spanning tree-ն ժամանակին O((n log n)^4/3),և ցանկացած մեծություն ավելի քան երեքը հնարավոր է վճռելու ժամանակին,այսինքն ավելի արագ քան quadratic ժամանակ ամբողջական գրաֆիկում և Delaunay triangulation ալգորիթմներում.^[4]^[5]

Subtree of Delaunay triangulation[խմբագրել | խմբագրել կոդը]

EMST-ի բոլոր եզրերը եզրեր են relative neighborhood graph-ի,^[6]^[7]^[8] որոնք իրենց հերթին ունեն եզրեր Gabriel graph-ից, ունեն եզրեր Delaunay triangulation-ի կետերից ,^[9]^[10] Որոնք կարելի է ապացուցել համարժեքության միջոցով contrapositive հայտարարությամբ.Ապացույցը հիմնված է minimum spanning tree-ի և Delaunay triangulation-ի երկու հատկությունների հիման վրա:

(the cycle property of minimum spanning trees): գրաֆիկի ցանկացած C շրջանի վրա,եթե C եզրի e կշիռը ավելի մեծ է քան C եզրի այլ կշիռները,ապա այդ կշիռները MST-ին չեն կարող պատկանել.
( Delaunay triangulation-ի սեփականություն): Եթե կա շրջան իր սահմաններին ներգծված երկու կետերով,որը չի պարունակում այլ կետեր գիծը այդ երկու կետերի միջև եզրն է ամեն մի Delaunay triangulation-ի.

Դիտարկենք e եզրի միջև ընկած p և q կետերը ,որոնք Delaunay triangulation-ի եզրերը չեն. Property 2-ն ենթադրում է ,որ Cշրջանը e-ի հետ նրանց տրամագիծը պետք է պարունակի մեկ այլ r կետ ներսում . Բացի այդ r-ը ավելի մոտ է p-ն և q-ին քան նրանք միմյանց և այսպիսով եզրերը դեպի p-ից q ամենաերկար եզրն է կետերի շրջանակներում p → q → r → p, և property 1 -ի e -ն ցանկացած EMST-ի չէ.

Սպասվելիք չափը[խմբագրել | խմբագրել կոդը]

EMST-ի սպասվելիք չափը մեծ թվով միավորների համար սահմանվել է J. Michael Steele-ի կողմից . Եթե $f$ -ը հավանականության ֆունկցիայի տեսակարար կշիռն է միավորներ հավաքելիս, այնուհետև մեծ $n$ -ի և $d\neq 1$ -ի EMST չափի համար մոտավորապես

c(d)n^{\frac {d-1}{d}}\int _{\mathbb {R} ^{d}}f(x)^{\frac {d-1}{d}}dx

է, որտեղ

$c(d)$ -ը դա հարթության վրաի հաստատուն կախվածություն է $d$ -ից. Կոնստանտի իրական արժեքը անհայտ է բայց կարող է գնահատված լինել փորձնական ապացույցներից.

Ծրագրեր[խմբագրել | խմբագրել կոդը]

Էվկլիդյան նվազագույն ճյուղավորված ծառ -ի ակնհայտ հայտը դա ամենաէժան լարերի կամ խողովակների ցանց գտնելն է ,որը պետք է միացնել մի շարք վայրերում. Ինչևէ, ամենանման ցանցերը նախընտրում են k-ծառին միացված գրաֆը, այսպիսով ցանկացած անհատական հղման ձախողումը չի պառակտում ցանցը մասերի.

Մեկ ուրիշ EMST-ի ծրագիրը դա constant-factor approximation algorithm-ն է մոտավորապեսEuclidean traveling salesman problem-ի լուծման համար, traveling salesman problem- վերսիան մի շարք հարթության կետերի և երկարության ծայրերի հետ .

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

խնդրի լուծումը Էվկլիդյան նվազագույն ճյուղավորված ծառ -ի համար սկսվում է հետևյալով : Տալով tree T = (V, E)-ը, գտնել D(u) կետը ցանկացած u ∈ V' 'այսպիսով T -ն D(u) նվազագույն ճյուղավորված ծառ -ի համար : u ∈ V, կամ որոշել որ նման տեղեր գոյություն ունեն. Իրականության մեջ փորձարկումը the plane դա NP-hard.^[11]

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

↑ ^1,0 ^1,1 ^1,2 ^1,3 Buchin, Kevin; Mulzer, Wolfgang (2009), «Delaunay triangulations in O(sort(n)) time and more», [[Symposium on Foundations of Computer Science|Proc. 50th IEEE Symposium on Foundations of Computer Science]] (PDF), էջեր 139–148, doi:10.1109/FOCS.2009.53 {{citation}}: URL–wikilink conflict (օգնություն).
↑ Yao, A. C.-C. (1989), «Lower bounds for algebraic computation trees with integer inputs», Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), էջեր 308–313, doi:10.1109/SFCS.1989.63495.
↑ Eppstein, David (1999), «Spanning trees and spanners», in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, էջեր 425–461; Mareš, Martin (2004), «Two linear time algorithms for MST on minor closed graph classes» (PDF), Archivum mathematicum, 40 (3): 315–320.
↑ ^4,0 ^4,1 Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), «Euclidean minimum spanning trees and bichromatic closest pairs», Discrete and Computational Geometry, Springer, 6 (1): 407–422, doi:10.1007/BF02574698.
↑ Chatterjee, S.; Connor, M.; Kumar, P. (2010,), «Geometric minimum spanning trees with GeoFilterKruskal», in Festa, Paola (ed.), Symposium on Experimental Algorithms, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, էջեր 486–500, doi:10.1007/978-3-642-13193-6_41{{citation}}: CS1 սպաս․ հավելյալ կետադրություն (link).
↑ Jerzy W. Jaromczyk and Godfried T. Toussaint, "Relative neighborhood graphs and their relatives," Proceedings of the IEEE, Vol. 80, No. 9, September 1992, pp. 1502-1517.
↑ Godfried T. Toussaint, "Comment on algorithms for computing relative neighborhood graph," Electronics Letters, Vol. 16, No. 22, October l981, pp. 860-861.
↑ Godfried T. Toussaint, "The relative neighborhood graph of a finite planar set," Pattern Recognition, Vol. 12, 1980, pp. 261-268.
↑ Robert Pless. Lecture 17: Voronoi Diagrams and Delauney Triangulations. Spring 2003, Computational Geometry Class Page. Associate Professor of Computer Science and Engineering at Washington University. http://www.cs.wustl.edu/~pless/506/l17.html
↑ Robert Sedgewick and Kevin Wayne. Minimum Spanning Tree lecture notes. Computer Science 226: Algorithms & Data Structures, Spring 2007. Princeton University. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf
↑ Eades, Peter; Whitesides, Sue (1994), «The realization problem for Euclidean minimum spanning trees is NP-hard», Proc. 10th ACM Symposium on Computational Geometry, էջեր 49–56, doi:10.1145/177424.177507.

Category:Spanning tree Category:Geometric graphs

[bm09-1] 1,0 ^1,1 ^1,2 ^1,3 Buchin, Kevin; Mulzer, Wolfgang (2009), «Delaunay triangulations in O(sort(n)) time and more», [[Symposium on Foundations of Computer Science|Proc. 50th IEEE Symposium on Foundations of Computer Science]] (PDF), էջեր 139–148, doi:10.1109/FOCS.2009.53 {{citation}}: URL–wikilink conflict (օգնություն).

[2] Yao, A. C.-C. (1989), «Lower bounds for algebraic computation trees with integer inputs», Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), էջեր 308–313, doi:10.1109/SFCS.1989.63495.

[3] Eppstein, David (1999), «Spanning trees and spanners», in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, էջեր 425–461; Mareš, Martin (2004), «Two linear time algorithms for MST on minor closed graph classes» (PDF), Archivum mathematicum, 40 (3): 315–320.

[EMSTBCP-4] 4,0 ^4,1 Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), «Euclidean minimum spanning trees and bichromatic closest pairs», Discrete and Computational Geometry, Springer, 6 (1): 407–422, doi:10.1007/BF02574698.

[EMSTCCP-5] Chatterjee, S.; Connor, M.; Kumar, P. (2010,), «Geometric minimum spanning trees with GeoFilterKruskal», in Festa, Paola (ed.), Symposium on Experimental Algorithms, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, էջեր 486–500, doi:10.1007/978-3-642-13193-6_41{{citation}}: CS1 սպաս․ հավելյալ կետադրություն (link).

[6] Jerzy W. Jaromczyk and Godfried T. Toussaint, "Relative neighborhood graphs and their relatives," Proceedings of the IEEE, Vol. 80, No. 9, September 1992, pp. 1502-1517.

[7] Godfried T. Toussaint, "Comment on algorithms for computing relative neighborhood graph," Electronics Letters, Vol. 16, No. 22, October l981, pp. 860-861.

[8] Godfried T. Toussaint, "The relative neighborhood graph of a finite planar set," Pattern Recognition, Vol. 12, 1980, pp. 261-268.

[9] Robert Pless. Lecture 17: Voronoi Diagrams and Delauney Triangulations. Spring 2003, Computational Geometry Class Page. Associate Professor of Computer Science and Engineering at Washington University. http://www.cs.wustl.edu/~pless/506/l17.html

[10] Robert Sedgewick and Kevin Wayne. Minimum Spanning Tree lecture notes. Computer Science 226: Algorithms & Data Structures, Spring 2007. Princeton University. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf

[11] Eades, Peter; Whitesides, Sue (1994), «The realization problem for Euclidean minimum spanning trees is NP-hard», Proc. 10th ACM Symposium on Computational Geometry, էջեր 49–56, doi:10.1145/177424.177507.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]