Կրուսկալի ալգորիթմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Կրուսկալի ալգորիթմը գրաֆների տեսության մեջ ժլատ ալգորիթմ է, որը փնտրում է նվազագույն ճյուղավորված ծառը կապված կշռված գրաֆի հետ։ Դա նշանակում է, որ այն փնտրում է բնագավառներ, որոնք ձևավորում են ծառ, որը պարունակում է բոլոր գագաթները, որտեղ ծառի բոլոր եզրերի ամբողջական կշիռը նվազագույնն է։ Եթե բոլոր գրաֆները կապված չեն, այն որոնում է նվազագույն ճյուղավորված անտառը (նվազագույն ճյուղավորված ծառը յուրաքանչյուր միացված կոմպոնենտի համար).

Այս ալգորիթմը առաջին անգամ հայտնվել է Ամերիկյան Մաթեմատիկական Միության վարույթի ժամանակ 1956 թվականին, և գրվել է Ջոզեֆ Կրուսկալի կողմից.

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

  • ստեղծել F անտառը (մի շարք ծառեր), որտեղ գրաֆի յուրաքանչյուր եզր առանձին ծառ է
  • ստեղծել մի շարք S, որոնք պարունակում են գրաֆի բոլոր եզրերը
  • մինչ Sդատարկ չէ և F-ը դեռ ճյուղավորվոծ չէ
    • հեռացնել S-ից նվազագույն կշիռ ունեցող ծայրը
    • եթե այդ ծայրը պարունակում է երկու տարբեր ծառեր, ապա ավելացնել դա անտառին՝ միավորելով երկու ծառերը որպես մեկ ծառ
    • հակառակ դեպքում անհետացնել այդ ծայրը։

Ալգորիթմի դադարեցման դեպքում անտառը կունենա միայն մեկ կոմպոնենտ և ձևավորի գրաֆի նվազագույն ճյուղավորված ծառը։

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

Երբ E-ն գրաֆի եզրերի թիվն է և V-ն բարձրության թիվը, Կրուսկալի ալգորիթմը կարող է ցույց տալ, որ O(E log E) ժամանակում աշխատելը, կամ որ նույնն է` O(E log V) ժամանակում, բոլորը պարզ կառուցվածքով տվյալների հետ է։ Այս կատարման ժամանակները հավասարազոր են, որովհետև.

  • E-ն ամենամեծ V2-ում է և \log V^2 = 2 \log V \; O(log V) է։
  • Եթե մենք անտեսում ենք առանձին բարձրությունները, որոնցից յուրաքնչյուրը կարող է լինել սեփական կոմպոնենտ նվազագույն ճյուղավորված անտառում, VE+1, այսպիսով` log V O(log E) է։

Մենք կարող ենք հասնել այդ կապվածությանը հետևյալ կերպ. առաջին հերթին տեսակավորենք եզրերը ըստ կշիռների` օգտագործելով համեմատության տեսակը O(E log E) ժամանակում, այս քայլը թույլ է տալիս "հեռացնել S-ից նվազագույն կշիռ ունեցող եզրը " հաստատուն ժամանակում աշխատելու համար։ Այնուհետև մենք օգտագործում ենք տվյալների չհատվող հավաքածուի կառուցվածքը (Միավորում&Որոնում) վերահսկելու համար, թե որ կոմպոնենտը ինչ բարձրություն ունի։ Մենք պետք է իրականացնենք O(E) գործողություններ, երկու 'փնտրման' գործողություններ և մեկ միավորում յուրաքանչյուր եզրի համար։ Նույնիսկ ամենապարզ տվյալների չհատվող հավաքածուի կառուցվածքը, ինչպիսինն են չհատվող անտառները կարող են իրականացնել O(E) գործողություններ O(E log V) ժամանակում։ Այնուամենայնիվ ընդհանուր ժամանակը` O(E log E) = O(E log V).

Պայմանով, որ եզրերը կամ արդեն տեսակավորված են կամ կարող են տեսակացորված լինել գծային ժամանակում, ալգորիթմը կարող է օգտագործել ավելի բարդ տվյալների չհատվող հավաքածուի կառուցվածք O(E α(V)) ամանակում աշխատելու համար, որտեղ α-ն չափազանց դանդաղ աճող հակադրությունն է Ակերմանի ֆունկցիայի:

Օրինակ[խմբագրել]

Բեռնել նմուշ տվյալներ

