अनंत (आलेख सिद्धांत )

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

अंतिम रूप से उत्पन्न समूहों के सिरों को परिभाषित करने के लिए रेखांकऩ के सिरों का उपयोग (केली रेखांकन के माध्यम से) किया जा सकता है। परिमित रूप से उत्पन्न अनंत समूहों में एक, दो, या असीम रूप से कई सिरे होते हैं, और समूहों के सिरों के बारे में स्टालिंग्स प्रमेय एक से अधिक सिरों वाले समूहों के लिए अपघटन प्रदान करता है।

परिभाषा और विशेषता

रेखांकन के सिरे रुडोल्फ हेलिन (1964) द्वारा परिभाषित किए गए थे, अनंत पथों के समतुल्य वर्गों के संदर्भ में।^[1] किरण एक अनंत रेखांकन में एक अर्ध-अनंत सरल पथ (रेखांकन सिद्धांत) है; अर्थात्, यह शीर्षों का एक अनंत क्रम है $v_{0},v_{1},v_{2},\dots$ जिसमें अनुक्रम में प्रत्येक शीर्ष अधिकतम एक बार प्रकट होता है और अनुक्रम में प्रत्येक दो क्रमागत शीर्ष रेखांकऩ में एक किनारे के दो अंतिम बिंदु होते हैं। हैलिन की परिभाषा के अनुसार दो किरणें $r_{0}$ और $r_{1}$ किरण होने पर समतुल्य हैं $r_{2}$ (जो दी गई दो किरणों में से एक के बराबर हो सकता है) जिसमें प्रत्येक में अपरिमित रूप से अनेक शीर्ष होते हैं $r_{0}$ और $r_{1}$ . यह एक तुल्यता संबंध है: प्रत्येक किरण स्वयं के तुल्य है, दो किरणों के क्रम के संबंध में परिभाषा सममित है, और इसे सकर्मक संबंध के रूप में दिखाया जा सकता है। इसलिए, यह सभी किरणों के समुच्चय को तुल्यता वर्गों में विभाजित करता है, और हैलिन ने छोरको इन तुल्यता वर्गों में से एक के रूप में परिभाषित किया।^[2]

समान तुल्यता संबंध की एक वैकल्पिक परिभाषा का भी उपयोग किया गया है: दो किरणें $r_{0}$ और $r_{1}$ समतुल्य हैं यदि कोई परिमित समुच्चय नहीं है $X$ उन शीर्षों का जो वर्टेक्स विभाजक अपरिमित रूप से अनेक शीर्षों का है $r_{0}$ के अपरिमित रूप से अनेक शीर्षों से $r_{1}$ .^[3] यह हैलिन की परिभाषा के समतुल्य है: यदि किरण $r_{2}$ हैलिन की परिभाषा से मौजूद है, तो किसी भी विभाजक में असीम रूप से कई बिंदु होने चाहिए और इसलिए $r_{2}$ परिमित नहीं हो सकता है, और इसके विपरीत यदि $r_{2}$ मौजूद नहीं है तो एक पथ जो जितनी बार संभव हो उतनी बार वैकल्पिक होता है $r_{0}$ और $r_{1}$ वांछित परिमित विभाजक बनाना चाहिए।

हेवन (रेखांकन थ्योरी) के संदर्भ में सिरों का एक अधिक ठोस लक्षण वर्णन है, ऐसे कार्य जो एक रेखांकन पर पीछा-भागना के खेल के लिए चोरी की रणनीतियों का वर्णन करते हैं। $G$ .^[4] विचाराधीन खेल में, एक लुटेरा किनारों के साथ शीर्ष से शीर्ष पर जाकर पुलिसकर्मियों के एक समूह से बचने की कोशिश कर रहा है $G$ . पुलिस के पास हेलीकॉप्टर हैं और इसलिए उन्हें किनारों का पालन करने की आवश्यकता नहीं है; हालाँकि लुटेरा पुलिस को आते हुए देख सकता है और यह चुन सकता है कि हेलीकॉप्टर के उतरने से पहले उसे कहाँ जाना है। एक हेवन एक फलन है $\beta$ जो प्रत्येक सेट को मैप करता है $X$ हटाने के द्वारा गठित सबरेखांकन के जुड़े घटकों में से एक के लिए पुलिस स्थान $X$ ; एक लुटेरा इस घटक के भीतर खेल के प्रत्येक दौर में एक शीर्ष पर जाकर पुलिस से बच सकता है। हेवन्स को एक स्थिरता गुण को संतुष्ट करना चाहिए (इस आवश्यकता के अनुरूप कि लुटेरा उन चोटियों से आगे नहीं बढ़ सकता है जिन पर पुलिस पहले ही उतर चुकी है): यदि $X$ का उपसमुच्चय है $Y$ , और दोनों $X$ और $Y$ पुलिस के दिए गए सेट के लिए स्थानों के मान्य सेट हैं, तब $\beta (X)$ का सुपरसेट होना चाहिए $\beta (Y)$ . एक आश्रय का आदेश है $k$ यदि पुलिस स्थानों का संग्रह जिसके लिए यह भागने की रणनीति प्रदान करता है, से कम के सभी सबसेट शामिल हैं $k$ रेखांकन में शिखर; विशेष रूप से, इसका आदेश है $\aleph _{0}$ (सबसे छोटी संख्या) यदि यह प्रत्येक परिमित सबसेट को मैप करता है $X$ के एक घटक के शीर्ष का $G\setminus X$ . में हर किरण $G$ आदेश के हेवन से मेल खाता है $\aleph _{0}$ , अर्थात्, फलन $\beta$ ; जो हर परिमित सेट को मैप करता है $X$ के अद्वितीय घटक के लिए $G\setminus X$ जिसमें किरण के अपरिमित रूप से अनेक शीर्ष होते हैं। इसके विपरीत, आदेश का हर आश्रय $\aleph _{0}$ एक किरण द्वारा इस प्रकार परिभाषित किया जा सकता है।^[5] दो किरणें समतुल्य होती हैं यदि और केवल यदि वे एक ही हेवन को परिभाषित करती हैं, तो एक रेखांकन के छोरएक-से-एक पत्राचार में अपने आदेश के साथ होते हैं $\aleph _{0}$ .^[4]

उदाहरण

एक अनंत ग्रिड रेखांकऩ का हिस्सा, उन बिंदुओं पर जहाँ दो ग्रिड रेखाएँ मिलती हैं। अनेक प्रकार की किरणें होते हुए भी उसका एक ही सिरा होता है।

यदि अनंत रेखांकन $G$ स्वयं एक किरण है, तो इसमें अपरिमित रूप से अनेक किरण उपसमूह होते हैं, जिनमें से प्रत्येक के शीर्ष से एक प्रारंभ होता है $G$ . हालाँकि, ये सभी किरणें एक दूसरे के समतुल्य हैं, इसलिए $G$ केवल एक छोर है।

अगर $G$ एक जंगल है (अर्थात, बिना परिमित चक्र वाला एक रेखांकन), तो किन्हीं दो किरणों का प्रतिच्छेदन या तो पथ या किरण है; दो किरणें समतुल्य होती हैं यदि उनका प्रतिच्छेदन एक किरण है। यदि प्रत्येक जुड़े हुए घटक में एक आधार शीर्ष चुना जाता है $G$ , फिर प्रत्येक छोर $G$ आधार के एक कोने से शुरू होने वाली एक अद्वितीय किरण होती है, इसलिए इन विहित किरणों के साथ एक-से-एक पत्राचार में सिरों को रखा जा सकता है। हर गणनीय रेखांकन $G$ के समान सिरों के साथ एक फैला हुआ जंगल है $G$ .^[6] हालाँकि, केवल एक छोर के साथ अनंत रेखांकन मौजूद हैं, जिसमें हर फैले हुए पेड़ के असीम रूप से कई छोर हैं।^[7] अगर $G$ एक अनंत ग्रिड रेखांकन है, तो इसमें कई किरणें हैं, और शीर्ष-विच्छेद किरणों के मनमाने ढंग से बड़े सेट हैं। हालाँकि, इसका केवल एक छोर है। हेवन के संदर्भ में सिरों के लक्षण वर्णन का उपयोग करते हुए इसे सबसे आसानी से देखा जा सकता है: शीर्ष के किसी भी परिमित सेट को हटाने से वास्तव में एक अनंत जुड़ा हुआ घटक निकलता है, इसलिए केवल एक हेवन है (वह जो प्रत्येक परिमित सेट को अद्वितीय अनंत से जुड़ा हुआ बनाता है) अवयव।

सांस्थितिक सिरों से संबंध

बिंदु-सेट सांस्थितिक में, छोर की एक अवधारणा है जो समान है, लेकिन काफी समान नहीं है, जैसा कि रेखांकन सिद्धांत में एक छोर की अवधारणा है, जो बहुत पहले फ्रायडेंथल (1931) ने की है। यदि एक सांस्थितिक समष्टि को संहतसमुच्चय के नीडित अनुक्रम द्वारा ढका जा सकता है $\kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots$ , तो समष्टि का छोर घटकों का एक क्रम है $U_{0}\supset U_{1}\supset U_{2}\dots$ संहतसमुच्चय के पूरक। यह परिभाषा संहतसमुच्चय की पसंद पर निर्भर नहीं करती है: इस तरह के एक विकल्प द्वारा परिभाषित छोर किसी अन्य विकल्प द्वारा परिभाषित छोर के साथ एक-से-एक पत्राचार में रखा जा सकता है।

एक अनंत रेखांकन $G$ दो अलग-अलग लेकिन संबंधित तरीकों से एक सांस्थितिक समष्टि में बनाया जा सकता है:

रेखांकऩ के प्रत्येक शीर्ष को एक बिंदु से और रेखांकऩ के प्रत्येक किनारे को एक खुली इकाई अंतराल द्वारा प्रतिस्थापित करने से रेखांकऩ से हॉसडॉर्फ स्पेस उत्पन्न होता है जिसमें एक सेट $S$ जब भी प्रत्येक चौराहे को खुला होना परिभाषित किया जाता है $S$ रेखांकऩ के किनारे के साथ इकाई अंतराल का एक खुला उपसमुच्चय है।
रेखांकऩ के प्रत्येक शीर्ष को एक बिंदु से और रेखांकऩ के प्रत्येक किनारे को एक बिंदु से बदलकर एक गैर-हॉसडॉर्फ स्थान उत्पन्न होता है जिसमें खुले सेट सेट होते हैं $S$ संपत्ति के साथ, यदि एक शीर्ष $v$ का $G$ से संबंधित $S$ , फिर ऐसा हर किनारे पर होता है $v$ इसके समापन बिंदुओं में से एक के रूप में।

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

यदि कोई रेखांकन $G$ जुड़ा हुआ है और स्थानीय रूप से परिमित है, तो इसमें एक कॉम्पैक्ट कवर होता है जिसमें सेट होता है $\kappa _{i}$ अधिकतम दूरी पर शीर्षों का समुच्चय है $i$ कुछ मनमाने ढंग से चुने गए शुरुआती शीर्ष से। इस मामले में कोई आश्रय $\beta$ सांस्थितिक समष्टि के छोरको परिभाषित करता है जिसमें $U_{i}=\beta (\kappa _{i})$ . और इसके विपरीत अगर $U_{0}\supset U_{1}\supset U_{2}\dots$ से परिभाषित सांस्थितिक समष्टि का छोरहै $G$ , यह एक हेवन को परिभाषित करता है जिसमें $\beta (X)$ युक्त घटक है $U_{i}$ , कहाँ $i$ क्या कोई संख्या इतनी बड़ी है $\kappa _{i}$ रोकना $X$ . इस प्रकार, जुड़े और स्थानीय रूप से परिमित रेखांकन के लिए, टोपोलॉजिकल छोर रेखांकन-सैद्धांतिक सिरों के साथ एक-से-एक पत्राचार में हैं।^[8] रेखांकऩ के लिए जो स्थानीय रूप से परिमित नहीं हो सकता है, अभी भी रेखांकऩ और उसके सिरों से एक स्थलीय स्थान को परिभाषित करना संभव है। इस स्थान को एक मीट्रिक स्थान के रूप में दर्शाया जा सकता है यदि और केवल तभी जब रेखांकन में ट्रेमाक्स ट्री हो, एक जड़ फैला हुआ पेड़ हो जैसे कि प्रत्येक रेखांकन किनारे पूर्वज-वंशज जोड़ी को जोड़ता है। यदि एक सामान्य फैला हुआ पेड़ मौजूद है, तो उसके पास दिए गए रेखांकन के समान सिरों का सेट है: रेखांकन के प्रत्येक छोर में पेड़ में बिल्कुल एक अनंत पथ होना चाहिए।^[9]

विशेष प्रकार के सिरे

मुक्त छोर

एक सिरा $E$ एक रेखांकन का $G$ यदि परिमित समुच्चय है तो मुक्त छोरके रूप में परिभाषित किया जाता है $X$ संपत्ति के साथ शीर्षों की $X$ अलग $E$ रेखांकन के अन्य सभी सिरों से। (अर्थात्, आश्रयों के संदर्भ में, $\beta _{E}(X)$ से जुदा है $\beta _{D}(X)$ हर दूसरे छोर के लिए $D$ .) एक रेखांकऩ में जिसके बहुत से छोरहैं, प्रत्येक छोर मुक्त होना चाहिए। Halin (1964) साबित करता है कि अगर $G$ असीम रूप से कई छोर हैं, तो या तो एक छोरमौजूद है जो मुक्त नहीं है, या किरणों का एक अनंत परिवार मौजूद है जो एक सामान्य प्रारंभिक शीर्ष साझा करता है और अन्यथा एक दूसरे से अलग होता है।

मोटा सिरा

एक रेखांकन का मोटा छोर $G$ एक छोरहै जिसमें असीम रूप से कई जोड़ीदार-असंबद्ध सेट किरणें होती हैं। हैलिन की ग्रिड प्रमेय उन रेखांकऩों की विशेषता बताती है जिनमें मोटे सिरे होते हैं: वे बिल्कुल ऐसे रेखांकऩ होते हैं जिनमें एक सबरेखांकन के रूप में हेक्सागोनल टाइलिंग का होमोमोर्फिज़्म (रेखांकऩ सिद्धांत) होता है।^[10]

विशेष प्रकार के रेखांकन

सममित और लगभग सममित रेखांकन

Mohar (1991) एक स्थानीय रूप से परिमित रेखांकन को लगभग सममित होने के लिए परिभाषित करता है यदि कोई शीर्ष मौजूद है $v$ और एक संख्या $D$ ऐसा है कि, हर दूसरे शीर्ष के लिए $w$ , रेखांकन का एक रेखांकन समरूपता है जिसके लिए छवि $v$ दूरी के भीतर है $D$ का $w$ ; समतुल्य रूप से, एक जुड़ा हुआ स्थानीय रूप से परिमित रेखांकन लगभग सममित होता है यदि इसके ऑटोमोर्फिज़्म समूह में बहुत सी कक्षाएँ होती हैं। जैसा कि वह दिखाता है, प्रत्येक स्थानीय रूप से परिमित लगभग-सममित रेखांकन के लिए, छोरों की संख्या या तो अधिकतम दो या बेशुमार है; यदि यह बेशुमार है, तो सिरों में कैंटर सेट की टोपोलॉजी होती है। इसके अतिरिक्त, मोहर दिखाता है कि सिरों की संख्या चीजर स्थिरांक (रेखांकन सिद्धांत) को नियंत्रित करती है

h=\inf \left\{{\frac {|\partial V|}{|V|}}\right\},

कहाँ

V

रेखांकऩ के शीर्षों के सभी परिमित गैर-रिक्त सेटों की श्रेणियाँ और कहाँ

\partial V

एक समापन बिंदु के साथ किनारों के सेट को दर्शाता है

V

. बेशुमार सिरों वाले लगभग-सममित रेखांकन के लिए,

h>0

; हालाँकि, केवल दो सिरों वाले लगभग-सममित रेखांकन के लिए,

h=0

.

केली रेखांकन

दो जनरेटर पर मुक्त समूह का केली रेखांकन

a

और

b

. समूह के छोरपहचान तत्व से किरणों (अनंत पथ) के साथ एक-से-एक पत्राचार में हैं

e

रेखांकन के किनारे तक।

समूह के लिए प्रत्येक समूह (गणित) और जेनरेटर का एक सेट केली रेखांकन निर्धारित करता है, एक रेखांकन जिसका शिखर समूह तत्व हैं और किनारे तत्वों के जोड़े हैं $(x,gx)$ कहाँ $g$ जनरेटर में से एक है। एक परिमित रूप से उत्पन्न समूह के मामले में, समूह के सिरों को जनरेटर के परिमित सेट के लिए केली रेखांकन के सिरों के रूप में परिभाषित किया गया है; यह परिभाषा जेनरेटर की पसंद के तहत अपरिवर्तनीय है, इस अर्थ में कि यदि जेनरेटर के दो अलग-अलग परिमित सेट चुने जाते हैं, तो दो केली रेखांकन के छोरएक-से-एक पत्राचार में एक-दूसरे के साथ होते हैं।

उदाहरण के लिए, प्रत्येक मुक्त समूह में एक केली रेखांकन होता है (इसके मुफ्त जेनरेटर के लिए) जो कि एक पेड़ है। एक जनरेटर पर मुक्त समूह केली रेखांकन के रूप में दो छोरों के साथ एक दोगुना अनंत पथ है। हर दूसरे मुक्त समूह के अपरिमित रूप से अनेक छोर होते हैं।

प्रत्येक सूक्ष्म रूप से उत्पन्न अनंत समूह में या तो 1, 2, या असीम रूप से कई सिरे होते हैं, और समूहों के सिरों के बारे में स्टालिंग्स प्रमेय एक से अधिक छोर वाले समूहों का अपघटन प्रदान करता है।^[11] विशेष रूप से:

एक निश्चित रूप से उत्पन्न अनंत समूह के 2 छोर होते हैं यदि और केवल अगर उसके पास एक उपसमूह के परिमित सूचकांक का चक्रीय समूह उपसमूह है।
एक परिमित रूप से उत्पन्न अनंत समूह के असीम रूप से कई छोर होते हैं यदि और केवल अगर यह या तो समामेलन के साथ एक गैर-तुच्छ मुक्त उत्पाद है या परिमित समामेलन के साथ एचएनएन-विस्तार है।
अन्य सभी अंतिम रूप से उत्पन्न अनंत समूहों का ठीक एक छोर होता है।

↑ However, as Krön & Möller (2008) point out, ends of graphs were already considered by Freudenthal (1945).
↑ Halin (1964).
↑ E.g., this is the form of the equivalence relation used by Diestel & Kühn (2003).
↑ ^4.0 ^4.1 The haven nomenclature, and the fact that two rays define the same haven if and only if they are equivalent, is due to Robertson, Seymour & Thomas (1991). Diestel & Kühn (2003) proved that every haven comes from an end, completing the bijection between ends and havens, using a different nomenclature in which they called havens "directions".
↑ The proof by Diestel & Kühn (2003) that every haven can be defined by a ray is nontrivial and involves two cases. If the set $S=\bigcap _{X}\left(\beta (X)\cup X\right)$ (where $X$ ranges over all finite sets of vertices) is infinite, then there exists a ray that passes through infinitely many vertices of $S$ , which necessarily determines $\beta$ . On the other hand, if $S$ is finite, then Diestel & Kühn (2003) show that in this case there exists a sequence of finite sets $X_{i}$ that separate the end from all points whose distance from an arbitrarily chosen starting point in $G\setminus S$ is $i$ . In this case, the haven is defined by any ray that is followed by a robber using the haven to escape police who land at set $X_{i}$ in round $i$ of the pursuit–evasion game.
↑ More precisely, in the original formulation of this result by Halin (1964) in which ends are defined as equivalence classes of rays, every equivalence class of rays of $G$ contains a unique nonempty equivalence class of rays of the spanning forest. In terms of havens, there is a one-to-one correspondence of havens of order $\aleph _{0}$ between $G$ and its spanning tree $T$ for which $\beta _{T}(X)\subset \beta _{G}(X)$ for every finite set $X$ and every corresponding pair of havens $\beta _{T}$ and $\beta _{G}$ .
↑ Seymour & Thomas (1991); Thomassen (1992); Diestel (1992).
↑ Diestel & Kühn (2003).
↑ Diestel (2006).
↑ Halin (1965); Diestel (2004).
↑ Stallings (1968, 1971).

संदर्भ

Diestel, Reinhard (1992), "The end structure of a graph: recent results and open problems", Discrete Mathematics, 100 (1–3): 313–327, doi:10.1016/0012-365X(92)90650-5, MR 1172358
Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, doi:10.1007/BF02941538, MR 2112834
Diestel, Reinhard (2006), "End spaces and spanning trees", Journal of Combinatorial Theory, Series B, 96 (6): 846–854, doi:10.1016/j.jctb.2006.02.010, MR 2274079
Diestel, Reinhard; Kühn, Daniela (2003), "Graph-theoretical versus topological ends of graphs", Journal of Combinatorial Theory, Series B, 87 (1): 197–206, doi:10.1016/S0095-8956(02)00034-5, MR 1967888
Freudenthal, Hans (1931), "Über die Enden topologischer Räume und Gruppen", Mathematische Zeitschrift, 33: 692–713, doi:10.1007/BF01174375
Freudenthal, Hans (1945), "Über die Enden diskreter Räume und Gruppen", Commentarii Mathematici Helvetici, 17: 1–38, doi:10.1007/bf02566233, MR 0012214
Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen, 157 (2): 125–137, doi:10.1007/bf01362670, hdl:10338.dmlcz/102294, MR 0170340
Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten, 30 (1–2): 63–85, doi:10.1002/mana.19650300106, MR 0190031
Krön, Bernhard; Möller, Rögnvaldur G. (2008), "Metric ends, fibers and automorphisms of graphs" (PDF), Mathematische Nachrichten, 281 (1): 62–74, doi:10.1002/mana.200510587, MR 2376468
Mohar, Bojan (1991), "Some relations between analytic and geometric properties of infinite graphs" (PDF), Discrete Mathematics, 95 (1–3): 193–219, doi:10.1016/0012-365X(91)90337-2, MR 1141939
Robertson, Neil; Seymour, Paul; Thomas, Robin (1991), "Excluding infinite minors", Discrete Mathematics, 95 (1–3): 303–319, doi:10.1016/0012-365X(91)90343-Z, MR 1141945
Seymour, Paul; Thomas, Robin (1991), "An end-faithful spanning tree counterexample", Proceedings of the American Mathematical Society, 113 (4): 1163–1171, doi:10.2307/2048796, JSTOR 2048796, MR 1045600
Stallings, John R. (1968), "On torsion-free groups with infinitely many ends", Annals of Mathematics, Second Series, 88 (2): 312–334, doi:10.2307/1970577, JSTOR 1970577, MR 0228573
Stallings, John R. (1971), Group theory and three-dimensional manifolds: A James K. Whittemore Lecture in Mathematics given at Yale University, 1969, Yale Mathematical Monographs, vol. 4, New Haven, Conn.: Yale University Press, MR 0415622
Thomassen, Carsten (1992), "Infinite connected graphs with no end-preserving spanning trees", Journal of Combinatorial Theory, Series B, 54 (2): 322–324, doi:10.1016/0095-8956(92)90059-7, hdl:10338.dmlcz/127625, MR 1152455

[1] However, as Krön & Möller (2008) point out, ends of graphs were already considered by Freudenthal (1945).

[FOOTNOTEHalin1964-2] Halin (1964).

[3] E.g., this is the form of the equivalence relation used by Diestel & Kühn (2003).

[haven-end-4] 4.0 ^4.1 The haven nomenclature, and the fact that two rays define the same haven if and only if they are equivalent, is due to Robertson, Seymour & Thomas (1991). Diestel & Kühn (2003) proved that every haven comes from an end, completing the bijection between ends and havens, using a different nomenclature in which they called havens "directions".

[5] The proof by Diestel & Kühn (2003) that every haven can be defined by a ray is nontrivial and involves two cases. If the set $S=\bigcap _{X}\left(\beta (X)\cup X\right)$ (where $X$ ranges over all finite sets of vertices) is infinite, then there exists a ray that passes through infinitely many vertices of $S$ , which necessarily determines $\beta$ . On the other hand, if $S$ is finite, then Diestel & Kühn (2003) show that in this case there exists a sequence of finite sets $X_{i}$ that separate the end from all points whose distance from an arbitrarily chosen starting point in $G\setminus S$ is $i$ . In this case, the haven is defined by any ray that is followed by a robber using the haven to escape police who land at set $X_{i}$ in round $i$ of the pursuit–evasion game.

[6] More precisely, in the original formulation of this result by Halin (1964) in which ends are defined as equivalence classes of rays, every equivalence class of rays of $G$ contains a unique nonempty equivalence class of rays of the spanning forest. In terms of havens, there is a one-to-one correspondence of havens of order $\aleph _{0}$ between $G$ and its spanning tree $T$ for which $\beta _{T}(X)\subset \beta _{G}(X)$ for every finite set $X$ and every corresponding pair of havens $\beta _{T}$ and $\beta _{G}$ .

[7] Seymour & Thomas (1991); Thomassen (1992); Diestel (1992).

[8] Diestel & Kühn (2003).

[FOOTNOTEDiestel2006-9] Diestel (2006).

[10] Halin (1965); Diestel (2004).

[11] Stallings (1968, 1971).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Anonymous

Search

अनंत (आलेख सिद्धांत )

Namespaces

More

Page actions

Contents

परिभाषा और विशेषता

उदाहरण

सांस्थितिक सिरों से संबंध