Matroid

Not to be confused with Metroid or Meteoroid.

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

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

परिभाषा

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

स्वतंत्र सेट

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

निर्भर सेट, आधार, या एक मेट्रॉइड के सर्किट पूरी तरह से मैट्रॉइड की विशेषता बताते हैं: एक सेट स्वतंत्र है अगर और केवल अगर यह निर्भर नहीं है, अगर और केवल अगर यह एक आधार का सबसेट है, और अगर और केवल अगर यह करता है एक सर्किट शामिल नहीं है। आश्रित सेटों, आधारों और सर्किटों के संग्रह में प्रत्येक में सरल गुण होते हैं जिन्हें मैट्रोइड के लिए सिद्धांतों के रूप में लिया जा सकता है। उदाहरण के लिए, कोई matroid को परिभाषित कर सकता है $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}}$ दूसरे का उचित उपसमुच्चय हो सकता है।

रैंक कार्य

यह matroid सिद्धांत का एक मूल परिणाम है, सीधे आधार के समान प्रमेय (रैखिक बीजगणित) के समान है, कि एक matroid के किसी भी दो आधार $M$ तत्वों की समान संख्या है। इस संख्या को मैट्रोइड रैंक कहा जाता है$M$. अगर $M$ मैट्रॉइड ऑन है $E$, और $A$ का उपसमुच्चय है $E$, फिर एक मैट्रॉइड ऑन $A$ के एक उपसमुच्चय पर विचार करके परिभाषित किया जा सकता है $A$ स्वतंत्र होने के लिए अगर और केवल अगर यह स्वतंत्र है $M$. यह हमें सबमेट्रोइड्स के बारे में और किसी भी सबसेट के रैंक के बारे में बात करने की अनुमति देता है $E$. एक उपसमुच्चय का पद $A$ matroid रैंक द्वारा दिया गया है $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)\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$ एक परिमित सेट पर एक matroid बनें $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}}$ निम्नलिखित गुणों के साथ सत्ता स्थापित को दर्शाता है:

• (C1) सभी उपसमूहों के लिए $X$ का $E$, $X\subseteq \operatorname {cl} (X)$.
• (C2) सभी उपसमुच्चयों के लिए $X$ का $E$, $\operatorname {cl} (X)=\operatorname {cl} (\operatorname {cl} (X))$.
• (C3) सभी उपसमूहों के लिए $X$ और $Y$ का $E$ साथ $X\subseteq Y$, $\operatorname {cl} (X)\subseteq \operatorname {cl} (Y)$.
• (C4) सभी तत्वों के लिए $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)$.

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

फ्लैट

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

• (F1) संपूर्ण बिंदु सेट $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$ matroid के सभी तत्वों की। एक समकक्ष परिभाषा यह है कि एक कोटॉम ई का एक उपसमुच्चय है जो एम तक नहीं फैलता है, लेकिन ऐसा है कि इसमें कोई अन्य तत्व जोड़ने से एक फैलाव सेट हो जाता है। परिवार ${\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$ (कोसर्किट कहा जाता है) में एक और होता है,
• (G3) कोई सेट नहीं है $C$ और सेट करें $D$ बिल्कुल एक तत्व में प्रतिच्छेद करें, और
• (G4) जब भी $L$ उपसमुच्चय के असंयुक्त संघ के रूप में प्रतिनिधित्व किया जाता है $R,G,B$ साथ $G=\{g\}$ (एक सिंगलटन सेट), फिर या तो a $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)$ एक ग्रेफॉइड है। इस प्रकार, ग्राफ़ोइड्स मैट्रोइड्स के एक स्व-दोहरी क्रिप्टोमोर्फिक स्वयंसिद्धकरण देते हैं।

उदाहरण

मुक्त matroid

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

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

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

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

रेखीय बीजगणित से matroids

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

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

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

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

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

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

ग्राफ थ्योरी से मैट्रोइड्स

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

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

रेखांकन पर अन्य matroids बाद में खोजे गए:

• एक ग्राफ के द्विवृत्ताकार मैट्रोइड को किनारों के एक सेट को कॉल करके परिभाषित किया जाता है यदि प्रत्येक जुड़े सबसेट में अधिकतम एक चक्र होता है।
• किसी भी निर्देशित या अप्रत्यक्ष ग्राफ में $G$ होने देना $E$ और $F$ शीर्षों के दो विशिष्ट समुच्चय हों। सेट में $E$, एक उपसमुच्चय परिभाषित करें $U$ स्वतंत्र होने के लिए अगर वहाँ हैं $|U|$ वर्टेक्स-डिसजॉइंट पाथ फ्रॉम $F$ पर $U$. यह एक matroid को परिभाषित करता है $E$ गैमॉइड कहा जाता है:एक सख्त गैमॉइड वह है जिसके लिए सेट है $E$ का संपूर्ण शीर्ष समुच्चय है $G$.
• द्विदलीय ग्राफ में $G=(U,V,E)$, कोई एक मैट्रॉइड बना सकता है जिसमें तत्व एक तरफ कोने होते हैं $U$ द्विदलीय और स्वतंत्र उपसमुच्चय ग्राफ़ के मिलान (ग्राफ़ सिद्धांत) के समापन बिंदुओं के सेट हैं। इसे ट्रांसवर्सल मैट्रॉइड कहा जाता है, और यह गैमॉइड का एक विशेष मामला है। अनुप्रस्थ matroids सख्त गैमोइड्स के लिए दोहरी matroids हैं।* ग्राफिक मैट्रोइड्स को हस्ताक्षरित ग्राफ़, लाभ ग्राफ ़ और पक्षपाती ग्राफ़ से मैट्रोइड्स के लिए सामान्यीकृत किया गया है। एक ग्राफ $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|$. एक matroid जो इस तरह के एक matroid के बराबर है बीजगणितीय matroid कहा जाता है। बीजगणितीय मैट्रोइड्स को चिह्नित करने की समस्या अत्यंत कठिन है; इसके बारे में बहुत कम जाना जाता है। वामोस मैट्रॉइड एक मैट्रॉइड का उदाहरण प्रदान करता है जो बीजगणितीय नहीं है।

मूल निर्माण

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

द्वैत

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

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

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

'उदाहरण'

एक ग्राफ का चक्र मैट्रॉइड इसके बॉन्ड मैट्रॉइड का दोहरा मैट्रॉइड है।

अवयस्क

Main article: Matroid minor

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

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

रकम और संघ

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

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

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

एम को तत्वों ई के अंतर्निहित सेट के साथ एक मैट्रॉइड होने दें।

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

एल्गोरिदम

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

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

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

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

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

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

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

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

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

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

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

ग्राउंड सेट E पर परिमित matroid M से जुड़े दो विशेष रूप से महत्वपूर्ण बहुपद हैं। प्रत्येक एक 'matroid invariant' है, जिसका अर्थ है कि isomorphic matroids में एक ही बहुपद है।

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

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

$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)(λ), जहां सी जी के जुड़े घटकों की संख्या है।

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

जब एम 'आर' में रैखिक हाइपरप्लेन के हाइपरप्लेन ए की व्यवस्था का मैट्रॉइड एम (ए) हैⁿ (या Fⁿ जहां F कोई क्षेत्र है), व्यवस्था का अभिलाक्षणिक बहुपद p द्वारा दिया गया है_A(λ) = λ^{एन−आर(एम)}पी_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 में कोई लूप और कोलूप नहीं है तो β(M) = β(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 फ्लैटों की संख्या है।

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

टूटे बहुपद

एक matroid के Tutte बहुपद, टी_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)}.$

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

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

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

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

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

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

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

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

अनंत matroids

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

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

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

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

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

1960 के दशक के अंत में matroid सिद्धांतकारों ने एक अधिक सामान्य धारणा के लिए कहा जो कि परिमित matroids के विभिन्न पहलुओं को साझा करता है और उनके द्वंद्व को सामान्य करता है। इस चुनौती के जवाब में अनंत मैट्रोइड्स की कई धारणाएं परिभाषित की गईं, लेकिन सवाल खुला रहा। डीए द्वारा जांचे गए दृष्टिकोणों में से एक। हिग्स को बी-मैट्रोइड्स के रूप में जाना जाता है और 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 के दशक में W. T. Tutte matroid सिद्धांत में अग्रणी व्यक्ति बन गए, एक स्थिति जिसे उन्होंने कई वर्षों तक बनाए रखा। उनका योगदान बहुतायत से था, जिसमें बाइनरी मैट्रोइड, रेगुलर मैट्रॉइड, और मैट्रोइड माइनर द्वारा ग्राफिक मैट्रोइड मैट्रोइड्स का लक्षण वर्णन शामिल था; नियमित-मैट्रॉइड प्रतिनिधित्व क्षमता प्रमेय; श्रृंखला समूहों और उनके मैट्रोइड्स का सिद्धांत; और उन्होंने अपने कई परिणामों को साबित करने के लिए जिन उपकरणों का इस्तेमाल किया, पथ प्रमेय और टुट्टे होमोटॉपी प्रमेय (देखें, उदाहरण के लिए, Tutte 1965), जो इतने जटिल हैं कि बाद के सिद्धांतकारों को सबूतों में उनका उपयोग करने की आवश्यकता को खत्म करने में बड़ी परेशानी हुई है। (एक अच्छा उदाहरण ए. एम. एच. जेरार्ड्स का संक्षिप्त प्रमाण (#CITEREFGerards1989) टुट्टे के नियमित मैट्रोइड्स के चरित्र-चित्रण का है।)

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

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

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

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

शोधकर्ता

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

यह भी देखें

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

संदर्भ

• 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], "Matroid", 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