Պատկեր Նկարագրություն
Kruskal Algorithm 1.svg AD-ն և CE-ն ամենակարճ եզրերն են` 5 լայնությամբ, և AD-ն կամայականորեն է ընտրվել։
Kruskal Algorithm 2.svg CE-ն ամենակարճ եզրն է` 5 լայնությամբ, որը չի ձևավորում ցիկլ, այսպիսով այն համարվում է երկրորդ եզրը։
Kruskal Algorithm 3.svg Հաջորդ եզրը` DF-ը` 6 լայնությամբ, առանձնացվում է օգտագործելով նույն մեթոդը։
Kruskal Algorithm 4.svg Հաջորդ ամենակարճ եզրերն են AB-ն և BE-ն` երկուսն էլ 7 լայնությամբ։ AB-ն ընտրվել է կամայականորեն։ BD եզրը առանձնացվում է կարմիր գույնով, որովհետև արդեն կա կանաչ գույն B-ի և A-ի միջև, այսպիսով այն կձևավորի ցիկլ (ABD), եթե այն ընտրվի։
Kruskal Algorithm 5.svg Պրոցեսը շարունակում է առանձնացնել հաջորդ ամենափոքր եզրը` BE-ն` 7 լայնությամբ։ Այս փուլում ավելի շատ եզրեր են առանձնացվում կարմիրով` BC-ն, որովհետև այն կձևավորի BCE հանգույց, DE-ն, որովհետև այն կձևավորի DEBA հանգույց, և FE-ն, որովհետև այն կձևավորի FEBAD:
Kruskal Algorithm 6.svg Վերջապես պրոցեսն ավարտվում է EG եզրով` 9 լայնությամբ, և նվազագույն ճյուղավորված ծառը գտնված է։

Ստույգության ապացույց[խմբագրել]

Ապացույցը բաղկացած է երկու մասից։ Առաջինը ապացուցվում է, որ ալգորիթմը ներկայացնում է ճյուղավորված ծառ: Երկրորդը ապացուցվում է, որ կառուցված ճյուղավորված ծառն ունի նվազագույն կշիռ։

Ճյուղավորված ծառ[խմբագրել]

Ենթադրենք ունենք միացված, կշռված P գրաֆ և ենթագրաֆ` ներկայացված ալգորիթմի կողմից Y P: Y-ը չի կարող ունենալ ցիկլ, քանի որ ցիկլին ավելացրած վերջին եզրը կլիներ մեկ ծառի մեջ և ոչ երկու տարբեր ծառերի։ Y-ը չի կարող լինել անջատ, քանի որ առաջինը բախվում է այն եզրին, որը միավորում է Y-ի երկու կոմպոնենտները։ Այսպիսով, Y-ը հանդիսանում է P-ի ճյուղավորված ծառը։

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

Մենք ցույց տվեցինք, որ հետևյալ P առաջարկությունը ճիշտ է։ Եթե F-ը եզրերի շարք է` ընտրված ալգորիթմի ցանկացած փուլում, ապա գոյություն ունի որևէ նվազագույն ճյուղավորված ծառ, որը պարունակում է F:

  • P-ն ճիշտ է սկզբում, երբ F-ը դատարկ է. որևէ նվազագույնճյուղավորված ծառ պետք է լինի, և գույություն ունի մեկը, որովհետև կշռված, միացված գրաֆը միշտ ունի նվազագույն ճյուղավորված ծառ։
  • Հիմա ենթադրենք, որ P-ն ճիշտ է որոշ ոչ վերջնական F եզրի համար և T-ն նվազագույն ճյուղավորված ծառն է, որը պարունակում է F: Եթե հաջորդ ընտրված e եզրը նույնպես T-ում է, ապա P-ն ճիշտ է F + e-ի համար։ Հակառակ դեպքում, T + e-ն ունի C ցիկլ և կա մեկ այլ` f եզր, որը C-ում է։ (Եթե չլիներ f եզրը, ապա e-ն չէր կարող ավելացվել F-ին, քանի որ դա կստեղծեր C ցիկլ։) Ապա Tf + e-ն ծառ է և ունի նույն կշիռը, ինչ T-ն, քանի որ T-ն ունի նվազագույն կշիռ և f-ի կշիռը չի կարող լինել ավելի քիչ, քան e-ի կշիռը, հակառակ դեպքում ալգորիթմը կընտրեր fe-ի փոխարեն։ Այսպիսով, Tf + e-ն նվազագույն ճյուղավորված ծառ է, որը պարունակում է F + e:
  • Հետևաբար, P -ն իմաստ ունի, երբ F-ը դառնում է ճյուղավորված ծառ, որը միայն հնարավոր է, երբ F-ը նվազագույն ճյուղավորված ծառ է։

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

  • Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50
  • 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. Section 23.2: The algorithms of Kruskal and Prim, pp. 567–574.
  • Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java, Fourth Edition. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0. Section 13.7.1: Kruskal's Algorithm, pp. 632.