आसन्नता आव्यूह: Difference between revisions

Latest revision as of 16:26, 16 October 2023

आलेख सिद्धांत और कंप्यूटर विज्ञान में, एक आसन्नता आव्यूह एक वर्ग आव्यूह है जो एक परिमित आलेख का प्रतिनिधित्व करने के लिए उपयोग किया जाता है। आव्यूह के अवयव निर्दिष्ट करते हैं कि शीर्ष के जोड़े आलेख में आसन्न हैं या नहीं।

परिमित सरल आलेख के विशेष स्थिति में, आसन्नता आव्यूह एक (0,1) -आव्यूह है जिसके विकर्ण पर शून्य हैं। यदि आलेख़ अप्रत्यक्ष है (अर्थात् इसके सभी किनारे द्विदिश हैं) तथा आसन्नता आव्यूह सममित है। वर्णक्रमीय आलेख सिद्धांत में एक आलेख और उसके आसन्नता आव्यूह के अभिलक्षणिक मान और अभिलक्षणिक सदिश के बीच संबंध का अध्ययन किया जाता है।

एक आलेख़ के आसन्नता आव्यूह को इसके आपतन आव्यूह से अलग किया जाना चाहिए, एक अलग आव्यूह प्रतिनिधित्व जिसके अवयव निर्दिष्ट करते हैं कि शीर्ष-किनारे जोड़े आपतन हैं या नहीं, और इसका डिग्री आव्यूह, जिसमें प्रत्येक शीर्ष की डिग्री के बारे में जानकारी सम्मिलित है

परिभाषा

शीर्ष समुच्चय $U = {u 1, \dots, u n}$ के साथ एक साधारण आलेख के लिए आसन्नता आव्यूह एक वर्ग $n \times n$ आव्यूह $A$ है, जैसे कि इसका अवयव $A ij$ एक है जब शीर्ष $u i$ से शीर्ष $u j$ , तक एक किनारा होता है, और शून्य जब कोई किनारा नहीं है।^[1] आव्यूह के विकर्ण अवयव सभी शून्य हैं, क्योंकि क्योंकि सरल रेखांकन में एक शीर्ष से स्वयं (लूप) के किनारों की अनुमति नहीं है। यह कभी-कभी बीजगणितीय आलेख सिद्धांत में गैर-शून्य अवयवों को बीजगणितीय चर के साथ बदलने के लिए भी उपयोगी होता है।^[2] संबंधित आव्यूह अवयव में प्रत्येक दो कोने के बीच किनारों की संख्या को संग्रहीत करके और गैर-शून्य विकर्ण अवयवों की अनुमति देकर एक ही अवधारणा को बहुलेख और लूप के साथ आलेख़ तक बढ़ाया जा सकता है। लूप्स को या तो एक बार (एक किनारे के रूप में) या दो बार (दो शीर्ष-किनारे आपतन के रूप में) गिना जा सकता है, जब तक कि एक सुसंगत सम्मेलन का पालन किया जाता है। अदिष्‍ट आलेख अक्सर दो बार गिनती के छोरों के बाद के सम्मेलन का उपयोग करते हैं, जबकि दिष्ट आलेख आमतौर पर पूर्व सम्मेलन का उपयोग करते हैं।

एक द्विदलीय आलेख का

एक द्विदलीय ग्राफ का आसन्नता आव्यूह $A$ , जिसके दो भागों में $r$ और $s$ कोने हैं, जिसको

$A={\begin{pmatrix}0_{r,r}&B\\B^{\mathsf {T}}&0_{s,s}\end{pmatrix}},$

के रूप में लिखा जा सकता है, जहाँ $B$ एक $r \times s$ आव्यूह है, और $0 r, r$ और $0 s, s$ , $r \times r$ और $s \times s$ शून्य आव्यूह का प्रतिनिधित्व करते हैं। इस स्थिति में, छोटा आव्यूह $B$ विशिष्ट रूप से आलेख और शेष भागों का प्रतिनिधित्व करता है, और $A$ के शेष हिस्सों को अनावश्यक के रूप में निराकृत कर दिया जाता है। $B$ को कभी-कभी द्विदिशता आव्यूह कहा जाता है।

औपचारिक रूप से, $G = (U, V, E)$ भागों $U = {u 1, ..., u r}$ , $V = {v 1, ..., v s}$ और किनारों $E$ के साथके साथ एक द्विदलीय ग्राफ होने दें। द्विआसन्नता आव्यूह $r \times s$ 0–1 आव्यूह $B$ है जिसमें $b i, j = 1$ और केवल $(u i, v j) \in E$ .

है।

यदि $G$ एक द्विपक्षीय बहुआलेख या भारित आलेख है, तो अवयव $b i,j$ को शीर्षों के बीच किनारों की संख्या या किनारों के भार $(u i, v j)$ के रूप में लिया जाता है।

विविधताएं

एक $(a, b, c)$ - साधारण आलेख के सहखंडज आव्यूह $A$ में $A i, j = a$ है ,और $(i, j)$ एक किनारा है, $b$ यह नहीं है, और $c$ विकर्ण पर है। साइजल आसन्नता आव्यूह एक $(-1, 1, 0)$ -सहखंडज आव्यूह है। यह आव्यूह दृढ़ता से नियमित आलेख और दो-आलेख का अध्ययन करने में प्रयोग किया जाता है।^[3]

दूरी आव्यूह की स्थिति $(i, j)$ में शीर्ष $v i$ और $v j$ के बीच दूरी है। दूरी शीर्षों को जोड़ने वाले सबसे छोटे पथ की लंबाई है। जब तक किनारों की लंबाई स्पष्ट रूप से प्रदान नहीं की जाती है, तब तक पथ की लंबाई इसमें किनारों की संख्या होती है। दूरी आव्यूह आसन्नता आव्यूह की एक उच्च शक्ति जैसा दिखता है, लेकिन केवल यह बताने के बजाय कि दो कोने जुड़े हुए हैं या नहीं (यानी, संयुग्मन, जिसमें बूलियन मान होता है), यह उनके बीच सटीक दूरी देता है।

उदाहरण

अदिष्‍ट आलेख

यहाँ (अदिष्‍ट आलेख के लिए) परिपाटी यह है कि प्रत्येक किनारा आव्यूह में उपयुक्त सेल में 1 जोड़ता है, और प्रत्येक लूप 2 जोड़ता है।^[4] यह आसन्नता आव्यूह में संबंधित पंक्ति या स्तंभ में मानों का योग लेकर किसी शीर्ष की डिग्री को आसानी से प्राप्त करने की अनुमति देता है।

लेबल ग्राफ	संलग्नता आव्यूह
	${\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}$ निर्देशांक 1-6 हैं।
नाउरू ग्राफ	निर्देशांक 0-23 हैं. सफेद क्षेत्र शून्य हैं, रंगीन क्षेत्र एक हैं।

दिष्ट आलेख

दिष्ट आलेख का आसन्नता आव्यूह असममित हो सकता है। एक दिष्ट आलेख के आसन्नता आव्यूह को इस तरह परिभाषित कर सकते हैं

एक गैर-शून्य अवयव $A ij$ $i$ से $j$ तक किनारे को निर्दिष्ट करता है या
यह $j$ से $i$ तक के किनारे को निर्दिष्ट करता है।

पूर्व परिभाषा आमतौर पर आलेख सिद्धांत और सामाजिक नेटवर्क विश्लेषण (जैसे, समाजशास्त्र, राजनीति विज्ञान, अर्थशास्त्र, मनोविज्ञान) में उपयोग की जाती है।^[5] उत्तरार्द्ध अन्य अनुप्रयुक्त विज्ञानों (जैसे, गतिशील प्रणाली, भौतिकी, नेटवर्क विज्ञान) में अधिक सामान्य है , जहां $A$ का उपयोग कभी-कभी आलेख पर रैखिक गतिकी का वर्णन करने के लिए किया जाता है।^[6]

पहली परिभाषा का उपयोग करते हुए, एक शीर्ष की अंतःकोटि की गणना संबंधित स्तम्भ की प्रविष्टियों और शीर्ष की बाह्‍य कोटि की गणना संबंधित पंक्ति की प्रविष्टियों को जोड़कर की जा सकती है। दूसरी परिभाषा का उपयोग करते समय, एक शीर्ष की अंतःकोटि संबंधित पंक्ति योग द्वारा दी जाती है और बाह्‍य कोटि संबंधित स्तम्भ योग द्वारा दी जाती है।

लेबल ग्राफ	संलग्नता आव्यूह
Directed Cayley graph of S₄	Coordinates are 0–23. As the graph is directed, the matrix is not necessarily symmetric.

तुच्छालेख

एक पूर्ण आलेख के आसन्नता आव्यूह में विकर्ण के अलावा सभी सम्मिलित हैं, जहां केवल शून्य हैं। खाली आलेख का आसन्नता आव्यूह एक शून्य आव्यूह है।

गुण

वर्णक्रम

एक अप्रत्यक्ष सरल आलेख का आसन्नता आव्यूह सममित आव्यूह है, और इसलिए वास्तविक संख्या अभिलक्षणिक मान और एक लाम्बिक अभिलक्षणिक सदिश आधार का एक पूरा समुच्चय है। एक आलेख के अभिलक्षणिक मान का समुच्चय आलेख का वर्णक्रम है।^[7] अभिलक्षणिक मान को

$\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$

