आपतन आव्यूह

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

ग्राफ सिद्धांत

घटना मैट्रिक्स ग्राफ सिद्धांत में एक सामान्य ग्राफ प्रतिनिधित्व है। यह आसन्न मैट्रिक्स से भिन्न है, जो वर्टेक्स-वर्टेक्स जोड़े के संबंध को कूटबद्ध करता है।

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

एक अप्रत्यक्ष ग्राफ।

ग्राफ़ थ्योरी में एक अप्रत्यक्ष ग्राफ़ में दो प्रकार के इंसिडेंस मैट्रिसेस होते हैं: अनओरिएंटेड और ओरिएंटेड।

एक अप्रत्यक्ष ग्राफ का अनियंत्रित घटना मैट्रिक्स (या केवल घटना मैट्रिक्स) एक है $n\times 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.