मैट्रोइड

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)\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}}$ निम्नलिखित गुणों के साथ पावर सेट को दर्शाता है:

• (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)$ है।

इनमें से पसमाधाने तीन गुण क्लोजर ऑपरेटर के परिभाषित गुण हैं। चौथे को कभी-कभी मैक लेन-अर्नेस्ट स्टीनिट्ज़ विनिमय गुण कहा जाता है। इन गुणों को मैट्रोइड की परिभाषा के रूप में लिया जा सकता है: प्रत्येक फलन $\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$ आइसोमोर्फिक है।

हाइपरप्लेन

पद के मेट्रोइड में $r$, पद का फ्लैट $r-1$ को हाइपरप्लेन कहा जाता है (हाइपरप्लेन को कोटम या सह-बिंदु भी कहा जाता है।) ये अधिकतम उचित फ्लैट हैं; अर्थात, हाइपरप्लेन का एकमात्र उप-समुच्चय जो फ्लैट भी है, समुच्चय मैट्रोइड के सभी तत्वों $E$ की समतुल्य परिभाषा यह है कि कोटोम $E$ का उपसमुच्चय है जो M तक नहीं विस्तारित है, किंतु ऐसा है कि इसमें कोई अन्य तत्व जोड़ने से स्पैनिंग समुच्चय बन जाता है।

सदस्य मैट्रोइड के हाइपरप्लेन के ${\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\}$ (सिंगलटन समुच्चय), फिर या तो $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 पद के सभी समान मैट्रोइड सरल हैं (देखें)। § अतिरिक्त शब्दावली) पद 2 की यूनिफार्म मैट्रोइड पर $n$ अंक को कहा जाता है $n$-बिंदु रेखा मैट्रोइड के समान होती है यदि केवल तभी जब इसमें मैट्रोइड का पद प्लस से कम आकार का कोई परिपथ न हो। एकसमान मैट्रोइड्स के प्रत्यक्ष योग को विभाजन मैट्रोइड्स कहा जाता है।

यूनिफार्म मेट्रोइड में $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 के दशक) के कारण बाइनरी मैट्रोइड्स (GF (2) पर प्रतिनिधित्व योग्य), रीड एवं बिक्सबी के कारण टर्नरी मैट्रोइड्स (3-तत्व क्षेत्र पर प्रतिनिधित्व योग्य) एवं भिन्न से सेमुर (1970 के दशक) के लक्षण वर्णन हैं।) एवं गिलेन, जेरार्ड्स एवं कपूर (2000) के कारण चतुर्धातुक मैट्रोइड्स (4-तत्व क्षेत्र पर प्रतिनिधित्व योग्य) यह अधिक ओपन क्षेत्र है।

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

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

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

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

ग्राफ़ पर अन्य मैट्रोइड्स पश्चात में परिक्षण किये गए:

• ग्राफ के द्विवृत्ताकार मैट्रोइड को किनारों के समुच्चय को स्वतंत्र कहकर परिभाषित किया जाता है यदि प्रत्येक जुड़े उपसमुच्चय में अधिकतम चक्र होता है।
• किसी भी निर्देशित या अप्रत्यक्ष ग्राफ़ में $G$ मान लीजिये $E$ एवं $F$ शीर्षों के दो विशिष्ट समुच्चय हैं। सेट में $E$, उपसमुच्चय परिभाषित करें यदि हैं तो स्वतंत्र रहें $|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$ समुच्चय है इसके स्वतंत्र समुच्चयों के वर्ग के रूप में, मैट्रोइड है जिसे बॉन्ड मैट्रोइड कहा जाता है $G$ पद फलन $r(F)$ किनारे उपसमुच्चय पर प्रेरित उपग्राफ की चक्रीय संख्या है $F$, जो उस उपसमूह के अधिकतम जंगल के बाहर किनारों की संख्या एवं उसमें स्वतंत्र चक्रों की संख्या के समान है।

क्षेत्र एक्सटेंशन से मैट्रोइड्स

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

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

