Ամուր կապակցված բաղադրիչներ

Ամուր կապակցված բաղադրիչներով գրաֆ

Ամուր կապակցված բաղադրիչ, ուղղորդված գրաֆը կոչվում է ամուր կապակցված, եթե այն ուղիղ է գրաֆի վրա ամեն մի բարձունքից դեպի մեկ այլ ուրիշ բարձունք։ Մասնավորապես, դա նշանակում է, որ ուղիղները մեկ ուղղության են՝ ուղիղը a-ից դեպի b և միայն ուղիղը b-ից դեպի a։ Գրաֆ G-ի ամուր կապակցված բաղադրիչները նրա մաքսիմալ ամուր կապակցված ենթագրաֆներն են։ Եթե ինչ-որ ամուր կապակցված բաղադրիչ մի բարձունքից բացակայում է, գրաֆի արդյունքն է ուղղորդված ացիկլիկ գրաֆը՝ G կոնդենսացիան։ Ուղղորդված գրաֆը ացիկլիկ է միայն և միայն այն դեպքում, եթե այն չունի ամուր կապակցված ենթագրաֆներ ոչ ավել, քան մեկ բարձունքի հետ, որովհետև ուղղորդված ցիկլը ամուր կապակցված է և յուրաքանչյուր ոչ սովորական ամուր կապակցված բաղադրիչ պարունակում է առնվազն մեկ ուղղորդված ցիկլ։

Ալգորիթմը

Այս ալգորիթմն իրարից անկախ առաջարկել են Կոսարայուն ( անգլ.՝ Kosaraju) և Շարիրը ( անգլ.՝ Sharir) 1979 թ.: Դա, իրականացման տեսակետից, ոչ բարդ ալգորիթմ է, որը հիմնված է ըստ խորության փնտրման ալգորիթմի վրա, և, հետևաբար, աշխատում է ժամանակում։

Ալգորիթմի առաջին քայլին անցնում ենք գրաֆի բոլոր գագաթներով և յուրաքանչյուր չայցելած գագաթից կատարում ենք փնտրում ըստ խորության։ Ընդ որում յուրաքանչյուր գագաթի համար պահում ենք նրա դուրս գալու ժամանակը։ Այդ արժեքները առանցքային դեր են խաղում ալգորիթմում, ինչն արտահայտված է ստորև բերված թեորեմում։

Նախ սահմանենք ուժեղ կապակցվածության կոմպոնենտից դուրս գալու ժամանակը որպես բոլոր պատկանում է համար -երից մաքսիմում։ Բացի այդ թեորեմի ապացույցում պետք են գալիս նաև յուրաքանչյուր գագաթ մտնելու ժամանակները։ Սահմանենք ուժեղ կապակցվածության կոմպոնենտ մտնելու ժամանակը որպես պատկանում է համար -երից մինիմում։

Թեորեմ

Դիցուք և ’-ը ուժեղ կապակցվածության երկու տարբեր կոմպոնենտներ են, և, դիցուք կոնդենսացիայի գրաֆում նրանց միջև կա (’) կող։ Այդ դեպքում :

Ապացույց

Հարկավոր է երկու տարբեր դեպք դիտարկել կախված նրանից, թե ըստ խորության շրջանցումը առաջինը երկու կոմպոնենտներից որը կմտնի, այսինքն կախված և արժեքներից։

  1. Առաջինը հասել է կոմպոնենտին։ Դա նշանակում է, որ ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի պատկանում է գագաթի, երբ և ’ կոմպոնենտների մնացած բոլոր գագաթները դեռ այցելված չեն։ Բայց քանի որ ըստ պայմանի կոնդենսացիայի գրաֆում կա (’) կող, ապա գագաթից հասանելի կլինի ոչ միայն ամբողջ կոմպոնենտը, այլև ամբողջ ’ կոմպոնենտը։ Դա նշանակում է գագաթից ըստ խորության շրջանցումը կանցնի և ’ կոմպոնենտների բոլոր գագաթներով, նշանակում է նրանք բոլորը ըստ խորության շրջանցման ծառում կլինեն գագաթի ժառանգներ, այսինքն ցանկացած պատկանում է միավորած ’ գագաթի համար տեղի կունենա , ինչը և պահանջվում էր ապացուցել։
  1. Առաջինը հասել է ’ կոմպոնենտին։ Կրկին, ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի պատկանում է ’ գագաթի, ընդ որում և ’ կոմպոնենտների մնացած բոլոր գագաթներն այցելված չեն։ Քանի որ, ըստ պայմանի կոնդենսացիայի գրաֆում գոյություն ունի (’) կող և քանի որ կոնդեսնացիայի գրաֆն ացիկլիկ է, նշանակում է հակառակ ճանապարհ գոյություն չունի, այսինքն v-ից ըստ խորության շրջանցումը չի հասնի -ի բոլոր գագաթներին։ Դա նշանակում է, որ նրանք կայցելվեն ըստ խորության շրջանցման կողմից ավելի ուշ, որտեղից և հետևում է, որ Չհաջողվեց վերլուծել (շարահյուսության սխալ): {\displaystyle tout[C]>tout[C’]} :

