अपोलोनियन नेटवर्क: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Graph formed by subdivision of triangles}}
{{Short description|Graph formed by subdivision of triangles}}
[[File:Apollonian-network.svg|thumb|240px|अपोलोनियन नेटवर्क]]
[[File:Apollonian-network.svg|thumb|240px|अपोलोनियन नेटवर्क]]
[[File:Goldner-Harary graph.svg|thumb|गोल्डनर-हैरी ग्राफ, गैर-हैमिल्टनियन अपोलोनियन नेटवर्क]][[साहचर्य|संयोजी]] गणित में, अपोलोनियन नेटवर्क [[अप्रत्यक्ष ग्राफ]] है जो त्रिभुज को तीन छोटे त्रिभुजों में पुनरावर्ती रूप से उप-विभाजित करने की प्रक्रिया द्वारा बनता है। अपोलोनियन नेटवर्क को समान रूप से [[ प्लेनर ग्राफ |समतली ग्राफ]] [[ k-वृक्ष |3-ट्री]] , अधिकतम तलीय कॉर्डल ग्राफ, [[विशिष्ट रंगीन ग्राफ|विशिष्ट 4-रंगीन तलीय ग्राफ]], और [[ स्टैक्ड पॉलीटॉप |स्टैक्ड बहुतलीय]] के ग्राफ के रूप में परिभाषित किया जा सकता है। उनका नाम पेर्गा के अपोलोनियस के नाम पर रखा गया है, जिन्होंने संबंधित सर्कल-पैकिंग निर्माण का अध्ययन किया था।
[[File:Goldner-Harary graph.svg|thumb|गोल्डनर-हैरी ग्राफ, गैर-हैमिल्टनियन अपोलोनियन नेटवर्क]][[साहचर्य|संयोजी]] गणित में, '''अपोलोनियन नेटवर्क''' [[अप्रत्यक्ष ग्राफ]] है जो त्रिभुज को तीन छोटे त्रिभुजों में पुनरावर्ती रूप से उप-विभाजित करने की प्रक्रिया द्वारा बनता है। अपोलोनियन नेटवर्क को समान रूप से [[ प्लेनर ग्राफ |समतली ग्राफ]] [[ k-वृक्ष |3-ट्री]] , अधिकतम तलीय कॉर्डल ग्राफ, [[विशिष्ट रंगीन ग्राफ|विशिष्ट 4-रंगीन तलीय ग्राफ]], और [[ स्टैक्ड पॉलीटॉप |स्टैक्ड बहुतलीय]] के ग्राफ के रूप में परिभाषित किया जा सकता है। उनका नाम पेर्गा के अपोलोनियस के नाम पर रखा गया है, जिन्होंने संबंधित सर्कल-पैकिंग निर्माण का अध्ययन किया था।


== परिभाषा ==
== परिभाषा ==
Line 7: Line 7:


== उदाहरण ==
== उदाहरण ==
तीन और चार शीर्षों पर पूर्ण रेखांकन, {{math|''K''<sub>3</sub>}} और {{math|''K''<sub>4</sub>}}, दोनों अपोलोनियन नेटवर्क हैं। {{math|''K''<sub>3</sub>}} त्रिकोण से शुरू करके और किसी भी उपखंड का प्रदर्शन नहीं करके बनता है, जबकि {{math|''K''<sub>4</sub>}} रोकने से पहले ही उपखण्ड बनाकर बनाया जाता है।
तीन और चार शीर्षों पर पूर्ण रेखांकन, {{math|''K''<sub>3</sub>}} और {{math|''K''<sub>4</sub>}}, दोनों अपोलोनियन नेटवर्क हैं। {{math|''K''<sub>3</sub>}} त्रिकोण से प्रारंभ करके और किसी भी उपखंड का प्रदर्शन नहीं करके बनता है, जबकि {{math|''K''<sub>4</sub>}} रोकने से पहले ही उपखण्ड बनाकर बनाया जाता है।


गोल्डनर-हैरी ग्राफ एक अपोलोनियन नेटवर्क है जो सबसे छोटा [[हैमिल्टनियन चक्र|गैर-हैमिल्टनियन चक्र]] अधिकतम तलीय ग्राफ बनाता है।<ref>This graph is named after the work of {{harvtxt|Goldner|Harary|1975}}; however, it appears earlier in the literature, for instance in {{harvtxt|Grünbaum|1967}}, p.&nbsp;357.</ref> एक और अधिक जटिल अपोलोनियन नेटवर्क का उपयोग {{harvtxt|निशिजेकी|1980}} द्वारा 1-कठिन गैर-हैमिल्टनियन अधिकतम तलीय ग्राफ का उदाहरण प्रदान करने के लिए किया गया था।
गोल्डनर-हैरी ग्राफ एक अपोलोनियन नेटवर्क है जो सबसे छोटा [[हैमिल्टनियन चक्र|गैर-हैमिल्टनियन चक्र]] अधिकतम तलीय ग्राफ बनाता है।<ref>This graph is named after the work of {{harvtxt|Goldner|Harary|1975}}; however, it appears earlier in the literature, for instance in {{harvtxt|Grünbaum|1967}}, p.&nbsp;357.</ref> एक और अधिक जटिल अपोलोनियन नेटवर्क का उपयोग {{harvtxt|निशिजेकी|1980}} द्वारा 1-कठिन गैर-हैमिल्टनियन अधिकतम तलीय ग्राफ का उदाहरण प्रदान करने के लिए किया गया था।


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


=== तारतम्य ===
=== तारतम्य ===
अपोलोनियन नेटवर्क [[अधिकतम तत्व]] प्लैनर ग्राफ़ के उदाहरण हैं, ग्राफ़ जिसमें कोई अतिरिक्त किनारों को बिना समतलता को नष्ट किए जोड़ा नहीं जा सकता है, या समान रूप से ग्राफ़ जो समतल में खींचे जा सकते हैं ताकि हर तल (बाहरी तल सहित) त्रिकोण हो। वे कॉर्डल ग्राफ़ भी हैं, ग्राफ़ जिसमें चार या अधिक वर्टिकल के प्रत्येक चक्र में दो गैर-लगातार चक्र वर्टिकल को जोड़ने वाला विकर्ण किनारा होता है, और जिस क्रम में वर्टिकल को उपखंड प्रक्रिया में जोड़ा जाता है जो अपोलोनियन नेटवर्क बनाता है, उन्मूलन क्रम है तारकीय ग्राफ। यह अपोलोनियन नेटवर्क का वैकल्पिक लक्षण वर्णन करता है: वे वास्तव में कॉर्डल अधिकतम तलीय ग्राफ़ या समतुल्य रूप से कॉर्डल पॉलीहेड्रल ग्राफ़ हैं।<ref>The equivalence of planar 3-trees and chordal maximal planar graphs was stated without proof by {{harvtxt|Patil|1986}}. For a proof, see {{harvtxt|Markenzon|Justel|Paciornik|2006}}. For a more general characterization of chordal planar graphs, and an efficient recognition algorithm for these graphs, see {{harvtxt|Kumar|Madhavan|1989}}. The observation that every chordal polyhedral graph is maximal planar was stated explicitly by {{harvtxt|Gerlach|2004}}.</ref>
अपोलोनियन नेटवर्क [[अधिकतम तत्व]] प्लैनर ग्राफ़ के उदाहरण हैं, ग्राफ़ जिसमें कोई अतिरिक्त किनारों को बिना समतलता को नष्ट किए जोड़ा नहीं जा सकता है, या समान रूप से ग्राफ़ जो समतल में खींचे जा सकते हैं जिससे प्रत्येक तल (बाहरी तल सहित) त्रिकोण हो। वे कॉर्डल ग्राफ़ भी हैं जिनमें चार या अधिक शीर्ष के प्रत्येक चक्र में दो गैर-लगातार चक्र शीर्ष को जोड़ने वाला एक विकर्ण किनारा होता है और जिस क्रम में उपखंड प्रक्रिया में शीर्ष जोड़े जाते हैं जो अपोलोनियन नेटवर्क बनाता है, एक कॉर्डल ग्राफ के रूप में एक उन्मूलन क्रम है। यह अपोलोनियन नेटवर्क का वैकल्पिक लक्षण वर्णन करता है: वे वास्तविक में कॉर्डल अधिकतम तलीय ग्राफ़ या समतुल्य रूप से कॉर्डल पॉलीहेड्रल ग्राफ़ हैं।<ref>The equivalence of planar 3-trees and chordal maximal planar graphs was stated without proof by {{harvtxt|Patil|1986}}. For a proof, see {{harvtxt|Markenzon|Justel|Paciornik|2006}}. For a more general characterization of chordal planar graphs, and an efficient recognition algorithm for these graphs, see {{harvtxt|Kumar|Madhavan|1989}}. The observation that every chordal polyhedral graph is maximal planar was stated explicitly by {{harvtxt|Gerlach|2004}}.</ref>
अपोलोनियन नेटवर्क में, प्रत्येक [[अधिकतम क्लिक]] चार शिखरों पर पूर्ण ग्राफ है, जो कि किसी शीर्ष और उसके तीन पूर्व पड़ोसियों को चुनकर बनाया गया है। प्रत्येक न्यूनतम [[मैं एक गुट हूँ|मैं गुट हूँ]] (क्लिक जो ग्राफ़ को दो डिस्कनेक्ट किए गए सबग्राफ में विभाजित करता है) उप-विभाजित त्रिकोणों में से है। कोर्डल ग्राफ जिसमें सभी अधिकतम क्लिक्स और सभी न्यूनतम क्लिक विभाजक समान आकार के होते हैं, के-ट्री है|{{math|''k''}}-ट्री और अपोलोनियन नेटवर्क 3-ट्री के उदाहरण हैं। हर 3-ट्री तलीय नहीं है, लेकिन तलीय 3-ट्री बिल्कुल अपोलोनियन नेटवर्क हैं।
 
