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

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

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

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

परिभाषा

वर्टेक्स सेट के साथ एक साधारण ग्राफ के लिए 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.