ओरिएंटेड मैट्रोइड

अभिविन्यस्त-मैट्रॉइड सिद्धांत मैक्स-फ्लो मिन-कट प्रमेय के लिए एक संयुक्त दृष्टिकोण की अनुमति देता है। एक सेंट कट की क्षमता के बराबर प्रवाह के मान वाला एक नेटवर्क

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

^[3]सभी अभिविन्यस्त मैट्रॉइड में एक अंतर्निहित मैट्रॉइड है। इस प्रकार, सामान्य मैट्रॉइड पर परिणाम अभिविन्यस्त मैट्रॉइड पर लागू किया जा सकता है। हालाँकि, रूपांतरण (तर्क) अमान्य है; अंतर्निहित संरचना (जैसे, परिपथ या स्वतंत्र समुच्चय) को अभिविन्यस्त करके कुछ मैट्रोइड एक अभिविन्यस्त मैट्रॉइड नहीं बन सकते हैं।^[4] मैट्रोइड्स और अभिविन्यस्त मैट्रोड्स के बीच अंतर पर नीचे चर्चा की गई है।

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

पृष्ठभूमि

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

एक हस्ताक्षरित समुच्चय, $X$ , वस्तुओं के एक समूह को जोड़ती है, ${\underline {X}}$ , उस समुच्चय के विभाजन के साथ दो उपसमुच्चय में: $X^{+}$ और $X^{-}$ के सदस्य $X^{+}$ सकारात्मक अवयव कहलाते हैं; जो कि $X^{-}$ सदस्यों के नकारात्मक अवयव हैं।

समुच्चय ${\underline {X}}=X^{+}\cup X^{-}$ का समर्थन कहा जाता है $X$ .
रिक्त हस्ताक्षरित समुच्चय, $\emptyset$ , रिक्त समुच्चय के रूप में परिभाषित किया गया है ${\underline {\emptyset }}$ इसके विभाजन के साथ दो रिक्त समुच्चयों में संयुक्त: $\emptyset ^{+}$ और $\emptyset ^{-}$ हैं।
हस्ताक्षरित समुच्चय $Y$ के विपरीत $X$ है, अर्थात, $Y=-X$ , यदि $Y^{+}=X^{-}$ और $Y^{-}=X^{+}$ हैं।

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

अभिगृहीतीकरण

साधारण मैट्रोइड्स की तरह, कई समतुल्य अभिगृहीत प्रणाली सम्मलित हैं। (ऐसी संरचनाएं जिनमें एकाधिक समकक्ष अभिगृहीताएं होती हैं, क्रिप्टोमोर्फिज्म कहलाती हैं।)

परिपथ अभिगृहीत

यदि $E$ कोई समुच्चय हो तो हम $E$ ग्राउंड समुच्चय के रूप में सन्दर्भ देते है। यदि ${\mathcal {C}}$ हस्ताक्षरित समुच्चयों का एक संग्रह हो, जिनमें से प्रत्येक एक उपसमुच्चय द्वारा समर्थित $E$ हो, यदि निम्नलिखित अभिगृहीत ${\mathcal {C}}$ धारण करते हैं, तो अभिविन्यस्त मैट्रॉइड के लिए $E$ फिर समकक्ष ${\mathcal {C}}$ हस्ताक्षरित परिपथ का समुच्चय हो जायेगा।

(C0) $\emptyset \notin {\mathcal {C}}$
(C1) (सममित) ${\text{ For all }}X\in {\mathcal {C}},~-\!X\in {\mathcal {C}}.$
(C2) (अतुलनीय) ${\text{ For all }}X,Y\in {\mathcal {C}},~~{\text{ if }}{\underline {X}}\subseteq {\underline {Y}}{\text{ then }}(X=Y{\text{ or }}X=-Y).$
(C3) (असमर्थ उन्मूलन) ${\text{ For all }}X,Y\in {\mathcal {C}},X\neq -Y{\text{ with an }}e\in X^{+}\cap Y^{-}{\text{ there is a }}Z\in {\mathcal {C}}{\text{ such that }}$ ${\text{ For all }}X,Y\in {\mathcal {C}},X\neq -Y{\text{ with an }}e\in X^{+}\cap Y^{-}{\text{ there is a }}Z\in {\mathcal {C}}{\text{ such that }}$
- $Z^{+}\subseteq (X^{+}\cup Y^{+})\setminus \{e\}{\text{ and }}$
- $Z^{-}\subseteq (X^{-}\cup Y^{-})\setminus \{e\}.$

