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

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

परिभाषा

ग्राफ $G=(V,E)$ दिया गया और $|V|=n$, डिग्री मैट्रिक्स $D$ के लिए $G$ है $n\times n$ विकर्ण मैट्रिक्स के रूप में परिभाषित किया गया है:

$D_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.$

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

उदाहरण

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

Vertex labeled graph	Degree matrix
	${\begin{pmatrix}4&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{pmatrix}}$

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

गुण

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

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