अपोलोनियन नेटवर्क

अपोलोनियन नेटवर्क

गोल्डनर-हैरी ग्राफ, गैर-हैमिल्टनियन अपोलोनियन नेटवर्क

संयोजी गणित में, अपोलोनियन नेटवर्क अप्रत्यक्ष ग्राफ है जो त्रिभुज को तीन छोटे त्रिभुजों में पुनरावर्ती रूप से उप-विभाजित करने की प्रक्रिया द्वारा बनता है। अपोलोनियन नेटवर्क को समान रूप से समतली ग्राफ 3-ट्री , अधिकतम तलीय कॉर्डल ग्राफ, विशिष्ट 4-रंगीन तलीय ग्राफ, और स्टैक्ड बहुतलीय के ग्राफ के रूप में परिभाषित किया जा सकता है। उनका नाम पेर्गा के अपोलोनियस के नाम पर रखा गया है, जिन्होंने संबंधित सर्कल-पैकिंग निर्माण का अध्ययन किया था।

परिभाषा

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

उदाहरण

तीन और चार शीर्षों पर पूर्ण रेखांकन, K₃ और K₄, दोनों अपोलोनियन नेटवर्क हैं। K₃ त्रिकोण से शुरू करके और किसी भी उपखंड का प्रदर्शन नहीं करके बनता है, जबकि K₄ रोकने से पहले ही उपखण्ड बनाकर बनाया जाता है।

गोल्डनर-हैरी ग्राफ एक अपोलोनियन नेटवर्क है जो सबसे छोटा गैर-हैमिल्टनियन चक्र अधिकतम तलीय ग्राफ बनाता है। एक और अधिक जटिल अपोलोनियन नेटवर्क का उपयोग निशिजेकी (1980) द्वारा 1-कठिन गैर-हैमिल्टनियन अधिकतम तलीय ग्राफ का उदाहरण प्रदान करने के लिए किया गया था।

ग्राफ-सैद्धांतिक लक्षण वर्णन

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

तारतम्य

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

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

अद्वितीय रंगीनता

प्रत्येक अपोलोनियन नेटवर्क भी एक विशिष्ट 4-रंगीन ग्राफ है। क्योंकि यह एक समतली ग्राफ है, चार रंग प्रमेय का अर्थ है कि इसमें केवल चार रंगों के साथ ग्राफ रंग है, लेकिन बार प्रारंभिक त्रिकोण के तीन रंगों का चयन करने के बाद, प्रत्येक उत्तरोत्तर शीर्ष के रंग के लिए केवल ही संभव विकल्प होता है, इसलिए रंगों के सेट के क्रमपरिवर्तन तक इसमें ठीक 4-रंग होता है। यह साबित करना अधिक कठिन है, लेकिन यह भी सच है कि प्रत्येक विशिष्ट 4-रंगीय तलीय ग्राफ अपोलोनियन नेटवर्क है। इसलिए, अपोलोनियन नेटवर्क को विशिष्ट रूप से 4-रंगीन तलीय ग्राफ़ के रूप में चित्रित किया जा सकता है। अपोलोनियन नेटवर्क, समतल ग्राफ़ के उदाहरण भी प्रदान करते हैं जिनमें k > 4 के लिए यथासंभव कुछ k-रंग होते हैं।

अपोलोनियन नेटवर्क भी अधिकतम तलीय ग्राफ़ हैं जो (बार बाहरी तल तय हो जाने पर) में अद्वितीय श्नाइडर लकड़ी होती है, जो ग्राफ़ के किनारों का विभाजन बाहरी तल के तीन कोने पर निहित तीन अंतरापत्रित ट्रीस में होती है।

ट्रीविड्थ

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

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

विकृति

अपोलोनियन नेटवर्क के प्रत्येक सबग्राफ में, सबसे हाल ही में जोड़े गए शीर्ष् में अधिकतम तीन डिग्री (ग्राफ सिद्धांत) हैं, इसलिए अपोलोनियन नेटवर्क में विकृति (ग्राफ प्रमेय) तीन हैं। जिस क्रम में नेटवर्क बनाने के लिए शीर्ष जोड़े जाते हैं, इसलिए अध: पतन क्रम होता है, और अपोलोनियन नेटवर्क 3-विकृति अधिकतम तलीय ग्राफ के साथ मेल खाते हैं।

आकार

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

