«Ամուր կապակցված բաղադրիչներ»–ի խմբագրումների տարբերություն

Content deleted Content added

Գծային

10:09, 23 Օգոստոսի 2016-ի տարբերակ

Ամուր կապակցված բաղադրիչ, ուղղորդված գրաֆը կոչվում է ամուր կապակցված, եթե այն ուղիղ է գրաֆի վրա ամեն մի բարձունքից դեպի մեկ այլ ուրիշ բարձունք։ Մասնավորապես, դա նշանակում է, որ ուղիղները մեկ ուղղության են՝ ուղիղը 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$ ’ $]$ արժեքներից։

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

Առաջինը հասել է $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 եզրերը կապակցված են։

Սա անավարտ հոդված է։ Դուք կարող եք օգնել Վիքիպեդիային՝ ուղղելով և լրացնելով այն։
Այս նշումը հարկավոր է փոխարինել համապատասխան թեմատիկ նշումով։

@@ Տող 1. / Տող 1. @@
 [[Image:Scc.png|thumb|Ամուր կապակցված բաղադրիչներով գրաֆ]]
+'''Ամուր կապակցված բաղադրիչ''', [[ուղղորդված գրաֆ]]ը կոչվում է ամուր կապակցված, եթե այն ուղիղ է [[գրաֆ]]ի վրա ամեն մի բարձունքից դեպի մեկ այլ ուրիշ բարձունք։ Մասնավորապես, դա նշանակում է, որ [[ուղիղ]]ները մեկ ուղղության են՝ ուղիղը a-ից դեպի b և միայն ուղիղը b-ից դեպի a։ Գրաֆ G-ի ամուր կապակցված բաղադրիչները նրա մաքսիմալ ամուր կապակցված ենթագրաֆներն են։ Եթե ինչ-որ ամուր կապակցված բաղադրիչ մի բարձունքից բացակայում է, գրաֆի արդյունքն է ուղղորդված ացիկլիկ գրաֆը՝ G կոնդենսացիան։ Ուղղորդված գրաֆը ացիկլիկ է միայն և միայն այն դեպքում, եթե այն չունի ամուր կապակցված ենթագրաֆներ ոչ ավել, քան մեկ բարձունքի հետ, որովհետև ուղղորդված ցիկլը ամուր կապակցված է և յուրաքանչյուր ոչ սովորական ամուր կապակցված բաղադրիչ պարունակում է առնվազն մեկ ուղղորդված ցիկլ։
-'''Ամուր կապակցված բաղադրիչ'''({{lang-en|strongly connected component}}), կոչվում է գագաթների այնպիսի (ընգրկվածությամբ մաքսիմալ) <math>C</math> ենթաբազմությունը, որ այդ ենթաբազմության ցանկացած երկու գագաթներ մեկը մյուսից հասանելի են, այսինքն <math>C</math>-ին պատկանող կամայական <math>u,v</math> գագաթների համար համար <math>u->v</math>, <math>v->u</math>, որտեղ <math>-></math> սիմվոլով նշանակված է հասանելիությունը, այսինքն առաջին գագաթից երկրորդ գագաթ տանող ճանապարհի գոյությունը։
-Պարզ է, որ տրված գրաֆի ուժեղ կապակցվածության կոմպոնենտները չեն հատվում, [[գրաֆ]]ի բոլոր գագաթները տրոհվում են այդպիսի կոմպոնենտների։ Գրաֆի <math>Gscc</math> կոնդենսացիան ստացվում է տրված գրաֆից ուժեղ կապակցվածության կոմպոնենտներից յուրաքանչյուրը մի գագաթի սեղմելու արդյունքում։ Կոնդենսացիայի գրաֆի յուրաքանչյուր գագաթին համապատասխանում է <math>G</math> գրաֆի ուժեղ կապակցվածության մի կոմպոնենտ, իսկ կոնդենսացիայի գրաֆի երկու <math>Ci</math> և <math>Cj</math> գագաթների միջև ուղղորդված կող տարվում է այն դեպքում, եթե գտնվի <math>u</math> պատկանում է <math>Ci,</math>  <math>v</math> պատկանում է <math>Cj</math> գագաթների այնպիսի զույգ, որոնց միացնող կող գոյություն ուներ սկզբնական գրաֆում, այսինքն (<math>u,v</math>) պատկանում է <math>E</math>:
-Կոնդենսացիայի գրաֆի կարևոր հատկությունն այն է, որ այն ացիկլիկ է։ Իրոք, ենթադրենք, որ <math>C</math>-><math>C</math>’, ապացուցենք, որ տեղի չունի <math>C</math>’ -> <math>C</math>:  Կոնդենսացիայի սահմանումից ստանում ենք, որ գոյություն ունեն երկու <math>u</math> պատկանում է <math>C</math>, <math>v</math> պատկանում է <math>C</math>’ գագաթներ, որ <math>u->v</math>: Անենք հակասող ենթադրություն. ենթադրենք <math>C</math>’-><math>C</math>, այդ դեպքում կգտնվեն երկու <math>u</math>’ պատկանում է <math>C</math>, <math>v</math>’ պատկանում է <math>C</math>’ գագաթներ, որ <math>v</math>’-><math>u</math>’: Բայց, քանի որ <math>u</math> և <math>u</math>’ գագաթները գտնվում են ուժեղ կապակցվածության մի կոմպոնենտում, ապա նրանց միջև գոյություն ունի ճանապարհ։ Նույնը կարելի է ասել <math>v</math> և <math>v</math>’ գագաթների մասին։ Արդյունքում, ճանապարհները միացնելով ստանում ենք, որ <math>u->v</math> և միաժամանակ <math>v->u</math>։ Հետևաբար <math>u</math> և <math>v</math> գագաթները պետք է պատկանեն ուժեղ կապակցվածության միևնույն կոմպոնենտին, այսինքն ստացանք հակասություն, ինչը և պահանջվում էր ապացուցել։
 == Ալգորիթմը ==
