आपतन आव्यूह

गणित में, आपतन आव्यूह एक तार्किक आव्यूह है जो वस्तुओं के दो वर्गों के बीच के संबंध को दर्शाता है, जिसे सामान्यतः आपतन (ज्यामिति) कहा जाता है। यदि पहली श्रेणी 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.$

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

एक अप्रत्यक्ष ग्राफ का उन्मुख आपतन आव्यूह ग्राफ के किसी भी ओरिएंटेशन (ग्राफ सिद्धांत) के निर्देशित ग्राफ के अर्थ में आपतन आव्यूह है। अर्थात्, किनारे ई के पंक्ति स्तम्भ में, ई के एक शीर्ष के अनुरूप पंक्ति में एक 1 है और ई के अन्य शीर्ष के अनुरूप पंक्ति में एक -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 का तत्समक आव्यूह है।

असतत Kirchhoff आव्यूह (या Kirchhoff आव्यूह) सूत्र द्वारा उन्मुख आपतन आव्यूह 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}}.$

hypergraph

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

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

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

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

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

पॉलीटोप्स

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

ब्लॉक डिजाइन

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

यह भी देखें

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

अग्रिम पठन

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