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

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

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

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

रेखांकन के एंड रुडोल्फ हेलिन (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$ .) एक रेखांकन में जिसके बहुत से एंड हैं, प्रत्येक एंड मुक्त होना चाहिए। हेलिन (1964) सिद्ध करता है कि यदि $G$ अपरिमित रूप से कई एंड हैं, तो या तो एक एंड सम्मलित है जो मुक्त नहीं है, या किरणों का एक अनंत परिवार सम्मलित है जो एक सामान्य प्रारंभिक शीर्ष साझा करता है और अन्यथा एक दूसरे से अलग होता है।

मोटा एंड

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

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

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

मोहर (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

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

उदाहरण

सांस्थितिक एंड से संबंध