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

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


== Ալգորիթմը ==
Այս ալգորիթմն իրարից անկախ առաջարկել են Կոսարայուն (անգլ.՝ Kosaraju) և Շարիրը (անգլ.՝ Sharir) 1979 թ.: Դա, իրականացման տեսակետից, ոչ բարդ ալգորիթմ է, որը հիմնված է ըստ խորության փնտրման ալգորիթմի վրա, և, հետևաբար, աշխատում է 
  
    
      
        O
        (
        n
        +
        m
        )
      
    
    {\displaystyle O(n+m)}
   ժամանակում։
Ալգորիթմի առաջին քայլին անցնում ենք գրաֆի բոլոր գագաթներով և յուրաքանչյուր չայցելած գագաթից կատարում ենք փնտրում ըստ խորության։ Ընդ որում յուրաքանչյուր 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթի համար պահում ենք նրա 
  
    
      
        t
        o
        u
        t
        [
        v
        ]
      
    
    {\displaystyle tout[v]}
   դուրս գալու ժամանակը։ Այդ արժեքները առանցքային դեր են խաղում ալգորիթմում, ինչն արտահայտված է ստորև բերված թեորեմում։
Նախ սահմանենք ուժեղ կապակցվածության 
  
    
      
        C
      
    
    {\displaystyle C}
   կոմպոնենտից դուրս գալու 
  
    
      
        t
        o
        u
        t
        [
        C
        ]
      
    
    {\displaystyle tout[C]}
   ժամանակը որպես բոլոր 
  
    
      
        v
      
    
    {\displaystyle v}
   պատկանում է 
  
    
      
        C
      
    
    {\displaystyle C}
   համար 
  
    
      
        t
        o
        u
        t
        [
        v
        ]
      
    
    {\displaystyle tout[v]}
  -երից մաքսիմում։ Բացի այդ թեորեմի ապացույցում պետք են գալիս նաև յուրաքանչյուր 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթ մտնելու 
  
    
      
        t
        [
        v
        ]
      
    
    {\displaystyle t[v]}
   ժամանակները։ Սահմանենք ուժեղ կապակցվածության 
  
    
      
        C
      
    
    {\displaystyle C}
   կոմպոնենտ մտնելու ժամանակը որպես 
  
    
      
        v
      
    
    {\displaystyle v}
   պատկանում է 
  
    
      
        C
      
    
    {\displaystyle C}
   համար 
  
    
      
        t
        i
        n
        [
        v
        ]
      
    
    {\displaystyle tin[v]}
  -երից մինիմում։


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


=== Ապացույց ===
Հարկավոր է երկու տարբեր դեպք դիտարկել կախված նրանից, թե ըստ խորության շրջանցումը առաջինը երկու կոմպոնենտներից որը կմտնի, այսինքն կախված 
  
    
      
        t
        i
        n
        [
        C
        ]
      
    
    {\displaystyle tin[C]}
   և 
  
    
      
        t
        i
        n
        [
        C
      
    
    {\displaystyle tin[C}
  ’
  
    
      
        ]
      
    
    {\displaystyle ]}
   արժեքներից։

