मैट्रोइड

Not to be confused with Metroid or Meteoroid.

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

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

परिभाषा

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

स्वतंत्र सेट

स्वतंत्रता की दृष्टि से, परिमित मैट्रोइड $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: Basis of a matroid

ग्राउंड सेट का उपसमुच्चय $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)$. यानी रैंक सबमॉड्यूलर फ़ंक्शन है।
• (आर4) किसी भी सेट के लिए $A$ और तत्व $x$, अपने पास: $r(A)\leq r(A\cup \{x\})\leq r(A)+1$. पहली असमानता से यह अधिक सामान्यतः इस प्रकार है कि, यदि $A\subseteq B\subseteq E$, तब $r(A)\leq r(B)\leq r(E)$. अर्थात्, रैंक मोनोटोनिक फ़ंक्शन है।

इन गुणों का उपयोग परिमित मैट्रोइड की वैकल्पिक परिभाषाओं में से के रूप में किया जा सकता है: यदि $(E,r)$ इन गुणों को संतुष्ट करता है, फिर मैट्रोइड के स्वतंत्र सेट खत्म हो जाते हैं $E$ उन उपसमुच्चय के रूप में परिभाषित किया जा सकता है $A$ का $E$ साथ $r(A)=|A|$. आंशिक रूप से क्रमबद्ध सेटों की भाषा में, ऐसी मैट्रोइड संरचना ज्यामितीय जाली के बराबर होती है जिसके तत्व उपसमुच्चय होते हैं $A\subset M$, आंशिक रूप से समावेशन द्वारा आदेश दिया गया।

के अंतर $|A|-r(A)$ उपसमुच्चय की शून्यता कहलाती है $A$. यह उन तत्वों की न्यूनतम संख्या है जिन्हें हटाया जाना चाहिए $A$ स्वतंत्र सेट प्राप्त करने के लिए. की अशक्तता $E$ में $M$ की शून्यता कहलाती है $M$. के अंतर $r(E)-r(A)$ इसे कभी-कभी उपसमुच्चय का कोरकांक भी कहा जाता है $A$.

क्लोजर ऑपरेटर

होने देना $M$ परिमित समुच्चय पर मैट्रोइड बनें $E$, रैंक फ़ंक्शन के साथ $r$ ऊपरोक्त अनुसार। समापन (या अवधि) $\operatorname {cl} (A)$ उपसमुच्चय का $A$ का $E$ सेट है

$\operatorname {cl} (A)={\Bigl \{}x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}.$

यह बंद करने वाला ऑपरेटर को परिभाषित करता है $\operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)$ कहाँ ${\mathcal {P}}$ निम्नलिखित गुणों के साथ सत्ता स्थापित को दर्शाता है:

• (सी1) सभी उपसमुच्चय के लिए $X$ का $E$, $X\subseteq \operatorname {cl} (X)$.
• (सी2) सभी उपसमुच्चय के लिए $X$ का $E$, $\operatorname {cl} (X)=\operatorname {cl} (\operatorname {cl} (X))$.
• (सी3) सभी उपसमुच्चय के लिए $X$ और $Y$ का $E$ साथ $X\subseteq Y$, $\operatorname {cl} (X)\subseteq \operatorname {cl} (Y)$.
• (सी4) सभी तत्वों के लिए $a$, और $b$ का $E$ और सभी उपसमुच्चय $Y$ का $E$, अगर $a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)$ तब $b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y)$.

इनमें से पहली तीन संपत्तियां क्लोजर ऑपरेटर की परिभाषित संपत्तियां हैं। चौथे को कभी-कभी सॉन्डर्स मैक अर्नेस्ट स्टीनिट्ज़ विनिमय संपत्ति कहा जाता है। इन गुणों को मैट्रोइड की और परिभाषा के रूप में लिया जा सकता है: प्रत्येक फ़ंक्शन $\operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)$ जो इन गुणों का पालन करता है वह मैट्रोइड निर्धारित करता है।

फ्लैट

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

• (एफ1) संपूर्ण बिंदु सेट $E$ बन्द है।
• (F2) यदि $S$ और $T$ फिर फ्लैट हैं $S\cap T$ फ्लैट है.
• (F3) यदि $S$ समतल है, तो प्रत्येक तत्व $E\smallsetminus S$ बिल्कुल फ्लैट में है $T$ वह रिश्ते को कवर करना $S$ (मतलब है कि $T$ ठीक से शामिल है $S$ लेकिन कोई फ्लैट नहीं है $U$ बीच में $S$ और $T$).

कक्षा ${\mathcal {L}}(M)$ सभी फ्लैटों में से, आंशिक रूप से सेट समावेशन द्वारा सेट किया गया, मैट्रोइड जाली बनाता है। इसके विपरीत, प्रत्येक मैट्रोइड जाली $L$ अपने सेट पर मैट्रोइड बनाता है $E$ निम्नलिखित क्लोजर ऑपरेटर के तहत एटम (ऑर्डर सिद्धांत) का: सेट के लिए $S$ जुड़ने के साथ परमाणुओं का $\bigvee S$,

$\operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}$.

इस मैट्रोइड के फ्लैट जाली के तत्वों के साथ एक-के-लिए-एक-करके मेल खाते हैं; जाली तत्व के अनुरूप फ्लैट $y$ सेट है

$\{x\in E\mid x\leq y\}$.

इस प्रकार, इस मैट्रोइड के फ्लैटों की जाली स्वाभाविक रूप से आइसोमोर्फिक है $L$.

हाइपरप्लेन

रैंक के matroid में $r$, रैंक का फ्लैट $r-1$ हाइपरप्लेन कहा जाता है. (हाइपरप्लेन को कोटम या सह-बिंदु भी कहा जाता है।) ये अधिकतम उचित फ्लैट हैं; यानी, हाइपरप्लेन का एकमात्र सुपरसेट जो फ्लैट भी है, सेट है $E$ मैट्रोइड के सभी तत्वों का. समतुल्य परिभाषा यह है कि कोटोम ई का उपसमुच्चय है जो एम तक नहीं फैला है, लेकिन ऐसा है कि इसमें कोई अन्य तत्व जोड़ने से स्पैनिंग सेट बन जाता है। परिवार ${\mathcal {H}}$ मैट्रोइड के हाइपरप्लेन में निम्नलिखित गुण होते हैं, जिन्हें मैट्रोइड के और स्वयंसिद्धीकरण के रूप में लिया जा सकता है:*(H1) अलग-अलग सेट मौजूद नहीं हैं $X$ और $Y$ में ${\mathcal {H}}$ साथ $X\subseteq Y$. अर्थात्, हाइपरप्लेन स्पर्नर परिवार बनाते हैं।

• (H2) प्रत्येक के लिए $x\in E$ और विशिष्ट $Y,Z\in {\mathcal {H}}$ साथ $x\notin Y\cup Z$, वहां मौजूद $X\in {\mathcal {H}}$ साथ $(Y\cap Z)\cup \{x\}\subseteq X$.

ग्राफोइड्स

जॉर्ज जे. मिन्टी (1966) ने ग्राफॉइड को त्रिक के रूप में परिभाषित किया $(L,C,D)$ जिसमें $C$ और $D$ के गैर-रिक्त उपसमुच्चय की कक्षाएं हैं $L$ ऐसा है कि