@@ Տող 21. / Տող 17. @@
 #Առաջինը հասել է <math>C</math> կոմպոնենտին։ Դա նշանակում է, որ ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի <math>v</math> պատկանում է <math>C</math> գագաթի, երբ <math>C</math> և <math>C</math>’ կոմպոնենտների մնացած բոլոր գագաթները դեռ այցելված չեն։ Բայց քանի որ ըստ պայմանի կոնդենսացիայի գրաֆում կա (<math>C,C</math>’) կող, ապա <math>v</math> գագաթից հասանելի կլինի ոչ միայն ամբողջ <math>C</math> կոմպոնենտը, այլև ամբողջ <math>C</math>’ կոմպոնենտը։ Դա նշանակում է <math>v</math> գագաթից ըստ խորության շրջանցումը կանցնի <math>C</math> և <math>C</math>’ կոմպոնենտների բոլոր գագաթներով, նշանակում է նրանք բոլորը ըստ խորության շրջանցման ծառում կլինեն <math>v</math> գագաթի ժառանգներ, այսինքն ցանկացած <math>u</math> պատկանում է <math>C</math> միավորած <math>C</math>’ գագաթի համար տեղի կունենա <math>tout[v]>tout[u]</math>, ինչը և պահանջվում էր ապացուցել։
-#Առաջինը հասել է <math>C</math>’ կոմպոնենտին։ Կրկին, ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի <math>v</math> պատկանում է <math>C</math>’ գագաթի, ընդ որում <math>C</math> և <math>C</math>’ կոմպոնենտների մնացած բոլոր գագաթներն այցելված չեն։ Քանի որ, ըստ պայմանի կոնդենսացիայի գրաֆում գոյություն ունի (<math>C,C</math>’) կող և քանի որ կոնդեսնացիայի գրաֆն ացիկլիկ է, նշանակում է հակառակ  ճանապարհ գոյություն չունի, այսինքն v-ից ըստ խորության շրջանցումը չի հասնի <math>C</math>-ի բոլոր գագաթներին։ Դա նշանակում է, որ նրանք կայցելվեն ըստ խորության շրջանցման կողմից ավելի ուշ, որտեղից և հետևում է, որ <math>tout[C]>tout[C</math>’<math>]</math>:
+#Առաջինը հասել է <math>C</math>’ կոմպոնենտին։ Կրկին, ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի <math>v</math> պատկանում է <math>C</math>’ գագաթի, ընդ որում <math>C</math> և <math>C</math>’ կոմպոնենտների մնացած բոլոր գագաթներն այցելված չեն։ Քանի որ, ըստ պայմանի կոնդենսացիայի գրաֆում գոյություն ունի (<math>C,C</math>’) կող և քանի որ կոնդեսնացիայի գրաֆն ացիկլիկ է, նշանակում է հակառակ  ճանապարհ գոյություն չունի, այսինքն v-ից ըստ խորության շրջանցումը չի հասնի <math>C</math>-ի բոլոր գագաթներին։ Դա նշանակում է, որ նրանք կայցելվեն ըստ խորության շրջանցման կողմից ավելի ուշ, որտեղից և հետևում է, որ <math>tout[C]>tout[C’]</math>:
 Ապացուցված թեորեմը ուժեղ կապակցվածության կոմպոնենտների փնտրման ալագորիթմի հիմքն է հանդիսանում։ Նրանից հետևում է, որ կոնդենսացիայի գրաֆում ցանկացած (<math>C,C</math>’) կող գնում է ավելի մեծ <math>tout</math>-ով կոմպոնենտից դեպի ավելի փոքր <math>tout</math>-ով կոմպոնենտը։