मैट्रोइड

Not to be confused with मेट्रोइड or मेटोरॉइड.

साहचर्य में, गणित की शाखा, मैट्रोइड संरचना है जो सदिश स्थानों में रैखिक स्वतंत्रता की धारणा को अमूर्त और सामान्यीकृत करती है। मैट्रोइड को स्वयंसिद्ध प्रणाली के रूप में परिभाषित करने की कई समकक्ष विधि हैं, सबसे महत्वपूर्ण हैं: स्वतंत्र समुच्चय; आधार या परिपथ; पद फलन; बंद करने वाले ऑपरेटर; और बंद समुच्चय या फ्लैट है। आंशिक रूप से क्रमित समुच्चयों की भाषा में, परिमित सरल मैट्रोइड ज्यामितीय जाली के समान है।

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

परिभाषा

(परिमित) मैट्रोइड को परिभाषित करने के लिए कई क्रिप्टोमोर्फिज्म विधि हैं।

स्वतंत्र समुच्चय

स्वतंत्रता की दृष्टि से, परिमित मैट्रोइड $M$ जोड़ी है $(E,{\mathcal {I}})$, जहाँ $E$ परिमित समुच्चय है (जिसे ग्राउंड समुच्चय कहा जाता है) और ${\mathcal {I}}$ के उपसमुच्चय का सदस्य है $E$ (स्वतंत्र समुच्चय कहा जाता है) निम्नलिखित गुणों के लिए निम्नलिखित है:

• (I1) रिक्त समुच्चय $\emptyset \in {\mathcal {I}}$ स्वतंत्र है,
• (I2) स्वतंत्र समुच्चय का प्रत्येक उपसमुच्चय स्वतंत्र होता है, अर्थात प्रत्येक के लिए $A'\subseteq A\subseteq E$, यदि $A\in {\mathcal {I}}$ तब $A'\in {\mathcal {I}}$ इसे कभी-कभी वंशानुगत गुण, या नीचे की ओर बंद गुण कहा जाता है।
• (I3) यदि $A$ और $B$ दो स्वतंत्र समुच्चय हैं (अर्थात्, प्रत्येक समुच्चय स्वतंत्र है) और $A$ में इससे अधिक तत्व हैं $B$, तो वहाँ उपस्तिथ है $x\in A\backslash B$ ऐसा है कि $B\cup \{x\}$ में है ${\mathcal {I}}$ इसे कभी-कभी वृद्धि गुण या स्वतंत्र समुच्चय विनिमय गुण कहा जाता है।

पसमाधाने दो गुण संयुक्त संरचना को परिभाषित करते हैं जिसे स्वतंत्रता प्रणाली (या अमूर्त सरलीकृत परिसर) के रूप में जाना जाता है। वास्तव में, (I2) मानते हुए, गुण (I1) इस तथ्य के समान है कि कम से कम उपसमुच्चय $E$ स्वतंत्र है, अर्थात, ${\mathcal {I}}\neq \emptyset$ है।

आधार और परिपथ

Main article: मैट्रोइड का आधार

ग्राउंड समुच्चय का उपसमुच्चय $E$ जो स्वतंत्र नहीं है उसे आश्रित कहते हैं। अधिकतम स्वतंत्र समुच्चय—अर्थात स्वतंत्र समुच्चय जो किसी भी तत्व को जोड़ने पर निर्भर हो जाता है $E$-को मैट्रोइड के लिए आधार कहा जाता है। मैट्रोइड में परिपथ $M$ का न्यूनतम आश्रित उपसमुच्चय है $E$- अर्थात, आश्रित समुच्चय जिसके सभी उचित उपसमुच्चय स्वतंत्र हैं। शब्दावली इसलिए उत्पन्न होती है क्योंकि ग्राफ़िक मैट्रोइड के परिपथ संबंधित ग्राफ़ में चक्र होते हैं।

मैट्रोइड के आश्रित समुच्चय, आधार, या परिपथ पूर्ण रूप से मैट्रोइड की विशेषता बताते हैं: समुच्चय स्वतंत्र है यदि यह निर्भर नहीं है, यदि केवल आधार का उपसमुच्चय है, और यदि ऐसा होता है इसमें कोई परिपथ नहीं है, आश्रित समुच्चयों, आधारों और परिपथों के संग्रह में प्रत्येक में सरल गुण होते हैं जिन्हें मैट्रोइड के लिए सिद्धांतों के रूप में लिया जा सकता है। उदाहरण के लिए, कोई मैट्रोइड को परिभाषित कर सकता है $M$ जोड़ी बनने के लिए $(E,{\mathcal {B}})$, जहाँ $E$ पूर्व के जैसे परिमित समुच्चय है ${\mathcal {B}}$ के उपसमुच्चय का संग्रह है $E$, जिसे निम्नलिखित गुणों के साथ आधार कहा जाता है:

• (बी1) ${\mathcal {B}}$ अरिक्त है।
• (बी2) यदि $A$ और $B$ के विशिष्ट सदस्य हैं ${\mathcal {B}}$ और $a\in A\smallsetminus B$, तो वहां तत्व उपस्तिथ है $b\in B\smallsetminus A$ ऐसा है कि $(A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}$ इस गुण को आधार विनिमय गुण कहा जाता है।

यह उस आधार विनिमय गुण से चलता है जिसका कोई सदस्य नहीं है ${\mathcal {B}}$ दूसरे का उचित उपसमुच्चय हो सकता है।

पद फलन

यह मैट्रोइड सिद्धांत का मूल परिणाम है, जो रैखिक बीजगणित में आधारों के समान प्रमेय के सरलता से अनुरूप है, कि मैट्रोइड के कोई भी दो आधार $M$ तत्वों की संख्या समान है। इस संख्या को मैट्रोइड पद कहा जाता है $M$ यदि $M$ मैट्रोइड प्रारंभ है $E$, और $A$ का उपसमुच्चय है $E$, फिर मैट्रोइड प्रारंभ $A$ के उपसमूह पर विचार करके परिभाषित किया जा सकता है $A$ को स्वतंत्र होना चाहिए यदि $M$ स्वतंत्र है यह हमें सबमैट्रोइड्स और किसी भी उपसमुच्चय के पद के बारे में बात करने की अनुमति देता है $E$ उपसमुच्चय का पद $A$ मैट्रोइड पद द्वारा दिया गया है $r(A)$ मैट्रोइड का, जिसमें निम्नलिखित गुण हैं:

(R1) पद फलन का मान सदैव अनकारात्मक पूर्णांक होता है।

• (R2) किसी भी उपसमुच्चय के लिए $A\subset E$, अपने पास $r(A)\leq |A|$ है
• (R3) किन्हीं दो उपसमुच्चयों के लिए $A,B\subset E$, अपने पास: $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$ अर्थात पद सबमॉड्यूलर फलन है।
• (R4) किसी भी समुच्चय के लिए $A$ और तत्व $x$, अपने पास: $r(A)\le <!--\; \le \; -->r(A\cup <!--\; \cup \; -->\{x\})\le <!--\; \le \; -->$