• (G1) का कोई तत्व नहीं $C$ (जिसे सर्किट कहा जाता है) में और शामिल है,
• (G2) का कोई तत्व नहीं $D$ (जिसे को-सर्किट कहा जाता है) में और शामिल है,
• (जी3) कोई सेट नहीं है $C$ और अंदर सेट करें $D$ बिल्कुल तत्व में प्रतिच्छेद करें, और
• (जी4) जब भी $L$ उपसमुच्चय के असंयुक्त संघ के रूप में दर्शाया गया है $R,G,B$ साथ $G=\{g\}$ (सिंगलटन सेट), फिर या तो $X\in C$ ऐसा मौजूद है $g\in X\subseteq R\cup G$ या ए $Y\in D$ ऐसा मौजूद है $g\in Y\subseteq B\cup G.$

उन्होंने साबित कर दिया कि जिसके लिए मैट्रोइड है $C$ सर्किट का वर्ग है और $D$ को-सर्किट का वर्ग है। इसके विपरीत, यदि $C$ और $D$ मैट्रोइड के सर्किट और को-सर्किट वर्ग हैं $M$ ग्राउंड सेट के साथ $E$, तब $(E,C,D)$ ग्राफ़ॉइड है. इस प्रकार, ग्राफ़ॉइड्स मैट्रोइड्स का स्व-दोहरा क्रिप्टोमोर्फिक स्वयंसिद्धीकरण देते हैं।

उदाहरण

मुफ़्त मैट्रोइड

होने देना $E$ परिमित समुच्चय हो. के सभी उपसमुच्चय का समुच्चय $E$ मैट्रोइड के स्वतंत्र सेट को परिभाषित करता है। इसे मुफ़्त मैट्रोइड ओवर कहा जाता है $E$.

यूनिफ़ॉर्म मैट्रिक्स

होने देना $E$ परिमित समुच्चय हो और $k$ प्राकृतिक संख्या. कोई मैट्रोइड को परिभाषित कर सकता है $E$ प्रत्येक को लेकर $k$-तत्व उपसमुच्चय $E$ आधार बनना. इसे रैंक की एकसमान मैट्रोइड के रूप में जाना जाता है $k$. रैंक के साथ समान मैट्रोइड $k$ और साथ $n$ तत्वों को दर्शाया गया है $U_{k,n}$. कम से कम 2 रैंक के सभी समान मैट्रोइड सरल हैं (देखें)। § Additional terminology) . रैंक 2 की वर्दी मैट्रोइड पर $n$ अंक कहा जाता है $n$-बिंदु रेखा. मैट्रोइड समान होता है यदि और केवल तभी जब इसमें मैट्रोइड की रैंक प्लस से कम आकार का कोई सर्किट न हो। एकसमान मैट्रोइड्स के प्रत्यक्ष योग को विभाजन मैट्रोइड्स कहा जाता है।

वर्दी matroid में $U_{0,n}$, प्रत्येक तत्व लूप है (ऐसा तत्व जो किसी स्वतंत्र सेट से संबंधित नहीं है), और एकसमान मैट्रोइड में है $U_{n,n}$, प्रत्येक तत्व कोलूप है (तत्व जो सभी आधारों से संबंधित है)। इन दो प्रकार के मैट्रोइड्स का सीधा योग विभाजन मैट्रोइड है जिसमें प्रत्येक तत्व लूप या कोलूप है; इसे असतत मैट्रोइड कहा जाता है। असतत मैट्रोइड की समतुल्य परिभाषा मैट्रोइड है जिसमें ग्राउंड सेट का प्रत्येक उचित, गैर-रिक्त उपसमुच्चय $E$ विभाजक है.

रैखिक बीजगणित से मैट्रोइड्स

फ़ानो मैट्रोइड, फ़ानो विमान से प्राप्त हुआ। यह GF(2)-रैखिक है लेकिन वास्तविक-रैखिक नहीं है।

वामोस मैट्रोइड, किसी भी क्षेत्र पर रैखिक नहीं है

मैट्रोइड सिद्धांत मुख्य रूप से वेक्टर स्थानों में स्वतंत्रता और आयाम के गुणों की गहन जांच से विकसित हुआ। इस प्रकार परिभाषित मैट्रोइड्स को प्रस्तुत करने के दो तरीके हैं:

• अगर $E$ सदिश समष्टि का कोई परिमित उपसमुच्चय है $V$, तो हम मैट्रोइड को परिभाषित कर सकते हैं $M$ पर $E$ के स्वतंत्र सेट लेकर $M$ का रैखिक स्वतंत्रता उपसमुच्चय होना $E$. इस मैट्रोइड के लिए स्वतंत्र-सेट स्वयंसिद्धों की वैधता स्टीनिट्ज़ एक्सचेंज लेम्मा से होती है। अगर $M$ मैट्रोइड है जिसे इस तरह से परिभाषित किया जा सकता है, हम सेट कहते हैं $E$ मैट्रोइड प्रतिनिधित्व $M$. इस प्रकार के मैट्रोइड्स को वेक्टर मैट्रोइड्स कहा जाता है। इस तरह से परिभाषित मैट्रोइड का महत्वपूर्ण उदाहरण फ़ानो मैट्रोइड है, फ़ानो विमान से प्राप्त रैंक-तीन मैट्रोइड, सात बिंदुओं (मैट्रोइड के सात तत्व) और सात रेखाओं (मैट्रोइड के उचित गैर-तुच्छ फ्लैट) के साथ परिमित ज्यामिति मैट्रोइड)। यह रैखिक मैट्रोइड है जिसके तत्वों को परिमित क्षेत्र GF(2) पर त्रि-आयामी वेक्टर अंतरिक्ष में सात गैर-शून्य बिंदुओं के रूप में वर्णित किया जा सकता है। हालाँकि, GF(2) के स्थान पर वास्तविक संख्याओं का उपयोग करके फ़ैनो मैट्रोइड के लिए समान प्रतिनिधित्व प्रदान करना संभव नहीं है।
• मैट्रिक्स (गणित) $A$ किसी क्षेत्र (गणित) में प्रविष्टियों के साथ मैट्रोइड उत्पन्न होता है $M$ इसके स्तंभों के सेट पर। मैट्रोइड में स्तंभों के आश्रित सेट वे होते हैं जो वैक्टर के रूप में रैखिक रूप से निर्भर होते हैं। इस मैट्रोइड को कॉलम मैट्रोइड कहा जाता है $A$, और $A$ प्रतिनिधित्व करने के लिए कहा जाता है $M$. उदाहरण के लिए, फ़ैनो मैट्रोइड को 3×7 लॉजिकल मैट्रिक्स|(0,1)-मैट्रिक्स के रूप में इस तरह दर्शाया जा सकता है। कॉलम मैट्रोइड्स किसी अन्य नाम के तहत सिर्फ वेक्टर मैट्रोइड्स हैं, लेकिन मैट्रिक्स प्रतिनिधित्व के पक्ष में अक्सर कारण होते हैं। (तकनीकी अंतर है: कॉलम मैट्रोइड में अलग-अलग तत्व हो सकते हैं जो ही वेक्टर होते हैं, लेकिन जैसा कि ऊपर परिभाषित किया गया है वेक्टर मैट्रोइड में ऐसा नहीं हो सकता है। आमतौर पर यह अंतर महत्वहीन है और इसे नजरअंदाज किया जा सकता है, लेकिन अनुमति देकर $E$ सदिशों का बहुसमूह होना दो परिभाषाओं को पूर्ण सहमति में लाता है।)