निरूपित करना सामान्य है। सबसे बड़ा अभिलक्षणिक मान $\lambda _{1}$ ऊपर अधिकतम डिग्री से घिरा है। इसे पेरोन-फ्रोबेनियस प्रमेय के परिणाम के रूप में देखा जा सकता है, लेकिन इसे आसानी से सिद्ध किया जा सकता है। मान लो $v$ $\lambda _{1}$ और $x$ से जुड़ा एक अभिलक्षणिक सदिश है जिसमे $v$ का अधिकतम निरपेक्ष मान है। व्यापकता के नुकसान के बिना मान लें कि $v x$ धनात्मक है क्योंकि अन्यथा आप केवल अभिलक्षणिक सदिश $-v$ लेते हैं ,जो $\lambda _{1}$ से भी जुड़ा है। तब

\lambda _{1}v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x).

$d$ -नियमित आलेख के लिए, $d$ सदिश $v = (1, \dots, 1)$ के लिए $A$ का पहला अभिलक्षणिक मान है (यह जांचना आसान है कि यह एक अभिलक्षणिक मान है और उपरोक्त सीमा के कारण यह अधिकतम है)। इस अभिलक्षणिक मान की बहुलता $G$ के जुड़े घटकों की संख्या है , विशेष रूप से $\lambda _{1}>\lambda _{2}$ जुड़े हुए आलेख के लिए। यह दिखाया जा सकता है कि प्रत्येक अभिलक्षणिक मान $\lambda _{i}$ के लिए, इसका विपरीत $-\lambda _{i}=\lambda _{n+1-i}$ भी $A$ का अभिलक्षणिक मान है यदि $G$ एक द्विपक्षीय आलेख है।^[8] विशेष रूप से - $d$ किसी भी $d$ -नियमित द्विपक्षीय आलेख का अभिलक्षणिक मान है।

अंतर $\lambda _{1}-\lambda _{2}$ को वर्णक्रमीय अंतराल कहा जाता है और यह $G$ के विस्तारक से संबंधित है। $A$ की वर्णक्रमीय त्रिज्या को $\lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|$ से प्रदर्शित करना भी उपयोगी है। यह संख्या $\lambda (G)\geq 2{\sqrt {d-1}}-o(1)$ से परिबद्ध है। यह सीमा रामानुजन आलेख में सीमित है, जिसके कई क्षेत्रों में अनुप्रयोग हैं।

समरूपता और निश्चरता

मान लीजिए दो निर्देशित या अदिष्‍ट आलेख $G 1$ और $G 2$ आसन्नता आव्यूह $A 1$ और $A 2$ के साथ दिए गए हैं। $G 1$ और $G 2$ समरूपीय हैं और केवल वहाँ एक क्रमपरिवर्तन आव्यूह $P$ मौजूद है जैसे कि

PA_{1}P^{-1}=A_{2}.

।

विशेष रूप से, $A 1$ और $A 2$ समान हैं और इसलिए समान न्यूनतम बहुपद , विशेषता बहुपद, विशेषता बहुपद अभिलक्षणिक मान, निर्धारक और ट्रेस हैं। इसलिए ये आलेख़ के समरूपता अपरिवर्तनीय के रूप में काम कर सकते हैं। हालाँकि, दो आलेख़ में समान मूल्यों का एक ही समुच्चय हो सकता है लेकिन समरूपीय नहीं हो सकता है।^[9] ऐसे रैखिक प्रचालक को आइसोस्पेक्ट्रल कहा जाता है।

आव्यूह शक्तियां

यदि $A$ निर्देशित या अप्रत्यक्ष आलेख $G$ का आसन्नता आव्यूह है , तो फिर आव्यूह $A n$ (यानी, $A$ की $n$ प्रतियों का आव्यूह गुणन) की एक रोचक व्याख्या है, अवयव $(i, j)$ शीर्ष $i$ से शीर्ष $j$ तक लंबाई $n$ के चलने (निर्देशित या अप्रत्यक्ष) की संख्या देता है। यदि $n$ सबसे छोटा गैर-ऋणात्मक पूर्णांक है, जैसे कि कुछ के लिए $i$ , $j$ के लिए, $A n$ का अवयव $(i, j)$ का धनात्मक है, तो $n$ शीर्ष $i$ और शीर्ष $j$ के बीच की दूरी है। यह कैसे उपयोगी है इसका एक बड़ा उदाहरण एक अप्रत्यक्ष आलेख $G$ में त्रिभुजों की संख्या की गणना करना है, जो कि $A 3$ का 6 से विभाजित अंश है। हम प्रत्येक त्रिकोण (3! = 6 बार) की अधिक गणना के लिए क्षतिपूर्ति करने के लिए 6 से विभाजित करते हैं। आसन्नता आव्यूह का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि आलेख जुड़ा हुआ है या नहीं।

डेटा संरचना

आसन्नता आव्यूह का उपयोग आलेख़ में हेरफेर करने के लिए कंप्यूटर प्रोग्राम में आलेख़ के प्रतिनिधित्व के लिए डेटा संरचना के रूप में किया जा सकता है। इस अनुप्रयोग के लिए उपयोग की जाने वाली मुख्य वैकल्पिक डेटा संरचना, आसन्न सूची है।^[10]^[11]

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

क्योंकि आसन्नता आव्यूह में प्रत्येक प्रविष्टि के लिए केवल एक बिट की आवश्यकता होती है, इसे बहुत संक्षिप्त तरीके से प्रदर्शित किया जा सकता है, केवल |V |² / 8 बाइट्स को एक दिष्ट आलेख का प्रतिनिधित्व करने के लिए, या (एक पैक त्रिकोणीय प्रारूप का उपयोग करके और केवल आव्यूह के निचले त्रिकोणीय भाग को संग्रहीत करके) लगभग |V |² / 16 बाइट्स एक अप्रत्यक्ष आलेख का प्रतिनिधित्व करने के लिए। हालांकि थोड़ा अधिक संक्षिप्त निरूपण संभव है, यह विधि सभी का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की न्यूनतम संख्या के लिए सूचना-सैद्धांतिक निचली सीमा के करीब पहुंच जाती है। $n$ -शीर्ष रेखांकन।^[12] पाठ फ़ाइल में आलेख़ को संग्रहीत करने के लिए, प्रति बाइट कम बिट्स का उपयोग यह सुनिश्चित करने के लिए किया जा सकता है कि सभी बाइट टेक्स्ट वर्ण हैं, उदाहरण के लिए बेस 64 प्रतिनिधित्व का उपयोग करके।^[13] व्यर्थ जगह से बचने के अलावा, यह संहतता संदर्भ के स्थानीयता को प्रोत्साहित करती है। हालांकि, एक बड़े विरल आलेख के लिए, आसन्न सूचियों को कम संग्रहण स्थान की आवश्यकता होती है, क्योंकि वे किनारों का प्रतिनिधित्व करने के लिए कोई स्थान बर्बाद नहीं करते हैं जो मौजूद नहीं हैं।^[11]^[14]

निकटता आव्यूह का एक वैकल्पिक रूप (हालाँकि, इसके लिए अधिक मात्रा में स्थान की आवश्यकता होती है) आव्यूह के प्रत्येक अवयव में अंकों को किनारे की वस्तुओं (जब किनारे मौजूद हैं) या अशक्त बिंदुओं (जब कोई किनारा नहीं है) के साथ बदल देता है।^[14]आसन्नता आव्यूह के अवयवों में सीधे किनारे के वजन को स्टोर करना भी संभव है।।^[11]

स्पेस ट्रेडऑफ़ के अलावा, विभिन्न डेटा संरचनाएँ भी विभिन्न कार्यों की सुविधा प्रदान करती हैं। आसन्न सूची में दिए गए शीर्ष से सटे सभी शीर्षों को ढूँढना उतना ही सरल है जितना कि सूची को पढ़ना, और निकटवर्ती की संख्या के अनुपात में समय लगता है। आसन्नता आव्यूह के साथ, इसके बजाय एक पूरी पंक्ति को पूरे आलेख में कोने की संख्या के अनुपात में क्रमवीक्षित किया जाना चाहिए, जिसमें अधिक समय लगता है। दूसरी ओर, यह जांचना कि क्या दो दिए गए शीर्षों के बीच एक किनारा है, आसन्नता आव्यूह के साथ एक बार में निर्धारित किया जा सकता है, जबकि आसन्न सूची के साथ दो शीर्षों की न्यूनतम डिग्री के लिए आनुपातिक समय की आवश्यकता होती है।^[11]^[14]

यह भी देखें

संदर्भ

↑ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Definition 2.1, p. 7.
↑ Harary, Frank (1962), "The determinant of the adjacency matrix of a graph", SIAM Review, 4 (3): 202–210, Bibcode:1962SIAMR...4..202H, doi:10.1137/1004057, MR 0144330.
↑ Seidel, J. J. (1968). "Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3". Lin. Alg. Appl. 1 (2): 281–298. doi:10.1016/0024-3795(68)90008-6.
↑ Shum, Kenneth; Blake, Ian (2003-12-18). "विस्तारक रेखांकन और कोड". Volume 68 of DIMACS series in discrete mathematics and theoretical computer science. Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory. American Mathematical Society. p. 63. ISBN 9780821871102.
↑ Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), सोशल नेटवर्क विश्लेषण (2nd ed.), SAGE, p. 20
↑ Newman, Mark (2018), नेटवर्क (2nd ed.), Oxford University Press, p. 110
↑ Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.
↑ Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Bipartite graphs", Spectra of Graphs, Universitext, New York: Springer, pp. 6–7, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR 2882891
↑ Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN 0-387-95241-1, p.164
↑ Goodrich & Tamassia (2015), p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."
↑ ^11.0 ^11.1 ^11.2 ^11.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.1: Representations of graphs", Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7.
↑ Turán, György (1984), "On the succinct representation of graphs", Discrete Applied Mathematics, 8 (3): 289–294, doi:10.1016/0166-218X(84)90126-4, MR 0749658.
↑ McKay, Brendan, Description of graph6 and sparse6 encodings, archived from the original on 2001-04-30, retrieved 2012-02-10.
↑ ^14.0 ^14.1 ^14.2 Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363.