सदिश अभिगृहीत

हस्ताक्षरित समुच्चय की संरचना $X$ और $Y$ हस्ताक्षरित समुच्चय $X\circ Y$ द्वारा परिभाषित है,

${\underline {X\circ Y}}={\underline {X}}\cup {\underline {Y}}$ , $(X\circ Y)^{+}=X^{+}\cup \left(Y^{+}\setminus X^{-}\right)$ , और $(X\circ Y)^{-}=X^{-}\cup \left(Y^{-}\setminus X^{+}\right)$ .

एक अभिविन्यस्त मैट्रोइड के सदिश परिपथ की रचनाएं हैं। सदिश ${\mathcal {V}}$ एक अभिविन्यस्त मैट्रोइड के निम्नलिखित अभिगृहीतों को संतुष्ट करते हैं:

$\emptyset \in {\mathcal {V}}$ * ${\mathcal {V}}=-{\mathcal {V}}$
सभी के लिए $X,Y\in {\mathcal {V}}$ , $X\circ Y\in {\mathcal {V}}$
सभी के लिए $X,Y\in {\mathcal {V}}$ $X,Y\in {\mathcal {V}}$ , $e\in X^{+}\cap Y^{-}$ $e\in X^{+}\cap Y^{-}$ और $f\in ({\underline {X}}\setminus {\underline {Y}})\cup ({\underline {Y}}\setminus {\underline {X}})\cup (X^{+}\cap Y^{+})\cup (X^{-}\cap Y^{-})$ $f\in ({\underline {X}}\setminus {\underline {Y}})\cup ({\underline {Y}}\setminus {\underline {X}})\cup (X^{+}\cap Y^{+})\cup (X^{-}\cap Y^{-})$ , वहां एक है $Z\in {\mathcal {V}}$ $Z\in {\mathcal {V}}$ , ऐसा है कि
- $Z^{+}\subset X^{+}\cup Y^{+}\setminus e$ ,
- $Z^{-}\subset X^{-}\cup Y^{-}\setminus e$ , और
- $f\in {\underline {Z}}$ .

चिरोटोप अभिगृहीत

यदि $E$ ऊपर जैसा हो। प्रत्येक गैर-ऋणात्मक पूर्णांक के लिए $r$ , श्रेणी का चिरोटोप $r$ एक फलन है $\chi \colon E^{r}\to \{-1,0,1\}$ जो निम्नलिखित अभिगृहीतों को संतुष्ट करता है:

(B0) (गैर तुच्छ): $\chi$ समान शून्य नहीं है
(B1) (वैकल्पिक): किसी भी क्रमपरिवर्तन के लिए $\sigma$ और $x_{1},\dots ,x_{r}\in E$ , $\chi \left(x_{\sigma (1)},\dots ,x_{\sigma (r)}\right)=\operatorname {sgn} (\sigma )\chi \left(x_{1},\dots ,x_{r}\right)$ , जहाँ $\operatorname {sgn} (\sigma )$ के क्रमपरिवर्तन की समानता है।
(B2) (स्थानांतरण): किसी के लिए भी $x_{1},\dots ,x_{r},y_{1},\dots ,y_{r}\in E$ ऐसा है कि $\chi (y_{i},x_{2},\dots ,x_{r})\chi (y_{1},\dots ,y_{i-1},x_{1},y_{i+1},\dots ,y_{r})\geq 0$ प्रत्येक के लिए $i$ है $\chi \left(x_{1},\dots ,x_{r}\right)\chi \left(y_{1},\dots ,y_{r}\right)\geq 0$ .

चिरोटोप शब्द को चिरलिटी (गणित) की गणितीय धारणा से लिया गया है, जो कि चिरलिटी (रसायन विज्ञान) से अलग की गई अवधारणा है, जहाँ इसका उपयोग उन अणुओं को अलग करने के लिए किया जाता है जिनकी संरचना एक प्रतिबिंब के अतिरिक्त समान होती है।

समानता

