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

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

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

लेबल ग्राफ	संलग्नता आव्यूह
File:6n-graph2.svg	${\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 हैं।
File:Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg नाउरू ग्राफ	File:Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg निर्देशांक 0-23 हैं. सफेद क्षेत्र शून्य हैं, रंगीन क्षेत्र एक हैं।

दिष्ट आलेख

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

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

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

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

लेबल ग्राफ	संलग्नता आव्यूह
File:Symmetric group 4; Cayley graph 4,9; numbers.svg Directed Cayley graph of S4	File:Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg 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}|$ से प्रदर्शित करना भी उपयोगी है। यह संख्या $$