बाहरी संबंध

Weisstein, Eric W. "Adjacency matrix". MathWorld.
Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.
Open Data Structures - Section 12.1 - AdjacencyMatrix: Representing a Graph by a Matrix, Pat Morin
Café math : Adjacency Matrices of Graphs : Application of the adjacency matrices to the computation generating series of walks.

[1] Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Definition 2.1, p. 7.

[2] Harary, Frank (1962), "The determinant of the adjacency matrix of a graph", SIAM Review, 4 (3): 202–210, Bibcode:1962SIAMR...4..202H, doi:10.1137/1004057, MR 0144330.

[3] Seidel, J. J. (1968). "Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3". Lin. Alg. Appl. 1 (2): 281–298. doi:10.1016/0024-3795(68)90008-6.

[4] Shum, Kenneth; Blake, Ian (2003-12-18). "विस्तारक रेखांकन और कोड". Volume 68 of DIMACS series in discrete mathematics and theoretical computer science. Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory. American Mathematical Society. p. 63. ISBN 9780821871102.

[5] Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), सोशल नेटवर्क विश्लेषण (2nd ed.), SAGE, p. 20

[6] Newman, Mark (2018), नेटवर्क (2nd ed.), Oxford University Press, p. 110

[7] Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.

[8] Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Bipartite graphs", Spectra of Graphs, Universitext, New York: Springer, pp. 6–7, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR 2882891

[9] Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN 0-387-95241-1, p.164

[10] Goodrich & Tamassia (2015), p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."

[clrs-11] 11.0 ^11.1 ^11.2 ^11.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.1: Representations of graphs", Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7.

[12] Turán, György (1984), "On the succinct representation of graphs", Discrete Applied Mathematics, 8 (3): 289–294, doi:10.1016/0166-218X(84)90126-4, MR 0749658.

[13] McKay, Brendan, Description of graph6 and sparse6 encodings, archived from the original on 2001-04-30, retrieved 2012-02-10.

[gt-14] 14.0 ^14.1 ^14.2 Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 1: / Line 1: @@
 {{Short description|Square matrix used to represent a graph or network}}
-[[ग्राफ सिद्धांत]] और [[कंप्यूटर विज्ञान]] में, एक आसन्नता आव्यूह एक [[स्क्वायर मैट्रिक्स]] है जो एक परिमित [[ग्राफ (असतत गणित)]] का प्रतिनिधित्व करने के लिए उपयोग किया जाता है। [[मैट्रिक्स (गणित)]] के तत्व इंगित करते हैं कि वर्टेक्स (ग्राफ सिद्धांत) के जोड़े नेबरहुड (ग्राफ सिद्धांत) हैं या नहीं।
+[[ग्राफ सिद्धांत|आलेख सिद्धांत]] और [[कंप्यूटर विज्ञान]] में, एक '''आसन्नता आव्यूह''' एक [[स्क्वायर मैट्रिक्स|वर्ग आव्यूह]] है जो एक परिमित [[ग्राफ (असतत गणित)|आलेख]] का प्रतिनिधित्व करने के लिए उपयोग किया जाता है। [[मैट्रिक्स (गणित)|आव्यूह]] के अवयव निर्दिष्ट करते हैं कि [[वर्टेक्स|शीर्ष]] के जोड़े आलेख में [[आसन्न]] हैं या नहीं।
-परिमित [[सरल ग्राफ]] के विशेष मामले में, आसन्नता आव्यूह एक (0,1) -मैट्रिक्स है जिसके विकर्ण पर शून्य हैं। यदि ग्राफ़ ग्राफ़ सिद्धांत शब्दों की शब्दावली है# अप्रत्यक्ष (अर्थात् इसके ग्राफ़ सिद्धांत शब्दों के सभी शब्दकोष # किनारे द्विदिश हैं), आसन्नता आव्यूह [[सममित मैट्रिक्स]] है।
+परिमित [[सरल ग्राफ|सरल आलेख]] के विशेष स्थिति में, आसन्नता आव्यूह एक [[(0,1) -आव्यूह]] है जिसके विकर्ण पर शून्य हैं। यदि आलेख़ [[अप्रत्यक्ष]] है (अर्थात् इसके सभी [[किनारे]] द्विदिश हैं) तथा आसन्नता आव्यूह [[सममित मैट्रिक्स|सममित]] है। [[वर्णक्रमीय ग्राफ सिद्धांत|वर्णक्रमीय आलेख सिद्धांत]] में एक आलेख और उसके आसन्नता आव्यूह के [[eigenvalue|अभिलक्षणिक मान]] और [[आइजन्वेक्टर|अभिलक्षणिक सदिश]] के बीच संबंध का अध्ययन किया जाता है।
-[[वर्णक्रमीय ग्राफ सिद्धांत]] में एक ग्राफ और उसके आसन्नता आव्यूह के [[eigenvalue]] और [[आइजन्वेक्टर]] के बीच संबंध का अध्ययन किया जाता है।
-एक ग्राफ़ के आसन्नता आव्यूह को इसकी [[घटना मैट्रिक्स]] से अलग किया जाना चाहिए, एक अलग मैट्रिक्स प्रतिनिधित्व जिसके तत्व इंगित करते हैं कि वर्टेक्स-एज जोड़े [[घटना (ग्राफ)]]ग्राफ़) हैं या नहीं, और इसकी [[डिग्री मैट्रिक्स]], जिसमें डिग्री (ग्राफ़ सिद्धांत) के बारे में जानकारी शामिल है प्रत्येक शीर्ष।
+एक आलेख़ के आसन्नता आव्यूह को इसके [[घटना मैट्रिक्स|आपतन आव्यूह]] से अलग किया जाना चाहिए, एक अलग आव्यूह प्रतिनिधित्व जिसके अवयव निर्दिष्ट करते हैं कि शीर्ष-किनारे जोड़े [[घटना (ग्राफ)|आपतन]] हैं या नहीं, और इसका [[डिग्री मैट्रिक्स|डिग्री आव्यूह]], जिसमें प्रत्येक शीर्ष की [[डिग्री]] के बारे में जानकारी सम्मिलित है
 == परिभाषा ==
