डिग्री मैट्रिक्स

From Vigyanwiki
Revision as of 23:22, 17 July 2023 by alpha>Artiverma

बीजीय ग्राफ सिद्धांत के गणित क्षेत्र में, अप्रत्यक्ष ग्राफ का डिग्री मैट्रिक्स ऐसा विकर्ण मैट्रिक्स होता है जिसमें प्रत्येक शीर्ष (ग्राफ सिद्धांत) की डिग्री (ग्राफ सिद्धांत) के बारे में जानकारी होती है- अर्थात, प्रत्येक शीर्ष से जुड़े किनारों की संख्या होती है,[1] ग्राफ़ के लाप्लासियन मैट्रिक्स का निर्माण करने के लिए इसका उपयोग आसन्न मैट्रिक्स के साथ किया जाता है: लाप्लासियन मैट्रिक्स डिग्री मैट्रिक्स और आसन्न मैट्रिक्स का अंतर है।[2]

परिभाषा

ग्राफ दिया गया और , डिग्री मैट्रिक्स के लिए है विकर्ण मैट्रिक्स के रूप में परिभाषित किया गया है[1]:

डिग्री जहां किसी शीर्ष की संख्या यह गिनती है कि कोई किनारा उस शीर्ष पर कितनी बार समाप्त होता है। अप्रत्यक्ष ग्राफ़ में, इसका तात्पर्य है कि प्रत्येक लूप शीर्ष की डिग्री को दो से बढ़ा देता है। निर्देशित ग्राफ में, डिग्री शब्द या तो इंडिग्री (प्रत्येक शीर्ष पर आने वाले किनारों की संख्या) या आउटडिग्री (प्रत्येक शीर्ष पर आउटगोइंग किनारों की संख्या) को संदर्भित कर सकता है।

उदाहरण

निम्नलिखित अप्रत्यक्ष ग्राफ़ में मानों के साथ 6x6 डिग्री मैट्रिक्स है:

Vertex labeled graph Degree matrix
6n-graph2.svg

ध्यान दें कि अप्रत्यक्ष ग्राफ़ की स्तिथि में, किनारा जो एक ही नोड में प्रारंभ और समाप्त होता है, संबंधित डिग्री मान को 2 से बढ़ा देता है (अर्थात इसे दो बार गिना जाता है)।

गुण

के-नियमित ग्राफ़ के डिग्री मैट्रिक्स का स्थिर विकर्ण होता है .

डिग्री योग सूत्र के अनुसार, डिग्री मैट्रिक्स का ट्रेस (रैखिक बीजगणित) विचारित ग्राफ के किनारों की संख्या से दोगुना है।

संदर्भ

  1. 1.0 1.1 Chung, Fan; Lu, Linyuan; Vu, Van (2003), "Spectra of random graphs with given expected degrees", Proceedings of the National Academy of Sciences of the United States of America, 100 (11): 6313–6318, Bibcode:2003PNAS..100.6313C, doi:10.1073/pnas.0937490100, MR 1982145, PMC 164443, PMID 12743375.
  2. Mohar, Bojan (2004), "Graph Laplacians", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Topics in algebraic graph theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, Cambridge, pp. 113–136, ISBN 0-521-80197-4, MR 2125091.