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

एक 3-आयामी उत्तल पॉलीटॉप

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

उत्तल बहुशीर्ष गणित की विभिन्न शाखाओं और अनुप्रयुक्त क्षेत्रों दोनों में एक महत्वपूर्ण भूमिका निभाते हैं, विशेष रूप से रैखिक प्रोग्रामिंग में।

ग्रुनबाम की प्रभावशाली पाठ्यपुस्तकों मेंऔर ज़िग्लरविषय पर, साथ ही असतत ज्यामिति में कई अन्य ग्रंथों में, उत्तल पॉलीटोप्स को अक्सर पॉलीटोप्स कहा जाता है। ग्रुनबाउम बताते हैं कि यह केवल उत्तल शब्द की अंतहीन पुनरावृत्ति से बचने के लिए है, और यह कि चर्चा को केवल उत्तल विविधता (पृष्ठ 51) पर लागू करने के रूप में समझा जाना चाहिए।

एक पॉलीटॉप को पूर्ण-आयामी कहा जाता है यदि यह एक है $n$-आयामी वस्तु में $\mathbb {R} ^{n}$.

उदाहरण

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

परिभाषाएँ

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

वर्टेक्स प्रतिनिधित्व (उत्तल पतवार)

अपनी पुस्तक उत्तल पॉलीटोप्स में, ग्रुनबाम एक उत्तल पॉलीटॉप को 'कॉम्पैक्ट स्पेस उत्तल सेट के साथ चरम बिंदुओं की एक सीमित संख्या' के रूप में परिभाषित करता है:

एक सेट $K$ का $\mathbb {R} ^{n}$ उत्तल है अगर, अलग-अलग बिंदुओं की प्रत्येक जोड़ी के लिए $a$, $b$ में $K$, समापन बिंदु के साथ बंद खंड $a$ तथा $b$ के भीतर निहित है $K$.

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

आधी जगहों का चौराहा

एक उत्तल पॉलीटॉप को अर्ध-स्थानों की परिमित संख्या के प्रतिच्छेदन के रूप में परिभाषित किया जा सकता है। ऐसी परिभाषा को आधा स्थान प्रतिनिधित्व (एच-प्रतिनिधित्व या एच-विवरण) कहा जाता है। एक उत्तल पॉलीटॉप के असीम रूप से कई एच-विवरण मौजूद हैं। हालांकि, एक पूर्ण-आयामी उत्तल पॉलीटॉप के लिए, न्यूनतम एच-विवरण वास्तव में अद्वितीय है और यह पहलू (ज्यामिति) के सेट द्वारा दिया जाता है - हाफस्पेस को परिभाषित करता है।

एक बंद अर्ध-स्थान को रैखिक असमानता के रूप में लिखा जा सकता है:

$a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b$

कहाँ पे $n$ विचाराधीन पॉलीटॉप वाले स्थान का आयाम है। इसलिए, एक बंद उत्तल पॉलीटॉप को रैखिक असमानताओं की प्रणाली के समाधान के सेट के रूप में माना जा सकता है:

${\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}$

कहाँ पे $m$ पॉलीटॉप को परिभाषित करने वाले आधे-स्थानों की संख्या है। इसे संक्षेप में मैट्रिक्स (गणित) असमानता के रूप में लिखा जा सकता है:

$Ax\leq b$

कहाँ पे $A$ एक $m\times n$ आव्यूह, $x$ एक $n\times 1$ स्तंभ सदिश जिसके निर्देशांक चर हैं $x_{1}$ प्रति $x_{n}$, तथा $b$ एक $m\times 1$ कॉलम वेक्टर जिसका निर्देशांक दाहिनी ओर है $b_{1}$ प्रति $b_{m}$ अदिश असमानताओं की।

एक खुले उत्तल पॉलीटोप को उसी तरह परिभाषित किया गया है, जिसमें गैर-सख्त लोगों के बजाय सूत्रों में सख्त असमानताओं का उपयोग किया गया है।

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

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

यदि पॉलीटॉप पूर्ण-आयामी नहीं है, तो समाधान $Ax\leq b$ के एक उचित संबंध उप-स्थान में झूठ बोलना $\mathbb {R} ^{n}$ और इस उप-स्थान में एक वस्तु के रूप में पॉलीटॉप का अध्ययन किया जा सकता है। इस मामले में, वहाँ रैखिक समीकरण मौजूद हैं जो पॉलीटॉप के सभी बिंदुओं से संतुष्ट हैं। इन समीकरणों में से किसी एक को परिभाषित असमानताओं में जोड़ने से पॉलीटॉप नहीं बदलता है। इसलिए, सामान्य तौर पर पॉलीटोप को परिभाषित करने वाली असमानताओं का कोई अनूठा न्यूनतम सेट नहीं है।

आम तौर पर मनमाना अर्ध-स्थानों के चौराहे को बाध्य करने की आवश्यकता नहीं होती है। हालांकि अगर कोई उत्तल हल के बराबर परिभाषा चाहता है, तो बाध्यता स्पष्ट रूप से आवश्यक होनी चाहिए।

=== विभिन्न अभ्यावेदन === का उपयोग करना दो अभ्यावेदन एक साथ यह तय करने का एक कुशल तरीका प्रदान करते हैं कि क्या दिए गए वेक्टर को दिए गए उत्तल पॉलीटॉप में शामिल किया गया है: यह दिखाने के लिए कि यह पॉलीटॉप में है, यह पॉलीटोप वर्टिस (वी-विवरण) के उत्तल संयोजन के रूप में प्रस्तुत करने के लिए पर्याप्त है प्रयोग किया जाता है); यह दिखाने के लिए कि यह पॉलीटॉप में नहीं है, यह एक एकल परिभाषित असमानता को प्रस्तुत करने के लिए पर्याप्त है जिसका यह उल्लंघन करता है। सदिशों द्वारा प्रतिनिधित्व में एक सूक्ष्म बिंदु यह है कि सदिशों की संख्या आयाम में घातीय हो सकती है, इसलिए प्रमाण है कि एक सदिश पॉलीटॉप में है, वह घातीय रूप से लंबा हो सकता है। सौभाग्य से, कैराथियोडोरी का प्रमेय (उत्तल हल) | कैराथियोडोरी का प्रमेय गारंटी देता है कि पॉलीटॉप में प्रत्येक वेक्टर को अधिकतम डी+1 परिभाषित वैक्टर द्वारा दर्शाया जा सकता है, जहां डी अंतरिक्ष का आयाम है।

असीमित पॉलीटोप्स का प्रतिनिधित्व

एक असीमित पॉलीटॉप (कभी-कभी कहा जाता है: पॉलीहेड्रॉन) के लिए, एच-विवरण अभी भी मान्य है, लेकिन वी-विवरण को बढ़ाया जाना चाहिए। थिओडोर मोट्ज़किन (1936) ने साबित किया कि किसी भी असीमित पॉलीटोप को एक बंधे हुए पॉलीटोप और एक उ