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

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

परिमित सरल आलेख के विशेष स्थिति में, आसन्नता आव्यूह एक (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 जोड़ता है। यह आसन्नता आव्यूह में संबंधित पंक्ति या स्तंभ में मानों का योग लेकर किसी शीर्ष की डिग्री को आसानी से प्राप्त करने की अनुमति देता है।

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.

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

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

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.

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

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

गुण

स्पेक्ट्रम

एक अप्रत्यक्ष सरल आलेख का आसन्नता आव्यूह सममित आव्यूह है, और इसलिए वास्तविक संख्या eigenvalues ​​​​और एक ऑर्थोगोनल eigenvector आधार का एक पूरा समुच्चय है। एक आलेख के eigenvalues ​​​​का समुच्चय आलेख का स्पेक्ट्रम है। द्वारा आइगेनवैल्यूज़ को निरूपित करना आम है $\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, …, 1) (यह जांचना आसान है कि यह एक ईजेनवेल्यू है और उपरोक्त सीमा के कारण यह अधिकतम है)। इस eigenvalue की बहुलता के जुड़े घटकों की संख्या है G, विशेष रूप से $\lambda _{1}>\lambda _{2}$ जुड़े हुए रेखांकन के लिए। यह दिखाया जा सकता है कि प्रत्येक eigenvalue के लिए $\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ⁿ (यानी, का आव्यूह गुणन n की प्रतियां A) की एक दिलचस्प व्याख्या है: अवयव (i, j) लंबाई की (निर्देशित या अप्रत्यक्ष) पथ (आलेख सिद्धांत) की संख्या देता है n शिखर से i शीर्ष पर j. अगर n सबसे छोटा अऋणात्मक पूर्णांक है, जैसे कि कुछ के लिए i, j, अवयव (i, j) का Aⁿ सकारात्मक है, तो 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.