Circuit rank
આલેખ સિદ્ધાંતમાં, ગણિતની એક શાખા, સર્કિટ ક્રમ, ચક્રીય સંખ્યા, ચક્ર ક્રમ, અથવા દિશાહીન આલેખની શૂન્યતા એ ધારની લઘુતમ સંખ્યા છે જેને તેના તમામ ચક્રને તોડવા માટે આલેખમાંથી દૂર કરવી આવશ્યક છે, જે તેને વૃક્ષ અથવા જંગલમાં બનાવે છે. તે આલેખમાં સ્વતંત્ર ચક્રોની સંખ્યા (ચક્ર આધારનું કદ) બરાબર છે. નિર્દેશિત આલેખ માટે અનુરૂપ પ્રતિક્રિયા ચાપ સમૂહ સમસ્યાથી વિપરીત, સર્કિટ ક્રમની ગણતરી સૂત્રનો ઉપયોગ કરીને સરળતાથી કરવામાં આવે છે, જ્યાં આપેલ આલેખમાં ધારની સંખ્યા છે, શિરોબિંદુઓની સંખ્યા છે, અને જોડાયેલા ઘટકોની સંખ્યા છે. લોભી અલ્ગોરિધમનો ઉપયોગ કરીને અથવા ફેલાયેલા જંગલને પૂરક બનાવીને, તમામ ચક્રોને અસરકારક રીતે તોડે તેવી કિનારીઓનો લઘુતમ-કદનો સમૂહ બનાવવો પણ શક્ય છે. સર્કિટ ક્રમને બીજગણિત આલેખ સિદ્ધાંતની દ્રષ્ટિએ આલેખની ચક્ર જગ્યાના પરિમાણ તરીકે, મેટ્રોઇડ સિદ્ધાંતની દ્રષ્ટિએ ગ્રાફિક મેટ્રોઇડના કોરંક તરીકે અને ટોપોલોજીની દ્રષ્ટિએ ગ્રાફમાંથી મેળવેલ ટોપોલોજિકલ જગ્યાના બેટ્ટી નંબરોમાંના એક તરીકે સમજાવી શકાય છે. તે આલેખના કાનના વિઘટનમાં કાનની ગણતરી કરે છે, લગભગ વૃક્ષો પર પરિમાણિત જટિલતાનો આધાર બનાવે છે, અને કોડના ભાગની ચક્રીય જટિલતાની વ્યાખ્યાના ભાગ રૂપે સોફ્ટવેર મેટ્રિક્સમાં લાગુ કરવામાં આવે છે. સાયક્લોમેટિક નંબરના નામ હેઠળ, આ ખ્યાલ ગુસ્તાવ કિર્ચોફ દ્વારા રજૂ કરવામાં આવ્યો હતો. મેટ્રોઇડ ક્રમ અને ન્યૂનતમ પ્રતિસાદ ધાર સમૂહની રચના મેટ્રોઇડ સિદ્ધાંતનો ઉપયોગ કરીને ગ્રાફના સર્કિટ ક્રમને મેટ્રોઇડના ગ્રાફિક મેટ્રોઇડના કોરંક તરીકે વર્ણવી શકાય છે. મેટ્રોઇડ્સના લોભી ગુણધર્મનો ઉપયોગ કરીને, આનો અર્થ એ છે કે કોઈ પણ વ્યક્તિ લોભી અલ્ગોરિધમનો ઉપયોગ કરીને તમામ ચક્રોને તોડતી ધારોનો ઓછામાં ઓછો સમૂહ શોધી શકે છે જે દરેક તબક્કે એક ધાર પસંદ કરે છે જે બાકીના ગ્રાફના ઓછામાં ઓછા એક ચક્ર સાથે સંબંધિત છે. વૈકલ્પિક રીતે, તમામ ચક્રોને તોડનારી કિનારીઓનો લઘુતમ સમૂહ ફેલાયેલા જંગલનું નિર્માણ કરીને અને વિસ્તરેલા જંગલ સાથે સંબંધિત ન હોય તેવા કિનારીઓના પૂરક સમૂહને પસંદ કરીને શોધી શકાય છે. સ્વતંત્ર ચક્રોની સંખ્યા બીજગણિત આલેખ સિદ્ધાંતમાં, સર્કિટ ક્રમ એ ચક્ર જગ્યાનું પરિમાણ પણ છે. સહજ ભાવે, આને અર્થ તરીકે સમજાવી શકાય છે કે સર્કિટ ક્રમ આલેખમાં સ્વતંત્ર ચક્રોની સંખ્યાની ગણતરી કરે છે, જ્યાં ચક્રોનો સંગ્રહ સ્વતંત્ર હોય છે જો અન્યના કેટલાક સબસેટના સમપ્રમાણ તફાવત તરીકે એક ચક્રની રચના કરવી શક્ય ન હોય. સ્વતંત્ર ચક્રની આ ગણતરીને ટોપોલોજીની એક શાખા, હોમોલોજી સિદ્ધાંતનો ઉપયોગ કરીને પણ સમજાવી શકાય છે. કોઈપણ આલેખને 1-પરિમાણીય સરળ સંકુલના ઉદાહરણ તરીકે જોઈ શકાય છે, જે એક પ્રકારનો ટોપોલોજિકલ અવકાશ છે જે દરેક આલેખની ધારને રેખા ખંડ દ્વારા રજૂ કરીને અને આ રેખા વિભાગોને તેમના અંતિમ બિંદુઓ પર એક સાથે જોડીને રચાય છે. સાયક્લોમેટિક સંખ્યા એ આ સંકુલના પ્રથમ (પૂર્ણાંક) સમરૂપતા જૂથનો ક્રમ છે, આ ટોપોલોજિકલ જોડાણને કારણે, આલેખની સાયક્લોમેટિક સંખ્યાને પ્રથમ બેટ્ટી સંખ્યા પણ કહેવામાં આવે છે. વધુ સામાન્ય રીતે, કોઈપણ ટોપોલોજિકલ જગ્યાની પ્રથમ બેટ્ટી સંખ્યા, જે તે જ રીતે વ્યાખ્યાયિત કરવામાં આવે છે, તે જગ્યામાં સ્વતંત્ર ચક્રની સંખ્યાની ગણતરી કરે છે. એપ્લિકેશન્સ મેશેડનેસ ગુણાંક સમતલીય આલેખ માટે સર્કિટ ક્રમનો એક પ્રકાર, જે સમાન શિરોબિંદુ સમૂહ સાથે કોઈપણ સમતલીય આલેખના મહત્તમ શક્ય સર્કિટ ક્રમ દ્વારા વિભાજીત કરીને સામાન્યીકૃત થાય છે, તેને મેશેડનેસ ગુણાંક કહેવામાં આવે છે. ધાર અને શિરોબિંદુઓ સાથે જોડાયેલા સમતલીય આલેખ માટે, મેશેડનેસ ગુણાંકની ગણતરી સૂત્ર દ્વારા કરી શકાય છે અહીં, સૂત્રનો અંશ એ આપેલ આલેખનો સર્કિટ ક્રમ છે, અને છેદ એ-વર્ટેક્સ સમતલીય આલેખનો સૌથી મોટો શક્ય સર્કિટ ક્રમ છે. મેશેડનેસ ગુણાંક વૃક્ષો માટે 0 અને મહત્તમ સમતલીય આલેખ માટે 1 ની વચ્ચે હોય છે. કાનનું વિઘટન સર્કિટ ક્રમ ગ્રાફના કાનના વિઘટનમાં કાનની સંખ્યાને નિયંત્રિત કરે છે, ગ્રાફની કિનારીઓનું પાથ અને ચક્રમાં વિભાજન જે ઘણા ગ્રાફ અલ્ગોરિધમ્સમાં ઉપયોગી છે. ખાસ કરીને, ગ્રાફ 2-વર્ટેક્સ-જોડાયેલ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં ખુલ્લા કાનનું વિઘટન હોય. આ સબગ્રાફ્સનો ક્રમ છે, જ્યાં પ્રથમ સબગ્રાફ એક સરળ ચક્ર છે, બાકીના સબગ્રાફ્સ બધા સરળ પાથ છે, દરેક પાથ અગાઉના સબગ્રાફ્સના શિરોબિંદુઓ પર શરૂ થાય છે અને સમાપ્ત થાય છે, અને પાથનો દરેક આંતરિક શિરોબિંદુ તે પાથમાં પ્રથમ વખત દેખાય છે. સર્કિટ રેન્ક સાથેના કોઈપણ બાયકનેક્ટેડ ગ્રાફમાં, દરેક ખુલ્લા કાનના વિઘટનમાં બરાબર કાન હોય છે. લગભગ વૃક્ષો ચક્રીય સંખ્યા ધરાવતા આલેખને r-સૌથી નજીકનો વૃક્ષ પણ કહેવામાં આવે છે, કારણ કે તેને વૃક્ષ અથવા જંગલ બનાવવા માટે આલેખમાંથી માત્ર r ધારને દૂર કરવાની જરૂર પડે છે. 1-સૌથી નજીકનું વૃક્ષ એ નજીકના વૃક્ષ છેઃ નજીકના વૃક્ષ સાથે જોડાયેલું એક સ્યુડોટ્રી છે, જે દરેક શિરોબિંદુ પર મૂળ ધરાવતા (સંભવતઃ તુચ્છ) વૃક્ષ સાથેનું ચક્ર છે. કેટલાક લેખકોએ આર-નજીકના વૃક્ષો પર ગ્રાફ અલ્ગોરિધમ્સની પરિમાણિત જટિલતાનો અભ્યાસ કર્યો છે. નિર્દેશિત આલેખમાં સામાન્યીકરણ ચક્ર ક્રમ એ નિર્દેશિત આલેખનું અપરિવર્તનશીલ છે જે આલેખમાં ચક્રના માળાના સ્તરને માપે છે. તેની સર્કિટ રેન્ક કરતાં વધુ જટિલ વ્યાખ્યા છે (દિશાહીન આલેખ માટે વૃક્ષ-ઊંડાઈની વ્યાખ્યા સાથે નજીકથી સંબંધિત) અને તેની ગણતરી કરવી વધુ મુશ્કેલ છે. સર્કિટ ક્રમ સાથે સંબંધિત નિર્દેશિત આલેખ માટેની બીજી સમસ્યા લઘુતમ પ્રતિસાદ ચાપ સમૂહ છે, જે ધારનો સૌથી નાનો સમૂહ છે જેને દૂર કરવાથી તમામ નિર્દેશિત ચક્ર તૂટી જાય છે. ચક્ર ક્રમ અને લઘુતમ પ્રતિસાદ ચાપ સમૂહ બંને એન. પી.-ગણવા માટે મુશ્કેલ છે. ધારની દિશાઓને અવગણીને અને અંતર્ગત દિશાહીન આલેખના સર્કિટ ક્રમની ગણતરી કરીને નિર્દેશિત આલેખના સરળ અપરિવર્તનની ગણતરી કરવી પણ શક્ય છે. આ સિદ્ધાંત સાયક્લોમેટિક જટિલતાની વ્યાખ્યાનો આધાર બનાવે છે, જે કમ્પ્યુટર કોડનો એક ભાગ કેટલો જટિલ છે તેનો અંદાજ કાઢવા માટેનું સોફ્ટવેર મેટ્રિક છે. કોમ્પ્યુટેશનલ રસાયણશાસ્ત્ર રસાયણશાસ્ત્ર અને કેમિન્ફોર્મેટિક્સના ક્ષેત્રોમાં, મોલેક્યુલર ગ્રાફની સર્કિટ રેન્ક (નાના રિંગ્સના સૌથી નાના સમૂહમાં રિંગ્સની સંખ્યા) ને કેટલીકવાર ફ્રેરેજેક નંબર તરીકે ઓળખવામાં આવે છે. પેરામેટ્રીઝ્ડ જટિલતા આલેખ પરની કેટલીક કોમ્પ્યુટેશનલ સમસ્યાઓ સામાન્ય રીતે એન. પી.-હાર્ડ હોય છે, પરંતુ નાના સર્કિટ ક્રમવાળા આલેખ માટે બહુપદી સમયમાં ઉકેલી શકાય છે. એક ઉદાહરણ પાથ પુનઃરૂપરેખાંકન સમસ્યા છે. સંબંધિત વિભાવનાઓ આલેખમાંથી વસ્તુઓ કાઢી નાખવાના સંદર્ભમાં વ્યાખ્યાયિત અન્ય સંખ્યાઓ છેઃ ધાર જોડાણ-આલેખને ડિસ્કનેક્ટ કરવા માટે કાઢી નાખવા માટેની ધારની લઘુતમ સંખ્યા; મેળ ખાતી પૂર્વધારણા-સંપૂર્ણ મેળના અસ્તિત્વને રોકવા માટે કાઢી નાખવા માટેની ધારની લઘુતમ સંખ્યા; પ્રતિસાદ શિરોબિંદુ સમૂહ સંખ્યા-આલેખને ચક્રીય બનાવવા માટે કાઢી નાખવા માટેના શિરોબિંદુઓની લઘુતમ સંખ્યા; પ્રતિસાદ ચાપ સમૂહ-નિર્દેશિત આલેખમાંથી કાઢી નાખવા માટે ચાપની લઘુતમ સંખ્યા, તેને ચક્રીય બનાવવા માટે. સંદર્ભો આલેખ અપરિવર્તનશીલ મેટ્રોઇડ સિદ્ધાંત વૃક્ષને ફેલાવે છે