आकार ग्राफ सिद्धांत में, अपोलोनियन नेटवर्क भी बिल्कुल n-शीर्ष् तलीय ग्राफ हैं, जिसमें ब्लॉक की संख्या अपने अधिकतम, n − 3 को प्राप्त करती है, और प्लेनर ग्राफ जिसमें त्रिकोण की संख्या अपने अधिकतम, 3n − 8 को प्राप्त करती है। प्रत्येक के बाद से एक समतल ग्राफ का K₄ तलीय ग्राफ का सबग्राफ ब्लॉक होना चाहिए, ये भी तलीय ग्राफ हैं जिसमे K₄ सबग्राफ की संख्या अपने अधिकतम, n − 3 को प्राप्त करती है, और ऐसे ग्राफ़ जिनमें किसी भी प्रकार के क्लिक (ग्राफ़ सिद्धांत) की संख्या अधिकतम 8n − 16 प्राप्त करती है।

ज्यामितीय अहसास

सर्कल पैकिंग से निर्माण

अपोलोनियन गैसकेट का उदाहरण

सर्कल पैकिंग से अपोलोनियन नेटवर्क का निर्माण

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

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

पॉलीहेड्रा

टर्नरी टेट्राहेड्रा की, 8-शीर्ष् अपोलोनियन नेटवर्क का बहुफलकीय अहसास

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

त्रिभुज जाल

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

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

गुण और अनुप्रयोग

मिलान-मुक्त रेखांकन

प्लमर (1992) ने अपोलोनियन नेटवर्क का उपयोग अधिकतम प्लानर ग्राफ के एक अनंत परिवार के निर्माण के लिए किया, जिसमें शीर्ष की एक समान संख्या थी, लेकिन कोई पूर्ण मिलान नहीं था। प्लमर के ग्राफ दो चरणों में बनते हैं। पहले चरण में, त्रिकोण abc से शुरू होने वाले पहले चरण में उपखंड के त्रिकोणीय फलक को बार-बार उप-विभाजित किया जाता है जिसमें किनारा bc होता है: परिणाम एक ग्राफ होता है जिसमें अंतिम उपखंड शीर्ष से a होता है जिसमें प्रत्येक पथ शीर्ष से प्रत्येक b और c के किनारे होते हैं। दूसरे चरण में, परिणामी तलीय ग्राफ के त्रिकोणीय तलों में से प्रत्येक को बार और उपविभाजित किया जाता है। यदि से पथ a पहले चरण के अंतिम उपखंड शीर्ष की लंबाई भी है, तो समग्र ग्राफ़ में शीर्षों की संख्या भी सम है। हालाँकि, लगभग 2/3 शीर्ष दूसरे चरण में डाले गए हैं; ये स्वतंत्र सेट (ग्राफ़ सिद्धांत) बनाते हैं, और दूसरे से मेल नहीं खा सकते हैं, और न ही स्वतंत्र सेट के बाहर उन सभी के लिए मैच खोजने के लिए पर्याप्त शीर्ष हैं।

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

पावर लॉ ग्राफ

एंड्रेड et al. (2005) ने इस प्रकार के नेटवर्क के विशेष मामले की डिग्री (ग्राफ सिद्धांत) में बिजली कानूनों का अध्ययन किया, जो सभी त्रिभुजों को समान संख्या में उपविभाजित करके बनाया गया था। उन्होंने इन नेटवर्कों का उपयोग अलग-अलग आकार के कणों द्वारा अंतरिक्ष की पैकिंग के मॉडल के लिए किया था। उनके काम के आधार पर, अन्य लेखकों ने यादृच्छिक अपोलोनियन नेटवर्क पेश किए, जो बार-बार यादृच्छिक तल को उपविभाजित करने के लिए चुनते हैं, और उन्होंने दिखाया कि ये भी उनके डिग्री वितरण में शक्ति कानूनों का पालन करते हैं और छोटी औसत दूरी रखते हैं। एलन एम. फ्रीज़ और चारलमपोस ई. त्सौराकाकिस ने यादृच्छिक अपोलोनियन नेटवर्क के उच्चतम डिग्री और आइगेनवैल्यू का विश्लेषण किया था। एंड्रेड एट अल. ने यह भी देखा कि उनके नेटवर्क छोटे विश्व प्रभाव को संतुष्ट करते हैं, कि सभी कोने दूसरे से थोड़ी दूरी पर हैं। संख्यात्मक साक्ष्य के आधार पर उन्होंने अनुमान लगाया कि में यादृच्छिक रूप से चयनित जोड़े के बीच औसत दूरी (log n)^3/4 के लिये आनुपातिक होना चाहिए, लेकिन बाद में शोधकर्ताओं ने दिखाया कि औसत दूरी वास्तविक में log n आनुपातिक है।

