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

Առանց խմբագրման ամփոփման
[[Image:Scc.png|thumb|Ամուր կապակցված բաղադրիչներով գրաֆ]]
'''Ամուր կապակցված բաղադրիչ'''({{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> սիմվոլով նշանակված է հասանելիությունը, այսինքն առաջին գագաթից երկրորդ գագաթ տանող ճանապարհի գոյությունը։
'''Ամուր կապակցված բաղադրիչ''', [[ուղղորդված գրաֆ]]ը կոչվում է ամուր կապակցված, եթե այն ուղիղ է [[գրաֆ]]ի վրա ամեն մի բարձունքից դեպի մեկ այլ ուրիշ բարձունք։ Մասնավորապես, դա նշանակում է, որ [[ուղիղ]]ները մեկ ուղղության են՝ ուղիղը a-ից դեպի b և միայն ուղիղը b-ից դեպի a։ Գրաֆ G-ի ամուր կապակցված բաղադրիչները նրա մաքսիմալ ամուր կապակցված ենթագրաֆներն են։ Եթե ինչ-որ ամուր կապակցված բաղադրիչ մի բարձունքից բացակայում է, գրաֆի արդյունքն է ուղղորդված ացիկլիկ գրաֆը՝ G կոնդենսացիան։ Ուղղորդված գրաֆը ացիկլիկ է միայն և միայն այն դեպքում, եթե այն չունի ամուր կապակցված ենթագրաֆներ ոչ ավել, քան մեկ բարձունքի հետ, որովհետև ուղղորդված ցիկլը ամուր կապակցված է և յուրաքանչյուր ոչ սովորական ամուր կապակցված բաղադրիչ պարունակում է առնվազն մեկ ուղղորդված ցիկլ։
 
Պարզ է, որ տրված գրաֆի ուժեղ կապակցվածության կոմպոնենտները չեն հատվում, [[գրաֆ]]ի բոլոր գագաթները տրոհվում են այդպիսի կոմպոնենտների։ Գրաֆի <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> գագաթները պետք է պատկանեն ուժեղ կապակցվածության միևնույն կոմպոնենտին, այսինքն ստացանք հակասություն, ինչը և պահանջվում էր ապացուցել։
== Ալգորիթմը ==
 
#Առաջինը հասել է <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’C</math>’<math>]</math>:
Ապացուցված թեորեմը ուժեղ կապակցվածության կոմպոնենտների փնտրման ալագորիթմի հիմքն է հանդիսանում։ Նրանից հետևում է, որ կոնդենսացիայի գրաֆում ցանկացած (<math>C,C</math>’) կող գնում է ավելի մեծ <math>tout</math>-ով կոմպոնենտից դեպի ավելի փոքր <math>tout</math>-ով կոմպոնենտը։
 
505

edits