Degree (graph theory)
ग्राफ सिद्धांत में, एक ग्राफ के शीर्ष की डिग्री (या संयोजकता) उन किनारों की संख्या है जो शीर्ष से जुड़े होते हैं; एक बहुलेखन में, एक लूप एक शीर्ष की डिग्री में 2 का योगदान देता है, किनारे के दो सिरों के लिए। एक शीर्ष की डिग्री को या दर्शाया जाता है। एक ग्राफ की अधिकतम डिग्री, और एक ग्राफ की न्यूनतम डिग्री, जिसके द्वारा निरूपित की जाती है, उसके शीर्षों की डिग्री की अधिकतम और न्यूनतम होती है। दाहिनी ओर दिखाए गए बहुलेखन में अधिकतम डिग्री 5 और न्यूनतम डिग्री 0 है। एक नियमित ग्राफ में, प्रत्येक शीर्ष की डिग्री समान होती है, और इसलिए हम ग्राफ की डिग्री की बात कर सकते हैं। एक पूर्ण ग्राफ (दर्शित, जहाँ ग्राफ में शीर्षों की संख्या है) एक विशेष प्रकार का नियमित ग्राफ है जहाँ सभी शीर्षों की अधिकतम संभव डिग्री होती है। एक हस्ताक्षरित ग्राफ में, शीर्ष से जुड़े सकारात्मक किनारों की संख्या को सकारात्मक डिग्री कहा जाता है और जुड़े नकारात्मक किनारों की संख्या को नकारात्मक डिग्री कहा जाता है। हाथ मिलाने का सूत्र डिग्री सम सूत्र बताता है कि, एक ग्राफ दिए जाने पर,। सूत्र का तात्पर्य है कि किसी भी दिशाहीन ग्राफ में विषम डिग्री वाले शीर्षों की संख्या सम होती है। इस कथन (साथ ही डिग्री सम सूत्र) को हाथ मिलाने वाले लेम्मा के रूप में जाना जाता है। बाद वाला नाम एक लोकप्रिय गणितीय समस्या से आया है, जो यह साबित करने के लिए है कि लोगों के किसी भी समूह में, समूह के विषम संख्या में अन्य लोगों के साथ हाथ मिलाने वाले लोगों की संख्या सम है। डिग्री अनुक्रम एक दिशाहीन ग्राफ का डिग्री अनुक्रम इसकी शीर्ष डिग्री का गैर-बढ़ता अनुक्रम है; उपरोक्त ग्राफ के लिए यह (5,3,3,2,2,1,0) है। डिग्री अनुक्रम एक ग्राफ अपरिवर्तनीय है, इसलिए समरूप ग्राफ में समान डिग्री अनुक्रम होता है। हालांकि, डिग्री अनुक्रम, सामान्य रूप से, एक ग्राफ की विशिष्ट रूप से पहचान नहीं करता है; कुछ मामलों में, गैर-समरूप ग्राफ में समान डिग्री अनुक्रम होता है। डिग्री अनुक्रम समस्या कुछ या सभी ग्राफों को खोजने की समस्या है जिसमें डिग्री अनुक्रम सकारात्मक पूर्णांकों का एक दिया गया गैर-बढ़ता अनुक्रम है। (पीछे के शून्यों को नजरअंदाज किया जा सकता है क्योंकि ग्राफ में अलग-अलग शीर्षों की एक उचित संख्या जोड़कर उन्हें मामूली रूप से महसूस किया जाता है।) एक अनुक्रम जो किसी ग्राफ का डिग्री अनुक्रम है, अर्थात। जिसके लिए डिग्री अनुक्रम समस्या का समाधान होता है, उसे ग्राफिक या ग्राफिकल अनुक्रम कहा जाता है। डिग्री सम सूत्र के परिणामस्वरूप, विषम योग वाले किसी भी अनुक्रम, जैसे (3,3,1), को ग्राफ के डिग्री अनुक्रम के रूप में महसूस नहीं किया जा सकता है। व्युत्क्रम भी सच हैः यदि किसी अनुक्रम का सम योग है, तो यह एक बहुलेखन का डिग्री अनुक्रम है। इस तरह के ग्राफ का निर्माण सीधा हैः जोड़ों में विषम डिग्री के साथ शीर्षों को जोड़ें (एक मिलान बनाते हुए), और शेष सम डिग्री गिनती को स्व-लूप द्वारा भरें। यह सवाल कि क्या किसी दिए गए डिग्री अनुक्रम को एक सरल ग्राफ द्वारा प्राप्त किया जा सकता है, अधिक चुनौतीपूर्ण है। इस समस्या को ग्राफ प्राप्ति समस्या भी कहा जाता है और इसे एर्दोस-गलाई प्रमेय या हावेल-हकीमी एल्गोरिदम द्वारा हल किया जा सकता है। दिए गए डिग्री अनुक्रम के साथ ग्राफ की संख्या को खोजने या अनुमान लगाने की समस्या ग्राफ गणना के क्षेत्र से एक समस्या है। अधिक आम तौर पर, एक हाइपरग्राफ का डिग्री अनुक्रम इसके शीर्ष डिग्री का गैर-बढ़ता अनुक्रम है। एक अनुक्रम-ग्राफिक है यदि यह किसी-समान हाइपरग्राफ का डिग्री अनुक्रम है। विशेष रूप से, एक-ग्राफिक अनुक्रम ग्राफिक होता है। यह तय करना कि क्या कोई दिया गया अनुक्रम-ग्राफिक है, बहुपद समय में एर्दोस-गलाई प्रमेय के माध्यम से किया जा सकता है, लेकिन सभी के लिए एन. पी.-पूर्ण है। विशेष मान 0 डिग्री वाले शीर्ष को पृथक शीर्ष कहा जाता है। डिग्री 1 वाले शीर्ष को पत्ती का शीर्ष या अंतिम शीर्ष या लटकन शीर्ष कहा जाता है, और उस शीर्ष के साथ किनारे की घटना को लटकन किनारा कहा जाता है। दाहिनी ओर ग्राफ में, {3,5} एक लटकन किनारा है। ग्राफ सिद्धांत में पेड़ों और विशेष रूप से डेटा संरचनाओं के रूप में पेड़ों के अध्ययन में यह शब्दावली आम है। एन शीर्षों पर ग्राफ में डिग्री एन-1 के साथ एक शीर्ष को एक प्रमुख शीर्ष कहा जाता है। वैश्विक गुण यदि ग्राफ के प्रत्येक शीर्ष में समान डिग्री k है, तो ग्राफ को k-नियमित ग्राफ कहा जाता है और ग्राफ को ही डिग्री k कहा जाता है। इसी तरह, एक द्विदलीय ग्राफ जिसमें द्विदलीय विभाजन के एक ही तरफ प्रत्येक दो शीर्षों में एक ही डिग्री होती है, जिसे द्विध्रुवीय ग्राफ कहा जाता है। एक दिशाहीन, जुड़े हुए ग्राफ में एक यूलरियन पथ होता है यदि और केवल तभी जब इसमें विषम डिग्री के 0 या 2 शीर्ष हों। यदि इसमें विषम डिग्री के 0 शीर्ष हैं, तो यूलरियन पथ एक यूलरियन परिपथ है। एक निर्देशित ग्राफ एक निर्देशित छद्म वन है यदि और केवल तभी जब प्रत्येक शीर्ष में अधिकतम 1 डिग्री हो। एक कार्यात्मक ग्राफ एक छद्म वन का एक विशेष मामला है जिसमें प्रत्येक शीर्ष की डिग्री बिल्कुल 1 होती है। ब्रूक्स के प्रमेय के अनुसार, एक गुट या एक विषम चक्र के अलावा किसी भी ग्राफ G में अधिकतम α (G) वर्णात्मक संख्या होती है, और वाइजिंग के प्रमेय के अनुसार किसी भी ग्राफ में अधिकतम α (G) + 1 वर्णात्मक सूचकांक होता है। एक के-अपक्षयी ग्राफ एक ग्राफ है जिसमें प्रत्येक उपग्राफ में अधिकतम के पर डिग्री का एक शीर्ष होता है। द्वि-पक्षीय ग्राफ नोट्स संदर्भों के लिए डिग्राफ डिग्री वितरण डिग्री अनुक्रम के लिए आउट डिग्री इंडेग्री भी देखें। .. .. ग्राफ सिद्धांत