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

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

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

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

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