Degree (graph theory)
આલેખ સિદ્ધાંતમાં, આલેખના શિરોબિંદુની ડિગ્રી (અથવા સંયોજકતા) એ શિરોબિંદુ સાથે સંકળાયેલી ધારની સંખ્યા છે; બહુવિજ્ઞાનમાં, એક લૂપ શિરોબિંદુની ડિગ્રીમાં 2 નું યોગદાન આપે છે, ધારના બે છેડા માટે. શિરોબિંદુની ડિગ્રી સૂચવવામાં આવે છે અથવા. ગ્રાફની મહત્તમ ડિગ્રી, દ્વારા સૂચવવામાં આવે છે, અને ગ્રાફની લઘુત્તમ ડિગ્રી, દ્વારા સૂચવવામાં આવે છે, તે તેના શિરોબિંદુઓની મહત્તમ અને લઘુત્તમ ડિગ્રી છે. જમણી બાજુએ બતાવેલ બહુવિજ્ઞાનમાં, મહત્તમ ડિગ્રી 5 અને લઘુત્તમ ડિગ્રી 0 છે. નિયમિત આલેખમાં, દરેક શિરોબિંદુ સમાન ડિગ્રી ધરાવે છે, અને તેથી આપણે આલેખની ડિગ્રી વિશે વાત કરી શકીએ છીએ. સંપૂર્ણ આલેખ (સૂચવવામાં આવે છે, ગ્રાફમાં શિરોબિંદુઓની સંખ્યા ક્યાં છે) એ એક ખાસ પ્રકારનો નિયમિત આલેખ છે જ્યાં તમામ શિરોબિંદુઓ મહત્તમ શક્ય ડિગ્રી ધરાવે છે. હસ્તાક્ષરિત આલેખમાં, શિરોબિંદુ સાથે જોડાયેલી હકારાત્મક ધારની સંખ્યાને હકારાત્મક ડિગ્રી કહેવામાં આવે છે અને જોડાયેલી નકારાત્મક ધારની સંખ્યાને નકારાત્મક ડિગ્રી કહેવામાં આવે છે. હેન્ડશેકિંગ લેમ્મા ડિગ્રી સમ સૂત્ર જણાવે છે કે, ગ્રાફ આપવામાં આવે તો. સૂત્ર સૂચવે છે કે કોઈપણ દિશાહીન આલેખમાં, વિષમ ડિગ્રીવાળા શિરોબિંદુઓની સંખ્યા સમ હોય છે. આ નિવેદન (તેમજ ડિગ્રી સમ સૂત્ર) હાથ મિલાવવાના લેમ્મા તરીકે ઓળખાય છે. પછીનું નામ એક લોકપ્રિય ગાણિતિક સમસ્યા પરથી આવ્યું છે, જે સાબિત કરવા માટે છે કે લોકોના કોઈપણ જૂથમાં, જૂથના અન્ય લોકોની વિચિત્ર સંખ્યા સાથે હાથ મિલાવનારા લોકોની સંખ્યા સરખી છે. દિશાહીન આલેખનો ડિગ્રી ક્રમ એ તેની શિરોબિંદુ ડિગ્રીનો બિન-વધતો ક્રમ છે; ઉપરોક્ત આલેખ માટે તે છે (5,3,3,2,1,0). ડિગ્રી ક્રમ એ આલેખ અપરિવર્તનશીલ છે, તેથી આઇસોમોર્ફિક આલેખમાં સમાન ડિગ્રી ક્રમ હોય છે. જો કે, ડિગ્રી ક્રમ, સામાન્ય રીતે, ગ્રાફને અનન્ય રીતે ઓળખતો નથી; કેટલાક કિસ્સાઓમાં, બિન-આઇસોમોર્ફિક ગ્રાફમાં સમાન ડિગ્રી ક્રમ હોય છે. ડિગ્રી ક્રમની સમસ્યા એ કેટલાક અથવા બધા આલેખ શોધવાની સમસ્યા છે જેમાં ડિગ્રી ક્રમ એ હકારાત્મક પૂર્ણાંકોનો આપેલ બિન-વધતો ક્રમ છે. (પાછળના શૂન્યને અવગણવામાં આવી શકે છે કારણ કે ગ્રાફમાં યોગ્ય સંખ્યામાં અલગ શિરોબિંદુઓ ઉમેરીને તેમને તુચ્છ રીતે સમજવામાં આવે છે.) એક ક્રમ જે અમુક આલેખનો ડિગ્રી ક્રમ છે, એટલે કે. જેના માટે ડિગ્રી સિક્વન્સ સમસ્યાનો ઉકેલ હોય છે, તેને ગ્રાફિક અથવા ગ્રાફિકલ સિક્વન્સ કહેવામાં આવે છે. ડિગ્રી સરવાળા સૂત્રના પરિણામે, (3,3,1) જેવા વિષમ સરવાળા કોઈપણ ક્રમને આલેખના ડિગ્રી ક્રમ તરીકે અનુભવી શકાતો નથી. ઊલટું પણ સાચું છેઃ જો કોઈ ક્રમમાં સમ સરવાળો હોય, તો તે બહુવિજ્ઞાનનો ડિગ્રી ક્રમ છે. આવા આલેખની રચના સીધી છેઃ શિરોબિંદુઓને જોડીમાં વિષમ ડિગ્રી સાથે જોડો (મેળ ખાતી રચના), અને બાકીની સમ ડિગ્રી ગણતરીઓને સ્વ-લૂપ્સ દ્વારા ભરો. આપેલ ડિગ્રી ક્રમને સરળ આલેખ દ્વારા સાકાર કરી શકાય છે કે કેમ તે પ્રશ્ન વધુ પડકારજનક છે. આ સમસ્યાને આલેખ અનુભૂતિ સમસ્યા પણ કહેવામાં આવે છે અને તેને એર્દોસ-ગલાઈ પ્રમેય અથવા હેવલ-હકીમી અલ્ગોરિધમ દ્વારા ઉકેલી શકાય છે. આપેલ ડિગ્રી ક્રમ સાથે આલેખની સંખ્યા શોધવાની અથવા અંદાજવાની સમસ્યા એ આલેખ ગણતરીના ક્ષેત્રની સમસ્યા છે. વધુ સામાન્ય રીતે, હાયપરગ્રાફનો ડિગ્રી ક્રમ એ તેના શિરોબિંદુ ડિગ્રીનો બિન-વધતો ક્રમ છે. એક ક્રમ-ગ્રાફિક હોય છે જો તે કોઈ એકસમાન હાયપરગ્રાફનો ડિગ્રી ક્રમ હોય. ખાસ કરીને, એક-ગ્રાફિક ક્રમ ગ્રાફિક છે. આપેલ ક્રમ-ગ્રાફિક છે કે નહીં તે નક્કી કરવું એર્ડોસ-ગલાઈ પ્રમેય દ્વારા બહુપદી સમયમાં કરી શકાય છે પરંતુ તે બધા માટે એન. પી.-પૂર્ણ છે. વિશેષ મૂલ્યો 0 ડિગ્રીવાળા શિરોબિંદુને અલગ શિરોબિંદુ કહેવામાં આવે છે. ડિગ્રી 1 સાથેના શિરોબિંદુને પર્ણ શિરોબિંદુ અથવા અંતિમ શિરોબિંદુ અથવા પેન્ડન્ટ શિરોબિંદુ કહેવામાં આવે છે, અને તે શિરોબિંદુ સાથેની ધારની ઘટનાને પેન્ડન્ટ ધાર કહેવામાં આવે છે. જમણી બાજુના આલેખમાં, {3,5} એ પેન્ડન્ટ ધાર છે. આ પરિભાષા આલેખ સિદ્ધાંતમાં વૃક્ષોના અભ્યાસમાં અને ખાસ કરીને વૃક્ષોને માહિતી માળખા તરીકે સામાન્ય છે. n શિરોબિંદુઓ પરના આલેખમાં n − 1 ડિગ્રી ધરાવતા શિરોબિંદુને પ્રભુત્વ ધરાવતું શિરોબિંદુ કહેવામાં આવે છે. વૈશ્વિક ગુણધર્મો જો આલેખના દરેક શિરોબિંદુમાં સમાન ડિગ્રી k હોય, તો આલેખને k-નિયમિત આલેખ કહેવામાં આવે છે અને આલેખ પોતે જ ડિગ્રી k હોવાનું કહેવાય છે. તેવી જ રીતે, દ્વિપક્ષી આલેખ જેમાં દ્વિપક્ષીકરણની એક જ બાજુએ દરેક બે શિરોબિંદુઓ એકબીજાની સમાન ડિગ્રી ધરાવે છે તેને બાયરેગ્યુલર ગ્રાફ કહેવામાં આવે છે. દિશાહીન, જોડાયેલા આલેખમાં યુલરિયન માર્ગ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં વિષમ ડિગ્રીના 0 અથવા 2 શિરોબિંદુ હોય. જો તેમાં વિષમ ડિગ્રીના 0 શિરોબિંદુઓ હોય, તો યુલરિયન માર્ગ એક યુલરિયન સર્કિટ છે. નિર્દેશિત આલેખ એ નિર્દેશિત સ્યુડોફોરેસ્ટ છે જો અને માત્ર ત્યારે જ જો દરેક શિરોબિંદુ મહત્તમ 1 ડિગ્રી હોય. કાર્યાત્મક આલેખ એ સ્યુડોફોરેસ્ટનો એક ખાસ કેસ છે જેમાં દરેક શિરોબિંદુ બરાબર 1 ડિગ્રી ધરાવે છે. બ્રૂક્સના પ્રમેય અનુસાર, સમૂહ અથવા વિષમ ચક્ર સિવાયના કોઈપણ આલેખ G માં મહત્તમ α (G) રંગસૂત્ર સંખ્યા હોય છે, અને વાઇઝિંગના પ્રમેય અનુસાર કોઈપણ આલેખમાં મહત્તમ α (G) + 1 રંગસૂત્ર સૂચકાંક હોય છે. કે-ડીજનરેટ આલેખ એ એક આલેખ છે જેમાં દરેક પેટા આલેખ મહત્તમ ડિગ્રીનો શિરોબિંદુ ધરાવે છે. દ્વિ-પક્ષીય આલેખ નોંધો સંદર્ભો માટે ડિગ્રાફ ડિગ્રી વિતરણ ડિગ્રી ક્રમ માટે આઉટ ડિગ્રી ઇન્ડીગ્રી પણ જુઓ. . . આલેખ સિદ્ધાંત