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

Revision as of 09:02, 11 May 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] यह आसन्नता आव्यूह में संबंधित पंक्ति या स्तंभ में मानों का योग लेकर किसी शीर्ष की डिग्री को आसानी से प्राप्त करने की अनुमति देता है।

Labeled graph	Adjacency matrix
	${\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}}$ Coordinates are 1–6.
Nauru graph	Coordinates are 0–23. White fields are zeros, colored fields are ones.

निर्देशित रेखांकन

निर्देशित ग्राफ का आसन्नता आव्यूह असममित हो सकता है। कोई एक निर्देशित ग्राफ के आसन्नता आव्यूह को इस तरह परिभाषित कर सकता है

एक गैर-शून्य अवयव $A ij$ किनारे को इंगित करता है $i$ को $j$ या
यह किनारे से इंगित करता है $j$ को $i$ .

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

Labeled graph	Adjacency matrix
Directed Cayley graph of S₄	Coordinates are 0–23. As the graph is directed, the matrix is not necessarily symmetric.

तुच्छ रेखांकन

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

गुण

स्पेक्ट्रम

एक अप्रत्यक्ष सरल ग्राफ का आसन्नता आव्यूह सममित आव्यूह है, और इसलिए वास्तविक संख्या eigenvalues और एक ऑर्थोगोनल eigenvector आधार का एक पूरा सेट है। एक ग्राफ के eigenvalues का सेट ग्राफ का स्पेक्ट्रम है।^[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$ का प्रथम eigenvalue है $A$ वेक्टर के लिए $v = (1, \dots, 1)$ (यह जांचना आसान है कि यह एक ईजेनवेल्यू है और उपरोक्त सीमा के कारण यह अधिकतम है)। इस eigenvalue की बहुलता के जुड़े घटकों की संख्या है $G$ , विशेष रूप से $\lambda _{1}>\lambda _{2}$ जुड़े हुए रेखांकन के लिए। यह दिखाया जा सकता है कि प्रत्येक eigenvalue के लिए $\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$ (यानी, का आव्यूह गुणन $n$ की प्रतियां $A$ ) की एक दिलचस्प व्याख्या है: अवयव $(i, j)$ लंबाई की (निर्देशित या अप्रत्यक्ष) पथ (ग्राफ सिद्धांत) की संख्या देता है $n$ शिखर से $i$ शीर्ष पर $j$ . अगर $n$ सबसे छोटा अऋणात्मक पूर्णांक है, जैसे कि कुछ के लिए $i$ , $j$ , अवयव $(i, j)$ का $A n$ सकारात्मक है, तो $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), Analyzing Social Networks (2nd ed.), SAGE, p. 20
↑ Newman, Mark (2018), Networks (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), Analyzing Social Networks (2nd ed.), SAGE, p. 20

