डिग्री (ग्राफ सिद्धांत)

एक लूप के साथ ग्राफ जिसमें डिग्री द्वारा लेबल किए गए कोने हैं

ग्राफ़ सिद्धांत में किसी ग्राफ़ के शीर्ष की डिग्री (या संयोजकता) उन किनारों की संख्या होती है जो शीर्ष पर आपतित होते हैं; मल्टीग्राफ में, किनारे के दोनों सिरों के लिए, लूप शीर्ष की डिग्री में 2 का योगदान देता है। किसी शीर्ष $v$ की डिग्री को $\deg(v)$ या $\deg v$ द्वारा निरूपित किया जाता है। ग्राफ़ $G$ की अधिकतम डिग्री, जिसे $\Delta (G)$ द्वारा निरूपित किया जाता है, और ग्राफ़ की न्यूनतम डिग्री, $\delta (G)$, इसके शीर्षों की अधिकतम और न्यूनतम डिग्री हैं। दाईं ओर दिखाए गए मल्टीग्राफ में अधिकतम डिग्री 5 और न्यूनतम डिग्री 0 है।

एक नियमित ग्राफ़ में, प्रत्येक शीर्ष की ही डिग्री होती है और इसलिए हम ग्राफ़ की डिग्री के बारे में बात कर सकते हैं। पूर्ण ग्राफ़ $K_{n}$ के रूप में दर्शाया गया है, $n$ ग्राफ़ में शीर्षों की संख्या है) विशेष प्रकार का नियमित ग्राफ़ है जहाँ सभी शीर्षों में अधिकतम संभव डिग्री $n-1$ होती है।

एक हस्ताक्षरित ग्राफ में, शीर्ष $v$ से जुड़े सकारात्मक किनारों की संख्या को सकारात्मक डिग्री $(v)$ कहा जाता है और जुड़े ऋणात्मक किनारों की संख्या को ऋणात्मक डिग्री $(v)$ कहा जाता है।

हैंडशेकिंग लेम्मा

Main article: हैंडशेकिंग लेम्मा

डिग्री योग सूत्र बताता है कि, ग्राफ $G=(V,E)$ दिया गया है।

$\sum _{v\in V}\deg(v)=2|E|\,$.

सूत्र का तात्पर्य है कि किसी भी अप्रत्यक्ष ग्राफ में विषम डिग्री वाले शीर्षों की संख्या सम है। यह कथन (साथ ही डिग्री योग सूत्र) हैंडशेकिंग लेम्मा के रूप में जाना जाता है। बाद वाला नाम लोकप्रिय गणितीय समस्या से आया है जो यह सिद्ध करना है कि लोगों के किसी भी समूह में समूह के अन्य लोगों की विषम संख्या के साथ हाथ मिलाने वाले लोगों की संख्या सम है।

डिग्री अनुक्रम

एक ही डिग्री अनुक्रम (3, 2, 2, 2, 2, 1, 1, 1) के साथ दो गैर-आइसोमोर्फिक ग्राफ।

एक अप्रत्यक्ष ग्राफ का डिग्री अनुक्रम इसके शीर्ष डिग्री का गैर-बढ़ता क्रम है; उपरोक्त ग्राफ के लिए यह (5, 3, 3, 2, 2, 1, 0) है। डिग्री अनुक्रम ग्राफ अपरिवर्तनीय है, इसलिए ग्राफ समरूपता में समान डिग्री अनुक्रम होता है। चूँकि डिग्री अनुक्रम सामान्य रूप से विशिष्ट रूप से किसी ग्राफ़ की पहचान नहीं करता है; कुछ स्थिति में गैर-आइसोमॉर्फिक ग्राफ़ में समान डिग्री अनुक्रम होता है।

डिग्री अनुक्रम समस्या डिग्री अनुक्रम के साथ कुछ या सभी ग्राफों को खोजने की समस्या है जो धनात्मक पूर्णांकों के दिए गए गैर-बढ़ते अनुक्रम हैं। (ट्रेलिंग जीरो को अनदेखा किया जा सकता है क्योंकि उन्हें ग्राफ में उचित संख्या में अलग-अलग वर्टिकल जोड़कर तुच्छ रूप से अनुभव किया जाता है।) अनुक्रम जो कुछ ग्राफ का डिग्री अनुक्रम है, अर्थात जिसके लिए डिग्री अनुक्रम समस्या का समाधान होता है, उसे ग्राफिक कहा जाता है। या चित्रमय अनुक्रम डिग्री योग सूत्र के परिणामस्वरूप विषम राशि वाले किसी भी क्रम, जैसे (3, 3, 1) को ग्राफ़ के डिग्री अनुक्रम के रूप में अनुभव नहीं किया जा सकता है। व्युत्क्रम भी सत्य है: यदि किसी अनुक्रम का सम योग है तो यह मल्टीग्राफ का डिग्री अनुक्रम है। इस तरह के ग्राफ़ का निर्माण सीधा है: जोड़ियों में विषम डिग्री के साथ कोने कनेक्ट करें (एक मिलान (ग्राफ़ सिद्धांत) बनाते हुए) और सेल्फ़-लूप द्वारा शेष सम डिग्री गणना भरें प्रश्न यह है कि क्या किसी दिए गए डिग्री अनुक्रम को साधारण ग्राफ द्वारा अनुभव किया जा सकता है यह अधिक चुनौतीपूर्ण है। इस समस्या को ग्राफ़ प्राप्ति समस्या भी कहा जाता है और इसे या तो एर्डोस-गैलाई प्रमेय या हावेल-हकीमी एल्गोरिथम द्वारा हल किया जा सकता है। दिए गए डिग्री अनुक्रम के साथ ग्राफ़ की संख्या खोजने या अनुमान लगाने की समस्या ग्राफ़ गणना के क्षेत्र से समस्या है।