Առաջինը հասել է 
  
    
      
        C
      
    
    {\displaystyle C}
   կոմպոնենտին։ Դա նշանակում է, որ ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի 
  
    
      
        v
      
    
    {\displaystyle v}
   պատկանում է 
  
    
      
        C
      
    
    {\displaystyle C}
   գագաթի, երբ 
  
    
      
        C
      
    
    {\displaystyle C}
   և 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ կոմպոնենտների մնացած բոլոր գագաթները դեռ այցելված չեն։ Բայց քանի որ ըստ պայմանի կոնդենսացիայի գրաֆում կա (
  
    
      
        C
        ,
        C
      
    
    {\displaystyle C,C}
  ’) կող, ապա 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթից հասանելի կլինի ոչ միայն ամբողջ 
  
    
      
        C
      
    
    {\displaystyle C}
   կոմպոնենտը, այլև ամբողջ 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ կոմպոնենտը։ Դա նշանակում է 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթից ըստ խորության շրջանցումը կանցնի 
  
    
      
        C
      
    
    {\displaystyle C}
   և 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ կոմպոնենտների բոլոր գագաթներով, նշանակում է նրանք բոլորը ըստ խորության շրջանցման ծառում կլինեն 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթի ժառանգներ, այսինքն ցանկացած 
  
    
      
        u
      
    
    {\displaystyle u}
   պատկանում է 
  
    
      
        C
      
    
    {\displaystyle C}
   միավորած 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ գագաթի համար տեղի կունենա 
  
    
      
        t
        o
        u
        t
        [
        v
        ]
        >
        t
        o
        u
        t
        [
        u
        ]
      
    
    {\displaystyle tout[v]>tout[u]}
  , ինչը և պահանջվում էր ապացուցել։Առաջինը հասել է 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ կոմպոնենտին։ Կրկին, ինչ-որ պահի ըստ խորության շրջանցումը հասնում է մի 
  
    
      
        v
      
    
    {\displaystyle v}
   պատկանում է 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ գագաթի, ընդ որում 
  
    
      
        C
      
    
    {\displaystyle C}
   և 
  
    
      
        C
      
    
    {\displaystyle C}
  ’ կոմպոնենտների մնացած բոլոր գագաթներն այցելված չեն։ Քանի որ, ըստ պայմանի կոնդենսացիայի գրաֆում գոյություն ունի (
  
    
      
        C
        ,
        C
      
    
    {\displaystyle C,C}
  ’) կող և քանի որ կոնդեսնացիայի գրաֆն ացիկլիկ է, նշանակում է հակառակ ճանապարհ գոյություն չունի, այսինքն v-ից ըստ խորության շրջանցումը չի հասնի 
  
    
      
        C
      
    
    {\displaystyle C}
  -ի բոլոր գագաթներին։ Դա նշանակում է, որ նրանք կայցելվեն ըստ խորության շրջանցման կողմից ավելի ուշ, որտեղից և հետևում է, որ 
:Ապացուցված թեորեմը ուժեղ կապակցվածության կոմպոնենտների փնտրման ալագորիթմի հիմքն է հանդիսանում։ Նրանից հետևում է, որ կոնդենսացիայի գրաֆում ցանկացած (
  
    
      
        C
        ,
        C
      
    
    {\displaystyle C,C}
  ’) կող գնում է ավելի մեծ 
  
    
      
        t
        o
        u
        t
      
    
    {\displaystyle tout}
  -ով կոմպոնենտից դեպի ավելի փոքր 
  
    
      
        t
        o
        u
        t
      
    
    {\displaystyle tout}
  -ով կոմպոնենտը։
Եթե կարգավորենք բոլոր 
  
    
      
        v
      
    
    {\displaystyle v}
   պատկանում է 
  
    
      
        V
      
    
    {\displaystyle V}
   գագաթները ըստ 
  
    
      
        t
        o
        u
        t
        [
        v
        ]
      
    
    {\displaystyle tout[v]}
   դուրս գալու ժամանակների նվազման կարգով, ապա առաջինը կլինի մի 
  
    
      
        u
      
    
    {\displaystyle u}
   գագաթ, որը պատկանում է ուժեղ կապակցվածության կոմպոնենտներից “արմատին”, այսինքն որը կոնդենսացիայի գրաֆում մտնող կող չունի։ Հիմա մենք կուզենայինք այդ 
  
    
      
        u
      
    
    {\displaystyle u}
   գագաթից այնպիսի շրջանցում բաց թողնել, որը այցելեր միայն այդ ուժեղ կապակցվածության կոմպոնենտը և ուրիշ ոչ մի կոմպոնենտ չմտներ։ Այդպիսով մենք կարող ենք աստիճանաբար առանձնացնել ուժեղ կապակցվածության բոլոր կոմպոնենտները. գրաֆից հեռացնելով առաջին առանձնացված կոմպոնենտի գագաթները, կարող ենք մնացածից կրկին գտնել ամենամեծ 
  
    
      
        t
        o
        u
        t
      
    
    {\displaystyle tout}
  -ով գագաթը, նրանից բաց թողնել այդ շրջանցումը և այդպես շարունակ։