श्रेणी का हर चिरोटोप $r$ एक मैट्रोइड के आधारों के एक समुच्चय को उत्पन्न करता है $E$ उन से मिलकर $r$ -अवयव उसे उपसमुच्चय $\chi$ करता है, और एक अशून्य मान प्रदान करता है और क्रमबद्ध किए गए क्षेत्र (गणित) पर सदिश की व्यवस्था के लिए जो जरूरी नहीं हैं।^[5] चिरोटोप तब उस मैट्रोइड के परिपथ पर हस्ताक्षर कर सकता है। यदि $C$ वर्णित मैट्रोइड का एक परिपथ है, फिर $C\subset \{x_{1},\dots ,x_{r},x_{r+1}\}$ जहाँ $\{x_{1},\dots ,x_{r}\}$ एक आधार है। तब $C$ सकारात्मक अवयवों के साथ हस्ताक्षर किए जा सकते हैं,

C^{+}=\{x_{i}:(-1)^{i}\chi (x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{r+1})=1\}

और नकारात्मक अवयव पूरक हैं। इस प्रकार एक चिरोटोप एक अभिविन्यस्त मैट्रॉइड के अभिविन्यस्त आधारों को उत्पन्न करता है। इस अर्थ में, (B0) आधारों के लिए गैर-रिक्त अभिगृहीत है और (B2) आधार विनिमय गुणधर्म है।

उदाहरण

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

निर्देशित रेखांकन

एक निर्देशित रेखाचित्र को देखते हुए, हम निम्नलिखित विधि द्वारा रेखाचित्र के मानक चक्र (रेखाचित्र सिद्धांत) से एक हस्ताक्षरित परिपथ को परिभाषित करते हैं। हस्ताक्षरित परिपथ का समर्थन $\textstyle {\underline {X}}$ न्यूनतम चक्र में किनारों का मानक समुच्चय है। हम चक्र के साथ दक्षिणावर्त या वामावर्त दिशा में उन किनारों को निर्दिष्ट करते हैं जिनका अभिविन्यास सकारात्मक अवयवों की दिशा $\textstyle X^{+}$ से सहमत है और वे किनारे जिनका अभिविन्यास नकारात्मक अवयवों की दिशा $\textstyle X^{-}$ से असहमत है, यदि $\textstyle {\mathcal {C}}$ ऐसे सभी का समुच्चय $\textstyle X$ है, तब $\textstyle {\mathcal {C}}$ निर्देशित रेखाचित्र के किनारों के समुच्चय पर एक अभिविन्यस्त मैट्रोइड के हस्ताक्षरित परिपथ का समुच्चय है।

निर्देशित रेखाचित्र

यदि हम दाईं ओर निर्देशित रेखाचित्र पर विचार करें, तो हम देख सकते हैं कि केवल दो परिपथ हैं, अर्थात् $\textstyle \{(1,2),(1,3),(3,2)\}$ और $\textstyle \{(3,4),(4,3)\}$ .

इसके बाद दक्षिणावर्त और वामावर्त अभिविन्यास के अनुरूप केवल चार संभावित हस्ताक्षरित परिपथ हैं, अर्थात् $\textstyle \{(1,2),-(1,3),-(3,2)\}$ , $\textstyle \{-(1,2),(1,3),(3,2)\}$ , $\textstyle \{(3,4),(4,3)\}$ , और $\textstyle \{-(3,4),-(4,3)\}$ .

ये चार समुच्चय पर एक अभिविन्यस्त मैट्रोइड के हस्ताक्षरित परिपथ का समुच्चय बनाते हैं $\textstyle \{(1,2),(1,3),(3,2),(3,4),(4,3)\}$ .

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

यदि $\textstyle E$ का कोई परिमित उपसमुच्चय $\textstyle \mathbb {R} ^{n}$ है, तो न्यूनतम रैखिक रूप से निर्भर समुच्चयों का समुच्चय एक मैट्रोइड के परिपथ समुच्चय $\textstyle E$ का निर्माण करता है, प्रत्येक परिपथ के लिए इस निर्माण को अभिविन्यस्त मैट्रोइड्स तक विस्तारित करने के लिए $\textstyle \{v_{1},\dots ,v_{m}\}$ न्यूनतम रैखिक निर्भरता निहित है।

\sum _{i=1}^{m}\lambda _{i}v_{i}=0

साथ ही $\textstyle \lambda _{i}\in \mathbb {R}$ . हस्ताक्षरित परिपथ $\textstyle X=\{X^{+},X^{-}\}$ सकारात्मक अवयव $\textstyle X^{+}=\{v_{i}:\lambda _{i}>0\}$ हैं और नकारात्मक अवयव $\textstyle X^{-}=\{v_{i}:\lambda _{i}<0\}$ . ऐसे सभी का समुच्चय $\textstyle X$ अभिविन्यस्त मैट्रोइड ऑन के हस्ताक्षरित परिपथ का समुच्चय $\textstyle E$ बनाता है, अभिविन्यस्त मैट्रोइड्स जिन्हें इस तरह से महसूस किया जा सकता है उन्हें मैट्रोइड प्रतिनिधित्व कहा जाता है।

सदिशों के समान समुच्चय को देखते हुए $E$ , हम उसी अभिविन्यस्त मैट्रोइड को चिरोटोप के साथ परिभाषित कर सकते हैं $\chi :E^{r}\rightarrow \{-1,0,1\}$ . किसी के लिए $x_{1},\dots ,x_{r}\in E$ यदि

\chi (x_{1},\dots ,x_{r})=\operatorname {sgn} (\det(x_{1},\dots ,x_{r}))

जहाँ समीकरण का दाहिना पक्ष निर्धारक का चिह्न है। तब $\chi$ समुच्चय पर उसी अभिविन्यस्त मैट्रोइड का चिरोटोप है $E$ .

अधिसमतल व्यवस्था

एक वास्तविक अधिसमतल व्यवस्था ${\mathcal {A}}=\{H_{1},\ldots ,H_{n}\}$ में अधिसमतल का एक परिमित समुच्चय $\mathbb {R} ^{d}$ है, प्रत्येक में मूल परिभाषित है। प्रत्येक अधिसमतल के एक पक्ष को धनात्मक पक्ष के रूप में चुनकर, हम अर्ध-स्थानों की व्यवस्था प्राप्त करते हैं। सभी अभिविन्यस्त मैट्रॉइड में एक अंतर्निहित मैट्रॉइड है। इस प्रकार, सामान्य मैट्रॉइड पर परिणाम अभिविन्यस्त मैट्रॉइड पर लागू किया जा सकता है। अर्ध स्थान की व्यवस्था परिवेशी स्थान को कोशिकाओं के एक सीमित संग्रह में तोड़ देती है, प्रत्येक को अधिसमतल के किस तरफ परिभाषित किया जाता है अर्थात प्रत्येक बिंदु आरक्षित करें। $x\in \mathbb {R} ^{d}$ हस्ताक्षरित समुच्चय के लिए $X=(X^{+},X^{-})$ साथ $i\in X^{+}$ यदि $x$ के सकारात्मक पक्ष में है $H_{i}$ और $i\in X^{-}$ यदि $x$ के नकारात्मक पक्ष $H_{i}$ में है, हस्ताक्षरित समुच्चयों का यह संग्रह अभिविन्यस्त मैट्रॉइड के सह-संवाहक के समुच्चय को परिभाषित करता है, जो द्वैत अभिविन्यस्त मैट्रोइड के सदिश हैं।^[6]

उत्तल पॉलीटॉप

गुंटर एम. ज़िग्लर ने उत्तल पॉलीटोप्स के माध्यम से अभिविन्यस्त मैट्रोइड्स का परिचय दिया।

परिणाम

अभिविन्यास

एक मानक मैट्रॉइड को अभिविन्यसनीय कहा जाता है यदि इसके परिपथ कुछ अभिविन्यस्त मैट्रोइड के हस्ताक्षरित परिपथ का समर्थन करते हैं तो यह ज्ञात है कि सभी वास्तविक प्रतिनिधित्व योग्य मैट्रॉइड अभिविन्यस्त हैं। तब प्रत्येक अवयव का चिन्ह इस अभिविन्यास के सापेक्ष अपनी दिशा को कूटबद्ध करेगा। यह भी ज्ञात है कि माथेरॉइड माइनर लेने के अनुसार अभिविन्यसनीय मैट्रोइड्स की श्रेणी बंद है, हालांकि अभिविन्यसनीय मैट्रोइड्स के लिए मेट्रॉइड फॉरबिडेन माइनर चरित्र चित्रण की सूची अनंत मानी जाती है।^[7] इस अर्थ में, अभिविन्यस्त मैट्रॉइड नियमित मैट्रॉइड की तुलना में एक बहुत जटिल औपचारिकता है।

द्वैत

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

इस अद्वितीय लांबिक विश्लेषण द्वैत अभिविन्यस्त मैट्रोइड के स्पष्ट निर्माण को देखने के लिए, अभिविन्यस्त मैट्रोइड के चिरोटोप $\chi :E^{r}\rightarrow \{-1,0,1\}$ पर विचार करें, यदि हम अवयवों की सूची $x_{1},\dots ,x_{k}\in E$ पर विचार करें तो एक चक्रीय क्रमचय के रूप में तो हम $\operatorname {sgn} (x_{1},\dots ,x_{k})$ परिभाषित करते हैं, संबंधित क्रमचय का संकेत $\chi ^{*}:E^{|E|-r}\rightarrow \{-1,0,1\}$ होना परिभाषित किया जाता है।

\chi ^{*}(x_{1},\dots ,x_{r})\mapsto \chi (x_{r+1},\dots ,x_{|E|})\operatorname {sgn} (x_{1},\dots ,x_{r},x_{r+1},\dots ,x_{|E|}),

तब $\chi ^{*}$ अद्वितीय लांबिक विश्लेषण द्वैत अभिविन्यस्त मैट्रोइड का चिरोटोप है।^[9]

सामयिक प्रतिनिधित्व

यह एक छद्म रेखा व्यवस्था का एक उदाहरण है जो कि किसी भी रेखा व्यवस्था से पप्पस के षट्भुज प्रमेय है।

सभी अभिविन्यस्त मैट्रोइड प्रतिनिधित्व करने योग्य नहीं हैं अर्थात्, सभी को बिंदु विन्यास या, समकक्ष, अधिसमतल व्यवस्था के रूप में प्राप्ति नहीं होती है। हालांकि, कुछ अर्थों में, सभी अभिविन्यस्त मैट्रोइड्स प्राप्ति के सन्निकट आते हैं जो कि अधिसमतल व्यवस्थाएं हैं। विशेष रूप से, फोकमैन-लॉरेंस सांस्थितिक प्रतिनिधित्व प्रमेय कहता है कि किसी भी अभिविन्यस्त मैट्रोइड को एक स्यूडोलिन अन्य प्रकार की व्यवस्था के रूप में एक संभावना है। $d$ -आयामी स्यूडोस्फीयर का एक एम्बेडिंग $e:S^{d}\hookrightarrow S^{d+1}$ है ऐसा है कि एक होमियोमोर्फिज्म सम्मलित है $h:S^{d+1}\rightarrow S^{d+1}$ जिससे कि $h\circ e$ एम्बेड $S^{d}$ भूमध्य रेखा के रूप में $S^{d+1}$ इस अर्थ में एक स्यूडोस्फीयर एक मैनीफोल्ड स्फीयर है (क्षेत्रों के विपरीत)। जिसमे एक स्यूडोस्फीयर व्यवस्था $S^{d}$ स्यूडोस्फीयर का एक संग्रह है जो स्यूडोस्फीयर के साथ प्रतिच्छेद करता है। अंत में, फोल्कमैन लॉरेंस सांस्थितिक प्रतिनिधित्व प्रमेय कहता है कि श्रेणी के प्रत्येक अभिविन्यस्त मैट्रोइड $d+1$ में एक स्यूडोस्फीयर व्यवस्था $S^{d}$ से प्राप्त किया जा सकता है।^[10] इसका नाम जॉन फोकमैन और जिम लॉरेंस (गणितज्ञ) के नाम पर रखा गया है, जिन्होंने इसे 1978 में प्रकाशित किया था।

ज्यामिति

एक ज़ोनोटोप, जो रेखा खंडों का मिंकोव्स्की योग है, उन्मुख मैट्रोइड्स के लिए एक मौलिक मॉडल है। सोलह गहरे लाल बिंदु (दाईं ओर) चार गैर-उत्तल सेटों (बाईं ओर) के मिंकोव्स्की योग का निर्माण करते हैं, जिनमें से प्रत्येक में लाल बिंदुओं की एक जोड़ी होती है। उनके उत्तल हल्स (गुलाबी छायांकित) में धन चिह्न (+) होते हैं: दायाँ धन चिह्न बाएँ धन चिह्न का योग होता है।

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