[6] Newman, Mark (2018), Networks (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) -आव्यूह]] है जिसके विकर्ण पर शून्य हैं। यदि ग्राफ़ [[अप्रत्यक्ष]] है (अर्थात् इसके सभी [[किनारे]] द्विदिश हैं) तथा आसन्नता आव्यूह [[सममित मैट्रिक्स|सममित]] है। [[वर्णक्रमीय ग्राफ सिद्धांत]] में एक ग्राफ और उसके आसन्नता आव्यूह के [[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> संबंधित आव्यूह अवयव में प्रत्येक दो कोने के बीच किनारों की संख्या को संग्रहीत करके और गैर-शून्य विकर्ण अवयवों की अनुमति देकर एक ही अवधारणा को [[मल्टीग्राफ]] और लूप के साथ ग्राफ़ तक बढ़ाया जा सकता है। लूप्स को या तो एक बार (एक किनारे के रूप में) या दो बार (दो शीर्ष-एज घटनाओं के रूप में) गिना जा सकता है, जब तक कि एक सुसंगत सम्मेलन का पालन किया जाता है। अप्रत्यक्ष रेखांकन अक्सर दो बार गिनती के छोरों के बाद के सम्मेलन का उपयोग करते हैं, जबकि निर्देशित रेखांकन आमतौर पर पूर्व सम्मेलन का उपयोग करते हैं।
 === एक द्विदलीय ग्राफ का ===
@@ Line 13: / Line 13: @@
 आसन्नता आव्यूह {{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}} को कभी-कभी बायडजेंसी मैट्रिक्स कहा जाता है।
+कहाँ {{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|''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>)}}, क्रमश।
+अगर {{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;"
@@ Line 53: / Line 53: @@
 === निर्देशित रेखांकन ===
 निर्देशित ग्राफ का आसन्नता आव्यूह असममित हो सकता है। कोई एक निर्देशित ग्राफ के आसन्नता आव्यूह को इस तरह परिभाषित कर सकता है
-# एक गैर-शून्य तत्व {{mvar|A<sub>ij</sub>}} किनारे को इंगित करता है {{mvar|i}} को {{mvar|j}} या
+# एक गैर-शून्य अवयव {{mvar|A<sub>ij</sub>}} किनारे को इंगित करता है {{mvar|i}} को {{mvar|j}} या
 # यह किनारे से इंगित करता है {{mvar|j}} को {{mvar|i}}.
@@ Line 75: / Line 75: @@
   | at=p.&nbsp;110
 }}</ref>
-पहली परिभाषा का उपयोग करते हुए, निर्देशित ग्राफ़ # इंडिग्री और आउटडिग्री | एक वर्टेक्स की इन-डिग्री की गणना संबंधित कॉलम की प्रविष्टियों और संबंधित पंक्ति की प्रविष्टियों को योग करके वर्टेक्स की आउट-डिग्री द्वारा की जा सकती है। दूसरी परिभाषा का उपयोग करते समय, एक वर्टेक्स की इन-डिग्री संबंधित पंक्ति योग द्वारा दी जाती है और आउट-डिग्री संबंधित कॉलम योग द्वारा दी जाती है।
+पहली परिभाषा का उपयोग करते हुए, निर्देशित ग्राफ़ # इंडिग्री और आउटडिग्री | एक शीर्ष की इन-डिग्री की गणना संबंधित कॉलम की प्रविष्टियों और संबंधित पंक्ति की प्रविष्टियों को योग करके शीर्ष की आउट-डिग्री द्वारा की जा सकती है। दूसरी परिभाषा का उपयोग करते समय, एक शीर्ष की इन-डिग्री संबंधित पंक्ति योग द्वारा दी जाती है और आउट-डिग्री संबंधित कॉलम योग द्वारा दी जाती है।
 {| class="wikitable" style="text-align: center; width: 700px;"
@@ Line 90: / Line 90: @@
 === तुच्छ रेखांकन ===
-एक पूर्ण ग्राफ के आसन्नता आव्यूह में विकर्ण के अलावा सभी शामिल हैं, जहां केवल शून्य हैं। [[खाली ग्राफ]] का आसन्नता आव्यूह एक शून्य मैट्रिक्स है।
+एक पूर्ण ग्राफ के आसन्नता आव्यूह में विकर्ण के अलावा सभी सम्मिलित हैं, जहां केवल शून्य हैं। [[खाली ग्राफ]] का आसन्नता आव्यूह एक शून्य आव्यूह है।
 == गुण ==
 === स्पेक्ट्रम ===
-एक अप्रत्यक्ष सरल ग्राफ का आसन्नता आव्यूह सममित मैट्रिक्स है, और इसलिए [[वास्तविक संख्या]] 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>
+एक अप्रत्यक्ष सरल ग्राफ का आसन्नता आव्यूह सममित आव्यूह है, और इसलिए [[वास्तविक संख्या]] 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>
 सबसे बड़ा ईगेनवैल्यू <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>. तब
@@ Line 104: / Line 104: @@
 === समरूपता और अपरिवर्तनीय ===
-मान लीजिए दो निर्देशित या अप्रत्यक्ष रेखांकन {{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|''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|''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 से विभाजित करते हैं। आसन्नता आव्यूह का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि ग्राफ [[कनेक्टिविटी (ग्राफ सिद्धांत)]] है या नहीं।
+अगर {{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>
-आसन्नता आव्यूह का प्रतिनिधित्व करने के लिए आवश्यक स्थान और उन पर संचालन करने के लिए आवश्यक समय अंतर्निहित मैट्रिक्स के लिए चुने गए [[मैट्रिक्स प्रतिनिधित्व]] पर निर्भर है। विरल मैट्रिक्स अभ्यावेदन केवल गैर-शून्य मैट्रिक्स प्रविष्टियों को संग्रहीत करते हैं और शून्य प्रविष्टियों का प्रतिनिधित्व करते हैं। उदाहरण के लिए, [[विरल ग्राफ]]़ के आसन्नता आव्यूह में कई शून्य प्रविष्टियों को संग्रहीत करने से अंतरिक्ष ओवरहेड के बिना विरल ग्राफ़ का प्रतिनिधित्व करने के लिए उपयोग किया जा सकता है। निम्नलिखित खंड में आसन्नता आव्यूह को एक [[सरणी डेटा संरचना]] द्वारा दर्शाया गया माना जाता है ताकि मैट्रिक्स में शून्य और गैर-शून्य प्रविष्टियां सीधे भंडारण में प्रदर्शित हों।
+आसन्नता आव्यूह का प्रतिनिधित्व करने के लिए आवश्यक स्थान और उन पर संचालन करने के लिए आवश्यक समय अंतर्निहित आव्यूह के लिए चुने गए [[मैट्रिक्स प्रतिनिधित्व|आव्यूह प्रतिनिधित्व]] पर निर्भर है। विरल आव्यूह अभ्यावेदन केवल गैर-शून्य आव्यूह प्रविष्टियों को संग्रहीत करते हैं और शून्य प्रविष्टियों का प्रतिनिधित्व करते हैं। उदाहरण के लिए, [[विरल ग्राफ]]़ के आसन्नता आव्यूह में कई शून्य प्रविष्टियों को संग्रहीत करने से अंतरिक्ष ओवरहेड के बिना विरल ग्राफ़ का प्रतिनिधित्व करने के लिए उपयोग किया जा सकता है। निम्नलिखित खंड में आसन्नता आव्यूह को एक [[सरणी डेटा संरचना]] द्वारा दर्शाया गया माना जाता है ताकि आव्यूह में शून्य और गैर-शून्य प्रविष्टियां सीधे भंडारण में प्रदर्शित हों।
-क्योंकि आसन्नता आव्यूह में प्रत्येक प्रविष्टि के लिए केवल एक बिट की आवश्यकता होती है, इसे बहुत कॉम्पैक्ट तरीके से प्रदर्शित किया जा सकता है, केवल |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 129: / Line 129: @@
 हालांकि, एक बड़े विरल ग्राफ के लिए, आसन्न सूचियों को कम संग्रहण स्थान की आवश्यकता होती है, क्योंकि वे किनारों का प्रतिनिधित्व करने के लिए कोई स्थान बर्बाद नहीं करते हैं जो मौजूद नहीं हैं।<ref name="clrs"/><ref name="gt"/>
-निकटता मैट्रिक्स का एक वैकल्पिक रूप (जो, हालांकि, बड़ी मात्रा में स्थान की आवश्यकता होती है) मैट्रिक्स के प्रत्येक तत्व में अंकों को किनारे की वस्तुओं (जब किनारे मौजूद हैं) या अशक्त बिंदुओं (जब कोई किनारा नहीं है) के साथ बदल देता है।<ref name="gt"/>आसन्नता आव्यूह के तत्वों में सीधे भारित ग्राफ को स्टोर करना भी संभव है।<ref name="clrs"/>
+निकटता आव्यूह का एक वैकल्पिक रूप (जो, हालांकि, बड़ी मात्रा में स्थान की आवश्यकता होती है) आव्यूह के प्रत्येक अवयव में अंकों को किनारे की वस्तुओं (जब किनारे मौजूद हैं) या अशक्त बिंदुओं (जब कोई किनारा नहीं है) के साथ बदल देता है।<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 135: / Line 135: @@
 == यह भी देखें ==
-* [[लाप्लासियन मैट्रिक्स]]
+* [[लाप्लासियन मैट्रिक्स|लाप्लासियन आव्यूह]]
-* [[स्व-समानता मैट्रिक्स]]
+* [[स्व-समानता मैट्रिक्स|स्व-समानता आव्यूह]]
 ==संदर्भ==

v t e Graph representations
Data structures	Graph (abstract data type) Adjacency list Edge list Adjacency matrix Incidence matrix
XML-based formats	DGML DotML GEXF GraphML GXL XGMML
Text-based formats	DOT Graph Modelling Language (GML) LCF notation for cubic Hamiltonian graphs Newick format for trees Trivial Graph Format
Related concepts	Graph database Graph drawing Linked data

v t e Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
' List of matrices Category:Matrices

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:02, 11 May 2023

Contents

परिभाषा

एक द्विदलीय ग्राफ का

विविधताएं

उदाहरण

अप्रत्यक्ष रेखांकन

निर्देशित रेखांकन

तुच्छ रेखांकन

गुण

स्पेक्ट्रम

समरूपता और अपरिवर्तनीय

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

डेटा संरचनाएं

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 09:02, 11 May 2023

परिभाषा

एक द्विदलीय ग्राफ का

विविधताएं

उदाहरण

अप्रत्यक्ष रेखांकन

निर्देशित रेखांकन

तुच्छ रेखांकन

गुण

स्पेक्ट्रम

समरूपता और अपरिवर्तनीय

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

डेटा संरचनाएं

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories