Weak component
આલેખ સિદ્ધાંતમાં, નિર્દેશિત આલેખના નબળા ઘટકો આલેખના શિરોબિંદુઓને ઉપગણમાં વિભાજિત કરે છે જે સંપૂર્ણપણે સુલભતા દ્વારા ક્રમબદ્ધ હોય છે. તેઓ શિરોબિંદુઓના સમૂહનું શ્રેષ્ઠ વિભાજન બનાવે છે જે સંપૂર્ણપણે આ રીતે ક્રમબદ્ધ હોય છે. વ્યાખ્યા નબળા ઘટકોને રોનાલ્ડ ગ્રેહામ, ડોનાલ્ડ નુથ અને (મરણોપરાંત) થિયોડોર મોત્ઝકિન દ્વારા 1972ના પેપરમાં નિર્દેશિત આલેખના મજબૂત રીતે જોડાયેલા ઘટકોની સામ્યતા દ્વારા વ્યાખ્યાયિત કરવામાં આવ્યા હતા, જે આલેખના શિરોબિંદુઓને ઉપગણમાં શ્રેષ્ઠ શક્ય વિભાજન બનાવે છે જે આંશિક રીતે સુલભતા દ્વારા ક્રમબદ્ધ કરવામાં આવે છે. તેના બદલે, તેઓએ નબળા ઘટકોને ઉપગણમાં શિરોબિંદુઓનું શ્રેષ્ઠ વિભાજન તરીકે વ્યાખ્યાયિત કર્યા છે, જે વધુ વિગતવાર, કોઈપણ નિર્દેશિત આલેખના શિરોબિંદુઓ પર ચાર સમપ્રમાણ સંબંધોના સંયોજન દ્વારા નબળા ઘટકોને વ્યાખ્યાયિત કરે છે, જે અહીં સૂચવવામાં આવે છે. કોઈપણ બે શિરોબિંદુઓ માટે અને આલેખ માટે, જો અને માત્ર ત્યારે જ જો કોઈ પણ શિરોબિંદુ બીજાથી પહોંચી શકાય તેવું ન હોય તોઃ આલેખમાં વચ્ચેની બંને દિશામાં કોઈ પાથ અસ્તિત્વમાં નથી. સંબંધને સંક્રમક બંધ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે એટલે કે, જ્યારે શિરોબિંદુઓનો ક્રમ હોય છે, ત્યારે તે ક્રમમાં દરેક ક્રમિક જોડી સંબંધિત હોય તેવી રીતે શરૂ થાય છે અને સમાપ્ત થાય છે પછી એક સમાનતા સંબંધ છેઃ દરેક શિરોબિંદુ તેની સાથે સંબંધિત છે (કારણ કે તે લંબાઈ શૂન્યના માર્ગો દ્વારા બંને દિશામાં પોતાને પહોંચી શકે છે), કોઈપણ બે શિરોબિંદુઓ કે જે તેનાથી સંબંધિત છે તે આ સંબંધને બદલ્યા વિના એકબીજા માટે અદલાબદલી કરી શકાય છે (કારણ કે તે સપ્રમાણ સંબંધોમાંથી બનેલો છે અને તે એક સંક્રમક સંબંધ છે (કારણ કે તે બીજા સંબંધની સંક્રમક બંધ છે). કોઈપણ સમાનતા સંબંધની જેમ, તેનો ઉપયોગ આલેખના શિરોબિંદુઓને સમાનતા વર્ગોમાં વિભાજિત કરવા માટે થઈ શકે છે, શિરોબિંદુઓના ઉપગણ જેમ કે બે શિરોબિંદુઓ જો અને માત્ર ત્યારે જ સંબંધિત હોય જો તેઓ સમાન સમાનતા વર્ગના હોય. આ સમાનતા વર્ગો આપેલા નબળા ઘટકો છે ગ્રેહામ, નુથ અને મોત્ઝકિન દ્વારા મૂળ વ્યાખ્યા સમકક્ષ છે પરંતુ કંઈક અલગ રીતે ઘડવામાં આવી છે. જેમ વર્ણવે છે તેમ, બે શિરોબિંદુઓ એક જ નબળા ઘટક સાથે સંબંધિત હોય છે જ્યારે તેઓ એક જ મજબૂત રીતે જોડાયેલા ઘટક સાથે સંબંધિત હોય અથવા જેમ ગ્રેહામ, નુથ અને મોત્ઝકિન સાબિત કરે છે તેમ, આ શરત ઉપર વ્યાખ્યાયિત સમાન સમાનતાને વ્યાખ્યાયિત કરે છે આ વ્યાખ્યાઓને અનુરૂપ, નિર્દેશિત આલેખને નબળા રીતે જોડાયેલ કહેવામાં આવે છે જો તેમાં બરાબર એક નબળો ઘટક હોય. આનો અર્થ એ છે કે તેના શિરોબિંદુઓને બે ઉપગણમાં વિભાજિત કરી શકાતા નથી, જેમ કે પ્રથમ ઉપગણમાંના તમામ શિરોબિંદુઓ બીજા ઉપગણમાંના તમામ શિરોબિંદુઓ સુધી પહોંચી શકે છે, પરંતુ એવું કે બીજા ઉપગણમાંના કોઈ પણ શિરોબિંદુઓ પ્રથમ ઉપગણમાંના કોઈપણ શિરોબિંદુઓ સુધી પહોંચી શકતા નથી. તે સાહિત્યમાં નબળા જોડાણની અન્ય ધારણાઓથી અલગ છે, જેમ કે અંતર્ગત અસંબદ્ધ આલેખમાં જોડાણ અને ઘટકો, જેના માટે ક્નુથ વૈકલ્પિક પરિભાષા ગુણધર્મો સૂચવે છે જો અને તે નિર્દેશિત આલેખના બે નબળા ઘટકો છે, તો પછી ક્યાં તો તમામ શિરોબિંદુઓ આલેખમાં પાથ દ્વારા તમામ શિરોબિંદુઓ સુધી પહોંચી શકે છે, અથવા તમામ શિરોબિંદુઓ તમામ શિરોબિંદુઓ સુધી પહોંચી શકે છે. તેથી, આપણે નબળા ઘટકો પરના ક્રમને વ્યાખ્યાયિત કરી શકીએ છીએ, જે મુજબ જ્યારે તમામ શિરોબિંદુઓ તમામ શિરોબિંદુઓ સુધી પહોંચી શકે છે વ્યાખ્યા અનુસાર, આ એક અસમપ્રમાણ સંબંધ છે (બે ઘટકો માત્ર એક જ દિશામાં સંબંધિત હોઈ શકે છે, બીજામાં નહીં) અને તે વારસામાં મળે છે. તેથી, તે નબળા ઘટકો પર કુલ ક્રમ વ્યાખ્યાયિત કરે છે. આ નબળા ઘટકો પરના ક્રમને વૈકલ્પિક રીતે શિરોબિંદુઓ પરના નબળા ક્રમ તરીકે અર્થઘટન કરી શકાય છે, આ ગુણધર્મ સાથે કે જ્યારે નબળા ક્રમમાં હોય, ત્યારે ત્યાં એક માર્ગ અસ્તિત્વમાં હોય છે પરંતુ તેમાંથી નહીં. જો કે, આ આ નબળા ક્રમની સંપૂર્ણ લાક્ષણિકતા નથી, કારણ કે બે શિરોબિંદુઓ અને દરેક જેવા જ નબળા ઘટક સાથે જોડાયેલા હોવા છતાં આ સમાન પહોંચનો ક્રમ હોઈ શકે છે. દરેક નબળો ઘટક મજબૂત રીતે જોડાયેલું સંયોજન છે. જો કોઈ પણ ગ્રાફના મજબૂત રીતે જોડાયેલા ઘટકો એક જ શિરોબિંદુ સાથે સંકુચિત થાય છે, જે નિર્દેશિત એસાયક્લિક ગ્રાફ (આપેલ ગ્રાફનો) ઉત્પન્ન કરે છે, અને પછી આ ઘનીકરણને ટોપોલોજિકલ રીતે સૉર્ટ કરવામાં આવે છે, તો પછી દરેક નબળા ઘટક જરૂરી રીતે સતત અનુગામી તરીકે દેખાય છે. નબળા ઘટકો માટેનું અલ્ગોરિધમ આ ક્રમમાં મજબૂત રીતે જોડાયેલા ઘટકો ઉત્પન્ન કરે છે, અને તેમના પ્રેરિત સબગ્રાફના નબળા ઘટકોમાં અત્યાર સુધી પેદા થયેલા ઘટકોના વિભાજનને જાળવી રાખે છે. બધા ઘટકો ઉત્પન્ન થયા પછી, આ પાર્ટીશન સમગ્ર નબળા ઘટકોનું વર્ણન કરશે વર્તમાન પાર્ટીશનને માળખામાં નબળા ઘટકોમાં જાળવવું અનુકૂળ છે, જેમાં દરેક નબળા ઘટક વધુમાં તેના, મજબૂત રીતે જોડાયેલા ઘટકોની સૂચિ જાળવી રાખે છે, જેમાં સમાન નબળા ઘટકમાં અન્ય મજબૂત રીતે જોડાયેલા ઘટકોમાંથી કોઈ આવનારી ધાર નથી, જેમાં સૌથી તાજેતરમાં ઉત્પન્ન થયેલ સ્રોત પ્રથમ છે. દરેક નવો પેદા થયેલ મજબૂત રીતે જોડાયેલ ઘટક તેના પોતાના પર એક નવો નબળો ઘટક બનાવી શકે છે, અથવા સ્ટેકની ટોચની નજીક અગાઉ બાંધવામાં આવેલા કેટલાક નબળા ઘટકો સાથે ભળી શકે છે, જેના માટે તે બધા સુધી પહોંચી શકતું નથી. ટોપોલોજિકલ ક્રમની વિરુદ્ધમાં આપેલ આલેખના મજબૂત રીતે જોડાયેલા ઘટકો પેદા કરવા માટે ટાર્જનના મજબૂત રીતે જોડાયેલા ઘટકોના અલ્ગોરિધમનો ઉપયોગ કરો. જ્યારે દરેક મજબૂત રીતે જોડાયેલ ઘટક ઉત્પન્ન થાય છે, ત્યારે તેની સાથે નીચેના પગલાંઓ અનુસરોઃ જ્યારે સ્ટેક ખાલી ન હોય અને તેમાં સ્ટેકના ટોચના નબળા ઘટકની કોઈ ધાર ન હોય, ત્યારે તે ઘટકને સ્ટેકમાંથી પૉપ કરો. જો સ્ટેક હજુ પણ ખાલી ન હોય અને તેના ટોચના નબળા ઘટકના કેટલાક સ્રોતો ધારથી પ્રભાવિત ન હોય તો ફરીથી તે ઘટકને સ્ટેકમાંથી પૉપ કરો. ઉપરના ઘટકમાંથી સ્ત્રોત તરીકે અને તમામ અનહિટ સ્રોતો ધરાવતી નવી નબળાઈ બનાવો જે પૉપ કરવામાં આવી હતી, અને સ્ટેક પર દબાણ કરો. નબળા ઘટકને ફટકો પડવાથી કોઈ પણ ધાર સતત સમયે કરી શકાય છે કે કેમ તે માટે દરેક પરીક્ષણ એકવાર આપણે સૌથી તાજેતરમાં પેદા થયેલા અગાઉ મજબૂત રીતે જોડાયેલા ઘટકની ધાર શોધી કાઢીએ, તે ધારના લક્ષ્ય ઘટકની તુલના બીજા-થી-ટોચ ઘટકના પ્રથમ સ્રોત સાથે કરીને. સંદર્ભો આલેખ જોડાણ આલેખ સિદ્ધાંત પદાર્થો