मैट्रोइड जो वेक्टर मैट्रोइड के समतुल्य है, हालांकि इसे अलग ढंग से प्रस्तुत किया जा सकता है, प्रतिनिधित्व योग्य या रैखिक कहा जाता है। अगर $M$ फ़ील्ड पर वेक्टर मैट्रोइड के बराबर है (गणित) $F$, तो हम कहते हैं $M$ ऊपर प्रतिनिधित्व करने योग्य है $F$; विशेष रूप से, $M$ यदि यह वास्तविक संख्याओं पर प्रस्तुत करने योग्य है तो यह वास्तविक-प्रतिनिधित्व योग्य है। उदाहरण के लिए, यद्यपि ग्राफिक मैट्रोइड (नीचे देखें) को ग्राफ के रूप में प्रस्तुत किया जाता है, यह किसी भी क्षेत्र में वैक्टर द्वारा भी प्रदर्शित किया जा सकता है। मैट्रोइड सिद्धांत में बुनियादी समस्या उन मैट्रोइड्स को चिह्नित करना है जिन्हें किसी दिए गए क्षेत्र में दर्शाया जा सकता है $F$; रोटा का अनुमान प्रत्येक परिमित क्षेत्र के लिए संभावित लक्षण वर्णन का वर्णन करता है। अब तक के मुख्य परिणाम डब्ल्यू.टी. टुटे (1950 के दशक) के कारण बाइनरी मैट्रोइड्स (जीएफ (2) पर प्रतिनिधित्व योग्य), रीड और बिक्सबी के कारण टर्नरी मैट्रोइड्स (3-तत्व क्षेत्र पर प्रतिनिधित्व योग्य) और पॉल सेमुर के कारण अलग से लक्षण वर्णन हैं। (गणितज्ञ) (1970), और गिलेन, जेरार्ड्स और कपूर (2000) के कारण चतुर्धातुक मैट्रोइड्स (4-तत्व क्षेत्र पर प्रतिनिधित्व योग्य)। यह काफी खुला क्षेत्र है.

नियमित मैट्रोइड मैट्रोइड है जो सभी संभावित क्षेत्रों में प्रतिनिधित्व योग्य है। वामोस मैट्रोइड मैट्रोइड का सबसे सरल उदाहरण है जो किसी भी क्षेत्र में प्रदर्शित नहीं किया जा सकता है।

ग्राफ़ सिद्धांत से मैट्रोइड्स

मैट्रोइड्स के सिद्धांत का दूसरा मूल स्रोत ग्राफ़ सिद्धांत है।

प्रत्येक परिमित ग्राफ (या मल्टीग्राफ) $G$ मैट्रोइड को जन्म देता है $M(G)$ इस प्रकार: के रूप में ले लो $E$ सभी किनारों का सेट $G$ और किनारों के सेट को स्वतंत्र मानें यदि और केवल यदि वह पेड़ है (ग्राफ़ सिद्धांत); अर्थात्, यदि इसमें कोई सरल चक्र न हो। तब $M(G)$ चक्र मैट्रोइड कहा जाता है। इस तरह से प्राप्त मैट्रोइड्स ग्राफिक मैट्रोइड्स हैं। प्रत्येक मैट्रोइड ग्राफिक नहीं है, लेकिन तीन तत्वों पर सभी मैट्रोइड ग्राफिक हैं। प्रत्येक ग्राफिक मैट्रोइड नियमित है।

ग्राफ़ पर अन्य मैट्रोइड्स बाद में खोजे गए:

• ग्राफ के द्विवृत्ताकार मैट्रोइड को किनारों के सेट को स्वतंत्र कहकर परिभाषित किया जाता है यदि प्रत्येक जुड़े उपसमुच्चय में अधिकतम चक्र होता है।
• किसी भी निर्देशित या अप्रत्यक्ष ग्राफ़ में $G$ होने देना $E$ और $F$ शीर्षों के दो विशिष्ट सेट हों। सेट में $E$, उपसमुच्चय परिभाषित करें $U$ यदि हैं तो स्वतंत्र होना $|U|$ शीर्ष-असंयुक्त पथ से $F$ पर $U$. यह मैट्रोइड को परिभाषित करता है $E$ गैमॉइड कहा जाता है:सख्त गैमॉइड वह है जिसके लिए सेट $E$ का संपूर्ण शीर्ष समुच्चय है $G$.
• द्विपक्षीय ग्राफ़ में $G=(U,V,E)$, कोई मैट्रोइड बना सकता है जिसमें तत्व तरफ शीर्ष पर हैं $U$ द्विविभाजन, और स्वतंत्र उपसमुच्चय ग्राफ के मिलान (ग्राफ सिद्धांत) के अंतिम बिंदुओं के सेट हैं। इसे ट्रांसवर्सल मैट्रोइड कहा जाता है, और यह गैमॉइड का विशेष मामला है। ट्रांसवर्सल मैट्रोइड्स सख्त गैमॉइड्स के दोहरे मैट्रोइड्स हैं।*ग्राफ़िक मैट्रोइड्स को हस्ताक्षरित ग्राफ़, लाभ ग्राफ ़ और पक्षपाती ग्राफ़ से मैट्रोइड्स में सामान्यीकृत किया गया है। ग्राफ $G$ विशिष्ट रैखिक वर्ग के साथ $B$ चक्रों का, जिसे पक्षपाती ग्राफ़ के रूप में जाना जाता है $(G,B)$, दो मैट्रोइड हैं, जिन्हें फ्रेम मैट्रोइड और बायस्ड ग्राफ के लिफ्ट मैट्रोइड के रूप में जाना जाता है। यदि प्रत्येक चक्र विशिष्ट वर्ग का है, तो ये मैट्रोइड्स चक्र मैट्रोइड के साथ मेल खाते हैं $G$. यदि कोई चक्र प्रतिष्ठित नहीं है, तो फ्रेम मैट्रोइड द्विवृत्ताकार मैट्रोइड है $G$. हस्ताक्षरित ग्राफ, जिसके किनारों को संकेतों द्वारा लेबल किया जाता है, और लाभ ग्राफ, जो ऐसा ग्राफ है जिसके किनारों को समूह से उन्मुख रूप से लेबल किया जाता है, प्रत्येक पक्षपाती ग्राफ को जन्म देता है और इसलिए इसमें फ्रेम और लिफ्ट मैट्रोइड होते हैं।
• लमान ग्राफ द्वि-आयामी कठोरता मैट्रोइड का आधार बनाते हैं, जो संरचनात्मक कठोरता के सिद्धांत में परिभाषित मैट्रोइड है।
• होने देना $G$ कनेक्टेड ग्राफ बनें और $E$ इसका किनारा सेट हो. होने देना $I$ उपसमुच्चय का संग्रह हो $F$ का $E$ ऐसा है कि $G-F$ अभी भी जुड़ा हुआ है. तब $M^{*}(G)$, जिसका तत्व समुच्चय है $E$ और साथ $I$ इसके स्वतंत्र समुच्चयों के वर्ग के रूप में, मैट्रोइड है जिसे बॉन्ड मैट्रोइड कहा जाता है $G$. रैंक फ़ंक्शन $r(F)$ किनारे उपसमुच्चय पर प्रेरित उपग्राफ की चक्रीय संख्या है $F$, जो उस उपसमूह के अधिकतम जंगल के बाहर किनारों की संख्या और उसमें स्वतंत्र चक्रों की संख्या के बराबर है।

