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

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

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

Ալգորիթմը

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

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

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

Թեորեմ

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

Ապացույց

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

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

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

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

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

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

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

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

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

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

Ալգորիթմի ասիմպտոտիկան $O(n+m)$ է, քանի որ այն իրենից ներկայացնում է երկու ըստ խորության շրջանցում։

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

Կիրառությունը խնդիրներում

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

Ալգորիթմները, գտնելով ամուր կապակցված բաղադրիչները, հնարավոր է օգտագործվեն, որպեսզի լուծեն 2 համապասխան խնդիրները։

Օրինակ՝ ինչպես Ասվպվալը, Փլասը և Տերջյանն (1979) են ցույց տվել, 2 համապատասխան օրինակները անհամապասխան են միայն և միայն այն դեպքում, եթե այն V փոփոխական է, ինչպես որ V և նրա համալրողները երկուսն էլ օրինակում պարունակում են գրաֆի մասնակցությամբ նույն ամուր կապակցված բաղադրիչ։ Համաձայն Ռոբբինի թեորեմի, չուղղորդված գրաֆը հնարավոր է կողնորոշի այնպիսի ճանապարհով, որ այն դառնա ամուր կապակցված, միայն և միայն այն դեպքում, եթե նրա 2 եզրերը կապակցված են։