End (graph theory)
अनंत ग्राफ के गणित में, एक ग्राफ का अंत सहज ज्ञान से, एक ऐसी दिशा का प्रतिनिधित्व करता है जिसमें ग्राफ अनंत तक फैला हुआ है। अंत को गणितीय रूप से अनंत पथों के समतुल्य वर्गों के रूप में औपचारिक रूप दिया जा सकता है, ग्राफ पर खोज-चोरी खेलों के लिए रणनीतियों का वर्णन करने वाले आश्रय के रूप में, या (स्थानीय रूप से सीमित ग्राफ के मामले में) ग्राफ से जुड़े टोपोलॉजिकल रिक्त स्थान के टोपोलॉजिकल छोर के रूप में। ग्राफ के अंत का उपयोग (केले ग्राफ के माध्यम से) परिमित रूप से उत्पन्न समूहों के अंत को परिभाषित करने के लिए किया जा सकता है। परिमित रूप से उत्पन्न अनंत समूहों के एक, दो या अनंत रूप से कई छोर होते हैं, और समूहों के छोरों के बारे में स्टैलिंग्स प्रमेय एक से अधिक छोर वाले समूहों के लिए एक अपघटन प्रदान करता है। ग्राफ की परिभाषा और लक्षण वर्णन अंत को अनंत पथों के समतुल्यता वर्गों के संदर्भ में परिभाषित किया गया था। एक अनंत ग्राफ में ए एक अर्ध-अनंत सरल पथ है; अर्थात, यह शीर्षों का एक अनंत अनुक्रम है जिसमें प्रत्येक शीर्ष अनुक्रम में अधिक से अधिक एक बार दिखाई देता है और अनुक्रम में प्रत्येक दो लगातार शीर्ष ग्राफ में एक किनारे के दो अंतिम बिंदु हैं। हेलिन की परिभाषा के अनुसार, दो किरणें और समान हैं यदि एक किरण है (जो दी गई दो किरणों में से एक के बराबर हो सकती है) जिसमें और में से प्रत्येक में असीम रूप से कई शीर्ष होते हैं। यह एक समतुल्यता संबंध हैः प्रत्येक किरण अपने आप में समतुल्य है, परिभाषा दो किरणों के क्रम के संबंध में सममित है, और इसे सकर्मक के रूप में दिखाया जा सकता है। इसलिए, यह सभी किरणों के समूह को समतुल्यता वर्गों में विभाजित करता है, और हैलिन ने अंत को इन समतुल्यता वर्गों में से एक के रूप में परिभाषित किया। समान समतुल्यता संबंध की एक वैकल्पिक परिभाषा का भी उपयोग किया गया हैः दो किरणें और समतुल्य हैं यदि शीर्षों का कोई सीमित सेट नहीं है जो के अनंत कई शीर्षों को अनंत रूप से अलग करता है। यह हेलिन की परिभाषा के बराबर हैः यदि हेलिन की परिभाषा से किरण मौजूद है, तो किसी भी विभाजक में असीम रूप से कई बिंदु होने चाहिए और इसलिए सीमित नहीं हो सकता है, और इसके विपरीत यदि मौजूद नहीं है तो एक ऐसा मार्ग जो जितना संभव हो उतना बार बारी-बारी से होता है और वांछित सीमित विभाजक का निर्माण करना चाहिए। एंड्स में हेवन के संदर्भ में अधिक ठोस लक्षण वर्णन भी होता है, जो एक ग्राफ पर पीछा-चोरी के खेल के लिए चोरी रणनीतियों का वर्णन करते हैं। विचाराधीन खेल में, एक डाकू के किनारों के साथ शीर्ष से शीर्ष पर जाकर पुलिसकर्मियों के एक समूह से बचने की कोशिश कर रहा है। पुलिस के पास हेलीकॉप्टर होते हैं और इसलिए उन्हें किनारों का अनुसरण करने की आवश्यकता नहीं होती है; हालाँकि डाकू पुलिस को आते हुए देख सकता है और हेलीकॉप्टर के उतरने से पहले यह चुन सकता है कि आगे कहाँ जाना है। एक हेवन एक ऐसा कार्य है जो हटाकर बनाए गए सबग्राफ के जुड़े घटकों में से एक के लिए पुलिस स्थानों के प्रत्येक सेट का मानचित्र बनाता है; एक डाकू खेल के प्रत्येक दौर में इस घटक के भीतर एक शीर्ष पर जाकर पुलिस से बच सकता है। हैवन्स को एक सुसंगतता संपत्ति को पूरा करना चाहिए (इस आवश्यकता के अनुरूप कि डाकू उन शीर्षों से आगे नहीं बढ़ सकता है जिन पर पुलिस पहले ही उतर चुकी है): यदि यह पुलिस के दिए गए समूह के लिए स्थानों का एक उपसमुच्चय है, और दोनों और वैध समूह हैं, तो यह एक सुपरसेट होना चाहिए। एक हेवन के पास आदेश होता है यदि पुलिस स्थानों के संग्रह के लिए जिसके लिए यह एक पलायन रणनीति प्रदान करता है, ग्राफ में शीर्षों से कम के सभी उपसमुच्चय शामिल हैं; विशेष रूप से, इसका क्रम (सबसे छोटी आलेफ संख्या) है यदि यह शीर्षों के प्रत्येक सीमित उपसमुच्चय को एक घटक के लिए मानचित्रित करता है। प्रत्येक किरण क्रम के एक स्वर्ग से मेल खाती है, अर्थात्, कार्य; जो प्रत्येक परिमित सेट को अद्वितीय घटक के लिए मैप करता है जिसमें किरण के अनंत रूप से कई शीर्ष होते हैं। इसके विपरीत, क्रम के प्रत्येक आश्रय को एक किरण द्वारा इस तरह से परिभाषित किया जा सकता है। दो किरणें तभी समतुल्य होती हैं जब वे एक ही आश्रय को परिभाषित करती हैं, इसलिए एक ग्राफ के छोर अपने क्रम के आश्रय के साथ एक-से-एक पत्राचार में होते हैं। उदाहरण यदि अनंत ग्राफ अपने आप में एक किरण है, तो इसमें असीम रूप से कई किरण उपग्राफ हैं, जिनमें से एक के प्रत्येक शीर्ष से शुरू होता है। हालाँकि, ये सभी किरणें एक दूसरे के बराबर हैं, इसलिए इसका केवल एक छोर है। यदि एक वन है (यानी, एक ग्राफ जिसमें कोई सीमित चक्र नहीं है), तो किसी भी दो किरणों का प्रतिच्छेदन या तो एक पथ या एक किरण है; दो किरणें बराबर हैं यदि उनका प्रतिच्छेदन एक किरण है। यदि प्रत्येक जुड़े हुए घटक में एक आधार शीर्ष चुना जाता है, तो प्रत्येक छोर में आधार शीर्षों में से एक से शुरू होने वाली एक अनूठी किरण होती है, इसलिए सिरों को इन विहित किरणों के साथ एक-से-एक पत्राचार में रखा जा सकता है। प्रत्येक गणना योग्य ग्राफ के समान छोरों के साथ एक फैला हुआ वन होता है। हालांकि, केवल एक छोर के साथ अनगिनत अनंत ग्राफ मौजूद हैं जिसमें प्रत्येक फैले हुए पेड़ के अनंत रूप से कई छोर होते हैं। यदि एक अनंत ग्रिड ग्राफ है, तो इसमें कई किरणें हैं, और मनमाने ढंग से शीर्ष-विच्छेद किरणों के बड़े समूह हैं। लेकिन इसका केवल एक ही अंत है। इसे हेवन के संदर्भ में सिरों के लक्षण वर्णन का उपयोग करके सबसे आसानी से देखा जा सकता हैः शीर्षों के किसी भी सीमित सेट को हटाने से बिल्कुल एक अनंत जुड़ा हुआ घटक निकलता है, इसलिए केवल एक ही हेवन होता है (वह जो प्रत्येक परिमित सेट को अद्वितीय अनंत जुड़े घटक के लिए मैप करता है)। टोपोलॉजिकल छोरों से संबंध बिंदु-सेट टोपोलॉजी में, एक अंत की अवधारणा है जो ग्राफ सिद्धांत में अंत की अवधारणा के समान है, लेकिन बिल्कुल वैसी नहीं है, जो बहुत पहले की है। यदि एक टोपोलॉजिकल स्थान को कॉम्पैक्ट सेटों के एक नेस्टेड अनुक्रम द्वारा कवर किया जा सकता है, तो स्थान का एक छोर कॉम्पैक्ट सेटों के पूरक घटकों का एक क्रम है। यह परिभाषा कॉम्पैक्ट सेटों के चयन पर निर्भर नहीं करती हैः इस तरह के एक विकल्प द्वारा परिभाषित छोरों को किसी अन्य विकल्प द्वारा परिभाषित छोरों के साथ एक-से-एक पत्राचार में रखा जा सकता है। एक अनंत ग्राफ को दो अलग-अलग लेकिन संबंधित तरीकों से एक स्थलवैज्ञानिक स्थान में बनाया जा सकता हैः ग्राफ के प्रत्येक शीर्ष को एक बिंदु से और ग्राफ के प्रत्येक किनारे को एक खुले इकाई अंतराल से बदलने से ग्राफ से एक हौसडॉर्फ स्थान उत्पन्न होता है जिसमें एक सेट को खुला होने के लिए परिभाषित किया जाता है जब भी ग्राफ के किनारे के साथ प्रत्येक प्रतिच्छेदन इकाई अंतराल का एक खुला उपसमुच्चय होता है। ग्राफ के प्रत्येक शीर्ष को एक बिंदु से और ग्राफ के प्रत्येक किनारे को एक बिंदु से बदलने से एक गैर-हौसडॉर्फ स्थान उत्पन्न होता है जिसमें खुले सेट उस गुण के साथ सेट होते हैं, यदि इसका एक शीर्ष संबंधित है, तो हर किनारे को इसके अंतिम बिंदुओं में से एक के रूप में होता है। दोनों ही मामलों में, प्रत्येक कॉम्पैक्ट सबस्पेस टोपोलॉजिकल स्पेस के एक कॉम्पैक्ट सबस्पेस से मेल खाता है, और प्रत्येक कॉम्पैक्ट सबस्पेस एक फाइनाइट सबग्राफ से मेल खाता है, हौसडॉर्फ मामले में, किनारों के परिमित रूप से कई कॉम्पैक्ट उचित सबसेट। इस प्रकार, एक ग्राफ को कॉम्पैक्ट सेटों के एक नेस्टेड अनुक्रम द्वारा कवर किया जा सकता है यदि और केवल तभी जब यह स्थानीय रूप से सीमित हो, जिसमें प्रत्येक शीर्ष पर किनारों की एक सीमित संख्या हो। यदि एक ग्राफ जुड़ा हुआ है और स्थानीय रूप से सीमित है, तो इसमें एक कॉम्पैक्ट कवर होता है जिसमें सेट कुछ मनमाने ढंग से चुने गए शुरुआती शीर्ष से अधिक से अधिक दूरी पर शीर्षों का सेट होता है। इस मामले में कोई भी आश्रय स्थल उस स्थलवैज्ञानिक स्थान के अंत को परिभाषित करता है जिसमें। और इसके विपरीत, यदि परिभाषित स्थलवैज्ञानिक स्थान का अंत है, तो यह एक ऐसे आश्रय को परिभाषित करता है जिसमें घटक होता है, जहां कोई भी संख्या पर्याप्त होती है। इस प्रकार, जुड़े हुए और स्थानीय रूप से सीमित ग्राफों के लिए, स्थलवैज्ञानिक छोर ग्राफ-सैद्धांतिक छोरों के साथ एक-से-एक पत्राचार में होते हैं। उन ग्राफों के लिए जो स्थानीय रूप से सीमित नहीं हो सकते हैं, ग्राफ और उसके सिरों से एक टोपोलॉजिकल स्थान को परिभाषित करना अभी भी संभव है। इस स्थान को एक मीट्रिक स्थान के रूप में दर्शाया जा सकता है यदि और केवल तभी जब ग्राफ में एक सामान्य फैला हुआ पेड़ हो, एक जड़ फैला हुआ पेड़ ऐसा हो कि प्रत्येक ग्राफ का किनारा एक पूर्वज-वंशज जोड़ी को जोड़ता हो। यदि एक सामान्य फैला हुआ वृक्ष मौजूद है, तो इसके सिरों का सेट दिए गए ग्राफ के समान हैः ग्राफ के प्रत्येक छोर में पेड़ में बिल्कुल एक अनंत पथ होना चाहिए। विशेष प्रकार के छोर मुक्त छोर एक ग्राफ के अंत को एक मुक्त अंत के रूप में परिभाषित किया जाता है यदि उस गुण के साथ शीर्षों का एक सीमित समूह होता है जो ग्राफ के अन्य सभी सिरों से अलग होता है। (अर्थात, आश्रय के संदर्भ में, हर दूसरे छोर से अलग है।) परिमित रूप से कई छोरों वाले ग्राफ में, प्रत्येक छोर मुक्त होना चाहिए। यह साबित करता है कि, यदि अनंत रूप से कई छोर हैं, तो या तो एक ऐसा अंत मौजूद है जो मुक्त नहीं है, या किरणों का एक अनंत परिवार मौजूद है जो एक सामान्य प्रारंभिक शीर्ष साझा करते हैं और अन्यथा एक दूसरे से अलग होते हैं। मोटे छोर ग्राफ का एक मोटा छोर एक ऐसा छोर है जिसमें असीम रूप से कई जोड़ीदार-विच्छेदित किरणें होती हैं। हेलिन का ग्रिड प्रमेय उन ग्राफों की विशेषता बताता है जिनमें मोटे छोर होते हैंः वे ठीक वही ग्राफ होते हैं जिनमें उपग्राफ के रूप में षट्कोणीय टाइलिंग का एक उपखंड होता है। विशेष प्रकार के ग्राफ सममित और लगभग सममित ग्राफ एक जुड़े हुए स्थानीय रूप से सीमित ग्राफ को "लगभग सममित" के रूप में परिभाषित करते हैं यदि एक शीर्ष और एक संख्या मौजूद है, तो प्रत्येक अन्य शीर्ष के लिए, ग्राफ का एक स्वरूपता है जिसके लिए छवि की दूरी के भीतर है; समतुल्य रूप से, एक जुड़ा हुआ स्थानीय रूप से सीमित ग्राफ लगभग सममित है यदि इसके स्वरूपता समूह में परिमित रूप से कई कक्षाएं हैं। जैसा कि वे दिखाते हैं, प्रत्येक जुड़े हुए स्थानीय रूप से सीमित लगभग सममित ग्राफ के लिए, सिरों की संख्या या तो अधिक से अधिक दो या अनगिनत होती है; यदि यह अनगिनत है, तो सिरों में एक कैंटर सेट की टोपोलॉजी होती है। इसके अतिरिक्त, मोहर से पता चलता है कि सिरों की संख्या चीगर स्थिरांक को नियंत्रित करती है जहां ग्राफ के शीर्षों के सभी सीमित गैर-खाली सेटों पर सीमा होती है और जहां एक अंतिम बिंदु के साथ किनारों के सेट को दर्शाता है। अनगिनत रूप से कई छोरों वाले लगभग-सममित आलेखों के लिए, हालांकि, केवल दो छोरों वाले लगभग-सममित आलेखों के लिए,। केले ग्राफ प्रत्येक समूह और समूह के लिए जनरेटर का एक समूह एक केले ग्राफ निर्धारित करता है, एक ग्राफ जिसके शीर्ष समूह तत्व हैं और किनारे तत्वों के जोड़े हैं जहां जनरेटर में से एक है। एक परिमित रूप से उत्पन्न समूह के मामले में, समूह के सिरों को जनरेटर के सीमित सेट के लिए केले ग्राफ के छोर के रूप में परिभाषित किया जाता है; यह परिभाषा जनरेटर के चयन के तहत अपरिवर्तनीय है, इस अर्थ में कि यदि जनरेटर के दो अलग-अलग सीमित सेट चुने जाते हैं, तो दो केले ग्राफ के छोर एक दूसरे के साथ एक-से-एक पत्राचार में होते हैं। उदाहरण के लिए, प्रत्येक मुक्त समूह के पास एक केली ग्राफ (इसके मुक्त जनरेटर के लिए) है जो एक वृक्ष है। एक जनरेटर पर मुक्त समूह का केली ग्राफ के रूप में दोगुना अनंत मार्ग होता है, जिसके दो छोर होते हैं। प्रत्येक अन्य मुक्त समूह के अनंत रूप से कई छोर होते हैं। प्रत्येक परिमित रूप से उत्पन्न अनंत समूह के या तो 1,2, या अनंत रूप से कई छोर होते हैं, और समूहों के छोरों के बारे में स्टैलिंग्स प्रमेय एक से अधिक छोर वाले समूहों का अपघटन प्रदान करता है। विशेष रूप सेः एक परिमित रूप से उत्पन्न अनंत समूह के 2 छोर होते हैं यदि और केवल तभी जब इसमें परिमित सूचकांक का एक चक्रीय उपसमूह होता है। एक परिमित रूप से उत्पन्न अनंत समूह के अनंत रूप से कई छोर होते हैं यदि और केवल तभी जब यह या तो समामेलन के साथ एक गैर-तुच्छ मुक्त उत्पाद हो या सीमित समामेलन के साथ एच. एन. एन.-विस्तार हो। अन्य सभी परिमित रूप से उत्पन्न अनंत समूहों का बिल्कुल एक छोर होता है। टिप्पणियाँ संदर्भ रेखाचित्र सिद्धांत अनंत रेखाचित्रों को लक्षित करता है