आसन्नता आव्यूह

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

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

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

परिभाषा

शीर्ष समुच्चय U = {u₁, …, u_n} के साथ एक साधारण आलेख के लिए आसन्नता आव्यूह एक वर्ग n × n आव्यूह A है, जैसे कि इसका अवयव A_ij एक है जब शीर्ष u_i से शीर्ष u_j, तक एक किनारा होता है, और शून्य जब कोई किनारा नहीं है। आव्यूह के विकर्ण अवयव सभी शून्य हैं, क्योंकि क्योंकि सरल रेखांकन में एक शीर्ष से स्वयं (लूप) के किनारों की अनुमति नहीं है। यह कभी-कभी बीजगणितीय आलेख सिद्धांत में गैर-शून्य अवयवों को बीजगणितीय चर के साथ बदलने के लिए भी उपयोगी होता है। संबंधित आव्यूह अवयव में प्रत्येक दो कोने के बीच किनारों की संख्या को संग्रहीत करके और गैर-शून्य विकर्ण अवयवों की अनुमति देकर एक ही अवधारणा को बहुलेख और लूप के साथ आलेख़ तक बढ़ाया जा सकता है। लूप्स को या तो एक बार (एक किनारे के रूप में) या दो बार (दो शीर्ष-किनारे आपतन के रूप में) गिना जा सकता है, जब तक कि एक सुसंगत सम्मेलन का पालन किया जाता है। अदिष्‍ट आलेख अक्सर दो बार गिनती के छोरों के बाद के सम्मेलन का उपयोग करते हैं, जबकि दिष्ट आलेख आमतौर पर पूर्व सम्मेलन का उपयोग करते हैं।

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

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

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

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

औपचारिक रूप से, G = (U, V, E) भागों U = {u₁, ..., u_r}, V = {v₁, ..., v_s}और किनारों E के साथके साथ एक द्विदलीय ग्राफ होने दें। द्विआसन्नता आव्यूह r × s 0–1 आव्यूह B है जिसमें b_i,j = 1 और केवल (u_i, v_j) ∈ E.

है।

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

विविधताएं

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

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

उदाहरण

अदिष्‍ट आलेख

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

लेबल ग्राफ	संलग्नता आव्यूह
	${\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 हैं. सफेद क्षेत्र शून्य हैं, रंगीन क्षेत्र एक हैं।

दिष्ट आलेख

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

1. एक गैर-शून्य अवयव A_ij i से j तक किनारे को निर्दिष्ट करता है या
2. यह j से i तक के किनारे को निर्दिष्ट करता है।

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

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

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

तुच्छालेख

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

गुण

वर्णक्रम

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

$\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, …, 1) के लिए A का पहला अभिलक्षणिक मान है (यह जांचना आसान है कि यह एक अभिलक्षणिक मान है और उपरोक्त सीमा के कारण यह अधिकतम है)। इस अभिलक्षणिक मान की बहुलता G के जुड़े घटकों की संख्या है , विशेष रूप से $\lambda _{1}>\lambda _{2}$ जुड़े हुए आलेख के लिए। यह दिखाया जा सकता है कि प्रत्येक अभिलक्षणिक मान $\lambda _{i}$ के लिए, इसका विपरीत $-\lambda _{i}=\lambda _{n+1-i}$ भी A का अभिलक्षणिक मान है यदि G एक द्विपक्षीय आलेख है। विशेष रूप से -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₁ और G₂ आसन्नता आव्यूह A₁ और A₂ के साथ दिए गए हैं। G₁ और G₂ समरूपीय हैं और केवल वहाँ एक क्रमपरिवर्तन आव्यूह P मौजूद है जैसे कि

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

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

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

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

डेटा संरचना

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

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

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

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

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

यह भी देखें

• लाप्लासियन आव्यूह
• स्व-समानता आव्यूह

बाहरी संबंध

• 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.