फ़ील्ड एक्सटेंशन से मैट्रोइड्स

मैट्रोइड सिद्धांत का तीसरा मूल स्रोत फ़ील्ड सिद्धांत (गणित) है।

किसी क्षेत्र का विस्तार क्षेत्र मैट्रोइड को जन्म देता है। कल्पना करना $F$ और $K$ के साथ फ़ील्ड हैं $K$ युक्त $F$. होने देना $E$ का कोई परिमित उपसमुच्चय हो $K$. उपसमुच्चय को परिभाषित करें $S$ का $E$ यदि विस्तार क्षेत्र बीजगणितीय स्वतंत्रता हो $F(S)$ पारगमन की डिग्री के बराबर है $|S|$. मैट्रोइड जो इस प्रकार के मैट्रोइड के बराबर होता है उसे बीजगणितीय मैट्रोइड कहा जाता है। बीजगणितीय मैट्रोइड्स को चिह्नित करने की समस्या अत्यंत कठिन है; इसके बारे में बहुत कम जानकारी है. वैमोस मैट्रोइड मैट्रोइड का उदाहरण प्रदान करता है जो बीजगणितीय नहीं है।

बुनियादी निर्माण

पुराने मैट्रोइड से नए मैट्रोइड बनाने के कुछ मानक तरीके हैं।

द्वैत

यदि एम परिमित मैट्रोइड है, तो हम उसी अंतर्निहित सेट को लेकर 'ऑर्थोगोनल' या 'डुअल मैट्रोइड' एम* को परिभाषित कर सकते हैं और सेट को एम* में आधार कह सकते हैं यदि और केवल यदि इसका पूरक एम में आधार है। यह सत्यापित करना कठिन नहीं है कि M* मैट्रोइड है और M* का द्वैत M है। मैट्रोइड को परिभाषित करने के अन्य तरीकों के संदर्भ में दोहरे को समान रूप से वर्णित किया जा सकता है। उदाहरण के लिए:

• M* में समुच्चय स्वतंत्र है यदि और केवल यदि उसका पूरक M तक फैला हो।
• सेट एम* का सर्किट है यदि और केवल यदि इसका पूरक एम में कोटोम है।
• डुअल का रैंक फंक्शन है $r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)$.

कुराटोस्की के प्रमेय के मैट्रोइड संस्करण के अनुसार, ग्राफिक मैट्रोइड एम का दोहरा ग्राफिक मैट्रोइड है यदि और केवल यदि एम समतलीय ग्राफ का मैट्रोइड है। इस मामले में, M का द्वैत, G के द्वैत ग्राफ का मैट्रॉइड है। वेक्टर मैट्रोइड का द्वैत विशेष क्षेत्र F पर प्रदर्शित होता है, F पर भी प्रदर्शित होता है। ट्रांसवर्सल मैट्रोइड का द्वैत सख्त गैमॉइड है और इसके विपरीत।

'उदाहरण'

किसी ग्राफ़ का चक्र मैट्रोइड उसके बांड मैट्रोइड का दोहरा मैट्रोइड है।

नाबालिग

Main article: Matroid minor

यदि M तत्व समुच्चय E वाला मैट्रोइड है, और S, E का उपसमुच्चय है, तो M से S का 'प्रतिबंध', जिसे M |S लिखा जाता है, समुच्चय S पर मैट्रोइड है जिसके स्वतंत्र समुच्चय M के स्वतंत्र समुच्चय हैं जो कि हैं एस में निहित है। इसके सर्किट एम के सर्किट हैं जो एस में निहित हैं और इसका रैंक फ़ंक्शन एम का है जो एस के सबसेट तक सीमित है। रैखिक बीजगणित में, यह एस में वैक्टर द्वारा उत्पन्न उप-स्थान तक सीमित करने के अनुरूप है। समान रूप से यदि T = M−S इसे T का 'विलोपन' कहा जा सकता है, जिसे M\T या M−T लिखा जाता है। एम के सबमैट्रोइड्स वास्तव में विलोपन के अनुक्रम के परिणाम हैं: आदेश अप्रासंगिक है। प्रतिबंध की दोहरी क्रिया संकुचन है। यदि T, E का उपसमुच्चय है, तो T द्वारा M का 'संकुचन', जिसे M/T लिखा जाता है, अंतर्निहित सेट E - T पर मैट्रोइड है जिसका रैंक फ़ंक्शन है $r'(A)=r(A\cup T)-r(T).$ रैखिक बीजगणित में, यह E-T में सदिशों की छवियों के साथ-साथ T में सदिशों द्वारा उत्पन्न रैखिक स्थान द्वारा भागफल स्थान को देखने से मेल खाता है।

मैट्रोइड एन जो प्रतिबंध और संकुचन संचालन के अनुक्रम द्वारा एम से प्राप्त किया जाता है, उसे एम का मैथेरॉइड माइनर कहा जाता है। हम कहते हैं कि एम में 'एन' नाबालिग है। मैट्रोइड्स के कई महत्वपूर्ण परिवारों को न्यूनतम तत्व द्वारा चित्रित किया जा सकता है | लघु-न्यूनतम मैट्रोइड्स जो परिवार से संबंधित नहीं हैं; इन्हें 'निषिद्ध' या 'बहिष्कृत अवयस्क' कहा जाता है।

योग और संघ

मान लीजिए कि M तत्वों E के अंतर्निहित सेट के साथ मैट्रॉइड है, और N को अंतर्निहित सेट F पर और मैट्रॉइड होने दें। मैट्रोइड्स एम और एन का 'प्रत्यक्ष योग' वह मैट्रोइड है जिसका अंतर्निहित सेट ई और एफ का असंयुक्त संघ है, और जिसका स्वतंत्र सेट एम के स्वतंत्र सेट और एन के स्वतंत्र सेट का असंयुक्त संघ है।

एम और एन का 'संघ' वह मैट्रोइड है जिसका अंतर्निहित सेट ई और एफ का मिलन (असंगठित संघ नहीं) है, और जिसका स्वतंत्र सेट वे उपसमुच्चय हैं जो एम में स्वतंत्र सेट और एन में का मिलन हैं। आमतौर पर यूनियन शब्द का प्रयोग तब किया जाता है जब E = F होता है, लेकिन यह धारणा आवश्यक नहीं है। यदि E और F असंयुक्त हैं, तो मिलन सीधा योग है।