-वर्टेक्स सेट के साथ एक साधारण ग्राफ के लिए {{math|''U'' {{=}} {''u''<sub>1</sub>, …, ''u''<sub>''n''</sub>}<nowiki/>}}, आसन्नता आव्यूह एक वर्ग है {{math|''n''&thinsp;×&thinsp;''n''}} आव्यूह {{mvar|A}} जैसे कि इसका तत्व {{mvar|A<sub>ij</sub>}} एक है जब वर्टेक्स से किनारा होता है {{math|''u''<sub>i</sub>}} शीर्ष पर {{math|''u''<sub>j</sub>}}, और शून्य जब कोई किनारा न हो।<ref>{{citation| title=Algebraic Graph Theory| edition=2nd| first=Norman|last=Biggs|series=Cambridge Mathematical Library|publisher=Cambridge University Press|year=1993|at=Definition 2.1, p.&nbsp;7}}.</ref> मैट्रिक्स के विकर्ण तत्व सभी शून्य हैं, क्योंकि किनारों से एक शीर्ष से स्वयं (लूप (ग्राफ सिद्धांत)) को सरल रेखांकन में अनुमति नहीं है। बीजगणितीय चर के साथ गैर-शून्य तत्वों को बदलने के लिए यह कभी-कभी [[बीजगणितीय ग्राफ सिद्धांत]] में भी उपयोगी होता है।<ref>{{citation|last=Harary|first=Frank|author-link=Frank Harary|journal=SIAM Review|mr=0144330|pages=202–210|title=The determinant of the adjacency matrix of a graph|volume=4|issue=3|year=1962|doi=10.1137/1004057|bibcode = 1962SIAMR...4..202H}}.</ref> संबंधित मैट्रिक्स तत्व में प्रत्येक दो कोने के बीच किनारों की संख्या को संग्रहीत करके और गैर-शून्य विकर्ण तत्वों की अनुमति देकर एक ही अवधारणा को [[मल्टीग्राफ]] और लूप के साथ ग्राफ़ तक बढ़ाया जा सकता है। लूप्स को या तो एक बार (एक किनारे के रूप में) या दो बार (दो वर्टेक्स-एज घटनाओं के रूप में) गिना जा सकता है, जब तक कि एक सुसंगत सम्मेलन का पालन किया जाता है। अप्रत्यक्ष रेखांकन अक्सर दो बार गिनती के छोरों के बाद के सम्मेलन का उपयोग करते हैं, जबकि निर्देशित रेखांकन आमतौर पर पूर्व सम्मेलन का उपयोग करते हैं।
+शीर्ष समुच्चय {{math|''U'' {{=}} {''u''<sub>1</sub>, …, ''u''<sub>''n''</sub>}<nowiki/>}} के साथ एक साधारण आलेख के लिए आसन्नता आव्यूह एक वर्ग {{math|''n''&thinsp;×&thinsp;''n''}} आव्यूह {{mvar|A}}  है, जैसे कि इसका अवयव {{mvar|A<sub>ij</sub>}} एक है जब शीर्ष {{math|''u''<sub>i</sub>}} से  शीर्ष {{math|''u''<sub>j</sub>}}, तक एक किनारा होता है, और शून्य जब कोई किनारा नहीं है।<ref>{{citation| title=Algebraic Graph Theory| edition=2nd| first=Norman|last=Biggs|series=Cambridge Mathematical Library|publisher=Cambridge University Press|year=1993|at=Definition 2.1, p.&nbsp;7}}.</ref> आव्यूह के विकर्ण अवयव सभी शून्य हैं, क्योंकि क्योंकि सरल रेखांकन में एक शीर्ष से स्वयं ([[लूप]]) के किनारों की अनुमति नहीं है। यह कभी-कभी [[बीजगणितीय ग्राफ सिद्धांत|बीजगणितीय आलेख सिद्धांत]] में गैर-शून्य अवयवों को बीजगणितीय चर के साथ बदलने के लिए भी उपयोगी होता है।<ref>{{citation|last=Harary|first=Frank|author-link=Frank Harary|journal=SIAM Review|mr=0144330|pages=202–210|title=The determinant of the adjacency matrix of a graph|volume=4|issue=3|year=1962|doi=10.1137/1004057|bibcode = 1962SIAMR...4..202H}}.</ref> संबंधित आव्यूह अवयव में प्रत्येक दो कोने के बीच किनारों की संख्या को संग्रहीत करके और गैर-शून्य विकर्ण अवयवों की अनुमति देकर एक ही अवधारणा को [[मल्टीग्राफ|बहुलेख]] और लूप के साथ आलेख़ तक बढ़ाया जा सकता है। लूप्स को या तो एक बार (एक किनारे के रूप में) या दो बार (दो शीर्ष-किनारे आपतन के रूप में) गिना जा सकता है, जब तक कि एक सुसंगत सम्मेलन का पालन किया जाता है। अदिष्‍ट आलेख अक्सर दो बार गिनती के छोरों के बाद के सम्मेलन का उपयोग करते हैं, जबकि दिष्ट आलेख आमतौर पर पूर्व सम्मेलन का उपयोग करते हैं।
-=== एक द्विदलीय ग्राफ का ===
+=== एक द्विदलीय आलेख का ===
-<!-- [[Adjacency matrix of a bipartite graph]] & [[Biadjacency matrix]] redirect here -->
+एक द्विदलीय ग्राफ का आसन्नता आव्यूह {{mvar|A}}, जिसके दो भागों में {{mvar|r}} और {{mvar|s}} कोने हैं, जिसको
-आसन्नता आव्यूह {{mvar|A}} एक द्विदलीय ग्राफ का जिसके दो भाग हैं {{mvar|r}} और {{mvar|s}} शीर्षों को रूप में लिखा जा सकता है
-: <math>A = \begin{pmatrix} 0_{r,r} & B \\ B^\mathsf{T} & 0_{s,s} \end{pmatrix},</math>
-कहाँ {{mvar|B}} एक {{math|''r''&thinsp;×&thinsp;''s''}} मैट्रिक्स, और {{math|0<sub>''r'',''r''</sub>}} और {{math|0<sub>''s'',''s''</sub>}} का प्रतिनिधित्व करते हैं {{math|''r''&thinsp;×&thinsp;''r''}} और {{math|''s''&thinsp;×&thinsp;''s''}} [[शून्य मैट्रिक्स]]। इस मामले में, छोटा मैट्रिक्स {{mvar|B}} विशिष्ट रूप से ग्राफ और शेष भागों का प्रतिनिधित्व करता है {{mvar|A}} को निरर्थक के रूप में खारिज किया जा सकता है। {{mvar|B}} को कभी-कभी बायडजेंसी मैट्रिक्स कहा जाता है।
-औपचारिक रूप से, चलो {{math|''G'' {{=}} (''U'', ''V'', ''E'')}} भागों के साथ एक द्विपक्षीय ग्राफ बनें {{math|''U'' {{=}} {''u''<sub>1</sub>, ..., ''u''<sub>''r''</sub>}<nowiki/>}}, {{math|''V'' {{=}} {''v''<sub>1</sub>, ..., ''v''<sub>''s''</sub>}<nowiki/>}} और किनारों {{mvar|E}}. बायडजेंसी मैट्रिक्स है {{math|''r''&thinsp;×&thinsp;''s''}} 0–1 मैट्रिक्स {{mvar|B}} जिसमें {{math|''b''<sub>''i'',''j''</sub> {{=}} 1}} [[अगर और केवल अगर]] {{math|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>) ∈ ''E''}}.
+<math>A = \begin{pmatrix} 0_{r,r} & B \\ B^\mathsf{T} & 0_{s,s} \end{pmatrix},</math>
-अगर {{mvar|G}} एक द्विपक्षीय मल्टीग्राफ या [[भारित ग्राफ]] है, फिर तत्व {{mvar|b''<sub>i,j</sub>''}} को शीर्षों के बीच किनारों की संख्या या किनारे के भार के रूप में लिया जाता है {{math|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>)}}, क्रमश।
+के रूप में लिखा जा सकता है, जहाँ {{mvar|B}} एक {{math|''r''&thinsp;×&thinsp;''s''}} आव्यूह है, और {{math|0<sub>''r'',''r''</sub>}} और {{math|0<sub>''s'',''s''</sub>}} ,{{math|''r''&thinsp;×&thinsp;''r''}} और {{math|''s''&thinsp;×&thinsp;''s''}} [[शून्य मैट्रिक्स|शून्य आव्यूह]] का प्रतिनिधित्व करते हैं। इस स्थिति में, छोटा आव्यूह {{mvar|B}} विशिष्ट रूप से आलेख और शेष भागों का प्रतिनिधित्व करता है, और {{mvar|A}} के शेष हिस्सों को अनावश्यक के रूप में निराकृत कर दिया जाता है। {{mvar|B}} को कभी-कभी द्विदिशता आव्यूह कहा जाता है।
+औपचारिक रूप से, {{math|''G'' {{=}} (''U'', ''V'', ''E'')}} भागों {{math|''U'' {{=}} {''u''<sub>1</sub>, ..., ''u''<sub>''r''</sub>}<nowiki/>}}, {{math|''V'' {{=}} {''v''<sub>1</sub>, ..., ''v''<sub>''s''</sub>}<nowiki/>}}और किनारों {{mvar|E}} के साथके साथ एक [[द्विदलीय ग्राफ]] होने दें। द्विआसन्नता आव्यूह {{math|''r''&thinsp;×&thinsp;''s''}} 0–1 आव्यूह {{mvar|B}} है जिसमें {{math|''b''<sub>''i'',''j''</sub> {{=}} 1}} [[अगर और केवल अगर|और केवल]]  {{math|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>) ∈ ''E''}}.
+है।
+यदि {{mvar|G}} एक द्विपक्षीय [[बहुआलेख]] या [[भारित ग्राफ|भारित आलेख]] है, तो अवयव {{mvar|b''<sub>i,j</sub>''}} को शीर्षों के बीच किनारों की संख्या या किनारों के भार {{math|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>)}} के रूप में लिया जाता है।
 === विविधताएं ===
-एक {{nowrap|{{math|(''a'', ''b'', ''c'')}}}}-सहखंडज मैट्रिक्स {{mvar|A}} का एक साधारण ग्राफ है {{math|''A''<sub>''i'',''j''</sub> {{=}} ''a''}} अगर {{math|(''i'', ''j'')}} किनारा है, {{mvar|b}} यदि यह नहीं है, और {{mvar|c}} विकर्ण पर। सेडेल आसन्नता आव्यूह एक है {{math|{{nowrap|(−1, 1, 0)}}}}-सहखंडज मैट्रिक्स। यह मैट्रिक्स [[दृढ़ता से नियमित ग्राफ]] और [[दो-ग्राफ]] का अध्ययन करने में प्रयोग किया जाता है।<ref>{{cite journal |last=Seidel |first=J. J. |title=Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3 |journal=[[Linear Algebra and Its Applications|Lin. Alg. Appl.]] |volume=1 |issue=2 |pages=281–298 |year=1968 |doi=10.1016/0024-3795(68)90008-6 |doi-access=free }}</ref>
+एक {{nowrap|{{math|(''a'', ''b'', ''c'')}}}}- साधारण आलेख के सहखंडज आव्यूह {{mvar|A}} में {{math|''A''<sub>''i'',''j''</sub> {{=}} ''a''}} है ,और  {{math|(''i'', ''j'')}} एक किनारा है, {{mvar|b}} यह नहीं है, और {{mvar|c}} विकर्ण पर है। [[साइजल आसन्नता आव्यूह]] एक  {{math|{{nowrap|(−1, 1, 0)}}}}-सहखंडज आव्यूह है। यह आव्यूह [[दृढ़ता से नियमित ग्राफ|दृढ़ता से नियमित आलेख]] और [[दो-ग्राफ|दो-आलेख]] का अध्ययन करने में प्रयोग किया जाता है।<ref>{{cite journal |last=Seidel |first=J. J. |title=Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3 |journal=[[Linear Algebra and Its Applications|Lin. Alg. Appl.]] |volume=1 |issue=2 |pages=281–298 |year=1968 |doi=10.1016/0024-3795(68)90008-6 |doi-access=free }}</ref>
-[[दूरी मैट्रिक्स]] की स्थिति है {{math|(''i'', ''j'')}} शिखरों के बीच की दूरी {{mvar|v<sub>i</sub>}} और {{mvar|v<sub>j</sub>}}. दूरी शीर्षों को जोड़ने वाले सबसे छोटे पथ की लंबाई है। जब तक किनारों की लंबाई स्पष्ट रूप से प्रदान नहीं की जाती है, पथ की लंबाई इसमें किनारों की संख्या होती है। दूरी मैट्रिक्स आसन्नता आव्यूह की एक उच्च शक्ति जैसा दिखता है, लेकिन केवल यह बताने के बजाय कि दो कोने जुड़े हुए हैं या नहीं (यानी, कनेक्शन मैट्रिक्स, जिसमें [[बूलियन बीजगणित]] होता है), यह उनके बीच सटीक दूरी देता है।
+[[दूरी मैट्रिक्स|दूरी आव्यूह]] की स्थिति {{math|(''i'', ''j'')}} में शीर्ष {{mvar|v<sub>i</sub>}} और {{mvar|v<sub>j</sub>}} के बीच दूरी है। दूरी शीर्षों को जोड़ने वाले सबसे छोटे पथ की लंबाई है। जब तक किनारों की लंबाई स्पष्ट रूप से प्रदान नहीं की जाती है, तब तक पथ की लंबाई इसमें किनारों की संख्या होती है। दूरी आव्यूह आसन्नता आव्यूह की एक उच्च शक्ति जैसा दिखता है, लेकिन केवल यह बताने के बजाय कि दो कोने जुड़े हुए हैं या नहीं (यानी, संयुग्मन, जिसमें [[बूलियन बीजगणित|बूलियन मान]]  होता है), यह उनके बीच सटीक दूरी देता है।
 == उदाहरण ==
