मैट्रोइड

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$ विभाजक है।

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

Error creating thumbnail:

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

File:Vamos matroid.svg

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

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

• यदि $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 में मेट्रोइड पैकेज सम्मिलित हैं।

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

ग्राउंड समुच्चय ई पर परिमित मैट्रोइड 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)}\ ,$

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

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

जब M 'आर' में रैखिक हाइपरप्लेन के हाइपरप्लेन ए की व्यवस्था का मैट्रोइड M (ए) हैⁿ (या एफⁿ जहां 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 के फ्लैटों की जाली पर निर्भर करता है। यदि 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 फ्लैट्स की संख्या है।

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

टुटे बहुपद

मैट्रोइड का टुटे बहुपद, टी_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)}.$

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