कोण वितरण

बटलर & ग्राहम (2010) ने देखा कि यदि प्रत्येक नए शीर्ष को उसके त्रिकोण के केंद्र में रखा जाता है, जिससे किनारों को त्रिभुज के नए शीर्ष द्विभाजक

कोण द्विभाजक पर ले जाया जा सके, तो उपखंड में त्रिभुजों के कोणों के त्रिगुणों का सेट, जब के त्रिगुणों के रूप में पुनर्व्याख्या की जाती है समबाहु त्रिभुज में बिंदुओं की बैरीसेंट्रिक समन्वय प्रणाली (गणित), उपखंड के स्तरों की संख्या बढ़ने पर सिरपिन्स्की त्रिभुज के आकार में परिवर्तित हो जाती है।

हैमिलटोनिसिटी

टेको (1960) ने गलत तरीके से दावा किया कि सभी अपोलोनियन नेटवर्क में हैमिल्टनियन चक्र होते हैं; हालाँकि, गोल्डनर-हैरी ग्राफ प्रति उदाहरण प्रदान करता है। यदि अपोलोनियन नेटवर्क में ग्राफ की कठोरता से अधिक है (जिसका अर्थ है कि ग्राफ से किसी भी कोने को हटाने से हटाए गए कोने की संख्या की तुलना में कनेक्टेड घटकों की संख्या कम हो जाती है) तो यह आवश्यक रूप से हैमिल्टनियन चक्र है, लेकिन गैर-हैमिल्टनियन अपोलोनियन मौजूद है जो नेटवर्क जिनकी क्रूरता के बराबर है।

गणना

ताकेओ (1960) द्वारा अपोलोनियन त्रिभुजों की गणना की संयोजी गणना समस्या का अध्ययन किया गया, जिन्होंने दिखाया कि उनके पास समीकरण f(x) = 1 + x(f(x))³ द्वारा वर्णित सरल जनरेटिंग फ़ंक्शन f(x) है।

इस जनरेटिंग फ़ंक्शन में, डिग्री n की अवधि अपोलोनियन नेटवर्क की संख्या को एक निश्चित बाहरी त्रिकोण और n + 3 शिखर के साथ गिनाती है।

इस प्रकार, 3, 4, 5, ... कोने पर अपोलोनियन नेटवर्क (निश्चित बाहरी त्रिकोण के साथ) की संख्या हैं:

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sequence A001764 in the OEIS),

अनुक्रम जो त्रिगुट ट्रीस और उत्तल बहुभुजों के विच्छेदन को विषम-पक्षीय बहुभुजों में भी गिनता है।

उदाहरण के लिए, 12 6-शीर्ष् अपोलोनियन नेटवर्क हैं: तीन बाहरी त्रिभुज को बार उपविभाजित करके और फिर परिणामी त्रिभुजों में से दो को उपविभाजित करके बनाए गए हैं, और नौ बाहरी त्रिभुज को बार उपविभाजित करके, उसके त्रिभुज को उपविभाजित करके, और फिर परिणामी छोटे त्रिभुजों में से को उपविभाजित करके बनाया गया।

इतिहास

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

अपोलोनियन नेटवर्क से निकटता से संबंधित ज्यामितीय संरचनाओं का अध्ययन कम से कम 1960 के दशक के प्रारंभ से पॉलीहेड्रल कॉम्बिनेटरिक्स में किया गया है, जब उनका उपयोग किया गया था। Grünbaum (1963) ग्राफ़ का वर्णन करने के लिए जिसे केवल ही तरीके से पॉलीटॉप के ग्राफ़ के रूप में महसूस किया जा सकता है, बिना आयामी या संयोजी अस्पष्टता के, और द्वारा Moon & Moser (1963) बिना लंबे रास्तों वाले साधारण बहुतलीय को खोजने के लिए। ग्राफ सिद्धांत में, प्लेनेरिटी और ट्रेविड्थ के बीच घनिष्ठ संबंध वापस चला जाता है Robertson & Seymour (1984), जिन्होंने दिखाया कि ग्राफ़ के प्रत्येक लघु-बंद परिवार में या तो ट्रेविड्थ की सीमा होती है या इसमें सभी तलीय ग्राफ़ होते हैं। ग्राफ़ के वर्ग के रूप में तलीय 3-ट्रीस को स्पष्ट रूप से माना जाता था Hakimi & Schmeichel (1979), Alon & Caro (1984), Patil (1986), और उनके बाद से कई लेखक।

