डिग्री मैट्रिक्स: Difference between revisions
(Created page with "बीजीय ग्राफ सिद्धांत के गणित क्षेत्र में, एक अप्रत्यक्ष ग्राफ का...") |
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 25: | Line 25: | ||
| year = 2004}}.</ref> | | year = 2004}}.</ref> | ||
== परिभाषा == | |||
==परिभाषा== | ग्राफ दिया गया <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 34: | Line 33: | ||
\right. | \right. | ||
</math> | </math> | ||
डिग्री कहां <math>\deg(v_i)</math> किसी शीर्ष की संख्या यह गिनती है कि कोई किनारा उस शीर्ष पर कितनी बार समाप्त होता है। | डिग्री कहां <math>\deg(v_i)</math> किसी शीर्ष की संख्या यह गिनती है कि कोई किनारा उस शीर्ष पर कितनी बार समाप्त होता है। अप्रत्यक्ष ग्राफ़ में, इसका मतलब है कि प्रत्येक लूप शीर्ष की [[डिग्री]] को दो से बढ़ा देता है। [[निर्देशित ग्राफ]]़ में, डिग्री शब्द या तो इंडिग्री (प्रत्येक शीर्ष पर आने वाले किनारों की संख्या) या [[आउटडिग्री]] (प्रत्येक शीर्ष पर आउटगोइंग किनारों की संख्या) को संदर्भित कर सकता है। | ||
==उदाहरण== | ==उदाहरण== | ||
| Line 54: | Line 53: | ||
\end{pmatrix}</math> | \end{pmatrix}</math> | ||
|} | |} | ||
ध्यान दें कि अप्रत्यक्ष ग्राफ़ के मामले में, | ध्यान दें कि अप्रत्यक्ष ग्राफ़ के मामले में, किनारा जो ही नोड में शुरू और समाप्त होता है, संबंधित डिग्री मान को 2 से बढ़ा देता है (यानी इसे दो बार गिना जाता है)। | ||
==गुण== | ==गुण== | ||
[[के-नियमित ग्राफ़]] के डिग्री मैट्रिक्स का | [[के-नियमित ग्राफ़]] के डिग्री मैट्रिक्स का स्थिर विकर्ण होता है <math>k</math>. | ||
[[डिग्री योग सूत्र]] के अनुसार, डिग्री मैट्रिक्स का [[ट्रेस (रैखिक बीजगणित)]] विचारित ग्राफ के किनारों की संख्या से दोगुना है। | [[डिग्री योग सूत्र]] के अनुसार, डिग्री मैट्रिक्स का [[ट्रेस (रैखिक बीजगणित)]] विचारित ग्राफ के किनारों की संख्या से दोगुना है। | ||
Revision as of 21:17, 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.