अनुकूलन

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

अभिविन्यस्त मैट्रोइड्स के लिए एक अभिगृहीत प्रणाली का विकास आर. टाइरेल रॉकफेलर द्वारा प्रारम्भ किया गया था जिससे कि डेंटज़िग के साधारण कलन विधि के धुरी संचालन के माध्यम से उत्पन्न होने वाले मैट्रिसेस के साइन पैटर्न का वर्णन किया जा सके; हालांकि, कुछ अर्थों में, सभी अभिविन्यस्त मैट्रोइड्स प्राप्ति के सन्निकट आते हैं, रॉकफेलर टकर की विशेषता में अल्बर्ट डब्ल्यू टकर के इस तरह के साइन पैटर्न के अध्ययन से प्रेरित था।^[13]अभिविन्यस्त मैट्रोड्स के सिद्धांत ने संयोजन अनुकूलन में सफलता प्राप्त की है। रैखिक प्रोग्रामिंग में, यह वह भाषा थी जिसमें रॉबर्ट जी. ब्लैंड ने अपना ब्लैंड का नियम तैयार किया, जिसके द्वारा साधारण कलन विधि चक्रों से बचता है। इसी तरह, टरलाकी और झांग ने यह प्रमाणित करने के लिए इसका उपयोग किया कि उनके क्रिस-क्रॉस कलन विधि में रैखिक प्रोग्रामिंग समस्याओं के लिए परिमित समाप्ति होती है। इसी तरह के परिणाम टोड और टेरलेकी द्वारा उत्तल द्विघात प्रोग्रामिंग में बनाए गए थे।^[14] इसे रैखिक-भिन्नात्मक प्रोग्रामिंग पर लागू किया गया है,^[15] द्विघात प्रोग्रामिंग|द्विघात-प्रोग्रामिंग समस्याएं, और रैखिक संपूरकता समस्याएं^[16]^[17]^[18]संयोजी अनुकूलन के बाहर, ओएम सिद्धांत रॉकफेलर के मोनोट्रोपिक प्रोग्रामिंग के सिद्धांत और गढ़वाले वंश के संबंधित विचारों में उत्तल न्यूनीकरण में भी प्रकट होता है।^[19] इसी तरह, मैट्रोइड सिद्धांत ने संयोजी कलन विधि के विकास को प्रभावित किया है, विशेष रूप से कलन विधि।^[20] अधिक सामान्यतः, कलन विधि की परिमित समाप्ति का अध्ययन करने के लिए एक ग्रेडोइड उपयोगी होता है।

संदर्भ

↑ R. Tyrrell Rockafellar 1969. Anders Björner et alia, Chapters 1-3. Jürgen Bokowski, Chapter 1. Günter M. Ziegler, Chapter 7.
↑ Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.
↑ Because matroids and oriented matroids are abstractions of other mathematical abstractions, nearly all the relevant books are written for mathematical scientists rather than for the general public. For learning about oriented matroids, a good preparation is to study the textbook on linear optimization by Nering and Tucker, which is infused with oriented-matroid ideas, and then to proceed to Ziegler's lectures on polytopes.
↑ Björner et alia, Chapter 7.9.
↑ Björner et alia, Chapter 3.5
↑ * Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Oriented Matroids. Encyclopedia of Mathematics and Its Applications. Vol. 46 (2nd ed.). Cambridge University Press. ISBN 978-0-521-77750-6. OCLC 776950824. Zbl 0944.52006.
↑ Björner et alia, Chapter 7.9
↑ Björner et alia, Chapter 3.4
↑ Björner et alia, Chapter 3.6
↑ Björner et alia, Chapter 5.2
↑ Bachem and Kern, Chapters 1–2 and 4–9. Björner et alia, Chapters 1–8. Ziegler, Chapter 7–8. Bokowski, Chapters 7–10.
↑ Bachem and Wanka, Chapters 1–2, 5, 7–9. Björner et alia, Chapter 8.
↑ Rockafellar, R. Tyrrell (1969). "The elementary vectors of a subspace of $R^{N}$ (1967)" (PDF). In R. C. Bose; Thomas A. Dowling (eds.). Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press. pp. 104–127. MR 0278972.
↑ Björner et alia, Chapters 8–9. Fukuda and Terlaky. Compare Ziegler.
↑ Illés, Szirmai & Terlaky (1999)
↑ Fukuda & Terlaky (1997)
↑ Fukuda & Terlaky (1997, p. 385)
↑ Fukuda & Namiki (1994, p. 367)
↑ Rockafellar 1984 and 1998.
↑ Lawler. Rockafellar 1984 and 1998.