Որպեսզի սովորենք այդպիսի շրջանցում անել, դիտարկենք 
  
    
      
        G
        T
      
    
    {\displaystyle GT}
   տրանսպոնացված գրաֆը։ Այն ստացվում է 
  
    
      
        G
      
    
    {\displaystyle G}
   գրաֆից յուրաքանչյուր կողի ուղղությունը հակառակի փոխելու արդյունքում։ Դժվար չէ հասկանալ, որ այդ գրաֆում կլինեն նույն ուժեղ կապակցվածության կոմպոնենտները, ինչ սկզբնական գրաֆում։ Ավելին, 
  
    
      
        (
        G
        T
        )
        S
        C
        C
      
    
    {\displaystyle (GT)SCC}
   կոնդենսացիայի գրաֆը կլինի 
  
    
      
        G
        S
        C
        C
      
    
    {\displaystyle GSCC}
   գրաֆի տրանսպոնացումը։ Դա նշանակում է, որ այժմ մեր դիտարկած “արմատ” հանդիսացող կոմպոնենտից արդեն դուրս եկող կող չի լինի։
Այսպիսով, 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթը պարունակող ամբողջ “արմատ” ուժեղ կապակցվածության կոմպոնենտը շրջանցելու համար բավական է բաց թողնել շրջանցումը 
  
    
      
        G
        T
      
    
    {\displaystyle GT}
   գրաֆի 
  
    
      
        v
      
    
    {\displaystyle v}
   գագաթից։ Այդ շրջանցումը կայցելի ուժեղ կապակցվածության այդ կոմպոնենտի բոլոր գագաթները և միայն դրանք։ Ինչպես արդեն ասվել է, ապա կարող ենք այդ գագաթները համարել գրաֆից հեռացված, գտնել հաջորդ գագաթը 
  
    
      
        t
        o
        u
        t
        [
        v
        ]
      
    
    {\displaystyle tout[v]}
   մաքսիմալ արժեքով և բաց թողնել շրջանցումը տրանսպոնացված գրաֆում նրանից, և այլն։
Այսպիսով, մենք կառուցեցինք ուժեղ կապակցվածության կոմպոնենտների առանձնացման հետևյալ ալգորիթմը.
Քայլ 1։ G գրաֆում կատարել ըստ խորության շրջանցումների շարք, որը վերադարձնում է գագաթները ըստ tout ելքի ժամանակի աճման կարգով, այսինքն կառուցում է ինչ-որ մի order ցուցակ։
Քայլ 2։ Կառուցել տրանսպոնացված GT գրաֆը։ Կատարել մի շարք շրջանցումներ ըստ խորության/լայնության order-ում տրված գագաթների հակառակ կարգով։ Հերթական շրջանցման ժամանակ այցելված գագաթների ենթաբազմությունը կկազմի հերթական ուժեղ կապակցվածության կոմպոնենտը։
Ալգորիթմի ասիմպտոտիկան 
  
    
      
        O
        (
        n
        +
        m
        )
      
    
    {\displaystyle O(n+m)}
   է, քանի որ այն իրենից ներկայացնում է երկու ըստ խորության շրջանցում։
Վերջապես, տեղին է նշել կապը տոպոլոգիական կարգավորում հասկացության հետ։ Նախ ալգորիթմի առաջին քայլին, ըստ էության կատարվում է 
  
    
      
        G
      
    
    {\displaystyle G}
   գրաֆի տոպոլոգիական կարգավորում (ըստ ելքի ժամանակների գագաթների կարգավորումը հենց դա է նշանակում)։ Երկրորդը՝ ալգորիթմի սխեման այնպիսին է, որ խիստ կապակցված կոմպոնենտները գեներացվում են ըստ ելքի ժամանակների նվազման կարգի, այսինքն կոնդենսացիայի գրաֆի գագաթները գեներացվում են ըստ տոպոլոգիական կարգավորման։


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