अपोलोनियन नेटवर्क में, प्रत्येक [[अधिकतम क्लिक]] चार शिखरों पर पूर्ण ग्राफ है, जो कि किसी शीर्ष और उसके तीन पूर्व पड़ोसियों को चुनकर बनाया गया है। प्रत्येक न्यूनतम [[मैं एक गुट हूँ|क्लिक विभाजक]] (क्लिक जो ग्राफ़ को दो डिस्कनेक्ट किए गए सबग्राफ में विभाजित करता है) उप-विभाजित त्रिकोणों में से एक है। कोर्डल ग्राफ जिसमें सभी अधिकतम क्लिक्स और सभी न्यूनतम क्लिक विभाजक समान आकार के होते हैं, {{math|''k''}}-ट्री है और अपोलोनियन नेटवर्क 3-ट्री के उदाहरण हैं। प्रत्येक 3-ट्री तलीय नहीं है, किन्तुतलीय 3-ट्री बिल्कुल अपोलोनियन नेटवर्क हैं।


=== अद्वितीय रंगीनता ===
=== अद्वितीय रंगीनता ===
प्रत्येक अपोलोनियन नेटवर्क भी विशिष्ट रंगीन ग्राफ है | विशिष्ट 4-रंगीन ग्राफ। क्योंकि यह समतली ग्राफ है, [[चार रंग प्रमेय]] का अर्थ है कि इसमें केवल चार रंगों के साथ [[ग्राफ रंग]] है, लेकिन बार प्रारंभिक त्रिकोण के तीन रंगों का चयन करने के बाद, प्रत्येक उत्तरोत्तर शीर्ष के रंग के लिए केवल ही संभव विकल्प होता है, इसलिए रंगों के सेट के क्रमपरिवर्तन तक इसमें ठीक 4-रंग होता है। यह साबित करना अधिक कठिन है, लेकिन यह भी सच है कि प्रत्येक विशिष्ट 4-रंगीय तलीय ग्राफ अपोलोनियन नेटवर्क है। इसलिए, अपोलोनियन नेटवर्क को विशिष्ट रूप से 4-रंगीन तलीय ग्राफ़ के रूप में चित्रित किया जा सकता है।{{sfnp|Fowler|1998}} Apollonian नेटवर्क भी कुछ के रूप में होने वाले तलीय ग्राफ़ के उदाहरण प्रदान करते हैं {{math|''k''}}-रंगों के लिए जितना संभव हो {{math|''k'' > 4}}.<ref>The fact that Apollonian networks minimize the number of colorings with more than four of colors was shown in a dual form for colorings of maps by {{harvtxt|Birkhoff|1930}}.</ref>
प्रत्येक अपोलोनियन नेटवर्क भी एक विशिष्ट 4-रंगीन ग्राफ है। क्योंकि यह एक समतली ग्राफ है, [[चार रंग प्रमेय]] का अर्थ है कि इसमें केवल चार रंगों के साथ [[ग्राफ रंग]] है, किन्तु बार प्रारंभिक त्रिकोण के तीन रंगों का चयन करने के बाद, प्रत्येक उत्तरोत्तर शीर्ष के रंग के लिए केवल ही संभव विकल्प होता है, इसलिए रंगों के सेट के क्रमपरिवर्तन तक इसमें ठीक 4-रंग होता है। यह सिद्ध करना अधिक कठिन है, किन्तु यह भी सच है कि प्रत्येक विशिष्ट 4-रंगीय तलीय ग्राफ अपोलोनियन नेटवर्क है। इसलिए, अपोलोनियन नेटवर्क को विशिष्ट रूप से 4-रंगीन तलीय ग्राफ़ के रूप में चित्रित किया जा सकता है।{{sfnp|Fowler|1998}} अपोलोनियन नेटवर्क, समतल ग्राफ़ के उदाहरण भी प्रदान करते हैं जिनमें {{math|''k'' > 4}} के लिए यथासंभव कुछ {{math|''k''}}-रंग होते हैं।<ref>The fact that Apollonian networks minimize the number of colorings with more than four of colors was shown in a dual form for colorings of maps by {{harvtxt|Birkhoff|1930}}.</ref>
Apollonian नेटवर्क भी अधिकतम तलीय ग्राफ़ हैं जो (बार बाहरी तल तय हो जाने पर) में अद्वितीय श्नाइडर लकड़ी होती है, जो ग्राफ़ के किनारों का विभाजन बाहरी तल के तीन कोने पर निहित तीन इंटरलीव्ड पेड़ों में होती है।<ref>{{harvtxt|Felsner|Zickfeld|2008}}; {{harvtxt|Bernardi|Bonichon|2009}}.</ref>
 
अपोलोनियन नेटवर्क भी अधिकतम तलीय ग्राफ़ हैं जो (बार बाहरी तल तय हो जाने पर) में अद्वितीय श्नाइडर लकड़ी होती है, जो ग्राफ़ के किनारों का विभाजन बाहरी तल के तीन कोने पर निहित तीन अंतरापत्रित ट्रीस में होती है।<ref>{{harvtxt|Felsner|Zickfeld|2008}}; {{harvtxt|Bernardi|Bonichon|2009}}.</ref>
 




