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

Jump to navigation Jump to search
Առանց խմբագրման ամփոփման
[[Image:Scc.png|thumb|Ամուր կապակցված բաղադրիչներով գրաֆ]]
'''Ամուր կապակցված բաղադրիչ''', [[ուղղորդված գրաֆ]]ը կոչվում է ամուր կապակցված, եթե այն ուղիղ է [[գրաֆ]]ի վրա ամեն մի բարձունքից դեպի մեկ այլ ուրիշ բարձունք։ Մասնավորապես, դա նշանակում է, որ [[ուղիղ]]ները մեկ ուղղության են՝ ուղիղը a-ից դեպի b և միայն ուղիղը b-ից դեպի a։ Գրաֆ G-ի ամուր կապակցված բաղադրիչները նրա մաքսիմալ ամուր կապակցված ենթագրաֆներն են։ Եթե ինչ-որ ամուր կապակցված բաղադրիչ մի բարձունքից բացակայում է, գրաֆի արդյունքն է ուղղորդված ացիկլիկ գրաֆը՝ G կոնդենսացիան։ Ուղղորդված գրաֆը ացիկլիկ է միայն և միայն այն դեպքում, եթե այն չունի ամուր կապակցված ենթագրաֆներ ոչ ավել, քան մեկ բարձունքի հետ, որովհետև ուղղորդված ցիկլը ամուր կապակցված է և յուրաքանչյուր ոչ սովորական ամուր կապակցված բաղադրիչ պարունակում է առնվազն մեկ ուղղորդված ցիկլ։
== Ալգորիթմը ==
 
Այս ալգորիթմն իրարից անկախ առաջարկել են Կոսարայուն ({{lang-en|Kosaraju}}) և Շարիրը ({{lang-en|Sharir}}) [[1979]] թ.: Դա, իրականացման տեսակետից, ոչ բարդ ալգորիթմ է, որը հիմնված է ըստ [[Փնտրում դեպի խորություն|խորության փնտրման]] ալգորիթմի վրա, և, հետևաբար, աշխատում է <math>O(n+m)</math> ժամանակում։
 
Ալգորիթմի առաջին քայլին անցնում ենք գրաֆի բոլոր գագաթներով և յուրաքանչյուր չայցելած գագաթից կատարում ենք փնտրում ըստ խորության։ Ընդ որում յուրաքանչյուր <math>v</math> գագաթի համար պահում ենք նրա <math>tout[v]</math> դուրս գալու ժամանակը։ Այդ արժեքները առանցքային դեր են խաղում [[ալգորիթմ]]ում, ինչն արտահայտված է ստորև բերված թեորեմում։
 
Նախ սահմանենք ուժեղ կապակցվածության <math>C</math> կոմպոնենտից դուրս գալու <math>tout[C]</math> ժամանակը որպես բոլոր <math>v</math> պատկանում է <math>C</math> համար <math>tout[v]</math>-երից մաքսիմում։ Բացի այդ թեորեմի ապացույցում պետք են գալիս նաև յուրաքանչյուր <math>v</math> գագաթ մտնելու <math>t[v]</math> ժամանակները։ Սահմանենք ուժեղ կապակցվածության <math>C</math> կոմպոնենտ մտնելու ժամանակը որպես <math>v</math> պատկանում է <math>C</math> համար <math>tin[v]</math>-երից մինիմում։
 
=== Թեորեմ ===
''Դիցուք <math>C</math> և <math>C</math>’-ը ուժեղ կապակցվածության երկու տարբեր կոմպոնենտներ են, և, դիցուք կոնդենսացիայի գրաֆում նրանց միջև կա (<math>C,C</math>’) կող։ Այդ դեպքում <math>tout[C]>tout[C</math>’<math>]</math>:''
 
=== Ապացույց ===
''Հարկավոր է երկու տարբեր դեպք դիտարկել կախված նրանից, թե ըստ խորության շրջանցումը առաջինը երկու կոմպոնենտներից որը կմտնի, այսինքն կախված <math>tin[C]</math> և <math>tin[C</math>’<math>]</math> արժեքներից։''
 
#Առաջինը հասել է <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>C,C</math>’) կող գնում է ավելի մեծ <math>tout</math>-ով կոմպոնենտից դեպի ավելի փոքր <math>tout</math>-ով կոմպոնենտը։
 
Եթե կարգավորենք բոլոր <math>v</math> պատկանում է <math>V</math> գագաթները ըստ <math>tout[v]</math> դուրս գալու ժամանակների նվազման կարգով, ապա առաջինը կլինի մի <math>u</math> գագաթ, որը պատկանում է ուժեղ կապակցվածության կոմպոնենտներից “արմատին”, այսինքն որը կոնդենսացիայի գրաֆում մտնող կող չունի։ Հիմա մենք կուզենայինք այդ <math>u</math> գագաթից այնպիսի շրջանցում բաց թողնել, որը այցելեր միայն այդ ուժեղ կապակցվածության կոմպոնենտը և ուրիշ ոչ մի կոմպոնենտ չմտներ։ Այդպիսով մենք կարող ենք աստիճանաբար առանձնացնել ուժեղ կապակցվածության բոլոր կոմպոնենտները. գրաֆից հեռացնելով առաջին առանձնացված կոմպոնենտի գագաթները, կարող ենք մնացածից կրկին գտնել ամենամեծ <math>tout</math>-ով գագաթը, նրանից բաց թողնել այդ շրջանցումը և այդպես շարունակ։
 
