आपतन आव्यूह

गणित में, आपतन आव्यूह एक तार्किक आव्यूह है जो वस्तुओं के दो वर्गों के बीच के संबंध को दर्शाता है, जिसे सामान्यतः आपतन (ज्यामिति) कहा जाता है। यदि पहली श्रेणी X है और दूसरी Y है, तो आव्यूह में X के प्रत्येक अवयव के लिए एक पंक्ति और Y के प्रत्येक अवयव के लिए एक पंक्ति स्तम्भ है। यदि 'x' और 'y संबंधित हैं तो पंक्ति 'x' और पंक्ति स्तम्भ 'y' में प्रविष्टि 1 है (इस संदर्भ में 'आपतन' कहा जाता है) अन्यथा प्रविष्टि 0 होने पर 'x' और 'y' एक दूसरे से संबंधित नहीं होंगे।

लेखाचित्र सिद्धांत

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

अप्रत्यक्ष और निर्देशित रेखांकन

एक अप्रत्यक्ष लेखाचित्र।

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

किसी एक अप्रत्यक्ष लेखाचित्र का अनियंत्रित आपतन आव्यूह (या केवल आपतन आव्यूह) एक $n\times m$ है, आव्यूह (गणित) B, जहां n और m क्रमशः शीर्षकोण बिंदु और कोर (लेखाचित्र सिद्धांत) की संख्याएं हैं, जैसे कि