अपोलोनियन नेटवर्क नाम किसके द्वारा दिया गया था Andrade et al. (2005) उन नेटवर्कों के लिए जिनका उन्होंने अध्ययन किया जिसमें त्रिभुजों के उपविभाजन का स्तर पूरे नेटवर्क में समान है; ये नेटवर्क ज्यामितीय रूप से प्रकार के स्टैक्ड पॉलीहेड्रॉन के अनुरूप होते हैं जिन्हें क्लीटोप कहा जाता है। अन्य लेखकों ने एंड्रेड एट अल के मॉडल को सामान्यीकृत करते हुए अपने काम में प्लैनर 3-ट्रीस के लिए समान नाम को अधिक व्यापक रूप से लागू किया। यादृच्छिक अपोलोनियन नेटवर्क के लिए।इस तरह से उत्पन्न त्रिभुजों को स्टैक्ड त्रिकोणासन भी नाम दिया गया है या ढेर-त्रिकोण।

यह भी देखें

• बैरीसेंट्रिक उपखंड, त्रिभुजों को छोटे त्रिभुजों में उपविभाजित करने की अलग विधि
• पाश उपविभाजन सतह, फिर भी त्रिभुजों को छोटे त्रिभुजों में उपविभाजित करने की और विधि

संदर्भ