Որպեսզի սովորենք այդպիսի շրջանցում անել, դիտարկենք <math>GT</math> տրանսպոնացված գրաֆը։ Այն ստացվում է <math>G</math> գրաֆից յուրաքանչյուր կողի ուղղությունը հակառակի փոխելու արդյունքում։ Դժվար չէ հասկանալ, որ այդ գրաֆում կլինեն նույն ուժեղ կապակցվածության կոմպոնենտները, ինչ սկզբնական գրաֆում։ Ավելին, <math>(GT)SCC</math> կոնդենսացիայի գրաֆը կլինի <math>GSCC</math> գրաֆի տրանսպոնացումը։ Դա նշանակում է, որ այժմ մեր դիտարկած “արմատ” հանդիսացող կոմպոնենտից արդեն դուրս եկող կող չի լինի։
 
Այսպիսով, <math>v</math> գագաթը պարունակող ամբողջ “արմատ” ուժեղ կապակցվածության կոմպոնենտը շրջանցելու համար բավական է բաց թողնել շրջանցումը <math>GT</math> գրաֆի <math>v</math> գագաթից։ Այդ շրջանցումը կայցելի ուժեղ կապակցվածության այդ կոմպոնենտի բոլոր գագաթները և միայն դրանք։ Ինչպես արդեն ասվել է, ապա կարող ենք այդ գագաթները համարել գրաֆից հեռացված, գտնել հաջորդ գագաթը <math>tout[v]</math> մաքսիմալ արժեքով և բաց թողնել շրջանցումը տրանսպոնացված գրաֆում նրանից, և այլն։
 
Այսպիսով, մենք կառուցեցինք ուժեղ կապակցվածության կոմպոնենտների առանձնացման հետևյալ ալգորիթմը.
 
Քայլ 1։ G գրաֆում կատարել ըստ խորության շրջանցումների շարք, որը վերադարձնում է գագաթները ըստ tout ելքի ժամանակի աճման կարգով, այսինքն կառուցում է ինչ-որ մի order ցուցակ։
 
Քայլ 2։ Կառուցել տրանսպոնացված GT գրաֆը։ Կատարել մի շարք շրջանցումներ ըստ խորության/լայնության order-ում տրված գագաթների հակառակ կարգով։ Հերթական շրջանցման ժամանակ այցելված գագաթների ենթաբազմությունը կկազմի հերթական ուժեղ կապակցվածության կոմպոնենտը։
 
Ալգորիթմի ասիմպտոտիկան <math>O(n+m)</math> է, քանի որ այն իրենից ներկայացնում է երկու ըստ խորության շրջանցում։
 
Վերջապես, տեղին է նշել կապը տոպոլոգիական կարգավորում հասկացության հետ։ Նախ ալգորիթմի առաջին քայլին, ըստ էության կատարվում է <math>G</math> գրաֆի տոպոլոգիական կարգավորում (ըստ ելքի ժամանակների գագաթների կարգավորումը հենց դա է նշանակում)։ Երկրորդը՝ ալգորիթմի սխեման այնպիսին է, որ խիստ կապակցված կոմպոնենտները գեներացվում են ըստ ելքի ժամանակների նվազման կարգի, այսինքն կոնդենսացիայի գրաֆի գագաթները գեներացվում են ըստ տոպոլոգիական կարգավորման։
== Կիրառությունը խնդիրներում ==
[[Կասարաջուի ալգորիթմ]]ը, [[Տարջանի ալգորիթմ]]ը և ուղղորդված ամուր բաղադրիչի ալգորիթմը էֆեկտիվ հաշվում են ուղղորդված գրաֆի ամուր կապակցված բաղադրիչները, բայց Տարջանի և ուղղորդված ալգորիթմը արտոնություններ ունեն պրակտիկայում, քանի որ նրանց անհրաժեշտ է միայն մեկը սկզբում խորը փնտրել, քան երկուսը։
 
 
Օրինակ՝ ինչպես Ասվպվալը, Փլասը և Տերջյանն (1979) են ցույց տվել, 2 համապատասխան օրինակները անհամապասխան են միայն և միայն այն դեպքում, եթե այն V փոփոխական է, ինչպես որ V և նրա համալրողները երկուսն էլ օրինակում պարունակում են գրաֆի մասնակցությամբ նույն ամուր կապակցված բաղադրիչ։ Համաձայն [[Ռոբբինի թեորեմ]]ի, չուղղորդված գրաֆը հնարավոր է կողնորոշի այնպիսի ճանապարհով, որ այն դառնա ամուր կապակցված, միայն և միայն այն դեպքում, եթե նրա 2 եզրերը կապակցված են։
== Աղբյուրներ ==
 
[[Կատեգորիա:Գրաֆների տեսություն]]
505

edits

Նավարկման ցանկ