अतिरिक्त शब्दावली

मान लीजिए कि M मैट्रोइड है जिसमें E तत्वों का अंतर्निहित सेट है।

• E को M का 'ग्राउंड सेट' कहा जा सकता है। इसके तत्वों को M का 'बिंदु' कहा जा सकता है।
• E का उपसमुच्चय M को फैलाता है यदि इसका समापन E है। समुच्चय को बंद समुच्चय K को 'फैलाने' वाला कहा जाता है यदि इसका समापन K है।
• किसी मैट्रोइड का मैट्रोइड घेरा उसके सबसे छोटे सर्किट या आश्रित सेट का आकार होता है।
• तत्व जो एम का एकल-तत्व सर्किट बनाता है उसे 'लूप' कहा जाता है। समान रूप से, तत्व लूप है यदि इसका कोई आधार नहीं है।
• तत्व जो किसी सर्किट से संबंधित नहीं होता है उसे कोलूप या इस्थमस कहा जाता है। समान रूप से, तत्व कोलूप है यदि वह हर आधार से संबंधित है। लूप और कोलूप परस्पर दोहरे हैं।* यदि दो-तत्व सेट {f, g} M का सर्किट है, तो M में f और g 'समानांतर' हैं।* मैट्रोइड को सरल कहा जाता है यदि इसमें 1 या 2 तत्वों से युक्त कोई सर्किट नहीं है। अर्थात्, इसमें कोई लूप नहीं है और कोई समानांतर तत्व नहीं है। संयोजक ज्यामिति शब्द का भी प्रयोग किया जाता है। सभी लूपों को हटाकर और प्रत्येक 2-तत्व सर्किट से तत्व को हटाकर जब तक कि कोई 2-तत्व सर्किट न रह जाए, अन्य मैट्रॉइड एम से प्राप्त साधारण मैट्रोइड को एम का 'सरलीकरण' कहा जाता है। मैट्रोइड सह-सरल है यदि उसका दोहरा मैट्रोइड सरल है।
• सर्किट के संघ को कभी-कभी एम का चक्र कहा जाता है। इसलिए चक्र दोहरे मैट्रोइड के फ्लैट का पूरक है। (यह प्रयोग ग्राफ़ सिद्धांत में चक्र के सामान्य अर्थ के साथ विरोधाभास रखता है।)
• M का विभाजक E का उपसमुच्चय S इस प्रकार है $r(S)+r(E-S)=r(M)$. उचित या गैर-तुच्छ विभाजक विभाजक है जो न तो ई है और न ही खाली सेट है। इरेड्यूसिबल विभाजक गैर-रिक्त विभाजक है जिसमें कोई अन्य गैर-रिक्त विभाजक नहीं होता है। इरेड्यूसिबल सेपरेटर ग्राउंड सेट ई को विभाजित करते हैं।
• मैट्रोइड जिसे दो गैर-रिक्त मैट्रोइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है, या समकक्ष जिसमें कोई उचित विभाजक नहीं है, उसे कनेक्टेड या इरेड्यूसिबल कहा जाता है। मैट्रोइड तभी जुड़ा होता है जब उसका डुअल जुड़ा होता है।
• एम के अधिकतम इरेड्यूसिबल सबमैट्रोइड को एम का 'घटक' कहा जाता है। घटक इरेड्यूसेबल विभाजक के लिए एम का प्रतिबंध है, और इसके विपरीत, इरेड्यूसेबल विभाजक के लिए एम का प्रतिबंध घटक है। विभाजक घटकों का संघ है।* मैट्रोइड एम को 'फ्रेम मैट्रोइड' कहा जाता है यदि इसका, या जिस मैट्रोइड में यह शामिल है, उसका आधार ऐसा है कि एम के सभी बिंदु उन रेखाओं में समाहित हैं जो आधार तत्वों के जोड़े को जोड़ते हैं।
• मैट्रोइड को फ़र्श विधि कहा जाता है यदि उसके सभी सर्किट का आकार कम से कम उसके रैंक के बराबर हो।
• मैट्रोइड पॉलीटोप $P_{M}$ के आधारों के सूचक सदिशों का उत्तल पतवार है $M$.

एल्गोरिदम

लालची एल्गोरिदम

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

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

मैट्रोइड विभाजन

मैट्रोइड विभाजन समस्या में मैट्रोइड के तत्वों को यथासंभव कुछ स्वतंत्र सेटों में विभाजित करना है, और मैट्रोइड पैकिंग समस्या यथासंभव अधिक से अधिक असंयुक्त स्पैनिंग सेट ढूंढना है। दोनों को बहुपद समय में हल किया जा सकता है, और रैंक की गणना करने या मैट्रोइड योग में स्वतंत्र सेट खोजने की समस्या को सामान्यीकृत किया जा सकता है।

मैट्रोइड चौराहा

दो या दो से अधिक मैट्रोइड्स का मैट्रोइड प्रतिच्छेदन सेटों का परिवार है जो प्रत्येक मैट्रोइड्स में साथ स्वतंत्र होते हैं। दो मैट्रोइड्स के प्रतिच्छेदन में सबसे बड़ा सेट, या अधिकतम भारित सेट खोजने की समस्या बहुपद समय में पाई जा सकती है, और कई अन्य महत्वपूर्ण संयोजन अनुकूलन समस्याओं का समाधान प्रदान करता है। उदाहरण के लिए, द्विदलीय ग्राफ़ में अधिकतम मिलान को दो विभाजन मैट्रोइड्स को प्रतिच्छेद करने की समस्या के रूप में व्यक्त किया जा सकता है। हालाँकि, तीन या अधिक मैट्रोइड्स के प्रतिच्छेदन में सबसे बड़ा सेट ढूंढना एनपी-पूर्ण है।

मैट्रोइड सॉफ़्टवेयर

मैट्रोइड्स के साथ गणना के लिए दो स्टैंडअलोन प्रणालियाँ हैं किंगन की Oid और Hlineny की Macek . ये दोनों ओपन सोर्स पैकेज हैं। ओइड मैट्रोइड्स के साथ प्रयोग करने के लिए इंटरैक्टिव, एक्स्टेंसिबल सॉफ्टवेयर सिस्टम है। मैसेक विशेष सॉफ्टवेयर प्रणाली है जिसमें प्रतिनिधित्वयोग्य मैट्रोइड्स के साथ यथोचित कुशल संयोजन संगणना के लिए उपकरण और रूटीन हैं।

दोनों ओपन सोर्स गणित सॉफ्टवेयर सिस्टम SageMath और Macaulay2 में matroid पैकेज शामिल हैं।

बहुपद अपरिवर्तनीय

ग्राउंड सेट ई पर परिमित मैट्रोइड एम से जुड़े दो विशेष रूप से महत्वपूर्ण बहुपद हैं। प्रत्येक 'मैट्रोइड इनवेरिएंट' है, जिसका अर्थ है कि आइसोमोर्फिक मैट्रोइड्स में ही बहुपद होता है।

विशेषता बहुपद

M का विशिष्ट बहुपद (जिसे कभी-कभी रंगीन बहुपद भी कहा जाता है,हालाँकि यह रंगों की गिनती नहीं करता), को परिभाषित किया गया है