• Albenque, Marie; Marckert, Jean-François (2008), "Some families of increasing planar maps", Electronic Journal of Probability, 13: 1624–1671, arXiv:0712.0593, doi:10.1214/ejp.v13-563, MR 2438817, S2CID 2420262
• Almering, J. H. J. (1963), "Rational quadrilaterals", Indagationes Mathematicae, 25: 192–199, doi:10.1016/S1385-7258(63)50020-1, MR 0147447.
• Alon, N.; Caro, Y. (1984), "On the number of subgraphs of prescribed type of planar graphs with a given number of vertices", in Rosenfeld, M.; Zaks, J. (eds.), Convexity and Graph Theory: proceedings of the Conference on Convexity and Graph Theory, Israel, March 1981, Annals of Discrete Mathematics 20, North-Holland Mathematical Studies 87, Elsevier, pp. 25–36, ISBN 978-0-444-86571-7, MR 0791009.
• Andrade, José S., Jr.; Herrmann, Hans J.; Andrade, Roberto F. S.; da Silva, Luciano R. (2005), "Apollonian Networks: Simultaneously Scale-Free, Small World, Euclidean, Space Filling, and with Matching Graphs", Physical Review Letters, 94 (1): 018702, arXiv:cond-mat/0406295, Bibcode:2005PhRvL..94a8702A, doi:10.1103/physrevlett.94.018702, PMID 15698147{{citation}}: CS1 maint: multiple names: authors list (link).
• Arnborg, S.; Proskurowski, A.; Corniel, D. (1986), Forbidden Minors Characterization of Partial 3-trees, Technical Report CIS-TR-86-07, Dept. of Computer and Information Science, University of Oregon. As cited by El-Mallah & Colbourn (1990).
• Badent, Melanie; Binucci, Carla; Di Giacomo, Emilio; Didimo, Walter; Felsner, Stefan; Giordano, Francesco; Kratochvíl, Jan; Palladino, Pietro; Patrignani, Maurizio; Trotta, Francesco (2007), "Homothetic triangle contact representations of planar graphs", Canadian Conference on Computational Geometry (PDF).
• Below, Alexander; De Loera, Jesús A.; Richter-Gebert, Jürgen (2000), The Complexity of Finding Small Triangulations of Convex 3-Polytopes, arXiv:math/0012177, Bibcode:2000math.....12177B.
• Bernardi, Olivier; Bonichon, Nicolas (2009), "Intervals in Catalan lattices and realizers of triangulations", Journal of Combinatorial Theory, Series A, 116 (1): 55–75, doi:10.1016/j.jcta.2008.05.005, MR 2469248.
• Biedl, Therese; Ruiz Velázquez, Lesvia Elena (2010), "Drawing planar 3-trees with given face-areas", Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22–25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 316–322, doi:10.1007/978-3-642-11805-0_30.
• Birkhoff, George D. (1930), "On the number of ways of colouring a map", Proceedings of the Edinburgh Mathematical Society, (2), 2 (2): 83–91, doi:10.1017/S0013091500007598.
• Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4, hdl:1874/18312, MR 1647486.
• Böhme, Thomas; Harant, Jochen; Tkáč, Michal (1999), "More than one tough chordal planar graphs are Hamiltonian", Journal of Graph Theory, 32 (4): 405–410, doi:10.1002/(SICI)1097-0118(199912)32:4<405::AID-JGT8>3.3.CO;2-Q, MR 1722793.
• Butler, S.; Graham, Ron (2010), "Iterated triangle partitions", in Katona, G.; Schrijver, A.; Szonyi, T. (eds.), Fete of Combinatorics and Computer Science (PDF), Bolyai Society Mathematical Studies, vol. 29, Heidelberg: Springer-Verlag, pp. 23–42.
• Dai, Wayne Wei-Ming; Sato, Masao (1990), "Minimal forbidden minor characterization of planar partial 3-trees and application to circuit layout", IEEE International Symposium on Circuits and Systems, vol. 4, pp. 2677–2681, doi:10.1109/ISCAS.1990.112560, S2CID 122926229
• Demaine, Erik; Schulz, André (2011), "Embedding stacked polytopes on a polynomial-size grid", Proc. ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 1177–1187, archived from the original (PDF) on 2011-06-01, retrieved 2011-03-07.
• Dujmović, Vida; Fijavž, Gašper; Joret, Gwenaël; Wood, David R. (2009), "The maximum number of cliques in a graph embedded in a surface", European Journal of Combinatorics, 32 (8): 1244–1252, arXiv:0906.4142, Bibcode:2009arXiv0906.4142D, doi:10.1016/j.ejc.2011.04.001, S2CID 1733300.
• El-Mallah, Ehab S.; Colbourn, Charles J. (1990), "On two dual classes of planar graphs", Discrete Mathematics, 80 (1): 21–40, doi:10.1016/0012-365X(90)90293-Q, MR 1045921.
• Elcock, E. W.; Gargantini, I.; Walsh, T. R. (1987), "Triangular decomposition", Image and Vision Computing, 5 (3): 225–231, doi:10.1016/0262-8856(87)90053-9.
• Felsner, Stefan; Zickfeld, Florian (2008), "On the number of planar orientations with prescribed degrees" (PDF), Electronic Journal of Combinatorics, 15 (1): R77, arXiv:math/0701771, Bibcode:2007math......1771F, doi:10.37236/801, MR 2411454, S2CID 13893657.
• Frieze, Alan M.; Tsourakakis, Charalampos E. (2011), High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks, arXiv:1104.5259, Bibcode:2011arXiv1104.5259F.
• Fowler, Thomas (1998), Unique Coloring of Planar Graphs (PDF), Ph.D. thesis, Georgia Institute of Technology Mathematics Department.
• Geelen, Jim; Guo, Anjie; McKinnon, David (2008), "Straight line embeddings of cubic planar graphs with integer edge lengths", Journal of Graph Theory, 58 (3): 270–274, doi:10.1002/jgt.20304, MR 2419522.
• Gerlach, T. (2004), "Toughness and Hamiltonicity of a class of planar graphs", Discrete Mathematics, 286 (1–2): 61–65, doi:10.1016/j.disc.2003.11.046, MR 2084280.
• Goldner, A.; Harary, F. (1975), "Note on a smallest nonhamiltonian maximal planar graph", Bull. Malaysian Math. Soc., 6 (1): 41–42. See also the same journal 6(2):33 (1975) and 8:104-106 (1977). Reference from listing of Harary's publications.
• Grünbaum, Branko (1963), "Unambiguous polyhedral graphs", Israel Journal of Mathematics, 1 (4): 235–238, doi:10.1007/BF02759726, MR 0185506, S2CID 121075042.
• Grünbaum, Branko (1967), Convex Polytopes, Wiley Interscience.
• Hakimi, S. L.; Schmeichel, E. F. (1979), "On the number of cycles of length k in a maximal planar graph", Journal of Graph Theory, 3 (1): 69–86, doi:10.1002/jgt.3190030108, MR 0519175.
• Jiménez, Andrea; Kiwi, Marcos (2010), Counting perfect matchings of cubic graphs in the geometric dual, arXiv:1010.5918, Bibcode:2010arXiv1010.5918J.
• Kumar, P. Sreenivasa; Madhavan, C. E. Veni (1989), "A new class of separators and planarity of chordal graphs", Foundations of Software Technology and Theoretical Computer Science, Ninth Conference, Bangalore, India December 19–21, 1989, Proceedings, Lecture Notes in Computer Science, vol. 405, Springer-Verlag, pp. 30–43, doi:10.1007/3-540-52048-1_30, MR 1048636.
• Markenzon, L.; Justel, C. M.; Paciornik, N. (2006), "Subclasses of k-trees: Characterization and recognition", Discrete Applied Mathematics, 154 (5): 818–825, doi:10.1016/j.dam.2005.05.021, MR 2207565.
• Mondal, Debajyoti; Nishat, Rahnuma Islam; Rahman, Md. Saidur; Alam, Muhammad Jawaherul (2010), "Minimum-area drawings of plane 3-trees", Canadian Conference on Computational Geometry (PDF).
• Moon, J. W.; Moser, L. (1963), "Simple paths on polyhedra", Pacific Journal of Mathematics, 13 (2): 629–631, doi:10.2140/pjm.1963.13.629, MR 0154276.
• Nishat, Rahnuma Islam; Mondal, Debajyoti; Rahman, Md. Saidur (2011), "Point-set embeddings of plane 3-trees", Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Springer-Verlag, pp. 317–328, doi:10.1007/978-3-642-18469-7_29.
• Nishizeki, Takao (1980), "A 1-tough non-Hamiltonian maximal planar graph", Discrete Mathematics, 30 (3): 305–307, doi:10.1016/0012-365X(80)90240-X, MR 0573648.
• Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069.
• Petersen, Julius (1891), "Die Theorie der regulären graphs", Acta Mathematica, 15: 193–220, doi:10.1007/BF02392606.
• Plummer, Michael D. (1992), "Extending matchings in planar graphs IV", Discrete Mathematics, 109 (1–3): 207–219, doi:10.1016/0012-365X(92)90292-N, MR 1192384.
• Politof, T. (1983), A characterization and efficient reliability computation of Δ-Y reducible networks, Ph.D. thesis, University of California, Berkeley. As cited by El-Mallah & Colbourn (1990).
• Robertson, Neil; Seymour, P. D. (1984), "Graph minors. III. Planar tree-width", Journal of Combinatorial Theory, Series B, 36 (1): 49–64, doi:10.1016/0095-8956(84)90013-3, MR 0742386.
• Takeo, Fujio (1960), "On triangulated graphs. I", Bull. Fukuoka Gakugei Univ. III, 10: 9–21, MR 0131372. An error regarding Hamiltonicity was pointed out by MathSciNet reviewer W. T. Tutte.
• Thurston, William (1978–1981), The geometry and topology of 3-manifolds, Princeton lecture notes.
• Tsourakakis, Charalampos E. (2011), The Degree Sequence of Random Apollonian Networks, arXiv:1106.1940.
• Wood, David R. (2007), "On the maximum number of cliques in a graph", Graphs and Combinatorics, 23 (3): 337–352, arXiv:math/0602191, doi:10.1007/s00373-007-0738-8, MR 2320588, S2CID 46700417.
• Zhang, Zhongzhi; Chen, Lichao; Zhou, Shuigeng; Fang, Lujun; Guan, Jihong; Zou, Tao (2008), "Analytical solution of average path length for Apollonian networks", Physical Review E, 77 (1): 017102, arXiv:0706.3491, Bibcode:2008PhRvE..77a7102Z, doi:10.1103/PhysRevE.77.017102, PMID 18351964, S2CID 30404208.
• Zhou, Tao; Yan, Gang; Wang, Bing-Hong (2005), "Maximal planar networks with large clustering coefficient and power-law degree distribution", Physical Review E, 71 (4): 046141, arXiv:cond-mat/0412448, Bibcode:2005PhRvE..71d6141Z, doi:10.1103/PhysRevE.71.046141, PMID 15903760, S2CID 21740312.
• Zhou, Tao; Yan, Gang; Zhou, Pei-Ling; Fu, Zhong-Qian; Wang, Bing-Hong (2004), Random Apollonian networks, arXiv:cond-mat/0409414v2, Bibcode:2004cond.mat..9414Z.
• Zickfeld, Florian; Ziegler, Günter M. (2006), "Integer realizations of stacked polytopes", Workshop on Geometric and Topological Combinatorics (PDF).

बाहरी संबंध

• Weisstein, Eric W., "Apollonian Network", MathWorld
• Matlab Simulation Code