Ապացուցված թեորեմը ուժեղ կապակցվածության կոմպոնենտների փնտրման ալագորիթմի հիմքն է հանդիսանում։ Նրանից հետևում է, որ կոնդենսացիայի գրաֆում ցանկացած (’) կող գնում է ավելի մեծ -ով կոմպոնենտից դեպի ավելի փոքր -ով կոմպոնենտը։

Եթե կարգավորենք բոլոր պատկանում է գագաթները ըստ դուրս գալու ժամանակների նվազման կարգով, ապա առաջինը կլինի մի գագաթ, որը պատկանում է ուժեղ կապակցվածության կոմպոնենտներից “արմատին”, այսինքն որը կոնդենսացիայի գրաֆում մտնող կող չունի։ Հիմա մենք կուզենայինք այդ գագաթից այնպիսի շրջանցում բաց թողնել, որը այցելեր միայն այդ ուժեղ կապակցվածության կոմպոնենտը և ուրիշ ոչ մի կոմպոնենտ չմտներ։ Այդպիսով մենք կարող ենք աստիճանաբար առանձնացնել ուժեղ կապակցվածության բոլոր կոմպոնենտները. գրաֆից հեռացնելով առաջին առանձնացված կոմպոնենտի գագաթները, կարող ենք մնացածից կրկին գտնել ամենամեծ -ով գագաթը, նրանից բաց թողնել այդ շրջանցումը և այդպես շարունակ։

Որպեսզի սովորենք այդպիսի շրջանցում անել, դիտարկենք տրանսպոնացված գրաֆը։ Այն ստացվում է գրաֆից յուրաքանչյուր կողի ուղղությունը հակառակի փոխելու արդյունքում։ Դժվար չէ հասկանալ, որ այդ գրաֆում կլինեն նույն ուժեղ կապակցվածության կոմպոնենտները, ինչ սկզբնական գրաֆում։ Ավելին, կոնդենսացիայի գրաֆը կլինի գրաֆի տրանսպոնացումը։ Դա նշանակում է, որ այժմ մեր դիտարկած “արմատ” հանդիսացող կոմպոնենտից արդեն դուրս եկող կող չի լինի։

Այսպիսով, գագաթը պարունակող ամբողջ “արմատ” ուժեղ կապակցվածության կոմպոնենտը շրջանցելու համար բավական է բաց թողնել շրջանցումը գրաֆի գագաթից։ Այդ շրջանցումը կայցելի ուժեղ կապակցվածության այդ կոմպոնենտի բոլոր գագաթները և միայն դրանք։ Ինչպես արդեն ասվել է, ապա կարող ենք այդ գագաթները համարել գրաֆից հեռացված, գտնել հաջորդ գագաթը մաքսիմալ արժեքով և բաց թողնել շրջանցումը տրանսպոնացված գրաֆում նրանից, և այլն։

Այսպիսով, մենք կառուցեցինք ուժեղ կապակցվածության կոմպոնենտների առանձնացման հետևյալ ալգորիթմը.

Քայլ 1։ G գրաֆում կատարել ըստ խորության շրջանցումների շարք, որը վերադարձնում է գագաթները ըստ tout ելքի ժամանակի աճման կարգով, այսինքն կառուցում է ինչ-որ մի order ցուցակ։

Քայլ 2։ Կառուցել տրանսպոնացված GT գրաֆը։ Կատարել մի շարք շրջանցումներ ըստ խորության/լայնության order-ում տրված գագաթների հակառակ կարգով։ Հերթական շրջանցման ժամանակ այցելված գագաթների ենթաբազմությունը կկազմի հերթական ուժեղ կապակցվածության կոմպոնենտը։

Ալգորիթմի ասիմպտոտիկան է, քանի որ այն իրենից ներկայացնում է երկու ըստ խորության շրջանցում։

Վերջապես, տեղին է նշել կապը տոպոլոգիական կարգավորում հասկացության հետ։ Նախ ալգորիթմի առաջին քայլին, ըստ էության կատարվում է գրաֆի տոպոլոգիական կարգավորում (ըստ ելքի ժամանակների գագաթների կարգավորումը հենց դա է նշանակում)։ Երկրորդը՝ ալգորիթմի սխեման այնպիսին է, որ խիստ կապակցված կոմպոնենտները գեներացվում են ըստ ելքի ժամանակների նվազման կարգի, այսինքն կոնդենսացիայի գրաֆի գագաթները գեներացվում են ըստ տոպոլոգիական կարգավորման։

Other Languages