अग्रिम पठन

किताबें

Bachem, Achim; Kern, Walter (1992). लीनियर प्रोग्रामिंग ड्यूलिटी: एन इंट्रोडक्शन टू ओरिएंटेड मैट्रोइड्स. Universitext. Springer-Verlag. doi:10.1007/978-3-642-58152-6. ISBN 978-3-540-55417-2. MR 1230380.
Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). ओरिएंटेड मैट्रोइड्स. Encyclopedia of Mathematics and Its Applications. Vol. 46 (2nd ed.). Cambridge University Press. ISBN 978-0-521-77750-6. Zbl 0944.52006.
Bokowski, Jürgen (2006). कम्प्यूटेशनल उन्मुख matroids। एक प्राकृतिक ढांचे के भीतर मेट्रिसेस की समतुल्य कक्षाएं. Cambridge University Press. ISBN 978-0-521-84930-2. Zbl 1120.52011.
Lawler, Eugene (2001). कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: नेटवर्क और मैट्रोइड्स. Dover. ISBN 978-0-486-41453-9. Zbl 1058.90057.
इवर डी. नेरिंग और अल्बर्ट डब्ल्यू. टकर, 1993, लीनियर प्रोग्राम्स एंड रिलेटेड प्रॉब्लम्स, एकेडमिक प्रेस। (प्राथमिक)
Rockafellar, R. Tyrrell (1984). नेटवर्क प्रवाह और मोनोट्रोपिक अनुकूलन. Wiley-Interscience. दिमित्रिस वर्टसेकस के एथेना साइंटिफिक द्वारा पुनर्प्रकाशित, 1998।
Ziegler, Günter M. (1994). पॉलीटोप्स पर व्याख्यान. New York: Springer-Verlag.
Richter-Gebert, Jürgen; Ziegler, Günter M. (1997). "Oriented Matroids". In Goodman, Jacob E.; O'Rourke, Joseph (eds.). असतत और कम्प्यूटेशनल ज्यामिति की पुस्तिका. Boca Raton: CRC Press. pp. 111–132. ISBN 9780849385247.

लेख