$p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},$

या समकक्ष (जब तक खाली सेट एम में बंद है)।

$p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)}\ ,$

जहां μ मैट्रोइड के ज्यामितीय जाली के मोबियस फ़ंक्शन (कॉम्बिनेटरिक्स) | मोबियस फ़ंक्शन को दर्शाता है और योग को मैट्रोइड के सभी फ्लैट्स ए पर लिया जाता है। जब M, ग्राफ G का चक्र मैट्रोइड M(G) है, तो विशेषता बहुपद रंगीन बहुपद का छोटा सा परिवर्तन है, जो χ द्वारा दिया गया है_G(λ) = λ^सीप_M(G)(λ), जहां c, G से जुड़े घटकों की संख्या है।

जब M, ग्राफ़ G का बॉन्ड मैट्रोइड M*(G) है, तो विशेषता बहुपद, G के टुटे बहुपद#प्रवाह बहुपद के बराबर होता है।

जब एम 'आर' में रैखिक हाइपरप्लेन के हाइपरप्लेन ए की व्यवस्था का मैट्रोइड एम (ए) हैⁿ (या एफⁿ जहां F कोई फ़ील्ड है), व्यवस्था का अभिलक्षणिक बहुपद p द्वारा दिया गया है_A(λ) = λ^n−r(M)p_M(एल).

बीटा अपरिवर्तनीय

हेनरी क्रैपो (गणितज्ञ) (1967) द्वारा प्रस्तुत मैट्रोइड के बीटा अपरिवर्तनीय को व्युत्पन्न के मूल्यांकन के रूप में विशेषता बहुपद पी के संदर्भ में व्यक्त किया जा सकता है।

$\beta (M)=(-1)^{r(M)-1}p_{M}'(1)\$

या सीधे तौर पर

$\beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X)\ .$

बीटा अपरिवर्तनीय गैर-नकारात्मक है, और शून्य है यदि और केवल यदि एम डिस्कनेक्ट हो गया है, या खाली है, या लूप है। अन्यथा यह केवल एम के फ्लैटों की जाली पर निर्भर करता है। यदि एम में कोई लूप और कोलूप नहीं है तो β(M) = β(M)^∗).

व्हिटनी संख्या

पहले प्रकार के एम के व्हिटनी नंबर की शक्तियों के गुणांक हैं $\lambda$ विशेषता बहुपद में. विशेष रूप से, i-वें व्हिटनी संख्या $w_{i}(M)$ का गुणांक है $\lambda ^{r(M)-i}$ और मोबियस फ़ंक्शन मानों का योग है:

$w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},$

सही रैंक के फ्लैटों का सारांश दिया गया। ये संख्याएँ संकेत में वैकल्पिक होती हैं, ताकि $(-1)^{i}w_{i}(M)>0$ के लिए $0\leq i\leq r(M).$ दूसरे प्रकार के एम के व्हिटनी नंबर प्रत्येक रैंक के फ्लैटों की संख्या हैं। वह है, $W_{i}(M)$ रैंक-I फ्लैट्स की संख्या है।

दोनों प्रकार के व्हिटनी नंबर पहले और दूसरे प्रकार के स्टर्लिंग संख्या ों को सामान्यीकृत करते हैं, जो पूर्ण ग्राफ के चक्र मैट्रोइड के व्हिटनी नंबर हैं और पार्टिशन_ऑफ_ए_सेट#रिफाइनमेंट_ऑफ_पार्टीशन के समकक्ष हैं। इनका नाम जियान-कार्लो रोटा द्वारा मैट्रोइड सिद्धांत के (सह) संस्थापक हस्लर व्हिटनी के नाम पर रखा गया था। नाम को परिमित श्रेणी वाले आंशिक रूप से क्रमित सेटों के लिए समान संख्याओं तक बढ़ा दिया गया है।

टुटे बहुपद

मैट्रोइड का टुटे बहुपद, टी_M(x,y), विशेषता बहुपद को दो चरों के लिए सामान्यीकृत करता है। यह इसे अधिक संयोजनात्मक व्याख्याएँ देता है, और इसे द्वैत गुण भी देता है

$T_{M^{*}}(x,y)=T_{M}(y,x),$

जो एम के गुणों और एम* के गुणों के बीच कई द्वंद्वों को दर्शाता है। टुट्टे बहुपद की परिभाषा है

$T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}(y-1)^{|S|-r(S)}.$

यह टुटे बहुपद को कॉरैंक-शून्यता या रैंक उत्पन्न करने वाले बहुपद के मूल्यांकन के रूप में व्यक्त करता है,

$R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}.$

इस परिभाषा से यह देखना आसान है कि विशेषता बहुपद, साधारण कारक तक, टी का मूल्यांकन है_M, विशेष रूप से,

$p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0).$

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

विलोपन और संकुचन द्वारा पुनरावर्तन के संदर्भ में और परिभाषा है। विलोपन-संकुचन पहचान है

$F(M)=F(M-e)+F(M/e)$ कब $e$ न तो लूप है और न ही कोलूप।

मैट्रोइड्स का अपरिवर्तनीय (यानी, फ़ंक्शन जो आइसोमोर्फिक मैट्रोइड्स पर समान मान लेता है) इस रिकर्सन और गुणक स्थिति को संतुष्ट करता है

$F(M\oplus M')=F(M)F(M')$

टुट्टे-ग्रोथेंडिक अपरिवर्तनीय कहा जाता है।टुट्टे बहुपद इस तरह का सबसे सामान्य अपरिवर्तनीय है; अर्थात्, टुट्टे बहुपद टुट्टे-ग्रोथेंडिक अपरिवर्तनीय है और ऐसा प्रत्येक अपरिवर्तनीय टुट्टे बहुपद का मूल्यांकन है। टुट्टे बहुपद टी_Gग्राफ का टुट्टे बहुपद T है_M(G) इसके चक्र मैट्रोइड का।

अनंत मैट्रोइड्स

अनंत मैट्रोइड्स का सिद्धांत परिमित मैट्रोइड्स की तुलना में बहुत अधिक जटिल है और इसका अपना विषय है। लंबे समय से, कठिनाई यह रही है कि कई उचित और उपयोगी परिभाषाएँ थीं, जिनमें से कोई भी परिमित मैट्रोइड सिद्धांत के सभी महत्वपूर्ण पहलुओं को पकड़ती नहीं थी। उदाहरण के लिए, अनंत मैट्रोइड्स की धारणा में आधार, सर्किट और द्वंद्व को साथ रखना कठिन प्रतीत होता है।

अनंत मैट्रोइड की सबसे सरल परिभाषा परिमित रैंक की आवश्यकता है; अर्थात्, E का पद परिमित है। यह सिद्धांत परिमित मैट्रोइड के समान है, इस तथ्य के कारण द्वैत की विफलता को छोड़कर कि परिमित रैंक के अनंत मैट्रोइड के दोहरे में परिमित रैंक नहीं है। परिमित-रैंक मैट्रोइड्स में परिमित-आयामी वेक्टर रिक्त स्थान और परिमित पारगमन डिग्री के फ़ील्ड (गणित) के किसी भी उपसमूह शामिल हैं।

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