=== ट्रीविड्थ ===
=== ट्रीविड्थ ===
अपोलोनियन नेटवर्क ग्राफ़ नाबालिगों को लेने के संचालन के तहत बंद किए गए ग्राफ़ के परिवार का निर्माण नहीं करते हैं, क्योंकि किनारों को हटाने के रूप में अपोलोनियन नेटवर्क से कोई ग्राफ़ उत्पन्न नहीं होता है जो अपोलोनियन नेटवर्क नहीं है। हालांकि, तलीय आंशिक के-ट्री|आंशिक 3-पेड़, अपोलोनियन नेटवर्क के सबग्राफ, माइनर-क्लोज्ड हैं। इसलिए, रॉबर्टसन-सीमोर प्रमेय के अनुसार, उन्हें वर्जित ग्राफ़ लक्षण वर्णन की सीमित संख्या द्वारा चित्रित किया जा सकता है। समतलीय आंशिक 3-वृक्षों के लिए न्यूनतम वर्जित अवयस्क, तलीय रेखांकन और आंशिक 3-वृक्षों के लिए वर्जित अवयस्कों में से चार न्यूनतम रेखांकन हैं: पूर्ण आलेख {{math|''K''<sub>5</sub>}}, [[पूर्ण द्विदलीय ग्राफ]] {{math|''K''<sub>3,3</sub>}}, [[अष्टफलक]] का ग्राफ और [[पंचकोणीय प्रिज्म]] का ग्राफ। अपोलोनियन ग्राफ़ अधिकतम ग्राफ़ हैं जिनमें इन चार ग्राफ़ों में से कोई भी मामूली नहीं है।<ref>The two forbidden minors for planar graphs are given by [[Wagner's theorem]]. For the forbidden minors for partial 3-trees (which include also the nonplanar [[Wagner graph]]) see {{harvtxt|Arnborg|Proskurowski|Corniel|1986}} and {{harvtxt|Bodlaender|1998}}. For direct proofs that the octahedral graph and the pentagonal-prism graph are the only two planar forbidden minors, see {{harvtxt|Dai|Sato|1990}} and {{harvtxt|El-Mallah|Colbourn|1990}}.</ref>
अपोलोनियन नेटवर्क ग्राफ़ अवयस्क को लेने के संचालन के अनुसार  बंद किए गए ग्राफ़ के परिवार का निर्माण नहीं करते हैं, क्योंकि किनारों को हटाने के रूप में अपोलोनियन नेटवर्क से कोई ग्राफ़ उत्पन्न नहीं होता है जो अपोलोनियन नेटवर्क नहीं है। चूंकि, तलीय आंशिक 3-ट्री, अपोलोनियन नेटवर्क के सबग्राफ, लघु-बंद हैं। इसलिए, रॉबर्टसन-सीमोर प्रमेय के अनुसार, उन्हें वर्जित ग्राफ़ लक्षण वर्णन की सीमित संख्या द्वारा चित्रित किया जा सकता है। समतलीय आंशिक 3-ट्रीस के लिए न्यूनतम वर्जित अवयस्क, तलीय रेखांकन और आंशिक 3-ट्रीस के लिए वर्जित अवयस्कों में से चार न्यूनतम रेखांकन: पूर्ण आलेख {{math|''K''<sub>5</sub>}}, [[पूर्ण द्विदलीय ग्राफ]] {{math|''K''<sub>3,3</sub>}}, [[अष्टफलक]] का ग्राफ और [[पंचकोणीय प्रिज्म]] का ग्राफ हैं। अपोलोनियन ग्राफ़ अधिकतम ग्राफ़ हैं जिनमें इन चार ग्राफ़ों में से कोई भी सामान्य नहीं है।<ref>The two forbidden minors for planar graphs are given by [[Wagner's theorem]]. For the forbidden minors for partial 3-trees (which include also the nonplanar [[Wagner graph]]) see {{harvtxt|Arnborg|Proskurowski|Corniel|1986}} and {{harvtxt|Bodlaender|1998}}. For direct proofs that the octahedral graph and the pentagonal-prism graph are the only two planar forbidden minors, see {{harvtxt|Dai|Sato|1990}} and {{harvtxt|El-Mallah|Colbourn|1990}}.</ref>
वाई-Δ परिवर्तन, ऑपरेशन जो अपने पड़ोसियों को जोड़ने वाले त्रिभुज द्वारा ग्राफ में डिग्री-तीन वर्टेक्स को प्रतिस्थापित करता है, किसी भी अपोलोनियन नेटवर्क को त्रिभुज में कम करने के लिए पर्याप्त है (साथ में समांतर किनारों को हटाने के साथ), और अधिक आम तौर पर तलीय ग्राफ़ जिन्हें Y-Δ ट्रांसफ़ॉर्म द्वारा किनारे तक कम किया जा सकता है, समानांतर किनारों को हटाना, डिग्री-वन वर्टिकल को हटाना और डिग्री-दो वर्टिकल का कम्प्रेशन बिल्कुल तलीय आंशिक 3-ट्रीज़ हैं। समतलीय आंशिक 3-वृक्षों के दोहरे ग्राफ़ अन्य छोटे-बंद ग्राफ़ परिवार का निर्माण करते हैं और वास्तव में प्लैनर ग्राफ़ हैं जिन्हें Δ-Y रूपांतरण, समानांतर किनारों को हटाने, डिग्री-कोने को हटाने, और किनारे तक कम किया जा सकता है। डिग्री-दो शीर्षों का संपीड़न।<ref>{{harvtxt|Politof|1983}} introduced the Δ-Y reducible planar graphs and characterized them in terms of forbidden homeomorphic subgraphs. The duality between the Δ-Y and Y-Δ reducible graphs, the forbidden minor characterizations of both classes, and the connection to planar partial 3-trees are all from {{harvtxt|El-Mallah|Colbourn|1990}}.</ref>


Y-Δ परिवर्तन, ऑपरेशन जो अपने पड़ोसियों को जोड़ने वाले त्रिभुज द्वारा ग्राफ में डिग्री-तीन शीर्ष् को प्रतिस्थापित करता है, किसी भी अपोलोनियन नेटवर्क को त्रिभुज में कम करने के लिए पर्याप्त है (साथ में समांतर किनारों को हटाने के साथ), और अधिक सामान्यतः तलीय ग्राफ़ जिन्हें Y-Δ रूपांतरण द्वारा किनारे तक कम किया जा सकता है, समानांतर किनारों को हटाना, डिग्री-वन शीर्ष को हटाना और डिग्री-दो शीर्ष का कम्प्रेशन बिल्कुल तलीय आंशिक 3-ट्रीज़ हैं। समतलीय आंशिक 3-ट्रीस के दोहरे ग्राफ़ अन्य लघु-बंद ग्राफ़ परिवार का निर्माण करते हैं और वास्तविक में प्लैनर ग्राफ़ होते हैं जिसे Δ-Y रूपांतरणों, समानांतर किनारों को हटाने, डिग्री-एक शीर्षों को हटाने, और डिग्री-दो शीर्षों के संपीड़न द्वारा एकल किनारे तक कम किया जा सकता है।<ref>{{harvtxt|Politof|1983}} introduced the Δ-Y reducible planar graphs and characterized them in terms of forbidden homeomorphic subgraphs. The duality between the Δ-Y and Y-Δ reducible graphs, the forbidden minor characterizations of both classes, and the connection to planar partial 3-trees are all from {{harvtxt|El-Mallah|Colbourn|1990}}.</ref>


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


=== चरमता ===
अपोलोनियन नेटवर्क के अन्य लक्षण वर्णन में उनकी कनेक्टिविटी (ग्राफ़ सिद्धांत) शामिल है। किसी भी मैक्सिमम तलीय ग्राफ को 4-वर्टेक्स-कनेक्टेड अधिकतम तलीय सबग्राफ में इसके अलग-अलग त्रिकोणों (त्रिकोण जो ग्राफ के तल नहीं हैं) के साथ विभाजित करके विघटित किया जा सकता है: किसी भी गैर-तल वाले त्रिकोण को देखते हुए: दो छोटे मैक्सिमम तलीय ग्राफ बना सकते हैं, में त्रिभुज के अंदर का भाग होता है और दूसरे में त्रिभुज के बाहर का भाग होता है। इस प्रकार के बार-बार विभाजित होने वाले त्रिभुजों को अलग किए बिना अधिकतम तलीय ग्राफ़ को कभी-कभी ब्लॉक कहा जाता है, हालांकि उस नाम का उपयोग ग्राफ़ के [[द्विसंबद्ध घटक]]ों के लिए भी किया गया है जो स्वयं द्विसंबद्ध नहीं है। अपोलोनियन नेटवर्क अधिकतम तलीय ग्राफ है जिसमें सभी ब्लॉक पूर्ण ग्राफ के लिए [[ ग्राफ समरूपता |ग्राफ समरूपता]] हैं{{math|''K''<sub>4</sub>}}.


[[चरम ग्राफ सिद्धांत]] में, अपोलोनियन नेटवर्क भी ठीक वैसा ही है {{math|''n''}}-वर्टेक्स तलीय ग्राफ जिसमें ब्लॉकों की संख्या अधिकतम हो जाती है, {{math|''n'' &minus; 3}}, और समतलीय रेखांकन जिसमें त्रिभुजों की संख्या अपने अधिकतम को प्राप्त करती है, {{math|3''n'' &minus; 8}}. चूंकि प्रत्येक {{math|''K''<sub>4</sub>}} तलीय ग्राफ का सबग्राफ ब्लॉक होना चाहिए, ये भी तलीय ग्राफ हैं जिनमें की संख्या {{math|''K''<sub>4</sub>}} सबग्राफ अपने अधिकतम को प्राप्त करता है, {{math|''n'' &minus; 3}}, और वे ग्राफ़ जिनमें किसी भी प्रकार के क्लिक (ग्राफ़ सिद्धांत) की संख्या अधिकतम हो जाती है, {{math|8''n'' &minus; 16}}.<ref>For the characterization in terms of the maximum number of triangles in a planar graph, see {{harvtxt|Hakimi|Schmeichel|1979}}. {{harvtxt|Alon|Caro|1984}} quote this result and provide the characterizations in terms of the isomorphism classes of blocks and numbers of blocks. The bound on the total number of cliques follows easily from the bounds on triangles and ''K''<sub>4</sub> subgraphs, and is also stated explicitly by {{harvtxt|Wood|2007}}, who provides an Apollonian network as an example showing that this bound is tight. For generalizations of these bounds to nonplanar surfaces, see {{harvtxt|Dujmović|Fijavž|Joret|Wood|2009}}.</ref>
=== विकृति ===
अपोलोनियन नेटवर्क के प्रत्येक सबग्राफ में, सबसे नवीन में जोड़े गए शीर्ष् में अधिकतम तीन [[ डिग्री (ग्राफ सिद्धांत) |डिग्री (ग्राफ सिद्धांत)]] हैं, इसलिए अपोलोनियन नेटवर्क में विकृति (ग्राफ प्रमेय) तीन हैं। जिस क्रम में नेटवर्क बनाने के लिए शीर्ष जोड़े जाते हैं, इसलिए अध: पतन क्रम होता है, और अपोलोनियन नेटवर्क 3-विकृति अधिकतम तलीय ग्राफ के साथ मेल खाते हैं।
 
=== आकार ===
अपोलोनियन नेटवर्क के एक अन्य लक्षण वर्णन में उनकी कनेक्टिविटी सम्मिलित  है। किसी भी अधिकतम समतल ग्राफ को 4-शीर्ष्-कनेक्टेड अधिकतम समतल सबग्राफ में विघटित किया जा सकता है, इसे इसके अलग-अलग त्रिकोणों (त्रिकोण जो ग्राफ के चेहरे नहीं हैं) के साथ विभाजित करके किसी भी गैर-तलीय वाले त्रिकोण को दो छोटे अधिकतम समतल ग्राफ बना सकते हैं, जिसमें से एक त्रिभुज के अंदर का भाग और दूसरा त्रिभुज के बाहर के भाग से मिलकर बनता है। इस प्रकार के बार-बार विभाजन के द्वारा बनने वाले त्रिभुजों को अलग किए बिना अधिक से अधिक समतल ग्राफ़ को कभी-कभी ब्लॉक कहा जाता है, चूंकि उस नाम का उपयोग ग्राफ़ के [[द्विसंबद्ध घटक|द्विसंबद्ध घटकों]] के लिए भी किया गया है जो स्वयं द्विसंबद्ध नहीं है। अपोलोनियन नेटवर्क एक अधिकतम समतल ग्राफ है जिसमें सभी ब्लॉक पूर्ण ग्राफ {{math|''K''<sub>4</sub>}} के लिए [[ ग्राफ समरूपता |ग्राफ समरूपता]] हैं।
 
[[चरम ग्राफ सिद्धांत|आकार ग्राफ सिद्धांत]] में, अपोलोनियन नेटवर्क भी बिल्कुल {{math|''n''}}-शीर्ष् तलीय ग्राफ हैं, जिसमें ब्लॉक की संख्या अपने अधिकतम, {{math|''n'' &minus; 3}} को प्राप्त करती है, और प्लेनर ग्राफ जिसमें त्रिकोण की संख्या अपने अधिकतम, {{math|3''n'' &minus; 8}} को प्राप्त करती है। प्रत्येक के बाद से एक समतल ग्राफ का {{math|''K''<sub>4</sub>}} तलीय ग्राफ का सबग्राफ ब्लॉक होना चाहिए, ये भी तलीय ग्राफ हैं जिसमे {{math|''K''<sub>4</sub>}} सबग्राफ की संख्या अपने अधिकतम, {{math|''n'' &minus; 3}} को प्राप्त करती है, और ऐसे ग्राफ़ जिनमें किसी भी प्रकार के क्लिक (ग्राफ़ सिद्धांत) की संख्या अधिकतम {{math|8''n'' &minus; 16}} प्राप्त करती है।<ref>For the characterization in terms of the maximum number of triangles in a planar graph, see {{harvtxt|Hakimi|Schmeichel|1979}}. {{harvtxt|Alon|Caro|1984}} quote this result and provide the characterizations in terms of the isomorphism classes of blocks and numbers of blocks. The bound on the total number of cliques follows easily from the bounds on triangles and ''K''<sub>4</sub> subgraphs, and is also stated explicitly by {{harvtxt|Wood|2007}}, who provides an Apollonian network as an example showing that this bound is tight. For generalizations of these bounds to nonplanar surfaces, see {{harvtxt|Dujmović|Fijavž|Joret|Wood|2009}}.</ref>




Line 41: Line 46:
===सर्कल पैकिंग से निर्माण===
===सर्कल पैकिंग से निर्माण===
[[File:Apollonian gasket.svg|thumb|अपोलोनियन गैसकेट का उदाहरण]]
[[File:Apollonian gasket.svg|thumb|अपोलोनियन गैसकेट का उदाहरण]]
[[File:Circle packing theorem K5 minus edge example.svg|thumb|left|सर्कल पैकिंग से अपोलोनियन नेटवर्क का निर्माण]]अपोलोनियन नेटवर्क का नाम पेरगा के अपोलोनियस के नाम पर रखा गया है, जिन्होंने अपोलोनियस की समस्या का अध्ययन तीन अन्य मंडलियों के लिए वृत्त स्पर्शरेखा बनाने के लिए किया था। अपोलोनियन नेटवर्क के निर्माण का तरीका तीन परस्पर-स्पर्शी मंडलियों के साथ शुरू करना है और फिर पहले से तैयार किए गए तीन हलकों द्वारा बनाई गई खाई के भीतर और चक्र को बार-बार अंकित करना है। इस तरह से निर्मित हलकों के भग्न संग्रह को [[अपोलोनियन गैसकेट]] कहा जाता है।
[[File:Circle packing theorem K5 minus edge example.svg|thumb|left|सर्कल पैकिंग से अपोलोनियन नेटवर्क का निर्माण]]अपोलोनियन नेटवर्क का नाम पेरगा के अपोलोनियस के नाम पर रखा गया है, जिन्होंने अपोलोनियस की समस्या का अध्ययन तीन अन्य मंडलियों के लिए वृत्त स्पर्शरेखा बनाने के लिए किया था। अपोलोनियन नेटवर्क के निर्माण की विधि तीन परस्पर-स्पर्शी मंडलियों के साथ प्रारंभ करना है और फिर पहले से तैयार किए गए तीन मंडलों द्वारा बनाई गई खाई के अंदर और चक्र को बार-बार अंकित करना है। इस तरह से निर्मित मंडलों के भग्न संग्रह को [[अपोलोनियन गैसकेट]] कहा जाता है।
 
यदि अपोलोनियन गैसकेट के निर्माण की प्रक्रिया को केवल मंडलों के परिमित सेट के साथ जल्दी ही रोक दिया जाता है, तो ग्राफ़ जिसमें प्रत्येक सर्कल के लिए शीर्ष् होता है और स्पर्शरेखा मंडलियों के प्रत्येक जोड़े के लिए किनारा अपोलोनियन नेटवर्क होता है।<ref>{{harvtxt|Andrade|Herrmann|Andrade|da Silva|2005}}.</ref> स्पर्शरेखा मंडलों के सेट का अस्तित्व, जिसकी स्पर्शरेखा किसी दिए गए अपोलोनियन नेटवर्क का प्रतिनिधित्व करती है, कोएबे-एंड्रीव-थर्स्टन सर्कल-पैकिंग प्रमेय का एक सरल उदाहरण बनाती है, जिसमें कहा गया है कि किसी भी प्लानर ग्राफ को उसी तरह स्पर्शरेखा मंडलों द्वारा दर्शाया जा सकता है।<ref>{{harvtxt|Thurston|1978–1981}}.</ref>


यदि अपोलोनियन गैसकेट के निर्माण की प्रक्रिया को केवल हलकों के परिमित सेट के साथ जल्दी ही रोक दिया जाता है, तो ग्राफ़ जिसमें प्रत्येक सर्कल के लिए वर्टेक्स होता है और स्पर्शरेखा मंडलियों के प्रत्येक जोड़े के लिए किनारा अपोलोनियन नेटवर्क होता है।<ref>{{harvtxt|Andrade|Herrmann|Andrade|da Silva|2005}}.</ref> स्पर्शरेखा मंडलों के सेट का अस्तित्व, जिसकी स्पर्शरेखा किसी दिए गए अपोलोनियन नेटवर्क का प्रतिनिधित्व करती है, सर्कल पैकिंग प्रमेय का सरल उदाहरण बनाती है। रास्ता।<ref>{{harvtxt|Thurston|1978–1981}}.</ref>




=== पॉलीहेड्रा ===
=== पॉलीहेड्रा ===
[[File:Triakistetrahedron.jpg|thumb|150px|[[टर्नरी टेट्राहेड्रा की]], 8-वर्टेक्स अपोलोनियन नेटवर्क का बहुफलकीय अहसास]]अपोलोनियन नेटवर्क प्लानेर [[वर्टेक्स कनेक्टिविटी]] | 3-कनेक्टेड ग्राफ़ हैं और इसलिए, स्टीनिट्ज़ के प्रमेय द्वारा, हमेशा उत्तल [[ बहुतल |बहुतल]] के ग्राफ़ के रूप में प्रदर्शित किया जा सकता है। अपोलोनियन नेटवर्क का प्रतिनिधित्व करने वाला उत्तल पॉलीहेड्रॉन 3-आयामी स्टैक्ड पॉलीटॉप है। इस तरह के पॉलीटॉप को टेट्राहेड्रॉन से बार-बार अतिरिक्त टेट्राहेड्रा को बार में अपने त्रिकोणीय तलों पर चिपकाकर प्राप्त किया जा सकता है। इसलिए, अपोलोनियन नेटवर्क को स्टैक्ड 3डी बहुतलीय के ग्राफ के रूप में भी परिभाषित किया जा सकता है।<ref>See, e.g., {{harvtxt|Below|De Loera|Richter-Gebert|2000}}.</ref> उत्तल 3डी पॉलीहेड्रॉन के रूप में किसी भी अपोलोनियन नेटवर्क का प्रतिनिधित्व करना संभव है, जिसमें सभी निर्देशांक बहुपद आकार के पूर्णांक हैं, जो कि अन्य तलीय ग्राफ़ के लिए जाना जाता है।<ref>{{harvtxt|Demaine|Schulz|2011}}.</ref>
[[File:Triakistetrahedron.jpg|thumb|150px|[[टर्नरी टेट्राहेड्रा की]], 8-शीर्ष् अपोलोनियन नेटवर्क का बहुफलकीय अहसास]]अपोलोनियन नेटवर्क तल [[वर्टेक्स कनेक्टिविटी|शीर्ष् 3-जुड़े ग्राफ़]] हैं और इसलिए, स्टीनिट्ज़ के प्रमेय द्वारा, सदैव उत्तल [[ बहुतल |बहुतल]] के ग्राफ़ के रूप में प्रदर्शित किया जा सकता है। अपोलोनियन नेटवर्क का प्रतिनिधित्व करने वाला उत्तल पॉलीहेड्रॉन 3-आयामी स्टैक्ड पॉलीटॉप है। इस तरह के पॉलीटॉप को टेट्राहेड्रॉन से बार-बार अतिरिक्त टेट्राहेड्रा को बार में अपने त्रिकोणीय तलों पर चिपकाकर प्राप्त किया जा सकता है। इसलिए, अपोलोनियन नेटवर्क को स्टैक्ड 3डी बहुतलीय के ग्राफ के रूप में भी परिभाषित किया जा सकता है।<ref>See, e.g., {{harvtxt|Below|De Loera|Richter-Gebert|2000}}.</ref> उत्तल 3डी पॉलीहेड्रॉन के रूप में किसी भी अपोलोनियन नेटवर्क का प्रतिनिधित्व करना संभव है, जिसमें सभी निर्देशांक बहुपद आकार के पूर्णांक हैं, जो कि अन्य तलीय ग्राफ़ के लिए जाना जाता है।<ref>{{harvtxt|Demaine|Schulz|2011}}.</ref>




=== त्रिभुज जाल ===
=== त्रिभुज जाल ===
तीन छोटे त्रिभुजों में त्रिभुजों के पुनरावर्ती उपविभाजन की [[कंप्यूटर दृष्टि]] में [[विभाजन (इमेज प्रोसेसिंग)]] तकनीक के रूप में जांच की गई थी {{harvtxt|Elcock|Gargantini|Walsh|1987}}; इस संदर्भ में, उन्होंने इसे त्रैमासिक विषमबाहु त्रिभुज अपघटन कहा। उन्होंने देखा कि, प्रत्येक नए शीर्ष को उसके संलग्न त्रिभुज के [[केन्द्रक]] पर रखकर, त्रिभुज को इस तरह से चुना जा सकता है कि सभी त्रिभुजों का क्षेत्रफल समान हो, हालाँकि उन सभी का आकार समान नहीं होता है। आम तौर पर अधिक,
तीन छोटे त्रिभुजों में त्रिभुजों के पुनरावर्ती उपखंड की जांच {{harvtxt|एल्कॉक|गर्गेंटिनी|वॉल्श|1987}} द्वारा [[कंप्यूटर दृष्टि]] में एक छवि [[विभाजन (इमेज प्रोसेसिंग)]] विधि के रूप में की गई थी; इस संदर्भ में, उन्होंने इसे त्रैमासिक विषमबाहु त्रिभुज अपघटन कहा था। उन्होंने देखा कि, प्रत्येक नए शीर्ष को उसके संलग्न त्रिभुज के [[केन्द्रक]] पर रखकर, त्रिभुज को इस तरह से चुना जा सकता है कि सभी त्रिभुजों का क्षेत्रफल समान हो, चूँकि उन सभी का आकार समान नहीं होता है। सामान्यतः, अपोलोनियन नेटवर्क प्रत्येक तल में किसी भी निर्धारित क्षेत्र के साथ समतल में खींचे जा सकते हैं; यदि क्षेत्र परिमेय संख्याएँ हैं, तो सभी शीर्ष निर्देशांक हैं।<ref>{{harvtxt|Biedl|Ruiz Velázquez|2010}}.</ref>
अपोलोनियन नेटवर्क प्रत्येक तल में किसी भी निर्धारित क्षेत्र के साथ समतल में खींचे जा सकते हैं; यदि क्षेत्र परिमेय संख्याएँ हैं, तो सभी शीर्ष निर्देशांक हैं।<ref>{{harvtxt|Biedl|Ruiz Velázquez|2010}}.</ref>
 
अपोलोनियन नेटवर्क बनाने के लिए त्रिभुज को उप-विभाजित करने की प्रक्रिया को इस तरह से पूरा करना भी संभव है कि, प्रत्येक चरण पर किनारे की लंबाई परिमेय संख्याएँ हों; यह खुली समस्या है कि क्या हर तलीय ग्राफ में इस संपत्ति के साथ चित्र है।<ref>For subdividing a triangle with rational side lengths so that the smaller triangles also have rational side lengths, see {{harvtxt|Almering|1963}}. For progress on the general problem of finding planar drawings with rational edge lengths, see {{harvtxt|Geelen|Guo|McKinnon|2008}}.</ref> बहुपद समय में यह संभव है कि ड्राइंग के [[ आकार निर्धारक बॉक्स |आकार निर्धारक बॉक्स]] के क्षेत्र को कम करने वाले पूर्णांक निर्देशांक के साथ तलीय 3-ट्री का आरेखण खोजा जाए और यह परीक्षण किया जाए कि दिए गए सेट पर दिए गए तलीय 3-ट्री को उसके शीर्षों के साथ खींचा जा सकता है या नहीं बिंदुओं का।<ref>For the drawings with integer coordinates, see {{harvtxt|Mondal|Nishat|Rahman|Alam|2010}}, and for the drawings on a given vertex set, see {{harvtxt|Nishat|Mondal|Rahman|2011}}.</ref>
अपोलोनियन नेटवर्क बनाने के लिए त्रिभुज को उप-विभाजित करने की प्रक्रिया को इस तरह से पूरा करना भी संभव है कि, प्रत्येक चरण पर किनारे की लंबाई परिमेय संख्याएँ हों; यह खुली समस्या है कि क्या प्रत्येक तलीय ग्राफ में इस संपत्ति के साथ चित्र है।<ref>For subdividing a triangle with rational side lengths so that the smaller triangles also have rational side lengths, see {{harvtxt|Almering|1963}}. For progress on the general problem of finding planar drawings with rational edge lengths, see {{harvtxt|Geelen|Guo|McKinnon|2008}}.</ref> बहुपद समय में यह संभव है कि ड्राइंग के [[ आकार निर्धारक बॉक्स |आकार निर्धारक बॉक्स]] के क्षेत्र को कम करने के लिए पूर्णांक निर्देशांक के साथ एक तलीय 3-ट्री का आरेखण खोजना संभव है, और यह परीक्षण करने के लिए कि क्या दिए गए प्लानर 3-ट्री को दिए गए बिंदुओं के सेट पर इसके शीर्ष के साथ खींचा जा सकता है।<ref>For the drawings with integer coordinates, see {{harvtxt|Mondal|Nishat|Rahman|Alam|2010}}, and for the drawings on a given vertex set, see {{harvtxt|Nishat|Mondal|Rahman|2011}}.</ref>
 




Line 59: Line 66:


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


हालांकि अपोलोनियन नेटवर्क में स्वयं पूर्ण मिलान नहीं हो सकता है, अपोलोनियन नेटवर्क के तलीय दोहरे ग्राफ़ [[क्यूबिक ग्राफ]]़ हैं | 3-रेगुलर ग्राफ़ बिना ब्रिज (ग्राफ़ थ्योरी) के, इसलिए प्रमेय द्वारा {{harvtxt|Petersen|1891}} उनके पास कम से कम पूर्ण मिलान होने की गारंटी है। हालांकि, इस मामले में अधिक ज्ञात है: अपोलोनियन नेटवर्क के दोहरे में हमेशा पूर्ण मिलान की घातीय संख्या होती है।<ref>{{harvtxt|Jiménez|Kiwi|2010}}.</ref> लेज़्लो लोवाज़ और माइकल डी. प्लमर ने अनुमान लगाया कि समान घातांकी निचली सीमा कट किनारों के बिना प्रत्येक 3-नियमित ग्राफ़ के लिए अधिक आम तौर पर धारण करती है, परिणाम जो बाद में सिद्ध हुआ।
चूंकि अपोलोनियन नेटवर्क में स्वयं पूर्ण मिलान नहीं हो सकता है, अपोलोनियन नेटवर्क के तलीय दोहरे ग्राफ़ [[क्यूबिक ग्राफ]] हैं जिनमें कोई कटा हुआ किनारा नहीं है, इसलिए {{harvtxt|पीटरसन|1891}} के एक प्रमेय द्वारा उन्हें कम से कम एक पूर्ण मिलान की गारंटी दी जाती है। चूंकि, इस स्थिति में अधिक ज्ञात है कि अपोलोनियन नेटवर्क के ड्यूल में सदैव त्रुटिहीन मिलान की एक घातीय संख्या होती है।<ref>{{harvtxt|Jiménez|Kiwi|2010}}.</ref> लेज़्लो लोवाज़ और माइकल डी. प्लमर ने अनुमान लगाया कि समान घातांकी निचली सीमा कटे किनारों के बिना प्रत्येक 3-नियमित ग्राफ़ के लिए अधिक सामान्यतः एक परिणाम है जो बाद में सिद्ध हुआ था।।


=== पावर लॉ ग्राफ ===
=== पावर लॉ ग्राफ ===
{{harvtxt|Andrade|Herrmann|Andrade|da Silva|2005}} इस प्रकार के नेटवर्क के विशेष मामले की डिग्री (ग्राफ सिद्धांत) में [[बिजली कानून]]ों का अध्ययन किया, जो सभी त्रिभुजों को समान संख्या में उपविभाजित करके बनाया गया था। उन्होंने इन नेटवर्कों का उपयोग अलग-अलग आकार के कणों द्वारा अंतरिक्ष की पैकिंग के मॉडल के लिए किया। उनके काम के आधार पर, अन्य लेखकों ने यादृच्छिक अपोलोनियन नेटवर्क पेश किए, जो बार-बार यादृच्छिक तल को उपविभाजित करने के लिए चुनते हैं, और उन्होंने दिखाया कि ये भी उनके डिग्री वितरण में शक्ति कानूनों का पालन करते हैं <ref>{{harvtxt|Tsourakakis|2011}}</ref> और छोटी औसत दूरी है।<ref name="ran">{{harvtxt|Zhou|Yan|Zhou|Fu|2004}}; {{harvtxt|Zhou|Yan|Wang|2005}}.</ref> एलन एम. फ्रीज़ और चारलमपोस ई. त्सौराकाकिस ने यादृच्छिक अपोलोनियन नेटवर्क के उच्चतम डिग्री और आइगेनवैल्यू का विश्लेषण किया।<ref>{{harvtxt|Frieze|Tsourakakis|2011}}</ref> एंड्रेड एट अल। यह भी देखा कि उनके नेटवर्क [[छोटे विश्व प्रभाव]]<nowiki> को संतुष्ट करते हैं, कि सभी कोने दूसरे से थोड़ी दूरी पर हैं। संख्यात्मक साक्ष्य के आधार पर उन्होंने अनुमान लगाया कि में यादृच्छिक रूप से चयनित जोड़े के बीच औसत दूरी {{math|</nowiki>''n''}इस प्रकार का }-वरटेक्स नेटवर्क आनुपातिक होना चाहिए {{math|(log ''n'')<sup>3/4</sup>}}, लेकिन बाद में शोधकर्ताओं ने दिखाया कि औसत दूरी वास्तव में आनुपातिक है {{math|log ''n''}}.<ref>{{harvtxt|Albenque|Marckert|2008}};{{harvtxt|Zhang|Chen|Zhou|Fang|2008}}.</ref>
{{harvtxt|एंड्रेड|हरमैन|एंड्रेड|दा सिल्वा|2005}} ने इस प्रकार के नेटवर्क के विशेष स्थिति की डिग्री (ग्राफ सिद्धांत) में [[बिजली कानून|बिजली कानूनों]] का अध्ययन किया, जो सभी त्रिभुजों को समान संख्या में उपविभाजित करके बनाया गया था। उन्होंने इन नेटवर्कों का उपयोग अलग-अलग आकार के कणों द्वारा अंतरिक्ष की पैकिंग के मॉडल के लिए किया था। उनके काम के आधार पर, अन्य लेखकों ने यादृच्छिक अपोलोनियन नेटवर्क प्रस्तुत किए, जो बार-बार यादृच्छिक तल को उपविभाजित करने के लिए चुनते हैं, और उन्होंने दिखाया कि ये भी उनके डिग्री वितरण में शक्ति कानूनों का पालन करते हैं <ref>{{harvtxt|Tsourakakis|2011}}</ref> और छोटी औसत दूरी रखते हैं।<ref name="ran">{{harvtxt|Zhou|Yan|Zhou|Fu|2004}}; {{harvtxt|Zhou|Yan|Wang|2005}}.</ref> एलन एम. फ्रीज़ और चारलमपोस ई. त्सौराकाकिस ने यादृच्छिक अपोलोनियन नेटवर्क के उच्चतम डिग्री और आइगेनवैल्यू का विश्लेषण किया था।<ref>{{harvtxt|Frieze|Tsourakakis|2011}}</ref> एंड्रेड एट अल. ने यह भी देखा कि उनके नेटवर्क [[छोटे विश्व प्रभाव]] को संतुष्ट करते हैं, कि सभी कोने दूसरे से थोड़ी दूरी पर हैं। संख्यात्मक साक्ष्य के आधार पर उन्होंने अनुमान लगाया कि में यादृच्छिक रूप से चयनित जोड़े के बीच औसत दूरी {{math|(log ''n'')<sup>3/4</sup>}} के लिये आनुपातिक होना चाहिए, किन्तु बाद में शोधकर्ताओं ने दिखाया कि औसत दूरी वास्तविक में {{math|log ''n''}} आनुपातिक है।<ref>{{harvtxt|Albenque|Marckert|2008}};{{harvtxt|Zhang|Chen|Zhou|Fang|2008}}.</ref>




=== कोण वितरण ===
=== कोण वितरण ===
{{harvtxt|Butler|Graham|2010}} ने देखा कि यदि प्रत्येक नए शीर्ष को उसके त्रिकोण के [[केंद्र में]] रखा जाता है, ताकि किनारों को त्रिभुज के नए शीर्ष द्विभाजक#कोण द्विभाजक पर ले जाया जा सके, तो उपखंड में त्रिभुजों के कोणों के त्रिगुणों का सेट, जब के त्रिगुणों के रूप में पुनर्व्याख्या की जाती है समबाहु त्रिभुज में बिंदुओं की [[बैरीसेंट्रिक समन्वय प्रणाली (गणित)]], उपखंड के स्तरों की संख्या बढ़ने पर सिरपिन्स्की त्रिभुज के आकार में परिवर्तित हो जाती है।
{{harvtxt|बटलर|ग्राहम|2010}} ने देखा कि यदि प्रत्येक नए शीर्ष को उसके त्रिकोण के [[केंद्र में]] रखा जाता है, जिससे किनारों को त्रिभुज के नए शीर्ष द्विभाजक  
 
कोण द्विभाजक पर ले जाया जा सके, तो उपखंड में त्रिभुजों के कोणों के त्रिगुणों का सेट, जब के त्रिगुणों के रूप में पुनर्व्याख्या की जाती है समबाहु त्रिभुज में बिंदुओं की [[बैरीसेंट्रिक समन्वय प्रणाली (गणित)]], उपखंड के स्तरों की संख्या बढ़ने पर सिरपिन्स्की त्रिभुज के आकार में परिवर्तित हो जाती है।


=== हैमिलटोनिसिटी ===
=== हैमिलटोनिसिटी ===
{{harvtxt|Takeo|1960}} ने गलत तरीके से दावा किया कि सभी अपोलोनियन नेटवर्क में हैमिल्टनियन चक्र होते हैं; हालाँकि, गोल्डनर-हैरी ग्राफ प्रति उदाहरण प्रदान करता है। यदि अपोलोनियन नेटवर्क में ग्राफ की कठोरता से अधिक है (जिसका अर्थ है कि ग्राफ से किसी भी कोने को हटाने से हटाए गए कोने की संख्या की तुलना में कनेक्टेड घटकों की संख्या कम हो जाती है) तो यह आवश्यक रूप से हैमिल्टनियन चक्र है, लेकिन गैर-हैमिल्टनियन अपोलोनियन मौजूद है नेटवर्क जिनकी क्रूरता के बराबर है।<ref>See {{harvtxt|Nishizeki|1980}} for a 1-tough non-Hamiltonian example, {{harvtxt|Böhme|Harant|Tkáč|1999}} for the proof that Apollonian networks with greater toughness are Hamiltonian, and {{harvtxt|Gerlach|2004}} for an extension of this result to a wider class of planar graphs.</ref>
{{harvtxt|टेको|1960}} ने गलत विधि से प्रमाणित  किया कि सभी अपोलोनियन नेटवर्क में हैमिल्टनियन चक्र होते हैं; चूँकि, गोल्डनर-हैरी ग्राफ प्रति उदाहरण प्रदान करता है। यदि अपोलोनियन नेटवर्क में ग्राफ की कठोरता से अधिक है (जिसका अर्थ है कि ग्राफ से किसी भी कोने को हटाने से हटाए गए कोने की संख्या की तुलना में कनेक्टेड घटकों की संख्या कम हो जाती है) तो यह आवश्यक रूप से हैमिल्टनियन चक्र है, किन्तु गैर-हैमिल्टनियन अपोलोनियन उपस्थित है जो नेटवर्क जिनकी क्रूरता के बराबर है।<ref>See {{harvtxt|Nishizeki|1980}} for a 1-tough non-Hamiltonian example, {{harvtxt|Böhme|Harant|Tkáč|1999}} for the proof that Apollonian networks with greater toughness are Hamiltonian, and {{harvtxt|Gerlach|2004}} for an extension of this result to a wider class of planar graphs.</ref>




=== गणना ===
=== गणना ===
अपोलोनियन त्रिभुजों की गिनती की संयोजी गणना समस्या का अध्ययन किसके द्वारा किया गया था? {{harvtxt|Takeo|1960}}, जिन्होंने दिखाया कि उनके पास सरल [[जनरेटिंग फ़ंक्शन]] है {{math|''f''(''x'')}} समीकरण द्वारा वर्णित {{math|1=''f''(''x'') = 1 + ''x''(''f''(''x''))<sup>3</sup>}}.
{{harvtxt|ताकेओ|1960}} द्वारा अपोलोनियन त्रिभुजों की गणना की संयोजी गणना समस्या का अध्ययन किया गया, जिन्होंने दिखाया कि उनके पास समीकरण {{math|1=''f''(''x'') = 1 + ''x''(''f''(''x''))<sup>3</sup>}} द्वारा वर्णित सरल [[जनरेटिंग फ़ंक्शन]]  {{math|''f''(''x'')}} है।
इस जनरेटिंग फ़ंक्शन में, डिग्री की अवधि {{mvar|n}} अपोलोनियन नेटवर्क की संख्या को निश्चित बाहरी त्रिभुज के साथ गिनता है और {{math|''n'' + 3}} शिखर।
 
इस जनरेटिंग फ़ंक्शन में, डिग्री {{mvar|n}} की अवधि अपोलोनियन नेटवर्क की संख्या को एक निश्चित बाहरी त्रिकोण और {{math|''n'' + 3}} शिखर के साथ गिनाती है।
 
इस प्रकार, 3, 4, 5, ... कोने पर अपोलोनियन नेटवर्क (निश्चित बाहरी त्रिकोण के साथ) की संख्या हैं:
इस प्रकार, 3, 4, 5, ... कोने पर अपोलोनियन नेटवर्क (निश्चित बाहरी त्रिकोण के साथ) की संख्या हैं:
:1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... {{OEIS|A001764}},
:1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... {{OEIS|A001764}},
अनुक्रम जो [[त्रिगुट वृक्ष]]ों और उत्तल बहुभुजों के विच्छेदन को विषम-पक्षीय बहुभुजों में भी गिनता है।
अनुक्रम जो [[त्रिगुट वृक्ष|त्रिगुट]] ट्रीस और उत्तल बहुभुजों के विच्छेदन को विषम-पक्षीय बहुभुजों में भी गिनता है।
उदाहरण के लिए, 12 6-वर्टेक्स अपोलोनियन नेटवर्क हैं: तीन बाहरी त्रिभुज को बार उपविभाजित करके और फिर परिणामी त्रिभुजों में से दो को उपविभाजित करके बनाए गए हैं,
 
और नौ बाहरी त्रिभुज को बार उपविभाजित करके, उसके त्रिभुज को उपविभाजित करके, और फिर परिणामी छोटे त्रिभुजों में से को उपविभाजित करके बनाया गया।
उदाहरण के लिए, 12 6-शीर्ष् अपोलोनियन नेटवर्क हैं: तीन बाहरी त्रिभुज को बार उपविभाजित करके और फिर परिणामी त्रिभुजों में से दो को उपविभाजित करके बनाए गए हैं, और नौ बाहरी त्रिभुज को बार उपविभाजित करके, उसके त्रिभुज को उपविभाजित करके, और फिर परिणामी छोटे त्रिभुजों में से को उपविभाजित करके बनाया गया।


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


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


अपोलोनियन नेटवर्क नाम किसके द्वारा दिया गया था {{harvtxt|Andrade|Herrmann|Andrade|da Silva|2005}} उन नेटवर्कों के लिए जिनका उन्होंने अध्ययन किया जिसमें त्रिभुजों के उपविभाजन का स्तर पूरे नेटवर्क में समान है; ये नेटवर्क ज्यामितीय रूप से प्रकार के स्टैक्ड पॉलीहेड्रॉन के अनुरूप होते हैं जिन्हें [[क्लीटोप]] कहा जाता है।<ref>{{harvtxt|Grünbaum|1963}}; {{harvtxt|Grünbaum|1967}}.</ref> अन्य लेखकों ने एंड्रेड एट अल के मॉडल को सामान्यीकृत करते हुए अपने काम में प्लैनर 3-वृक्षों के लिए समान नाम को अधिक व्यापक रूप से लागू किया। यादृच्छिक अपोलोनियन नेटवर्क के लिए।<ref name="ran"/>इस तरह से उत्पन्न त्रिभुजों को स्टैक्ड त्रिकोणासन भी नाम दिया गया है<ref>{{harvtxt|Alon|Caro|1984}}; {{harvtxt|Zickfeld|Ziegler|2006}}; {{harvtxt|Badent|Binucci|Di Giacomo|Didimo|2007}}; {{harvtxt|Felsner|Zickfeld|2008}}.</ref> या ढेर-त्रिकोण।<ref>{{harvtxt|Albenque|Marckert|2008}}; {{harvtxt|Bernardi|Bonichon|2009}}; {{harvtxt|Jiménez|Kiwi|2010}}.</ref>
अपोलोनियन नेटवर्क नाम किसके द्वारा दिया गया था {{harvtxt|एंड्राडे|Herrmann|Andrade|da Silva|2005}} उन नेटवर्कों के लिए जिनका उन्होंने अध्ययन किया जिसमें त्रिभुजों के उपविभाजन का स्तर पूरे नेटवर्क में समान है; ये नेटवर्क ज्यामितीय रूप से प्रकार के स्टैक्ड पॉलीहेड्रॉन के अनुरूप होते हैं जिन्हें [[क्लीटोप]] कहा जाता है।<ref>{{harvtxt|Grünbaum|1963}}; {{harvtxt|Grünbaum|1967}}.</ref> अन्य लेखकों ने एंड्रेड एट अल के मॉडल को सामान्यीकृत करते हुए अपने काम में प्लैनर 3-ट्रीस के लिए समान नाम को अधिक व्यापक रूप से प्रयुक्त किया। यादृच्छिक अपोलोनियन नेटवर्क के लिए।<ref name="ran"/>इस तरह से उत्पन्न त्रिभुजों को स्टैक्ड त्रिकोणासन या ढेर-त्रिकोण भी नाम दिया गया है।<ref>{{harvtxt|Alon|Caro|1984}}; {{harvtxt|Zickfeld|Ziegler|2006}}; {{harvtxt|Badent|Binucci|Di Giacomo|Didimo|2007}}; {{harvtxt|Felsner|Zickfeld|2008}}.</ref><ref>{{harvtxt|Albenque|Marckert|2008}}; {{harvtxt|Bernardi|Bonichon|2009}}; {{harvtxt|Jiménez|Kiwi|2010}}.</ref>




Line 610: Line 621:
*{{mathworld|title=Apollonian Network|urlname=ApollonianNetwork|mode=cs2}}
*{{mathworld|title=Apollonian Network|urlname=ApollonianNetwork|mode=cs2}}
* [http://www.math.cmu.edu/~ctsourak/ran.html Matlab Simulation Code]
* [http://www.math.cmu.edu/~ctsourak/ran.html Matlab Simulation Code]
[[Category: ग्राफ परिवार]] [[Category: बिल्कुल सही रेखांकन]] [[Category: प्लानर रेखांकन]] [[Category: त्रिकोणासन (ज्यामिति)]]


[[Category: Machine Translated Page]]
[[Category:Created On 28/02/2023]]
[[Category:Created On 28/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ग्राफ परिवार]]
[[Category:त्रिकोणासन (ज्यामिति)]]
[[Category:प्लानर रेखांकन]]
[[Category:बिल्कुल सही रेखांकन]]

Latest revision as of 12:11, 18 September 2023

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

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

परिभाषा

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

उदाहरण

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

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

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

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

तारतम्य

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

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

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

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

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


ट्रीविड्थ

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

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


विकृति

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

आकार

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

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


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

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

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

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

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


पॉलीहेड्रा

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

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


त्रिभुज जाल

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

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


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

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

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

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

पावर लॉ ग्राफ

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


कोण वितरण

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

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

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

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


गणना

ताकेओ (1960) द्वारा अपोलोनियन त्रिभुजों की गणना की संयोजी गणना समस्या का अध्ययन किया गया, जिन्होंने दिखाया कि उनके पास समीकरण f(x) = 1 + x(f(x))3 द्वारा वर्णित सरल जनरेटिंग फ़ंक्शन 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 के दशक के प्रारंभ से पॉलीहेड्रल कॉम्बिनेटरिक्स में किया गया है, जब उनका उपयोग ग्रुनबौम (1963) द्वारा ग्राफ़ का वर्णन करने के लिए किया गया था, जिसे आयामी या कॉम्बीनेटरियल के बिना केवल एक तरह से पॉलीटॉप के ग्राफ़ के रूप में अस्पष्टता के, और मून & मोजर (1963) बिना लंबे रास्तों वाले साधारण बहुतलीय को खोजने के लिए अनुभूत किया जा सकता है। ग्राफ सिद्धांत में, प्लेनेरिटी और ट्रेविड्थ के बीच घनिष्ठ संबंध वापस चला जाता है रॉबर्टसन & सेमुर (1984), जिन्होंने दिखाया कि ग्राफ़ के प्रत्येक लघु-बंद परिवार में या तो ट्रेविड्थ की सीमा होती है या इसमें सभी तलीय ग्राफ़ होते हैं। ग्राफ़ के एक वर्ग के रूप में तलीय 3-ट्रीस को स्पष्ट रूप से हकीमी & शमीचेल (1979), अलोन & कारो (1984), पाटिल (1986), और उनके बाद से कई लेखकों द्वारा माने गए थे।

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


यह भी देखें

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

टिप्पणियाँ

  1. ↑ This graph is named after the work of Goldner & Harary (1975); however, it appears earlier in the literature, for instance in Grünbaum (1967), p. 357.
  2. ↑ The equivalence of planar 3-trees and chordal maximal planar graphs was stated without proof by Patil (1986). For a proof, see Markenzon, Justel & Paciornik (2006). For a more general characterization of chordal planar graphs, and an efficient recognition algorithm for these graphs, see Kumar & Madhavan (1989). The observation that every chordal polyhedral graph is maximal planar was stated explicitly by Gerlach (2004).
  3. ↑ Fowler (1998).
  4. ↑ The fact that Apollonian networks minimize the number of colorings with more than four of colors was shown in a dual form for colorings of maps by Birkhoff (1930).
  5. ↑ Felsner & Zickfeld (2008); Bernardi & Bonichon (2009).
  6. ↑ The two forbidden minors for planar graphs are given by Wagner's theorem. For the forbidden minors for partial 3-trees (which include also the nonplanar Wagner graph) see Arnborg, Proskurowski & Corniel (1986) and Bodlaender (1998). For direct proofs that the octahedral graph and the pentagonal-prism graph are the only two planar forbidden minors, see Dai & Sato (1990) and El-Mallah & Colbourn (1990).
  7. ↑ Politof (1983) introduced the Δ-Y reducible planar graphs and characterized them in terms of forbidden homeomorphic subgraphs. The duality between the Δ-Y and Y-Δ reducible graphs, the forbidden minor characterizations of both classes, and the connection to planar partial 3-trees are all from El-Mallah & Colbourn (1990).
  8. ↑ For the characterization in terms of the maximum number of triangles in a planar graph, see Hakimi & Schmeichel (1979). Alon & Caro (1984) quote this result and provide the characterizations in terms of the isomorphism classes of blocks and numbers of blocks. The bound on the total number of cliques follows easily from the bounds on triangles and K4 subgraphs, and is also stated explicitly by Wood (2007), who provides an Apollonian network as an example showing that this bound is tight. For generalizations of these bounds to nonplanar surfaces, see Dujmović et al. (2009).
  9. ↑ Andrade et al. (2005).
  10. ↑ Thurston (1978–1981).
  11. ↑ See, e.g., Below, De Loera & Richter-Gebert (2000).
  12. ↑ Demaine & Schulz (2011).
  13. ↑ Biedl & Ruiz Velázquez (2010).
  14. ↑ For subdividing a triangle with rational side lengths so that the smaller triangles also have rational side lengths, see Almering (1963). For progress on the general problem of finding planar drawings with rational edge lengths, see Geelen, Guo & McKinnon (2008).
  15. ↑ For the drawings with integer coordinates, see Mondal et al. (2010), and for the drawings on a given vertex set, see Nishat, Mondal & Rahman (2011).
  16. ↑ Jiménez & Kiwi (2010).
  17. ↑ Tsourakakis (2011)
  18. ↑ 18.0 18.1 Zhou et al. (2004); Zhou, Yan & Wang (2005).
  19. ↑ Frieze & Tsourakakis (2011)
  20. ↑ Albenque & Marckert (2008);Zhang et al. (2008).
  21. ↑ See Nishizeki (1980) for a 1-tough non-Hamiltonian example, Böhme, Harant & Tkáč (1999) for the proof that Apollonian networks with greater toughness are Hamiltonian, and Gerlach (2004) for an extension of this result to a wider class of planar graphs.
  22. ↑ Grünbaum (1963); Grünbaum (1967).
  23. ↑ Alon & Caro (1984); Zickfeld & Ziegler (2006); Badent et al. (2007); Felsner & Zickfeld (2008).
  24. ↑ Albenque & Marckert (2008); Bernardi & Bonichon (2009); Jiménez & Kiwi (2010).


संदर्भ


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अपोलोनियन_नेटवर्क&oldid=258335’