डिग्री मैट्रिक्स: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
बीजीय ग्राफ सिद्धांत के गणित क्षेत्र में, [[अप्रत्यक्ष ग्राफ]] का डिग्री मैट्रिक्स [[विकर्ण मैट्रिक्स]] होता है जिसमें प्रत्येक शीर्ष (ग्राफ सिद्धांत) की [[डिग्री (ग्राफ सिद्धांत)]] के बारे में जानकारी होती है - अर्थात, प्रत्येक शीर्ष से जुड़े किनारों की | बीजीय ग्राफ सिद्धांत के गणित क्षेत्र में, [[अप्रत्यक्ष ग्राफ]] का '''डिग्री मैट्रिक्स ऐसा''' [[विकर्ण मैट्रिक्स]] होता है जिसमें प्रत्येक शीर्ष (ग्राफ सिद्धांत) की [[डिग्री (ग्राफ सिद्धांत)]] के बारे में जानकारी होती है- अर्थात, प्रत्येक शीर्ष से जुड़े किनारों की संख्या होती है,<ref name="clv">{{citation | ||
| last1 = Chung | first1 = Fan | author1-link = Fan Chung | | last1 = Chung | first1 = Fan | author1-link = Fan Chung | ||
| last2 = Lu | first2 = Linyuan | | last2 = Lu | first2 = Linyuan | ||
| Line 26: | Line 26: | ||
== परिभाषा == | == परिभाषा == | ||
ग्राफ | ग्राफ <math>G=(V,E)</math> दिया गया और <math>|V|=n</math>, डिग्री मैट्रिक्स <math>D</math> के लिए <math>G</math> है <math>n \times n</math> विकर्ण मैट्रिक्स के रूप में परिभाषित किया गया है<ref name="clv"/>: | ||
<math>D_{i,j}:=\left\{ | |||
\begin{matrix} | \begin{matrix} | ||
\deg(v_i) & \mbox{if}\ i = j \\ | \deg(v_i) & \mbox{if}\ i = j \\ | ||
| Line 33: | Line 35: | ||
\right. | \right. | ||
</math> | </math> | ||
डिग्री | |||
डिग्री जहां <math>\deg(v_i)</math> किसी शीर्ष की संख्या यह गिनती है कि कोई किनारा उस शीर्ष पर कितनी बार समाप्त होता है। अप्रत्यक्ष ग्राफ़ में, इसका तात्पर्य है कि प्रत्येक लूप शीर्ष की [[डिग्री]] को दो से बढ़ा देता है। [[निर्देशित ग्राफ]] में, डिग्री शब्द या तो इंडिग्री (प्रत्येक शीर्ष पर आने वाले किनारों की संख्या) या [[आउटडिग्री]] (प्रत्येक शीर्ष पर आउटगोइंग किनारों की संख्या) को संदर्भित कर सकता है। | |||
==उदाहरण== | ==उदाहरण== | ||
| Line 53: | Line 56: | ||
\end{pmatrix}</math> | \end{pmatrix}</math> | ||
|} | |} | ||
ध्यान दें कि अप्रत्यक्ष ग्राफ़ | ध्यान दें कि अप्रत्यक्ष ग्राफ़ की स्तिथि में, किनारा जो एक ही नोड में प्रारंभ और समाप्त होता है, संबंधित डिग्री मान को 2 से बढ़ा देता है (अर्थात इसे दो बार गिना जाता है)। | ||
==गुण== | ==गुण== | ||
[[के-नियमित ग्राफ़]] के डिग्री मैट्रिक्स का स्थिर विकर्ण | [[के-नियमित ग्राफ़]] के डिग्री मैट्रिक्स का स्थिर विकर्ण <math>k</math> होता है . | ||
[[डिग्री योग सूत्र]] के अनुसार, डिग्री मैट्रिक्स का [[ट्रेस (रैखिक बीजगणित)]] विचारित ग्राफ के किनारों की संख्या से दोगुना है। | [[डिग्री योग सूत्र]] के अनुसार, डिग्री मैट्रिक्स का [[ट्रेस (रैखिक बीजगणित)]] विचारित ग्राफ के किनारों की संख्या से दोगुना है। | ||
Revision as of 23:22, 17 July 2023
बीजीय ग्राफ सिद्धांत के गणित क्षेत्र में, अप्रत्यक्ष ग्राफ का डिग्री मैट्रिक्स ऐसा विकर्ण मैट्रिक्स होता है जिसमें प्रत्येक शीर्ष (ग्राफ सिद्धांत) की डिग्री (ग्राफ सिद्धांत) के बारे में जानकारी होती है- अर्थात, प्रत्येक शीर्ष से जुड़े किनारों की संख्या होती है,[1] ग्राफ़ के लाप्लासियन मैट्रिक्स का निर्माण करने के लिए इसका उपयोग आसन्न मैट्रिक्स के साथ किया जाता है: लाप्लासियन मैट्रिक्स डिग्री मैट्रिक्स और आसन्न मैट्रिक्स का अंतर है।[2]
परिभाषा
ग्राफ दिया गया और , डिग्री मैट्रिक्स के लिए है विकर्ण मैट्रिक्स के रूप में परिभाषित किया गया है[1]:
डिग्री जहां किसी शीर्ष की संख्या यह गिनती है कि कोई किनारा उस शीर्ष पर कितनी बार समाप्त होता है। अप्रत्यक्ष ग्राफ़ में, इसका तात्पर्य है कि प्रत्येक लूप शीर्ष की डिग्री को दो से बढ़ा देता है। निर्देशित ग्राफ में, डिग्री शब्द या तो इंडिग्री (प्रत्येक शीर्ष पर आने वाले किनारों की संख्या) या आउटडिग्री (प्रत्येक शीर्ष पर आउटगोइंग किनारों की संख्या) को संदर्भित कर सकता है।
उदाहरण
निम्नलिखित अप्रत्यक्ष ग्राफ़ में मानों के साथ 6x6 डिग्री मैट्रिक्स है:
| Vertex labeled graph | Degree matrix |
|---|---|
|
ध्यान दें कि अप्रत्यक्ष ग्राफ़ की स्तिथि में, किनारा जो एक ही नोड में प्रारंभ और समाप्त होता है, संबंधित डिग्री मान को 2 से बढ़ा देता है (अर्थात इसे दो बार गिना जाता है)।
गुण
के-नियमित ग्राफ़ के डिग्री मैट्रिक्स का स्थिर विकर्ण होता है .
डिग्री योग सूत्र के अनुसार, डिग्री मैट्रिक्स का ट्रेस (रैखिक बीजगणित) विचारित ग्राफ के किनारों की संख्या से दोगुना है।
संदर्भ
- ↑ 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.
- ↑ 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.