$x\in \operatorname {cl} (Y)\ \Leftrightarrow \ {\text{ there is a finite set }}Y'\subseteq Y{\text{ such that }}x\in \operatorname {cl} (Y').$

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

1960 के दशक के अंत में मैट्रोइड सिद्धांतकारों ने अधिक सामान्य धारणा की मांग की जो परिमित मैट्रोइड के विभिन्न पहलुओं को साझा करती है और उनके द्वंद्व को सामान्य बनाती है। इस चुनौती के जवाब में अनंत मैट्रोइड्स की कई धारणाओं को परिभाषित किया गया, लेकिन प्रश्न खुला रहा। डी.ए. द्वारा जांचे गए दृष्टिकोणों में से एक। हिग्स को बी-मैट्रोइड्स के रूप में जाना जाने लगा और 1960 और 1970 के दशक में हिग्स, ऑक्सले और अन्य लोगों द्वारा इसका अध्ययन किया गया। द्वारा हाल ही में आये परिणाम के अनुसार Bruhn, Diestel, and Kriesell et al. (2013), यह समस्या का समाधान करता है: स्वतंत्र रूप से ही धारणा पर पहुंचते हुए, उन्होंने स्वतंत्रता, आधार, सर्किट, क्लोजर और रैंक के संदर्भ में स्वयंसिद्ध की पांच समकक्ष प्रणालियां प्रदान कीं। बी-मैट्रोइड्स का द्वंद्व उन द्वंद्वों को सामान्यीकृत करता है जिन्हें अनंत ग्राफ़ में देखा जा सकता है।

स्वतंत्रता के सिद्धांत इस प्रकार हैं:

1. खाली सेट स्वतंत्र है.
2. स्वतंत्र समुच्चय का प्रत्येक उपसमुच्चय स्वतंत्र होता है।
3. प्रत्येक अधिकतम तत्व (सेट समावेशन के तहत) के लिए स्वतंत्र सेट I और अधिकतम स्वतंत्र सेट J है $x\in J\smallsetminus I$ ऐसा है कि $I\cup \{x\}$ स्वतंत्र है.
4. आधार स्थान के प्रत्येक उपसमुच्चय X के लिए, X के प्रत्येक स्वतंत्र उपसमुच्चय I को X के अधिकतम स्वतंत्र उपसमुच्चय तक बढ़ाया जा सकता है।

इन सिद्धांतों के साथ, प्रत्येक मैट्रोइड में दोहरा होता है।

इतिहास

मैट्रोइड सिद्धांत किसके द्वारा प्रस्तुत किया गया था? Hassler Whitney (1935). इसकी खोज भी ताकेओ नाकासावा ने स्वतंत्र रूप से की थी, जिनके काम को कई वर्षों तक भुला दिया गया था (Nishimura & Kuroda 2009).

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

व्हिटनी द्वारा मैट्रोइड्स के बारे में पहली बार लिखने के लगभग तुरंत बाद, महत्वपूर्ण लेख लिखा गया था Saunders Mac Lane (1936) मैट्रोइड्स के प्रक्षेप्य ज्यामिति से संबंध पर। वर्ष बाद, B. L. van der Waerden (1937) आधुनिक बीजगणित पर अपनी क्लासिक पाठ्यपुस्तक में बीजगणितीय और रैखिक निर्भरता के बीच समानताएं नोट की गईं।

1940 के दशक में रिचर्ड राडो ने ट्रांसवर्सल (कॉम्बिनेटरिक्स) को ध्यान में रखते हुए इंडिपेंडेंस सिस्टम नाम से और सिद्धांत विकसित किया, जहां विषय के लिए उनका नाम अभी भी कभी-कभी उपयोग किया जाता है।