अधिक सामान्यतः हाइपरग्राफ का डिग्री अनुक्रम इसके शीर्ष डिग्री का गैर-बढ़ता क्रम है। अनुक्रम $k$-ग्राफ़िक है यदि यह कुछ $k$-समान हाइपरग्राफ़ का डिग्री अनुक्रम है। विशेष रूप से $2$-ग्राफ़िक अनुक्रम ग्राफ़िक है। यह तय करना कि क्या दिया गया अनुक्रम $k$-ग्राफ़िक बहुपद समय में $k=2$ के लिए एर्डोस-गलई प्रमेय के माध्यम से संभव है, किंतु सभी $k\geq 3$ (डेज़ा एट अल।, 2018 ) के लिए एनपी-पूर्ण है।

विशेष मूल्य

लीफ नोड्स 4, 5, 6, 7, 10, 11 और 12 के साथ अप्रत्यक्ष ग्राफ

* डिग्री 0 वाले शीर्ष को पृथक शीर्ष कहा जाता है।

• डिग्री 1 वाले शीर्ष को लीफ वर्टेक्स या एंड वर्टेक्स या पेंडेंट वर्टेक्स कहा जाता है, और उस शीर्ष के साथ होने वाले किनारे को पेंडेंट एज कहा जाता है। दाईं ओर के ग्राफ़ में, {3,5} लटकता हुआ किनारा है। यह शब्दावली पेड़ (ग्राफ सिद्धांत) के ग्राफ सिद्धांत और विशेष रूप से पेड़ (डेटा संरचना) के अध्ययन में डेटा संरचनाओं के रूप में समान्य है।
• n शीर्षों पर ग्राफ़ में डिग्री n − 1 वाला शीर्ष प्रभावशाली शीर्ष कहलाता है।

वैश्विक गुण

• यदि ग्राफ़ के प्रत्येक शीर्ष की डिग्री k समान है, तो ग्राफ़ को नियमित ग्राफ़ k-नियमित ग्राफ़ कहा जाता है और ग्राफ़ को ही डिग्री k कहा जाता है। इसी तरह द्विदलीय ग्राफ जिसमें द्विभाजित के ही तरफ प्रत्येक दो शीर्षों में ही डिग्री होती है द्विनियमित ग्राफ कहलाता है।
• एक अप्रत्यक्ष जुड़े हुए ग्राफ में यूलेरियन पथ होता है यदि और केवल यदि इसमें विषम डिग्री के 0 या 2 कोने हों यदि इसमें विषम कोटि के 0 शीर्ष हों तो ऑयलरीय पथ ऑयलरीय परिपथ होता है।
• एक निर्देशित ग्राफ़ निर्देशित स्यूडोफ़ॉरेस्ट होता है यदि और केवल यदि हर वर्टेक्स में ज़्यादा से ज़्यादा 1 आउटडिग्री हो कार्यात्मक ग्राफ स्यूडोफ़ॉरेस्ट का विशेष स्थिति है जिसमें हर वर्टेक्स स्पष्ट रूप से आउटडिग्री है।
• ब्रूक्स के प्रमेय के अनुसार क्लिक या विषम चक्र के अतिरिक्त किसी भी ग्राफ G में अधिकतम Δ(G) रंगीन संख्या होती है, और वाइज़िंग के प्रमेय के अनुसार किसी भी ग्राफ़ में अधिकतम Δ(G) + 1 वर्णक्रमीय सूचकांक होता है।
• ए डीजेनेरेसी (ग्राफ सिद्धांत) के-डिजेनरेट ग्राफ ग्राफ है जिसमें प्रत्येक सबग्राफ में अधिकतम k डिग्री का शीर्ष होता है।

यह भी देखें

• डिग्राफ (गणित) के लिए इंडिग्री, आगे की डिग्री
• डिग्री वितरण
• द्विपक्षीय ग्राफ या डिग्री

संदर्भ

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok (in magyar), 11: 264–274.
• Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis Pro Pěstování Matematiky (in čeština), 80 (4): 477–480, doi:10.21136/CPM.1955.108220
• Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10 (3): 496–506, doi:10.1137/0110037, MR 0148049.
• Sierksma, Gerard; Hoogeveen, Han (1991), "Seven criteria for integer sequences being graphic", Journal of Graph Theory, 15 (2): 223–231, doi:10.1002/jgt.3190150209, MR 1106533.