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

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

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

Հատկություններ

Հնարավոր բազմազանություն 

Կարող են լինել մի քանի նվազագույն ճյուղավորված ծառեր` նույն կշիռն ունեցող; մասնավորապես, եթե տվյալ գրաֆի բոլոր եզրերը նույնն են, ապա տվյալ գրաֆի յուրաքանչյուր ճյուղավորված ծառը նվազագույնն է։
Եթե գրաֆում կան n բարձրություններ, ապա յուրաքանչյուր երրորդը ունի n-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)։ Ամենաարագ ոչ-randomized համեմատությունը գործող ալգորիթմի համար, ըստ
Bernard Chazelle-ի, հիմնված է փափուկ կույտի վրա։

Նրա աշխատանքի ժամանակահատվածն է O(m α(m,n)),որտեղ՝
m-ը եզրերի քանակն է,
n-ը բարձրությունների քանակն է,
a-ն Ackermann գործառույթի դասական ֆունկցիոնալ հավանականությունն է։ α ֆունկցիան աճում է շատ դանդաղ, այնպես որ, բոլոր գործնական նպատակների համար կարելի է համարել հաստատուն, ոչ մեծ 4-ից։ Seth Pettie և Vijaya Ramachandran գտան օպտիմալ դետերմինացված համեմատություն՝ հիմնված նվազագույն ճյուղաորված ծառի ալգորիթմի վրա, որը անհայտ հաշվողական բարդություն է։

Ուսումնասիրությունները նաև համարվում են զուգահեռ ալգորիթմներ, նվազագույն ճյուղաորված ծառի խնդրի համար։
Պրոցեսորների մի շարք գծային վերամշակման խնդիրը կարելի է որոշել  բանաձևով։

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

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

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

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

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

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

k-նվազագույն ճյուղավորված ծառերի A փաթեթը, k ճյուղավորված ծառերի մի ենթաբազմություն է (դուրս է բոլոր հնարավոր ճյուղավորված ծառերից), այնպես որ ոչ մի ճյուղավորված ծառ՝ ենթաբազմությունից դուրս, չունի փոքր կշիռ, (Նշենք, որ այս պրոբլեմը չի վերաբերվում 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

Հղումներ

Հավելյալ նյութեր 
 .
 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).

Արտաքին հղումներ 
 Jeff Erickson's MST lecture notes 
 Implemented in BGL, the Boost Graph Library
 The Stony Brook Algorithm Repository - Minimum Spanning Tree codes
 Implemented in QuickGraph for .Net

Գրաֆների տեսություն