1950 के दशक में डब्ल्यू. टी. टुटे मैट्रोइड सिद्धांत में अग्रणी व्यक्ति बन गए, यह पद उन्होंने कई वर्षों तक बरकरार रखा। उनका योगदान प्रचुर मात्रा में था, जिसमें मैट्रोइड माइनर द्वारा बाइनरी मैट्रोइड, रेगुलर मैट्रोइड और ग्राफिक मैट्रोइड मैट्रोइड्स का लक्षण वर्णन शामिल था; रेगुलर-मैट्रोइड अभ्यावेदन प्रमेय; श्रृंखला समूहों और उनके मैट्रोइड्स का सिद्धांत; और अपने कई परिणामों को सिद्ध करने के लिए उन्होंने जिन उपकरणों का उपयोग किया, पथ प्रमेय और टूटे होमोटॉपी प्रमेय (देखें, उदाहरण के लिए, Tutte 1965), जो इतने जटिल हैं कि बाद के सिद्धांतकारों को प्रमाणों में उनका उपयोग करने की आवश्यकता को खत्म करने में बहुत परेशानी हुई। (अच्छा उदाहरण ए.एम.एच. जेरार्ड्स का टुटे के नियमित मैट्रोइड्स के लक्षण वर्णन का संक्षिप्त प्रमाण (#CITEREFGerards1989) है।)

Henry Crapo (1969) और Thomas Brylawski (1972) मैट्रोइड्स टुट्टे के डाइक्रोमेट के लिए सामान्यीकृत, ग्राफिक बहुपद जिसे अब टुट्टे बहुपद (क्रैपो द्वारा नामित) के रूप में जाना जाता है। उनके काम के बाद हाल ही में (विशेष रूप से 2000 के दशक में) कागजात की बाढ़ आ गई है - हालांकि ग्राफ के टुटे बहुपद के बराबर नहीं।

1976 में डोमिनिक वेल्श ने मैट्रोइड सिद्धांत पर पहली व्यापक पुस्तक प्रकाशित की।

नियमित मैट्रोइड्स के लिए पॉल सेमुर (गणितज्ञ) का अपघटन प्रमेय (#CITEREFSeymore1980) 1970 के दशक के अंत और 1980 के दशक का सबसे महत्वपूर्ण और प्रभावशाली काम था। और मौलिक योगदान, द्वारा Kahn & Kung (1982), दिखाया गया कि प्रोजेक्टिव ज्योमेट्री और डाउलिंग ज्यामिति मैट्रोइड सिद्धांत में इतनी महत्वपूर्ण भूमिका क्यों निभाते हैं।

इस समय तक कई अन्य महत्वपूर्ण योगदानकर्ता थे, लेकिन टुट्टे के बाइनरी मैट्रोइड्स के लक्षण वर्णन के ज्योफ व्हिटल के टर्नरी मैट्रोइड्स के विस्तार का उल्लेख करना नहीं भूलना चाहिए जो कि तर्कसंगत पर प्रतिनिधित्व योग्य हैं। (Whittle 1995), शायद 1990 के दशक का सबसे बड़ा एकल योगदान। वर्तमान अवधि में (2000 के आसपास से) जिम गिलेन, जेरार्ड्स, व्हिटल और अन्य का मैट्रोइड माइनर्स प्रोजेक्ट, जो सीमित क्षेत्र में प्रतिनिधित्व करने योग्य मैट्रोइड्स की नकल करने का प्रयास करता है, रॉबर्टसन-सेमुर ग्राफ माइनर्स प्रोजेक्ट की सफलता (रॉबर्टसन देखें) -सीमोर प्रमेय), ने मैट्रोइड्स के संरचना सिद्धांत में पर्याप्त प्रगति की है। कई अन्य लोगों ने भी मैट्रोइड सिद्धांत के उस हिस्से में योगदान दिया है, जो (21वीं सदी के पहले और दूसरे दशकों में) फल-फूल रहा है।

शोधकर्ता

मैट्रोइड्स के अध्ययन की शुरुआत करने वाले गणितज्ञों में ताकेओ नाकासावा, सॉन्डर्स मैक लेन, रिचर्ड राडो, डब्ल्यू. टी. टुट्टे, बार्टेल लिएन्डर्ट वान डेर वेर्डन|बी. एल वैन डेर वेर्डन, और हस्लर व्हिटनी। अन्य प्रमुख योगदानकर्ताओं में जैक एडमंड्स, जिम गिलेन, यूजीन लॉलर, लास्ज़लो लोवाज़, जियान-कार्लो रोटा, पॉल सेमुर (गणितज्ञ)|पी शामिल हैं। डी. सेमुर, और डोमिनिक वेल्श।

यह भी देखें

• एंटीमैट्रोइड
• कॉक्सेटर मैट्रोइड
• ओरिएंटेड मैट्रोइड
• प्रीजियोमेट्री (मॉडल सिद्धांत)
• पॉलीमेट्रोइड
• लालची

संदर्भ

• Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013), "Axioms for infinite matroids", Advances in Mathematics, 239: 18–46, arXiv:1003.3919, doi:10.1016/j.aim.2013.01.011, MR 3045140, S2CID 10436077.
• Bryant, Victor; Perfect, Hazel (1980), Independence Theory in Combinatorics, London and New York: Chapman and Hall, ISBN 978-0-412-22430-0.
• Brylawski, Thomas H. (1972), "A decomposition for combinatorial geometries", Transactions of the American Mathematical Society, 171: 235–282, doi:10.2307/1996381, JSTOR 1996381.
• Crapo, Henry H. (1969), "The Tutte polynomial", Aequationes Mathematicae, 3 (3): 211–229, doi:10.1007/BF01817442, S2CID 119602825.
• Crapo, Henry H.; Rota, Gian-Carlo (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries, Cambridge, Mass.: M.I.T. Press, ISBN 978-0-262-53016-3, MR 0290980.
• Geelen, Jim; Gerards, A. M. H.; Whittle, Geoff (2007), "Towards a matroid-minor structure theory", in Grimmett, Geoffrey; et al. (eds.), Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and its Applications, vol. 34, Oxford: Oxford University Press, pp. 72–82.
• Gerards, A. M. H. (1989), "A short proof of Tutte's characterization of totally unimodular matrices", Linear Algebra and Its Applications, 114/115: 207–212, doi:10.1016/0024-3795(89)90461-8.
• Kahn, Jeff; Kung, Joseph P. S. (1982), "Varieties of combinatorial geometries", Transactions of the American Mathematical Society, 271 (2): 485–499, doi:10.2307/1998894, JSTOR 1998894.
• Kingan, Robert; Kingan, Sandra (2005), "A software system for matroids", Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 287–296.
• Kung, Joseph P. S., ed. (1986), A Source Book in Matroid Theory, Boston: Birkhäuser, doi:10.1007/978-1-4684-9199-9, ISBN 978-0-8176-3173-4, MR 0890330.
• Mac Lane, Saunders (1936), "Some interpretations of abstract linear dependence in terms of projective geometry", American Journal of Mathematics, 58 (1): 236–240, doi:10.2307/2371070, JSTOR 2371070.
• Minty, George J. (1966), "On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming", Journal of Mathematics and Mechanics, 15: 485–520, MR 0188102.
• Nishimura, Hirokazu; Kuroda, Susumu, eds. (2009), A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory, Basel: Birkhäuser Verlag, doi:10.1007/978-3-7643-8573-6, ISBN 978-3-7643-8572-9, MR 2516551, Zbl 1163.01001.
• Oxley, James (1992), Matroid Theory, Oxford: Oxford University Press, ISBN 978-0-19-853563-8, MR 1207587, Zbl 0784.05002.
• Recski, András (1989), Matroid Theory and its Applications in Electric Network Theory and in Statics, Algorithms and Combinatorics, vol. 6, Berlin and Budapest: Springer-Verlag and Akademiai Kiado, doi:10.1007/978-3-662-22143-3, ISBN 978-3-540-15285-9, MR 1027839, S2CID 117772439.
• Sapozhenko, A.A. (2001) [1994], "मैट्रोइड", Encyclopedia of Mathematics, EMS Press
• Seymour, Paul D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, hdl:10338.dmlcz/101946, Zbl 0443.05027.
• Truemper, Klaus (1992), Matroid Decomposition, Boston: Academic Press, ISBN 978-0-12-701225-4, MR 1170126.
• Tutte, W. T. (1959), "Matroids and graphs", Transactions of the American Mathematical Society, 90 (3): 527–552, doi:10.2307/1993185, JSTOR 1993185, MR 0101527.
• Tutte, W. T. (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards Section B, 69: 1–47.
• Tutte, W.T. (1971), Introduction to the theory of matroids, Modern Analytic and Computational Methods in Science and Mathematics, vol. 37, New York: American Elsevier Publishing Company, Zbl 0231.05027.
• Vámos, Peter (1978), "The missing axiom of matroid theory is lost forever", Journal of the London Mathematical Society, 18 (3): 403–408, doi:10.1112/jlms/s2-18.3.403.
• van der Waerden, B. L. (1937), Moderne Algebra.
• Welsh, D. J. A. (1976), Matroid Theory, L.M.S. Monographs, vol. 8, Academic Press, ISBN 978-0-12-744050-7, Zbl 0343.05002.
• White, Neil, ed. (1986), Theory of Matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl 0579.00001.
• White, Neil, ed. (1987), Combinatorial geometries, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge: Cambridge University Press, ISBN 978-0-521-33339-9, Zbl 0626.00007
• White, Neil, ed. (1992), Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, ISBN 978-0-521-38165-9, Zbl 0742.00052.
• Whitney, Hassler (1935), "On the abstract properties of linear dependence", American Journal of Mathematics, 57 (3): 509–533, doi:10.2307/2371182, hdl:10338.dmlcz/100694, JSTOR 2371182, MR 1507091. Reprinted in Kung (1986), pp. 55–79.
• Whittle, Geoff (1995), "A characterization of the matroids representable over GF(3) and the rationals", Journal of Combinatorial Theory, Series B, 65 (2): 222–261, doi:10.1006/jctb.1995.1052.

बाहरी संबंध

• "Matroid", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Kingan, Sandra : Matroid theory. A large bibliography of matroid papers, matroid software, and links.
• Locke, S. C. : Greedy Algorithms.
• Pagano, Steven R. : Matroids and Signed Graphs.
• Mark Hubenthal: A Brief Look At Matroids (PDF) (contain proofs for statements of this article)
• James Oxley : What is a matroid? (PDF)
• Neil White : Matroid Applications