मैट्रोइड जो इस प्रकार के मैट्रोइड के समान होता है उसे बीजगणितीय मैट्रोइड कहा जाता है।बीजगणितीय मैट्रोइड्स को चिह्नित करने की समस्या अत्यंत कठिन है; इसके बारे में अधिक कम जानकारी है, वैमोस मैट्रोइड का उदाहरण प्रदान करता है जो बीजगणितीय नहीं है।

मूलभूत निर्माण

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

द्वैत

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

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

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

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

उदाहरण

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

माइनर्स

Main article: मैट्रोइड माइनर

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

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

योग एवं संघ

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

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

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

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

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

एल्गोरिदम

ग्रेडी एल्गोरिदम

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

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

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

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

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

मैट्रोइड अंत:खंड

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

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

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

दोनों ओपन सोर्स गणित सॉफ्टवेयर प्रणाली सेग एवं मैकाले2 में मेट्रोइड पैकेज सम्मिलित हैं।

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

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

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

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

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

या समकक्ष (जब तक रिक्त समुच्चय M में संवृत है)।

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

जहां μ मैट्रोइड के ज्यामितीय लैटिस के मोबियस फलन (कॉम्बिनेटरिक्सको दर्शाता है एवं योग को मैट्रोइड के सभी फ्लैट्स A पर लिया जाता है।

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

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

जब M 'Rⁿ' (या Fn जहां F कोई क्षेत्र है) में रैखिक हाइपरप्लेन की व्यवस्था A का मैट्रोइड M(A) है, तो व्यवस्था का विशिष्ट बहुपद p_A (λ) = λ^n−r(M)p_M (λ) द्वारा दिया जाता है।

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

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

$\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)^∗) होता है।

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

प्रथम प्रकार के 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).$ है।

दूसरे प्रकार के M के व्हिटनी नंबर प्रत्येक पद के फ्लैटों की संख्या हैं। वह है, $W_{i}(M)$ पद-I फ्लैट्स की संख्या है।

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

टुट्टे बहुपद

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

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

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

$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).$

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

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

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

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

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

कहा जाता है कि यह टुट्टे-ग्रोथेंडिक अपरिवर्तनीय है।टुट्टे बहुपद इस प्रकार का सबसे सामान्य अपरिवर्तनीय है; अर्थात्, टुट्टे बहुपद टुट्टे-ग्रोथेंडिक अपरिवर्तनीय है एवं ऐसा प्रत्येक अपरिवर्तनीय टुट्टे बहुपद का मूल्यांकन है।

ग्राफ का टुट्टे बहुपद T_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 दशक में हिग्स, ऑक्सले एवं अन्य लोगों द्वारा इसका अध्ययन किया गया। ब्रुहन, डायस्टेल एवं क्रिसेल एट अल के परिणाम के अनुसार (2013), यह समस्या का समाधान करता है: स्वतंत्र रूप से एक ही धारणा पर पहुंचते हुए, उन्होंने स्वतंत्रता, आधार, परिपथ, क्लोजर एवं पद के संदर्भ में स्वयंसिद्ध की पांच समकक्ष प्रणालियां प्रदान कीं। बी-मैट्रोइड्स का द्वंद्व उन द्वंद्वों को सामान्यीकृत करता है जिन्हें अनंत ग्राफ़ में देखा जा सकता है।

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

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

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

इतिहास

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

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

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

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

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

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

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

नियमित मैट्रोइड्स के लिए पॉल सेमुर (गणितज्ञ) का अपघटन प्रमेय (1980) 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 : मेट्रोइड theory. A large bibliography of मेट्रोइड papers, मेट्रोइड software, and links.
• Locke, S. C. : Greedy Algorithms.
• Pagano, Steven R. : मेट्रोइडs and Signed Graphs.
• Mark Hubenthal: A Brief Look At मेट्रोइडs (PDF) (contain proofs for statements of this article)
• James Oxley : What is a मेट्रोइड? (PDF)
• Neil White : मेट्रोइड Applications