ए. बेचेम, ए. वांका, अभिविन्यस्त मैट्रोइड्स के लिए पृथक्करण प्रमेय, डिस्क्रीट मैथ। 70 (1988) 303—310।
रॉबर्ट जी. ब्लैंड, न्यू फाइनाइट पिवटिंग रूल्स फॉर सिम्प्लेक्स मेथड, मैथ. संचालन। रेस। 2 (1977) 103–107।
Folkman, Jon; Lawrence, Jim (October 1978). "ओरिएंटेड मैट्रोइड्स". J. Combin. Theory Ser. B. 25 (2): 199–236. doi:10.1016/0095-8956(78)90039-4.
Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य" (PDF). Mathematical Programming, Series B. Amsterdam: North-Holland Publishing Co. 79 (1–3): 369–395. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.
Fukuda, Komei; Namiki, Makoto (March 1994). "मर्टी की सबसे कम सूचकांक पद्धति के चरम व्यवहार पर". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636.
Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "अतिशयोक्तिपूर्ण प्रोग्रामिंग के लिए परिमित क्रिस-क्रॉस विधि". European Journal of Operational Research. 114 (1): 198–214. CiteSeerX 10.1.1.36.7090. doi:10.1016/S0377-2217(98)00049-6. ISSN 0377-2217.
आर टायरेल रॉकफेलर। की एक उपसमष्टि के प्रारंभिक सदिश $R^{n}$ , कॉम्बिनेटोरियल गणित और उसके अनुप्रयोगों में, आर. सी. बोस और टी. ए. डाउलिंग (एड्स), यूनीव। उत्तरी केरोलिना प्रेस, 1969, 104-127।
Roos, C. (1990). "क्रिस-क्रॉस सिम्प्लेक्स विधि के लिए टर्लाकी के धुरी नियम के लिए एक घातीय उदाहरण". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483.
Terlaky, T. (1985). "एक अभिसरण क्रिस-क्रॉस विधि". Optimization: A Journal of Mathematical Programming and Operations Research. 16 (5): 683–690. doi:10.1080/02331938508843067. ISSN 0233-1934. MR 0798939.
Terlaky, Tamás (1987). "ओरिएंटेड मैट्रोइड्स के लिए एक परिमित क्रिस्क्रॉस विधि". Journal of Combinatorial Theory. Series B. 42 (3): 319–327. doi:10.1016/0095-8956(87)90049-9. ISSN 0095-8956. MR 0888684.
Terlaky, Tamás; Zhang, Shu Zhong (1993). "लीनियर प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण". Annals of Operations Research. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.
माइकल जे. टोड, अभिविन्यस्त मैट्रोइड्स में रेखीय और द्विघात प्रोग्रामिंग, जे. कॉम्बिन। थ्योरी सेर। बी 39 (1985) 105—133।
Wang, Zhe Min (1987). "ओरिएंटेड मैट्रोइड प्रोग्रामिंग पर एक परिमित अनुरूप-उन्मूलन मुक्त एल्गोरिदम". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Series B. 8 (1): 120–125. ISSN 0252-9599. MR 0886756.

वेब पर

Ziegler, Günter (1998). "उन्मुख गणित आज". The Electronic Journal of Combinatorics: DS4: Sep 10–1998. doi:10.37236/25.
Malkevitch, Joseph. "उन्मुखी Matroids: एकता की शक्ति". Feature Column. American Mathematical Society. Retrieved 2009-09-14.

बाहरी संबंध

[1] R. Tyrrell Rockafellar 1969. Anders Björner et alia, Chapters 1-3. Jürgen Bokowski, Chapter 1. Günter M. Ziegler, Chapter 7.

[2] Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.

[3] Because matroids and oriented matroids are abstractions of other mathematical abstractions, nearly all the relevant books are written for mathematical scientists rather than for the general public. For learning about oriented matroids, a good preparation is to study the textbook on linear optimization by Nering and Tucker, which is infused with oriented-matroid ideas, and then to proceed to Ziegler's lectures on polytopes.

[4] Björner et alia, Chapter 7.9.

[5] Björner et alia, Chapter 3.5

[6] * Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Oriented Matroids. Encyclopedia of Mathematics and Its Applications. Vol. 46 (2nd ed.). Cambridge University Press. ISBN 978-0-521-77750-6. OCLC 776950824. Zbl 0944.52006.

[7] Björner et alia, Chapter 7.9

[8] Björner et alia, Chapter 3.4

[9] Björner et alia, Chapter 3.6

[10] Björner et alia, Chapter 5.2

[11] Bachem and Kern, Chapters 1–2 and 4–9. Björner et alia, Chapters 1–8. Ziegler, Chapter 7–8. Bokowski, Chapters 7–10.

[12] Bachem and Wanka, Chapters 1–2, 5, 7–9. Björner et alia, Chapter 8.

[13] Rockafellar, R. Tyrrell (1969). "The elementary vectors of a subspace of $R^{N}$ (1967)" (PDF). In R. C. Bose; Thomas A. Dowling (eds.). Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press. pp. 104–127. MR 0278972.

[14] Björner et alia, Chapters 8–9. Fukuda and Terlaky. Compare Ziegler.

[LF99Hyperbolic-15] Illés, Szirmai & Terlaky (1999)

[FukudaTerlaky-16] Fukuda & Terlaky (1997)

[FTNamiki-17] Fukuda & Terlaky (1997, p. 385)

[FukudaNamiki-18] Fukuda & Namiki (1994, p. 367)

[19] Rockafellar 1984 and 1998.

[20] Lawler. Rockafellar 1984 and 1998.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Anonymous

Search

ओरिएंटेड मैट्रोइड

Namespaces

More

Page actions

Contents

पृष्ठभूमि