$B_{ij}=\left\{{\begin{array}{rl}\,1&{\text{if vertex }}v_{i}{\text{ is incident with edge }}e_{j},\\0&{\text{otherwise.}}\end{array}}\right.$

उदाहरण के लिए, दाईं ओर दिखाए गए अप्रत्यक्ष लेखाचित्र का आपतन आव्यूह वह आव्यूह है जिसमें 4 पंक्तियाँ (चार कोने, 1-4 के अनुरूप) और 4 पंक्ति स्तम्भ (चार किनारों के अनुरूप, $e_{1},e_{2},e_{3},e_{4}$) है:

e1 e2 e3 e4 1 1 1 1 0 2 1 0 0 0 3 0 1 0 1 4 0 0 1 1

=

${\begin{bmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{bmatrix}}.$

यदि हम आपतन आव्यूह को देखते हैं, तो हम देखते हैं कि प्रत्येक स्तंभ का योग 2 के बराबर है। ऐसा इसलिए है क्योंकि प्रत्येक कोर के प्रत्येक सिरे से जुड़ा एक शीर्ष है।

निर्देशित लेखाचित्र का आपतन आव्यूह एक है $n\times m$ आव्यूह बी जहां n और m क्रमशः कोने और किनारों की संख्या है, जैसे कि

$B_{ij}=\left\{{\begin{array}{rl}{-1}&{\text{if edge }}e_{j}{\text{ leaves vertex }}v_{i},\\{\phantom {-}}1&{\text{if edge }}e_{j}{\text{ enters vertex }}v_{i},\\{\phantom {-}}0&{\text{otherwise.}}\end{array}}\right.$

(कई लेखक विपरीत चिह्न अभिसमय का उपयोग करते हैं।)

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

एक लेखाचित्र G का अनियंत्रित आपतन आव्यूह निम्नलिखित प्रमेय द्वारा इसके रेखा लेखाचित्र L(G) के आसन्न आव्यूह से संबंधित है:

$A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}.$

जहाँ A(L(G)) G के लाइन लेखाचित्र का आसन्न आव्यूह है, B(G) आपतन आव्यूह है, और I_m आयाम m का तत्समक आव्यूह है।

असतत किरचॉफ आव्यूह (या किरचॉफ आव्यूह) सूत्र द्वारा उन्मुख आपतन आव्यूह B(G) से प्राप्त किया जाता है

$B(G)B(G)^{\textsf {T}}.$

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

हस्ताक्षरित और द्विदिश रेखांकन

एक हस्ताक्षरित लेखाचित्र का आपतन आव्यूह उन्मुख आपतन आव्यूह का एक सामान्यीकरण है। यह किसी भी द्विदिश लेखाचित्र का आपतन आव्यूह है जो दिए गए हस्ताक्षरित लेखाचित्र को अभिविन्यास करता है। एक सकारात्मक कोर के पंक्ति स्तम्भ में एक समापन बिंदु के अनुरूप पंक्ति में 1 और दूसरे समापन बिंदु के अनुरूप ठीक एक साधारण (अहस्ताक्षरित) लेखाचित्र में कोर की तरह पंक्ति में -1 होता है। एक नकारात्मक कोर के पंक्ति स्तम्भ में दोनों पंक्तियों में या तो 1 या -1 होता है। लाइन लेखाचित्र और किरचॉफ आव्यूह गुण हस्ताक्षरित लेखाचित्र के लिए सामान्यीकृत होते हैं।

बहुलेखाचित्र

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

भारित रेखांकन

एक भारित अप्रत्यक्ष लेखाचित्र

भारित लेखाचित्र को 1 के स्थान पर कोर के भार का उपयोग करके प्रदर्शित किया जा सकता है। उदाहरण के लिए, दाईं ओर लेखाचित्र का आपतन आव्यूह है:

e1 e2 e3 e4 1 2 1 5 0 2 2 0 0 0 3 0 1 0 6 4 0 0 5 6

=

${\begin{bmatrix}2&1&5&0\\2&0&0&0\\0&1&0&6\\0&0&5&6\\\end{bmatrix}}.$

हाइपरलेखाचित्र

क्योंकि सामान्य रेखांकन के किनारों में केवल दो कोने (प्रत्येक छोर पर एक) हो सकते हैं, अर्थात लेखाचित्र के लिए एक आपतन आव्यूह के स्तंभ में केवल दो गैर-शून्य प्रविष्टियाँ हो सकती हैं। इसके विपरीत, एक हाइपरलेखाचित्र में एक कोर पर निर्दिष्ट कई कोने हो सकते हैं; इस प्रकार, गैर-ऋणात्मक पूर्णांकों का एक सामान्य आव्यूह एक हाइपरलेखाचित्र का वर्णन करता है।

आपतन संरचनाएं

आपतन संरचना C का आपतन आव्यूह p × q है, आव्यूह B (या इसका स्थानान्तरण), जहां p और q क्रमशः बिंदुओं और रेखाओं की संख्या हैं, जैसे कि B_i,j = 1 यदि बिंदु p_i और लाइन L_j आपतन हैं और 0 इस प्रकरण में, आपतन आव्यूह संरचना के लेवी लेखाचित्र का एक बायडजेंसी आव्यूह भी है। जैसा कि प्रत्येक लेवी लेखाचित्र के लिए एक हाइपरलेखाचित्र है, और इसके विपरीत एक आपतन संरचना का आपतन आव्यूह एक हाइपरलेखाचित्र का वर्णन करता है।

परिमित ज्यामिति

एक महत्वपूर्ण उदाहरण परिमित ज्यामिति है। उदाहरण के लिए, एक परिमित तल में X बिंदुओं का समुच्चय है और Y रेखाओं का समुच्चय है। उच्च आयाम की परिमित ज्यामिति में, X बिंदुओं का समुच्चय हो सकता है और Y पूरे समतल अक्ष (हाइपरप्लेन) के आयाम से एक कम आयाम के उप-स्थानों का समुच्चय हो सकता है; या, अधिक सामान्यतः, X एक आयाम d के सभी उप-स्थानों का समुच्चय हो सकता है और Y दूसरे आयाम e के सभी उप-समूहों का समुच्चय हो सकता है, जिसमें नियंत्रण के रूप में परिभाषित आपतन आयाम होते हैं।

बहुशीर्ष

इसी तरह, प्रकोष्ठ के बीच संबंध जिनके आयाम एक बहुशीर्ष में एक से भिन्न होते हैं, वे एक आपतन आव्यूह द्वारा प्रदर्शित किए जा सकते हैं।

ब्लॉक डिजाइन

इसका एक अन्य उदाहरण ब्लॉक डिज़ाइन है। यहाँ X बिंदुओं का एक परिमित समूह है और Y, X के उपसमुच्चय का एक वर्ग है, जिसे ब्लॉक कहा जाता है, जो नियमों के अधीन है तथा जो डिज़ाइन के प्रकार पर निर्भर करता है। आपतन आव्यूह ब्लॉक डिजाइन के सिद्धांत में एक महत्वपूर्ण उपकरण है। उदाहरण के लिए, इसका उपयोग फिशर की असमानता को प्रमाणित करने के लिए किया जा सकता है। संतुलित अपूर्ण 2-डिजाइन (बीआईबीडी) का एक मौलिक प्रमेय, जिसमे एक नकारात्मक कोर के पंक्ति स्तम्भ में दोनों पंक्तियों में या तो 1 या -1 होता है। ब्लॉक को समुच्चय की एक प्रणाली के रूप में देखते हुए, आपतन आव्यूह का स्थायी (गणित) अलग-अलग प्रतिनिधियों (एसडीआर) की प्रणाली की संख्या सुनिश्चित करता है।

यह भी देखें

• पैरी-सुलिवन अपरिवर्तनीय

अग्रिम पठन

• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Springer-Verlag, ISBN 3-540-26183-4
• Jonathan L Gross, Jay Yellen, Graph Theory and its applications, second edition, 2006 (p 97, Incidence Matrices for undirected graphs; p 98, incidence matrices for digraphs)

बाहरी संबंध

• Weisstein, Eric W. "Incidence matrix". MathWorld.