आसन्नता आव्यूह: 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 33: / Line 33: @@
 {|class="wikitable" style="text-align: center; width: 700px;"
-![[Labeled graph]]
+![[लेबल ग्राफ]]
-!Adjacency matrix
+!संलग्नता आव्यूह
 |-
 |[[Image:6n-graph2.svg|200px]]
@@ Line 45: / 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>सफेद क्षेत्र शून्य हैं, रंगीन क्षेत्र एक हैं।
 |}
@@ Line 62: / Line 72: @@
 पूर्व परिभाषा आमतौर पर आलेख सिद्धांत और सामाजिक नेटवर्क विश्लेषण (जैसे, समाजशास्त्र, राजनीति विज्ञान, अर्थशास्त्र, मनोविज्ञान) में उपयोग की जाती है।<ref>
 {{citation
-  | title=Analyzing Social Networks
+  | title=सोशल नेटवर्क विश्लेषण
   | edition=2nd
   | first1=Steve   | last1=Borgatti
@@ Line 72: / Line 82: @@
 }}</ref> उत्तरार्द्ध अन्य अनुप्रयुक्त विज्ञानों (जैसे, गतिशील प्रणाली, भौतिकी, नेटवर्क विज्ञान) में अधिक सामान्य है , जहां {{mvar|A}} का उपयोग कभी-कभी आलेख पर रैखिक गतिकी का वर्णन करने के लिए किया जाता है।<ref>
 {{citation
-  | title=Networks
+  | title=नेटवर्क
   | edition=2nd
   | first=Mark | last=Newman
@@ Line 83: / Line 93: @@
 {| class="wikitable" style="text-align: center; width: 700px;"
-! Labeled graph
+! लेबल ग्राफ
-! Adjacency matrix
+! संलग्नता आव्यूह
 |-
 | [[File:Symmetric group 4; Cayley graph 4,9; numbers.svg|250px]]
@@ Line 92: / Line 102: @@
 <br>As the graph is directed, the matrix is not necessarily [[Symmetric matrix|symmetric]].
 |}
@@ Line 119: / Line 139: @@
 यदि {{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 से विभाजित करते हैं। आसन्नता आव्यूह का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि आलेख [[कनेक्टिविटी (ग्राफ सिद्धांत)|जुड़ा]] हुआ है या नहीं।
-== [[डेटा संरचना]]एं ==
+== डेटा संरचना ==
-आसन्नता आव्यूह का उपयोग आलेख़ में हेरफेर करने के लिए कंप्यूटर प्रोग्राम में [[ग्राफ़ (सार डेटा प्रकार)|आलेख़ (सार डेटा प्रकार)]] के लिए डेटा संरचना के रूप में किया जा सकता है। इस एप्लिकेशन के लिए उपयोग की जाने वाली मुख्य वैकल्पिक डेटा संरचना, आसन्न सूची है।<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 134: / 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 157: / 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