-=== अप्रत्यक्ष रेखांकन ===
+=== अदिष्‍ट आलेख ===
-यहाँ (अप्रत्यक्ष रेखांकन के लिए) परिपाटी यह है कि प्रत्येक किनारा मैट्रिक्स में उपयुक्त सेल में 1 जोड़ता है, और प्रत्येक लूप 2 जोड़ता है।<ref>{{cite conference |url=https://books.google.com/books?id=wp7XsCAm_9EC&pg=PA63 |title=विस्तारक रेखांकन और कोड|last1=Shum |first1=Kenneth |last2=Blake |first2=Ian |date=2003-12-18 |publisher=American Mathematical Society |book-title=Volume 68 of DIMACS series in discrete mathematics and theoretical computer science |pages=63 |isbn=9780821871102 |conference=Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory }}</ref> यह आसन्नता आव्यूह में संबंधित पंक्ति या स्तंभ में मानों का योग लेकर किसी शीर्ष की डिग्री को आसानी से प्राप्त करने की अनुमति देता है।
+यहाँ (अदिष्‍ट आलेख के लिए) परिपाटी यह है कि प्रत्येक किनारा आव्यूह में उपयुक्त सेल में 1 जोड़ता है, और प्रत्येक लूप 2 जोड़ता है।<ref>{{cite conference |url=https://books.google.com/books?id=wp7XsCAm_9EC&pg=PA63 |title=विस्तारक रेखांकन और कोड|last1=Shum |first1=Kenneth |last2=Blake |first2=Ian |date=2003-12-18 |publisher=American Mathematical Society |book-title=Volume 68 of DIMACS series in discrete mathematics and theoretical computer science |pages=63 |isbn=9780821871102 |conference=Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory }}</ref> यह आसन्नता आव्यूह में संबंधित पंक्ति या स्तंभ में मानों का योग लेकर किसी शीर्ष की डिग्री को आसानी से प्राप्त करने की अनुमति देता है।
 {|class="wikitable" style="text-align: center; width: 700px;"
-![[Labeled graph]]
+![[लेबल ग्राफ]]
-!Adjacency matrix
+!संलग्नता आव्यूह
 |-
 |[[Image:6n-graph2.svg|200px]]
@@ Line 42: / Line 45: @@
 & 0 & 0 & 1 & 0 & 0
 \end{pmatrix}</math>
-<br>Coordinates are 1–6.
+<br>निर्देशांक 1-6 हैं।
 |-
 |[[File:Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg|250px]]
-<br>[[Nauru graph]]
+<br>[[नाउरू ग्राफ]]
 |[[File:Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg|250px]]
-<br>Coordinates are 0–23.
+<br>निर्देशांक 0-23 हैं.
-<br>White fields are zeros, colored fields are ones.
+<br>सफेद क्षेत्र शून्य हैं, रंगीन क्षेत्र एक हैं।
 |}
-=== निर्देशित रेखांकन ===
-निर्देशित ग्राफ का आसन्नता आव्यूह असममित हो सकता है। कोई एक निर्देशित ग्राफ के आसन्नता आव्यूह को इस तरह परिभाषित कर सकता है
-# एक गैर-शून्य तत्व {{mvar|A<sub>ij</sub>}} किनारे को इंगित करता है {{mvar|i}} को {{mvar|j}} या
-# यह किनारे से इंगित करता है {{mvar|j}} को {{mvar|i}}.
-पूर्व परिभाषा आमतौर पर ग्राफ सिद्धांत और सामाजिक नेटवर्क विश्लेषण (जैसे, समाजशास्त्र, राजनीति विज्ञान, अर्थशास्त्र, मनोविज्ञान) में उपयोग की जाती है।<ref>
+=== दिष्ट आलेख ===
+दिष्ट आलेख का आसन्नता आव्यूह असममित हो सकता है। एक दिष्ट आलेख के आसन्नता आव्यूह को इस तरह परिभाषित  कर सकते हैं
+# एक गैर-शून्य अवयव {{mvar|A<sub>ij</sub>}} {{mvar|i}} से {{mvar|j}} तक किनारे को निर्दिष्ट करता है या
+# यह {{mvar|j}} से {{mvar|i}} तक के किनारे को निर्दिष्ट करता है।
+पूर्व परिभाषा आमतौर पर आलेख सिद्धांत और सामाजिक नेटवर्क विश्लेषण (जैसे, समाजशास्त्र, राजनीति विज्ञान, अर्थशास्त्र, मनोविज्ञान) में उपयोग की जाती है।<ref>
 {{citation
-  | title=Analyzing Social Networks
+  | title=सोशल नेटवर्क विश्लेषण
   | edition=2nd
   | first1=Steve   | last1=Borgatti
@@ Line 67: / Line 80: @@
   | year=2018
   | at=p.&nbsp;20
-}}</ref> उत्तरार्द्ध अन्य अनुप्रयुक्त विज्ञानों (जैसे, गतिशील प्रणाली, भौतिकी, नेटवर्क विज्ञान) में अधिक सामान्य है {{mvar|A}} का उपयोग कभी-कभी रेखांकन पर रैखिक गतिकी का वर्णन करने के लिए किया जाता है।<ref>
+}}</ref> उत्तरार्द्ध अन्य अनुप्रयुक्त विज्ञानों (जैसे, गतिशील प्रणाली, भौतिकी, नेटवर्क विज्ञान) में अधिक सामान्य है , जहां {{mvar|A}} का उपयोग कभी-कभी आलेख पर रैखिक गतिकी का वर्णन करने के लिए किया जाता है।<ref>
 {{citation
-  | title=Networks
+  | title=नेटवर्क
   | edition=2nd
   | first=Mark | last=Newman
@@ Line 76: / Line 89: @@
   | at=p.&nbsp;110
 }}</ref>
-पहली परिभाषा का उपयोग करते हुए, निर्देशित ग्राफ़ # इंडिग्री और आउटडिग्री | एक वर्टेक्स की इन-डिग्री की गणना संबंधित कॉलम की प्रविष्टियों और संबंधित पंक्ति की प्रविष्टियों को योग करके वर्टेक्स की आउट-डिग्री द्वारा की जा सकती है। दूसरी परिभाषा का उपयोग करते समय, एक वर्टेक्स की इन-डिग्री संबंधित पंक्ति योग द्वारा दी जाती है और आउट-डिग्री संबंधित कॉलम योग द्वारा दी जाती है।
+पहली परिभाषा का उपयोग करते हुए, एक शीर्ष की [[अंतःकोटि]] की गणना संबंधित स्तम्भ की प्रविष्टियों और शीर्ष की बाह्‍य कोटि की गणना संबंधित पंक्ति की प्रविष्टियों को जोड़कर की जा सकती है। दूसरी परिभाषा का उपयोग करते समय, एक शीर्ष की अंतःकोटि संबंधित पंक्ति योग द्वारा दी जाती है और बाह्‍य कोटि संबंधित स्तम्भ योग द्वारा दी जाती है।
 {| class="wikitable" style="text-align: center; width: 700px;"
-! Labeled graph
+! लेबल ग्राफ
-! Adjacency matrix
+! संलग्नता आव्यूह
 |-
 | [[File:Symmetric group 4; Cayley graph 4,9; numbers.svg|250px]]
@@ Line 90: / Line 104: @@
-=== तुच्छ रेखांकन ===
-एक पूर्ण ग्राफ के आसन्नता आव्यूह में विकर्ण के अलावा सभी शामिल हैं, जहां केवल शून्य हैं। [[खाली ग्राफ]] का आसन्नता आव्यूह एक शून्य मैट्रिक्स है।
+=== तुच्छालेख ===
+एक पूर्ण आलेख के आसन्नता आव्यूह में विकर्ण के अलावा सभी सम्मिलित हैं, जहां केवल शून्य हैं। [[खाली ग्राफ|खाली आलेख]] का आसन्नता आव्यूह एक [[शून्य आव्यूह]] है।
 == गुण ==
-=== स्पेक्ट्रम ===
+=== वर्णक्रम ===
-एक अप्रत्यक्ष सरल ग्राफ का आसन्नता आव्यूह सममित मैट्रिक्स है, और इसलिए [[वास्तविक संख्या]] eigenvalues और एक ऑर्थोगोनल eigenvector आधार का एक पूरा सेट है। एक ग्राफ के eigenvalues का सेट ग्राफ का स्पेक्ट्रम है।<ref>{{harvtxt|Biggs|1993}}, Chapter 2 ("The spectrum of a graph"), pp.&nbsp;7–13.</ref> द्वारा आइगेनवैल्यूज़ को निरूपित करना आम है <math>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n.</math>
+एक [[अप्रत्यक्ष]] सरल आलेख का आसन्नता आव्यूह सममित आव्यूह है, और इसलिए [[वास्तविक संख्या]] अभिलक्षणिक मान और एक लाम्बिक [[अभिलक्षणिक सदिश]] आधार का एक पूरा समुच्चय है। एक आलेख के अभिलक्षणिक मान का समुच्चय आलेख का वर्णक्रम है।<ref>{{harvtxt|Biggs|1993}}, Chapter 2 ("The spectrum of a graph"), pp.&nbsp;7–13.</ref> अभिलक्षणिक मान को
-सबसे बड़ा ईगेनवैल्यू <math>\lambda_1</math> अधिकतम डिग्री से ऊपर घिरा हुआ है। इसे पेरोन-फ्रोबेनियस प्रमेय के परिणाम के रूप में देखा जा सकता है, लेकिन इसे आसानी से सिद्ध किया जा सकता है। होने देना {{mvar|v}} से संबंधित एक ईजेनवेक्टर हो <math>\lambda_1</math> और {{mvar|x}} जिस घटक में {{mvar|v}} का अधिकतम निरपेक्ष मान है। सामान्यता के नुकसान के बिना मान लें {{mvar|v<sub>x</sub>}} सकारात्मक है क्योंकि अन्यथा आप केवल ईजेनवेक्टर लेते हैं <math>-v</math>, से भी जुड़ा हुआ है <math>\lambda_1</math>. तब
+<math>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n</math>
+निरूपित करना सामान्य है। सबसे बड़ा अभिलक्षणिक मान <math>\lambda_1</math> ऊपर अधिकतम डिग्री से घिरा है। इसे [[पेरोन-फ्रोबेनियस प्रमेय]] के परिणाम के रूप में देखा जा सकता है, लेकिन इसे आसानी से सिद्ध किया जा सकता है। मान लो {{mvar|v}} <math>\lambda_1</math> और {{mvar|x}} से जुड़ा एक अभिलक्षणिक सदिश है जिसमे {{mvar|v}} का अधिकतम निरपेक्ष मान है। व्यापकता के नुकसान के बिना मान लें कि {{mvar|v<sub>x</sub>}} धनात्मक है क्योंकि अन्यथा आप केवल अभिलक्षणिक सदिश <math>-v</math> लेते हैं ,जो  <math>\lambda_1</math>से भी जुड़ा है। तब
 : <math>\lambda_1 v_x = (Av)_x = \sum_{y=1}^n A_{x,y}v_y \leq \sum_{y=1}^n A_{x,y} v_x = v_x \deg(x).</math>
-के लिए {{mvar|d}}-नियमित रेखांकन, {{mvar|d}} का प्रथम eigenvalue है {{mvar|A}} वेक्टर के लिए {{math|{{nowrap|''v'' {{=}} (1, …, 1)}}}} (यह जांचना आसान है कि यह एक ईजेनवेल्यू है और उपरोक्त सीमा के कारण यह अधिकतम है)। इस eigenvalue की बहुलता के जुड़े घटकों की संख्या है {{mvar|G}}, विशेष रूप से <math>\lambda_1>\lambda_2</math> जुड़े हुए रेखांकन के लिए। यह दिखाया जा सकता है कि प्रत्येक eigenvalue के लिए <math>\lambda_i</math>, इसका उल्टा <math>-\lambda_i = \lambda_{n+1-i}</math> का आइगेनवैल्यू भी है {{mvar|A}} अगर {{mvar|G}} एक द्विपक्षीय ग्राफ है।<ref>{{citation|last1=Brouwer|first1=Andries E.|last2=Haemers|first2=Willem H.|contribution=1.3.6 Bipartite graphs|contribution-url=https://books.google.com/books?id=F98THwYgrXYC&pg=PA6|doi=10.1007/978-1-4614-1939-6|isbn=978-1-4614-1938-9|location=New York|mr=2882891|pages=6–7|publisher=Springer|series=Universitext|title=Spectra of Graphs|year=2012}}</ref> विशेष रूप से -{{mvar|d}} किसी का आइगेन मान है {{mvar|d}}-नियमित द्विपक्षीय ग्राफ।
+{{mvar|d}}-नियमित आलेख के लिए, {{mvar|d}}  सदिश {{math|{{nowrap|''v'' {{=}} (1, …, 1)}}}}  के लिए {{mvar|A}} का पहला अभिलक्षणिक मान है (यह जांचना आसान है कि यह एक अभिलक्षणिक मान है और उपरोक्त सीमा के कारण यह अधिकतम है)। इस अभिलक्षणिक मान की बहुलता {{mvar|G}} के जुड़े घटकों की संख्या है , विशेष रूप से <math>\lambda_1>\lambda_2</math> जुड़े हुए आलेख के लिए। यह दिखाया जा सकता है कि प्रत्येक अभिलक्षणिक मान <math>\lambda_i</math> के लिए, इसका विपरीत <math>-\lambda_i = \lambda_{n+1-i}</math> भी {{mvar|A}} का अभिलक्षणिक मान है यदि {{mvar|G}} एक [[द्विपक्षीय आलेख]] है।<ref>{{citation|last1=Brouwer|first1=Andries E.|last2=Haemers|first2=Willem H.|contribution=1.3.6 Bipartite graphs|contribution-url=https://books.google.com/books?id=F98THwYgrXYC&pg=PA6|doi=10.1007/978-1-4614-1939-6|isbn=978-1-4614-1938-9|location=New York|mr=2882891|pages=6–7|publisher=Springer|series=Universitext|title=Spectra of Graphs|year=2012}}</ref> विशेष रूप से -{{mvar|d}} किसी भी {{mvar|d}} -नियमित द्विपक्षीय आलेख का अभिलक्षणिक मान है।
+अंतर <math>\lambda_1 - \lambda_2</math> को [[वर्णक्रमीय अंतर|वर्णक्रमीय अंतराल]] कहा जाता है और यह {{mvar|G}} के [[विस्तारक ग्राफ|विस्तारक]] से संबंधित है। <math>A</math> की [[वर्णक्रमीय त्रिज्या]] को <math>\lambda(G) = \max_{\left|\lambda_i\right| < d} |\lambda_i|</math> से प्रदर्शित करना भी उपयोगी है। यह संख्या <math>\lambda(G) \geq 2\sqrt{d-1} - o(1)</math>से परिबद्ध है। यह सीमा रामानुजन आलेख में सीमित है, जिसके कई क्षेत्रों में अनुप्रयोग हैं।
-के अंतर <math>\lambda_1 - \lambda_2</math> [[वर्णक्रमीय अंतर]] कहा जाता है और यह के [[विस्तारक ग्राफ]] से संबंधित है {{mvar|G}}. की [[वर्णक्रमीय त्रिज्या]] का परिचय देना भी उपयोगी है <math>A</math> द्वारा चिह्नित <math>\lambda(G) = \max_{\left|\lambda_i\right| < d} |\lambda_i|</math>. यह संख्या से घिरा हुआ है <math>\lambda(G) \geq 2\sqrt{d-1} - o(1)</math>. यह सीमा रामानुजन रेखांकन में तंग है, जिसके कई क्षेत्रों में अनुप्रयोग हैं।
+=== समरूपता और निश्चरता ===
+मान लीजिए दो निर्देशित या अदिष्‍ट आलेख {{math|''G''<sub>1</sub>}} और {{math|''G''<sub>2</sub>}} आसन्नता आव्यूह  {{math|''A''<sub>1</sub>}} और {{math|''A''<sub>2</sub>}}  के साथ दिए गए हैं। {{math|''G''<sub>1</sub>}} और {{math|''G''<sub>2</sub>}} [[ ग्राफ समरूपता |समरूपीय]] हैं और केवल वहाँ एक [[क्रमपरिवर्तन मैट्रिक्स|क्रमपरिवर्तन आव्यूह]] {{mvar|P}} मौजूद है जैसे कि
+: <math>P A_1 P^{-1} = A_2.</math>।
+विशेष रूप से, {{math|''A''<sub>1</sub>}} और {{math|''A''<sub>2</sub>}} [[समान (रैखिक बीजगणित)|समान]] हैं और इसलिए समान [[न्यूनतम बहुपद (रैखिक बीजगणित)|न्यूनतम बहुपद]] , [[विशेषता बहुपद]], [[विशेषता बहुपद]] [[अभिलक्षणिक मान]], [[निर्धारक]] और [[ट्रेस (मैट्रिक्स)|ट्रेस]]  हैं। इसलिए ये आलेख़ के समरूपता अपरिवर्तनीय के रूप में काम कर सकते हैं। हालाँकि, दो आलेख़ में समान मूल्यों का एक ही समुच्चय हो सकता है लेकिन समरूपीय नहीं हो सकता है।<ref>[[Chris Godsil|Godsil, Chris]]; [[Gordon Royle|Royle, Gordon]] ''Algebraic Graph Theory'', Springer (2001), {{ISBN|0-387-95241-1}}, p.164</ref> ऐसे [[ रैखिक ऑपरेटर | रैखिक प्रचालक]] को [[आइसोस्पेक्ट्रल]] कहा जाता है।
-=== समरूपता और अपरिवर्तनीय ===
+=== आव्यूह शक्तियां ===
-मान लीजिए दो निर्देशित या अप्रत्यक्ष रेखांकन {{math|''G''<sub>1</sub>}} और {{math|''G''<sub>2</sub>}} निकटता मेट्रिसेस के साथ {{math|''A''<sub>1</sub>}} और {{math|''A''<sub>2</sub>}} दिया जाता है। {{math|''G''<sub>1</sub>}} और {{math|''G''<sub>2</sub>}} [[ ग्राफ समरूपता ]] हैं अगर और केवल तभी [[क्रमपरिवर्तन मैट्रिक्स]] मौजूद है {{mvar|P}} ऐसा है कि
+यदि {{mvar|A}} निर्देशित या अप्रत्यक्ष आलेख {{mvar|G}} का आसन्नता आव्यूह है , तो फिर आव्यूह {{math|''A''<sup>''n''</sup>}} (यानी, {{mvar|A}} की {{mvar|n}} प्रतियों का [[मैट्रिक्स गुणन|आव्यूह गुणन]]) की एक रोचक व्याख्या है, अवयव {{math|{{nowrap|(''i'', ''j'')}}}} शीर्ष {{mvar|i}} से शीर्ष {{mvar|j}} तक लंबाई {{mvar|n}} के चलने (निर्देशित या अप्रत्यक्ष) की संख्या देता है। यदि {{mvar|n}} सबसे छोटा गैर-ऋणात्मक पूर्णांक है, जैसे कि कुछ के लिए {{mvar|i}}, {{mvar|j}} के लिए, {{math|''A''<sup>''n''</sup>}} का अवयव {{math|{{nowrap|(''i'', ''j'')}}}} का धनात्मक है, तो {{mvar|n}} शीर्ष {{mvar|i}} और शीर्ष {{mvar|j}} के बीच की दूरी है। यह कैसे उपयोगी है इसका एक बड़ा उदाहरण एक अप्रत्यक्ष आलेख {{mvar|G}} में त्रिभुजों की संख्या की गणना करना है, जो  कि {{math|''A''<sup>3</sup>}} का 6 से [[विभाजित]] अंश है। हम प्रत्येक त्रिकोण (3! = 6 बार) की अधिक गणना के लिए क्षतिपूर्ति करने के लिए 6 से विभाजित करते हैं। आसन्नता आव्यूह का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि आलेख [[कनेक्टिविटी (ग्राफ सिद्धांत)|जुड़ा]] हुआ है या नहीं।
-: <math>P A_1 P^{-1} = A_2.</math>
-विशेष रूप से, {{math|''A''<sub>1</sub>}} और {{math|''A''<sub>2</sub>}} [[समान (रैखिक बीजगणित)]] हैं और इसलिए एक ही [[न्यूनतम बहुपद (रैखिक बीजगणित)]], [[विशेषता बहुपद]], आइगेनवैल्यू और ईजेनवेक्टर, निर्धारक और [[ट्रेस (मैट्रिक्स)]] हैं। इसलिए ये ग्राफ़ के आइसोमोर्फिज़्म इनवेरिएंट के रूप में काम कर सकते हैं। हालाँकि, दो ग्राफ़ में समान मूल्यों का एक ही सेट हो सकता है लेकिन आइसोमोर्फिक नहीं हो सकता है।<ref>[[Chris Godsil|Godsil, Chris]]; [[Gordon Royle|Royle, Gordon]] ''Algebraic Graph Theory'', Springer (2001), {{ISBN|0-387-95241-1}}, p.164</ref> ऐसे [[ रैखिक ऑपरेटर ]]्स को [[आइसोस्पेक्ट्रल]] कहा जाता है।
-=== मैट्रिक्स शक्तियां ===
+== डेटा संरचना ==
-अगर {{mvar|A}} निर्देशित या अप्रत्यक्ष ग्राफ का आसन्नता आव्यूह है {{mvar|G}}, फिर मैट्रिक्स {{math|''A''<sup>''n''</sup>}} (यानी, का [[मैट्रिक्स गुणन]] {{mvar|n}} की प्रतियां {{mvar|A}}) की एक दिलचस्प व्याख्या है: तत्व {{math|{{nowrap|(''i'', ''j'')}}}} लंबाई की (निर्देशित या अप्रत्यक्ष) [[पथ (ग्राफ सिद्धांत)]] की संख्या देता है {{mvar|n}} शिखर से {{mvar|i}} शीर्ष पर {{mvar|j}}. अगर {{mvar|n}} सबसे छोटा अऋणात्मक पूर्णांक है, जैसे कि कुछ के लिए {{mvar|i}}, {{mvar|j}}, तत्व {{math|{{nowrap|(''i'', ''j'')}}}} का {{math|''A''<sup>''n''</sup>}} सकारात्मक है, तो {{mvar|n}} शीर्ष के बीच की दूरी है {{mvar|i}} और वर्टेक्स {{mvar|j}}. यह कैसे उपयोगी है इसका एक बड़ा उदाहरण एक अप्रत्यक्ष ग्राफ में त्रिभुजों की संख्या की गणना करना है {{mvar|G}}, जो बिल्कुल [[ट्रेस (रैखिक बीजगणित)]] है {{math|''A''<sup>3</sup>}} को 6 से विभाजित किया जाता है। हम प्रत्येक त्रिकोण (3! = 6 बार) की अधिक गणना के लिए क्षतिपूर्ति करने के लिए 6 से विभाजित करते हैं। आसन्नता आव्यूह का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि ग्राफ [[कनेक्टिविटी (ग्राफ सिद्धांत)]] है या नहीं।
+आसन्नता आव्यूह का उपयोग आलेख़ में हेरफेर करने के लिए कंप्यूटर प्रोग्राम में [[ग्राफ़ (सार डेटा प्रकार)|आलेख़]] के प्रतिनिधित्व के लिए [[डेटा संरचना]] के रूप में किया जा सकता है। इस अनुप्रयोग के लिए उपयोग की जाने वाली मुख्य वैकल्पिक डेटा संरचना, [[आसन्न सूची]] है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."</ref><ref name="clrs">{{citation |author-link=Thomas H. Cormen |first1=Thomas H. |last1=Cormen |author-link2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |author-link3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |author-link4=Clifford Stein |first4=Clifford |last4=Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |chapter=Section 22.1: Representations of graphs |pages=527–531 }}.</ref>
-== [[डेटा संरचना]]एं ==
+आसन्नता आव्यूह का प्रतिनिधित्व करने के लिए आवश्यक स्थान और उन पर संचालन करने के लिए आवश्यक समय अंतर्निहित आव्यूह के लिए चुने गए [[मैट्रिक्स प्रतिनिधित्व|आव्यूह प्रतिनिधित्व]] पर निर्भर है। [[विरल आव्यूह]] अभ्यावेदन केवल गैर-शून्य आव्यूह प्रविष्टियों को संग्रहीत करते हैं और शून्य प्रविष्टियों का प्रतिनिधित्व करते हैं। उदाहरण के लिए, [[विरल ग्राफ|विरल आलेख]] के आसन्नता आव्यूह में कई शून्य प्रविष्टियों को संग्रहीत करने से अतिरिक्त समष्टि के बिना विरल आलेख़ का प्रतिनिधित्व करने के लिए उपयोग किया जा सकता है। निम्नलिखित खंड में आसन्नता आव्यूह को एक [[सरणी डेटा संरचना]] द्वारा दर्शाया गया माना जाता है ताकि आव्यूह में शून्य और गैर-शून्य प्रविष्टियां सीधे भंडारण में प्रदर्शित हों।
-आसन्नता आव्यूह का उपयोग ग्राफ़ में हेरफेर करने के लिए कंप्यूटर प्रोग्राम में [[ग्राफ़ (सार डेटा प्रकार)]] के लिए डेटा संरचना के रूप में किया जा सकता है। इस एप्लिकेशन के लिए उपयोग की जाने वाली मुख्य वैकल्पिक डेटा संरचना, आसन्न सूची है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."</ref><ref name="clrs">{{citation |author-link=Thomas H. Cormen |first1=Thomas H. |last1=Cormen |author-link2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |author-link3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |author-link4=Clifford Stein |first4=Clifford |last4=Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |chapter=Section 22.1: Representations of graphs |pages=527–531 }}.</ref>
-आसन्नता आव्यूह का प्रतिनिधित्व करने के लिए आवश्यक स्थान और उन पर संचालन करने के लिए आवश्यक समय अंतर्निहित मैट्रिक्स के लिए चुने गए [[मैट्रिक्स प्रतिनिधित्व]] पर निर्भर है। विरल मैट्रिक्स अभ्यावेदन केवल गैर-शून्य मैट्रिक्स प्रविष्टियों को संग्रहीत करते हैं और शून्य प्रविष्टियों का प्रतिनिधित्व करते हैं। उदाहरण के लिए, [[विरल ग्राफ]]़ के आसन्नता आव्यूह में कई शून्य प्रविष्टियों को संग्रहीत करने से अंतरिक्ष ओवरहेड के बिना विरल ग्राफ़ का प्रतिनिधित्व करने के लिए उपयोग किया जा सकता है। निम्नलिखित खंड में आसन्नता आव्यूह को एक [[सरणी डेटा संरचना]] द्वारा दर्शाया गया माना जाता है ताकि मैट्रिक्स में शून्य और गैर-शून्य प्रविष्टियां सीधे भंडारण में प्रदर्शित हों।
-क्योंकि आसन्नता आव्यूह में प्रत्येक प्रविष्टि के लिए केवल एक बिट की आवश्यकता होती है, इसे बहुत कॉम्पैक्ट तरीके से प्रदर्शित किया जा सकता है, केवल |V |<sup>2</sup>&hairsp;/&hairsp;8 बाइट्स एक निर्देशित ग्राफ का प्रतिनिधित्व करने के लिए, या (एक पैक त्रिकोणीय प्रारूप का उपयोग करके और केवल मैट्रिक्स के निचले त्रिकोणीय भाग को संग्रहीत करके) लगभग |V |<sup>2</sup>&hairsp;/&hairsp;16 बाइट्स एक अप्रत्यक्ष ग्राफ का प्रतिनिधित्व करने के लिए। हालांकि थोड़ा अधिक संक्षिप्त निरूपण संभव है, यह विधि सभी का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की न्यूनतम संख्या के लिए सूचना-सैद्धांतिक निचली सीमा के करीब पहुंच जाती है। {{mvar|n}}-वर्टेक्स रेखांकन।<ref>{{citation
+क्योंकि आसन्नता आव्यूह में प्रत्येक प्रविष्टि के लिए केवल एक बिट की आवश्यकता होती है, इसे बहुत संक्षिप्त तरीके से प्रदर्शित किया जा सकता है, केवल |V |<sup>2</sup>&hairsp;/&hairsp;8 बाइट्स को एक दिष्ट आलेख का प्रतिनिधित्व करने के लिए, या (एक पैक त्रिकोणीय प्रारूप का उपयोग करके और केवल आव्यूह के निचले त्रिकोणीय भाग को संग्रहीत करके) लगभग |V |<sup>2</sup>&hairsp;/&hairsp;16 बाइट्स एक अप्रत्यक्ष आलेख का प्रतिनिधित्व करने के लिए। हालांकि थोड़ा अधिक संक्षिप्त निरूपण संभव है, यह विधि सभी का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की न्यूनतम संख्या के लिए सूचना-सैद्धांतिक निचली सीमा के करीब पहुंच जाती है। {{mvar|n}}-शीर्ष रेखांकन।<ref>{{citation
   | last = Turán | first = György
   | doi = 10.1016/0166-218X(84)90126-4
@@ Line 127: / Line 155: @@
   | year = 1984
 | doi-access = free
-  }}.</ref> [[पाठ फ़ाइल]]ों में ग्राफ़ को संग्रहीत करने के लिए, प्रति बाइट कम बिट्स का उपयोग यह सुनिश्चित करने के लिए किया जा सकता है कि सभी बाइट टेक्स्ट वर्ण हैं, उदाहरण के लिए [[बेस 64]] प्रतिनिधित्व का उपयोग करके।<ref>{{citation|first1=Brendan|last1=McKay|author-link=Brendan McKay (mathematician)|title=Description of graph6 and sparse6 encodings|url=http://cs.anu.edu.au/~bdm/data/formats.txt|access-date=2012-02-10|archive-date=2001-04-30|archive-url=https://web.archive.org/web/20010430081526/http://cs.anu.edu.au/~bdm/data/formats.txt|url-status=live}}.</ref> व्यर्थ जगह से बचने के अलावा, यह कॉम्पैक्टनेस संदर्भ के स्थानीयता को प्रोत्साहित करती है।
+  }}.</ref> [[पाठ फ़ाइल]] में आलेख़ को संग्रहीत करने के लिए, प्रति बाइट कम बिट्स का उपयोग यह सुनिश्चित करने के लिए किया जा सकता है कि सभी बाइट टेक्स्ट वर्ण हैं, उदाहरण के लिए [[बेस 64]] प्रतिनिधित्व का उपयोग करके।<ref>{{citation|first1=Brendan|last1=McKay|author-link=Brendan McKay (mathematician)|title=Description of graph6 and sparse6 encodings|url=http://cs.anu.edu.au/~bdm/data/formats.txt|access-date=2012-02-10|archive-date=2001-04-30|archive-url=https://web.archive.org/web/20010430081526/http://cs.anu.edu.au/~bdm/data/formats.txt|url-status=live}}.</ref> व्यर्थ जगह से बचने के अलावा, यह संहतता [[संदर्भ के स्थानीयता]] को प्रोत्साहित करती है। हालांकि, एक बड़े [[विरल आलेख]] के लिए, आसन्न सूचियों को कम संग्रहण स्थान की आवश्यकता होती है, क्योंकि वे किनारों का प्रतिनिधित्व करने के लिए कोई स्थान बर्बाद नहीं करते हैं जो मौजूद नहीं हैं।<ref name="clrs"/><ref name="gt"/>
-हालांकि, एक बड़े विरल ग्राफ के लिए, आसन्न सूचियों को कम संग्रहण स्थान की आवश्यकता होती है, क्योंकि वे किनारों का प्रतिनिधित्व करने के लिए कोई स्थान बर्बाद नहीं करते हैं जो मौजूद नहीं हैं।<ref name="clrs"/><ref name="gt"/>
-निकटता मैट्रिक्स का एक वैकल्पिक रूप (जो, हालांकि, बड़ी मात्रा में स्थान की आवश्यकता होती है) मैट्रिक्स के प्रत्येक तत्व में अंकों को किनारे की वस्तुओं (जब किनारे मौजूद हैं) या अशक्त बिंदुओं (जब कोई किनारा नहीं है) के साथ बदल देता है।<ref name="gt"/>आसन्नता आव्यूह के तत्वों में सीधे भारित ग्राफ को स्टोर करना भी संभव है।<ref name="clrs"/>
-स्पेस ट्रेडऑफ़ के अलावा, विभिन्न डेटा संरचनाएँ भी विभिन्न कार्यों की सुविधा प्रदान करती हैं। आसन्न सूची में दिए गए शीर्ष से सटे सभी शीर्षों को ढूँढना उतना ही सरल है जितना कि सूची को पढ़ना, और पड़ोसियों की संख्या के अनुपात में समय लगता है। आसन्नता आव्यूह के साथ, इसके बजाय एक पूरी पंक्ति को स्कैन किया जाना चाहिए, जिसमें अधिक समय लगता है, पूरे ग्राफ में कोने की संख्या के अनुपात में। दूसरी ओर, यह जांचना कि क्या दो दिए गए शीर्षों के बीच एक बढ़त है, एक आसन्नता आव्यूह के साथ एक बार में निर्धारित किया जा सकता है, जबकि आसन्न सूची के साथ दो शीर्षों की न्यूनतम डिग्री के लिए आनुपातिक समय की आवश्यकता होती है।<ref name="clrs"/><ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|page=363}}.</ref>
+निकटता आव्यूह का एक वैकल्पिक रूप (हालाँकि, इसके लिए अधिक मात्रा में स्थान की आवश्यकता होती है) आव्यूह के प्रत्येक अवयव में अंकों को किनारे की वस्तुओं (जब किनारे मौजूद हैं) या अशक्त बिंदुओं (जब कोई किनारा नहीं है) के साथ बदल देता है।<ref name="gt"/>आसन्नता आव्यूह के अवयवों में सीधे [[किनारे के वजन]] को स्टोर करना भी संभव है।।<ref name="clrs"/>
+स्पेस ट्रेडऑफ़ के अलावा, विभिन्न डेटा संरचनाएँ भी विभिन्न कार्यों की सुविधा प्रदान करती हैं। आसन्न सूची में दिए गए शीर्ष से सटे सभी शीर्षों को ढूँढना उतना ही सरल है जितना कि सूची को पढ़ना, और निकटवर्ती की संख्या के अनुपात में समय लगता है। आसन्नता आव्यूह के साथ, इसके बजाय एक पूरी पंक्ति को पूरे आलेख में कोने की संख्या के अनुपात में क्रमवीक्षित किया जाना चाहिए, जिसमें अधिक समय लगता है। दूसरी ओर, यह जांचना कि क्या दो दिए गए शीर्षों के बीच एक किनारा है, आसन्नता आव्यूह के साथ एक बार में निर्धारित किया जा सकता है, जबकि आसन्न सूची के साथ दो शीर्षों की न्यूनतम डिग्री के लिए आनुपातिक समय की आवश्यकता होती है।<ref name="clrs"/><ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|page=363}}.</ref>
 == यह भी देखें ==
-* [[लाप्लासियन मैट्रिक्स]]
+* [[लाप्लासियन मैट्रिक्स|लाप्लासियन आव्यूह]]
-* [[स्व-समानता मैट्रिक्स]]
+* [[स्व-समानता मैट्रिक्स|स्व-समानता आव्यूह]]
 ==संदर्भ==
@@ Line 150: / Line 175: @@
 * [https://web.archive.org/web/20190325054550/http://www.cafemath.fr/mathblog/article.php?page=GoodWillHunting.php Café math : Adjacency Matrices of Graphs] : Application of the adjacency matrices to the computation generating series of walks.
-{{Graph representations}}
+[[Category:Collapse templates]]
-{{Matrix classes}}
+[[Category:Commons category link is locally defined]]
-{{Authority control}}
-[[Category: बीजगणितीय ग्राफ सिद्धांत]] [[Category: मैट्रिसेस]] [[Category: ग्राफ डेटा संरचनाएं]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 01/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with empty portal template]]
+[[Category:Pages with script errors]]
+[[Category:Portal-inline template with redlinked portals]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]

Anonymous

Search

आसन्नता आव्यूह: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:26, 16 October 2023

Contents

परिभाषा

एक द्विदलीय आलेख का

विविधताएं

उदाहरण

अदिष्‍ट आलेख

दिष्ट आलेख

तुच्छालेख

गुण

वर्णक्रम

समरूपता और निश्चरता

आव्यूह शक्तियां

डेटा संरचना

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

आसन्नता आव्यूह: Difference between revisions

Latest revision as of 16:26, 16 October 2023

परिभाषा

एक द्विदलीय आलेख का

विविधताएं

उदाहरण

अदिष्‍ट आलेख

दिष्ट आलेख

तुच्छालेख

गुण

वर्णक्रम

समरूपता और निश्चरता

आव्यूह शक्तियां

डेटा संरचना

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories