वक्र संकुलन प्रमेय

"वृत्त ग्राफ" redirects here. For समान-त्रिज्या डिस्क के संपर्क ग्राफ, see पेनी ग्राफ.

पाँच-शीर्ष तलीय ग्राफ के लिए एक वृत्त संकुलन

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

वक्र संकुलन प्रमेय: प्रत्येक जुड़े सरल प्लानर ग्राफ 'जी' के लिए तल में एक वक्र संकुलन होती है जिसका प्रतिच्छेदन ग्राफ (ग्राफ समरूपता) जी है।

अद्वितीयता

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

'कोएबे-एंड्रीव-थर्स्टन प्रमेय': यदि जी एक परिमित अधिकतम प्लेनर ग्राफ है, तो वक्र संकुलन जिसका स्पर्शरेखा ग्राफ जी के लिए आइसोमॉर्फिक है, अद्वितीय है, मोबियस परिवर्तन और लाइनों में प्रतिबिंब तक।

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

किसी परिमित समुच्चय में अधिकतम मान के अस्तित्व के आधार पर और इस अवलोकन पर कि, तीन पारस्परिक रूप से स्पर्शरेखा मंडलों के केंद्रों को जोड़ने वाले त्रिभुज में, एक के केंद्र में बने कोण के आधार पर, एक ही अद्वितीयता संपत्ति का एक और प्राथमिक प्रमाण भी है। वृत्तों की संख्या अपनी त्रिज्या में एकरसता घट रही है और दो अन्य त्रिज्याओं में एकरसता बढ़ रही है। एक ही ग्राफ के लिए दो संकुलन दी गई हैं $G$, कोई इन दो संकुलों में बाहरी वृत्तों को एक दूसरे के अनुरूप बनाने के लिए प्रतिबिंब और मोबियस रूपांतरण लागू कर सकता है और एक ही त्रिज्या हो सकता है। तो करने दें $v$ का आंतरिक शीर्ष हो $G$ जिसके लिए दो संकुलन में वक्रों के आकार हैं जो जितना संभव हो उतना दूर हैं: यानी, चुनें $v$ अनुपात को अधिकतम करने के लिए $r_{1}/r_{2}$ दो संकुलन में इसके वक्रों की त्रिज्या। के प्रत्येक त्रिकोणीय चेहरे के लिए $G$ युक्त $v$, यह इस प्रकार है कि वृत्त के केंद्र में कोण के लिए $v$ पहली संकुलन में दूसरी संकुलन के कोण से कम या उसके बराबर है, समानता के साथ तभी संभव है जब त्रिभुज बनाने वाले अन्य दो वृत्तों का अनुपात समान हो $r_{1}/r_{2}$ दो संकुलन में रेडी की। लेकिन त्रिभुज के केंद्र को घेरने वाले इन सभी त्रिभुजों के कोणों का योग होना चाहिए $2\pi$ दोनों संकुलन में, इसलिए सभी पड़ोसी कोने $v$ के समान अनुपात होना चाहिए $v$ अपने आप। इन अन्य वृत्तों पर समान तर्क लागू करने से, यह पता चलता है कि दोनों संकुलों में सभी वृत्तों का अनुपात समान है। लेकिन बाहरी वक्रों को एक अनुपात में बदल दिया गया है, इसलिए $r_{1}/r_{2}=1$ और दो संकुलन में सभी वक्रों के लिए समान त्रिज्या है।

अनुरूप मानचित्रण सिद्धांत के साथ संबंध

वक्र संकुलन का उपयोग लगभग अनुरूप मैपिंग के बीच किया जा सकता है निर्दिष्ट डोमेन। बाईं ओर प्रत्येक वृत्त दाईं ओर एक वृत्त से मेल खाता है।

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

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

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

थर्स्टन के अनुमान द्वारा सिद्ध किया गया था Rodin & Sullivan (1987). अधिक सटीक रूप से, उन्होंने दिखाया कि, जैसे n अनंत तक जाता है, फ़ंक्शन f_nथर्स्टन की विधि का उपयोग त्रिज्या -1 / एन वक्र के हेक्सागोनल संकुलन से ए से सी के अनुरूप मानचित्र के ए के कॉम्पैक्ट सबसेट पर समान रूप से अभिसरण करता है।

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

प्रमाण

वक्र संकुलन प्रमेय के कई ज्ञात प्रमाण हैं। पॉल कोबे का मूल प्रमाण है उनके अनुरूप एकरूपता प्रमेय के आधार पर कहा गया है कि एक अंतिम रूप से जुड़ा प्लानर डोमेन अनुरूप रूप से एक वक्र डोमेन के बराबर है। कई अलग-अलग सामयिक प्रमाण हैं जो जाने जाते हैं। थर्स्टन की उपपत्ति Brouwer नियत बिंदु प्रमेय | Brouwer की नियत बिंदु प्रमेय पर आधारित है। एक स्नातक छात्र के रूप में, प्रिंसटन विश्वविद्यालय में थर्स्टन द्वारा ओडेड श्राम की देखरेख की गई थी। जैसा Rohde (2011, p. 1628) याद करता है, श्रैम के शोध प्रबंध में एक काव्यात्मक वर्णन है कि वक्र संकुलन के लिए अस्तित्व को निश्चित बिंदु प्रमेय से कैसे घटाया जा सकता है: कोई भी भयानक राक्षस को अपनी बाहों को सरासर क्रोध में झूलते हुए देख सकता है, एक भयानक फुफकार पैदा करने वाले तंबू, जैसे वे रगड़ते हैं एक दूसरे के खिलाफ। समाधान के निर्माण के पेरोन की विधि के असतत संस्करण का उपयोग करने का एक प्रमाण भी है डिरिचलेट समस्या। यवेस कॉलिन डी वेर्डिएर साबित हुए एक निश्चित कॉन्फ़िगरेशन पर एक उत्तल फ़ंक्शन के न्यूनतम के रूप में वक्र संकुलन का अस्तित्व अंतरिक्ष।

अनुप्रयोग

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

एक पॉलीहेड्रॉन और उसका मिडस्फीयर। वक्र संकुलन प्रमेय का तात्पर्य है कि प्रत्येक बहुफलकीय ग्राफ को एक पॉलीहेड्रॉन के ग्राफ के रूप में दर्शाया जा सकता है जिसमें मिडस्फीयर होता है।

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

एल्गोरिथम पहलू

Collins & Stephenson (2003) विलियम थर्स्टन के विचारों के आधार पर वक्र संकुलन खोजने के लिए एक संख्यात्मक विश्राम (पुनरावृत्ति विधि) का वर्णन करें। वक्र संकुलन समस्या का संस्करण जिसे वे हल करते हैं, इनपुट के रूप में एक प्लानर ग्राफ लेता है, जिसमें सभी आंतरिक चेहरे त्रिकोण होते हैं और जिसके लिए बाहरी कोने सकारात्मक संख्याओं द्वारा लेबल किए जाते हैं। यह आउटपुट के रूप में एक वक्र संकुलन का उत्पादन करता है जिसकी स्पर्शरेखाएं दिए गए ग्राफ का प्रतिनिधित्व करती हैं, और जिसके लिए बाहरी कोने का प्रतिनिधित्व करने वाले वक्रों में इनपुट में निर्दिष्ट त्रिज्या होती है। जैसा कि वे सुझाव देते हैं, समस्या की कुंजी पहले संकुलन में वक्रों की त्रिज्या की गणना करना है; एक बार त्रिज्या ज्ञात हो जाने के बाद, वक्रों की ज्यामितीय स्थिति की गणना करना मुश्किल नहीं होता है। वे अस्थायी रेडी के एक सेट से शुरू होते हैं जो वैध संकुलन के अनुरूप नहीं होते हैं, और फिर बार-बार निम्न चरणों का पालन करते हैं:

1. इनपुट ग्राफ़ का एक आंतरिक शीर्ष v चुनें।
2. कुल कोण θ की गणना करें कि इसके k पड़ोसी मंडल वक्र के चारों ओर v के लिए कवर करेंगे, यदि पड़ोसियों को एक दूसरे के लिए स्पर्शरेखा और उनके अस्थायी त्रिज्या का उपयोग करके केंद्रीय वक्र में रखा गया हो।
3. पड़ोसी वक्रों के लिए एक प्रतिनिधि त्रिज्या r निर्धारित करें, जैसे कि त्रिज्या r के k वृत्त वही आवरण कोण θ देंगे जो v के पड़ोसी देते हैं।
4. v के लिए नई त्रिज्या को वह मान सेट करें जिसके लिए त्रिज्या r के k वृत्त ठीक 2π का आवरण कोण देंगे।

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

Mohar (1993) एक पॉलीहेड्रल ग्राफ और उसके दोहरे के एक साथ संकुलन को खोजने के लिए एक समान पुनरावृत्त तकनीक का वर्णन करता है, जिसमें दोहरे वृत्त प्रारंभिक वक्रों के समकोण पर होते हैं। वह साबित करता है कि विधि में वक्रों की संख्या और लॉग 1/ε में समय लगता है, जहां ε केंद्रों की दूरी और एक इष्टतम संकुलन में गणना की गई संकुलन की त्रिज्या पर एक सीमा है।

सामान्यीकरण

वक्र संकुलन प्रमेय उन ग्राफ़ों को सामान्यीकृत करता है जो प्लानर नहीं हैं। अगर जी एक ग्राफ है जिसे सतह एस पर एम्बेड किया जा सकता है, तो S पर एक स्थिर वक्रता रीमैनियन कई गुना d और (S, d) पर एक वक्र संकुलन है जिसका संपर्क ग्राफ G के लिए आइसोमॉर्फिक है। यदि S बंद है (कॉम्पैक्ट जगह और सीमा के साथ मैनिफोल्ड के बिना) और G, S का त्रिभुज है, फिर (S, d) और संकुलन अनुरूप समानता तक अद्वितीय हैं। यदि S गोला है, तो यह तुल्यता मोबियस रूपांतरणों तक है; यदि यह एक टोरस है, तो तुल्यता एक स्थिरांक और आइसोमेट्री द्वारा स्केलिंग तक है, जबकि यदि S में जीनस (गणित) कम से कम 2 है, तो तुल्यता आइसोमेट्रीज़ तक है।

वक्र संकुलन प्रमेय के एक अन्य सामान्यीकरण में स्पर्शरेखा की स्थिति को पड़ोसी कोने के अनुरूप वक्रों के बीच एक निर्दिष्ट चौराहे कोण के साथ बदलना शामिल है। एक विशेष रूप से सुरुचिपूर्ण संस्करण इस प्रकार है। मान लीजिए कि जी एक परिमित कनेक्टिविटी (ग्राफ सिद्धांत) | 3-कनेक्टेड प्लानर ग्राफ (यानी, एक पॉलीहेड्रल ग्राफ) है, तो वक्र संकुलन की एक युग्म है, जिसका चौराहे का ग्राफ जी के लिए आइसोमॉर्फिक है, दूसरा जिसका इंटरसेक्शन ग्राफ आइसोमोर्फिक है जी के दोहरे ग्राफ के लिए, और G में प्रत्येक शीर्ष के लिए और उसके निकटवर्ती फलक के लिए, पहले संकुलन में शीर्ष के संगत वृत्त चेहरे के अनुरूप दूसरी संकुलन में वक्र के साथ लंबवत रूप से प्रतिच्छेद करता है। उदाहरण के लिए, इस परिणाम को टेट्राहेड्रॉन के ग्राफ पर लागू करने से, किन्हीं भी चार पारस्परिक स्पर्शरेखा वक्रों के लिए, चार पारस्परिक रूप से स्पर्शरेखा वाले वक्रों का एक दूसरा सेट मिलता है, जिनमें से प्रत्येक पहले चार में से तीन के लिए ऑर्थोगोनल है। एक और सामान्यीकरण, प्रतिच्छेदन कोण को व्युत्क्रम दूरी के साथ बदलकर, संकुलन के विनिर्देशन की अनुमति देता है जिसमें कुछ वक्रों को पार करने या स्पर्शरेखा होने के बजाय एक दूसरे से अलग होना आवश्यक है। फिर भी एक अन्य प्रकार के सामान्यीकरण उन आकृतियों की अनुमति देते हैं जो वृत्त नहीं हैं। मान लीजिए कि G = (V, E) एक परिमित समतलीय ग्राफ़ है, और G के प्रत्येक शीर्ष v के लिए एक आकृति से मेल खाता है $K_{v}\subset \mathbb {R} ^{2}$, जो होमियोमोर्फिज्म है बंद इकाई डिस्क के लिए और जिसकी सीमा चिकनी है। फिर संकुलन होती है $P=(K'_{v}:v\in V)$ प्लेन में ऐसा है कि $K'_{v}\cap K'_{u}\neq \varnothing$ अगर और केवल अगर $[v,u]\in E$ और प्रत्येक के लिए $v\in V$ सेट $K'_{v}$ से प्राप्त होता है $K_{v}$ अनुवाद करके और स्केलिंग। (ध्यान दें कि मूल वक्र संकुलन प्रमेय में प्रति शीर्ष तीन वास्तविक पैरामीटर हैं, जिनमें से दो संगत वृत्त के केंद्र का वर्णन करते हैं और जिनमें से एक त्रिज्या का वर्णन करता है, और प्रति किनारा एक समीकरण है। यह इस सामान्यीकरण में भी है।) कोबे के मूल प्रमाण को लागू करके इस सामान्यीकरण का एक प्रमाण प्राप्त किया जा सकता हैऔर प्रमेय ब्रांट का और हैरिंगटन यह बताते हुए कि कोई भी अंतिम रूप से जुड़ा हुआ डोमेन अनुरूप रूप से समतुल्य है एक प्लानर डोमेन जिसके सीमा घटकों में निर्दिष्ट आकार हैं, अनुवाद और स्केलिंग तक।

इतिहास

सर्किल संकुलन का अध्ययन 1910 की शुरुआत में, phyllotaxis (पौधे के विकास के गणित) में डॉयल सर्पिल पर अर्नोल्ड एमच के काम में किया गया था। वक्र संकुलन प्रमेय को सबसे पहले पॉल कोएबे ने सिद्ध किया था। विलियम थर्स्टन वक्र संकुलन प्रमेय को फिर से खोजा, और ने नोट किया कि यह ई. एम. एंड्रीव के काम का अनुसरण करता है। थर्स्टन ने यूनिट डिस्क के इंटीरियर पर तल के एक सरल रूप से जुड़े उचित उपसमुच्चय के होमोमोर्फिज्म को प्राप्त करने के लिए वक्र संकुलन प्रमेय का उपयोग करने के लिए एक योजना भी प्रस्तावित की। वक्र संकुलन के लिए थर्स्टन अनुमान उनका अनुमान है कि होमोमोर्फिज्म रीमैन मैपिंग प्रमेय में परिवर्तित हो जाएगा क्योंकि वक्रों की त्रिज्या शून्य हो जाती है। थर्स्टन अनुमान बाद में सिद्ध हुआ बर्टन रोडिन और डेनिस सुलिवन द्वारा। इसने वक्र संकुलन प्रमेय के विस्तार, संबंधों पर शोध की सुगबुगाहट को जन्म दिया अनुरूप मानचित्रण, और अनुप्रयोग।

यह भी देखें

• Apollonian गैसकेट, एक अनंत संकुलन त्रिकोणीय अंतराल को बार-बार भरने से बनता है
• सर्किल संकुलन , निर्दिष्ट स्पर्शरेखाओं के बिना वक्रों की सघन व्यवस्था
• डॉयल सर्पिल, अनंत 6-नियमित प्लानर ग्राफ का प्रतिनिधित्व करने वाली वक्र संकुलन
• फोर्ड वक्र , परिमेय संख्या रेखा के साथ वक्रों की संकुलन
• पेनी ग्राफ, कॉइन ग्राफ जिसके सभी वृत्तों की त्रिज्याएँ समान हैं
• रिंग लेम्मा, एक संकुलन में आसन्न वक्रों के आकार पर बाध्य

संदर्भ

• Andreev, E. M. (1970), "Convex polyhedra in Lobačevskiĭ spaces", Mat. Sb., New Series, 81 (123): 445–478, Bibcode:1970SbMat..10..413A, doi:10.1070/SM1970v010n03ABEH001677, MR 0259734.
• Beardon, Alan F.; Stephenson, Kenneth (1990), "The uniformization theorem for circle packings", Indiana Univ. Math. J., 39 (4): 1383–1425, doi:10.1512/iumj.1990.39.39062
• Beardon, Alan F.; Stephenson, Kenneth (1991), "The Schwarz-Pick lemma for circle packings", Illinois J. Math., 35 (4): 577–606, doi:10.1215/ijm/1255987673
• Andreev, E. M. (1970), "Convex polyhedra of finite volume in Lobačevskiĭ space", Mat. Sb., New Series, 83 (125): 256–260, Bibcode:1970SbMat..12..255A, doi:10.1070/SM1970v012n02ABEH000920, MR 0273510.
• Benjamini, Itai; Schramm, Oded (2001), "Recurrence of distributional limits of finite planar graphs", Electronic Journal of Probability, 6, doi:10.1214/EJP.v6-96, MR 1873300, S2CID 2862151.
• Brandt, M. (1980), "Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete", Bull. De la Soc. Des Sc. Et des Lettr. De Łódź, 30.
• Brightwell, Graham R.; Scheinerman, Edward R. (1993), "Representations of planar graphs", SIAM J. Discrete Math., 6 (2): 214–229, doi:10.1137/0406017.
• Carter, Ithiel; Rodin, Burt (1992), "An inverse problem for circle packing and conformal mapping", Trans. Amer. Math. Soc., 334 (2): 861–875, doi:10.1090/S0002-9947-1992-1081937-X
• Colin de Verdière, Yves (1991), "Une principe variationnel pour les empilements de cercles", Inventiones Mathematicae, 104 (1): 655–669, Bibcode:1991InMat.104..655C, doi:10.1007/BF01245096, S2CID 121028882.
• Collins, Charles R.; Stephenson, Kenneth (2003), "A circle packing algorithm", Computational Geometry. Theory and Applications, 25 (3): 233–256, doi:10.1016/S0925-7721(02)00099-8, MR 1975216.
• Harrington, Andrew N. (1982), "Conformal mappings onto domains with arbitrarily specified boundary shapes", Journal d'Analyse Mathématique, 41 (1): 39–53, doi:10.1007/BF02803393, S2CID 120752035
• Jonnason, Johan; Schramm, Oded (2000), "On the cover time of planar graphs", Electronic Communications in Probability, 5: 85–90.
• Kelner, Jonathan A. (2006), "Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus", SIAM Journal on Computing, 35 (4): 882–902, doi:10.1137/S0097539705447244, hdl:1721.1/30169.
• Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör (2011), "Drawing planar graphs of bounded degree with few slopes", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, MR 2781274, S2CID 817874.
• Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88: 141–164.
• Lipton, Richard J.; Tarjan, Robert E. (1979), "A separator theorem for planar graphs", SIAM Journal on Applied Mathematics, 36 (2): 177–189, CiteSeerX 10.1.1.104.6528, doi:10.1137/0136016.
• Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.
• Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997), "Separators for sphere-packings and nearest neighbor graphs", J. ACM, 44 (1): 1–29, doi:10.1145/256292.256294, S2CID 17331739.
• Mohar, Bojan (1993), "A polynomial time circle packing algorithm", Discrete Mathematics, 117 (1–3): 257–263, doi:10.1016/0012-365X(93)90340-Y.
• Rodin, Burton; Sullivan, Dennis (1987), "The convergence of circle packings to the Riemann mapping", Journal of Differential Geometry, 26 (2): 349–360, doi:10.4310/jdg/1214441375.
• Rohde, Steffen (2011), "Oded Schramm: from circle packing to SLE", Ann. Probab., 39 (5): 1621–1667, doi:10.1214/10-AOP590
• Stephenson, Kenneth (1999), "The approximation of conformal structures via circle packing" (PDF), Computational methods and function theory 1997 (Nicosia), Ser. Approx. Decompos., vol. 11, World Sci. Publ., River Edge, NJ, pp. 551–582, MR 1700374.
• Stephenson, Ken (2003), "Circle packing: a mathematical tale" (PDF), Notices Amer. Math. Soc., 50: 1376–1388
• Stephenson, Ken (2005), Introduction to circle packing, the theory of discrete analytic functions, Cambridge: Cambridge University Press.
• Thurston, William (1985), The finite Riemann mapping theorem, Invited talk at the International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture.
• Thurston, William (1978–1981), The geometry and topology of 3-manifolds, Princeton lecture notes.

बाहरी संबंध

• CirclePack (free software for constructing circle packings from graphs) and Circle packing bibliography by Kenneth Stephenson, Univ. of Tennessee