मूर ग्राफ: Difference between revisions

Revision as of 08:51, 11 May 2023

Unsolved problem in गणित:

क्या मूर ग्राफ 5 और डिग्री 57 के साथ सम्मिलित है?

आरेख़ सिद्धांत में मूर आरेख़ एक नियमित आरेख है जिसकी परिधि (सबसे छोटे वृत्त की लंबाई) उसके व्यास (सबसे दूर के दो शीर्षों के बीच की दूरी) से दो गुना अधिक होती है। यदि इस प्रकार के आरेख की डिग्री $d$ है और इसका व्यास $k$ है तो इसकी परिधि $2 k + 1$ के बराबर होना चाहिए। यह सच है कि डिग्री $d$ और व्यास $k$ के आरेख के लिए यदि और केवल यदि इसके शीर्षों की संख्या बराबर होती है:

1+d\sum _{i=0}^{k-1}(d-1)^{i},

इस डिग्री और व्यास के साथ किसी भी आरेख में शीर्ष की सबसे बड़ी संभव संख्या पर एक ऊपरी सीमा होती है इसलिए ये रेखांकन उनके मापदंडों के लिए डिग्री व्यास की समस्या को हल करते हैं।

मूर आरेख $G$ की एक और समतुल्य परिभाषा यह है कि इसकी परिधि $g = 2 k + 1$ और $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n/g(m – n + 1)$ , $g$ लंबाई का वृत्त है जहाँ $n$ और $m$ क्रमश: शीर्षों और किनारों की संख्या $G$ है वे वास्तव में उन वृत्तों की संख्या के संबंध में शीर्ष पर हैं जिनकी लंबाई आरेख की परिधि है।^[1]

एडवर्ड एफ.मूर के नाम पर हॉफमैन & सिंगलटन (1960) द्वारा मूर आरेख का नामकरण किया गया था। जिन्होंने इन आरेखों का वर्णन और वर्गीकरण करने का प्रश्न उठाया था।

डिग्री और व्यास के दिए गए संयोजन के लिए अधिकतम संभावित संख्या होने के साथ-साथ, मूर आरेख़ में दी गई डिग्री और परिधि के साथ एक नियमित आरेख़ के लिए न्यूनतम संभव संख्या में शीर्ष होते हैं। अर्थात्, कोई भी मूर आरेख एक केज (आरेख सिद्धांत) है।^[2] मूर आरेख़ में शीर्षों की संख्या के लिए एक सूत्र को सामान्यीकृत किया जा सकता है क्योकि मूर आरेख़ की परिभाषा मे सम परिधि के साथ-साथ विषम परिधि और रेखांकन केज आरेख भी हो सकते हैं।

डिग्री और व्यास द्वारा शीर्ष सीमांकन

मूर ग्राफ के रूप में पीटरसन आरेख किसी चौड़ाई वाले प्रथम खोज वृत्त के iवें स्तर में

d (d - 1) i

शीर्ष होते हैं।

माना कि G अधिकतम डिग्री d और व्यास k के साथ कोई भी आरेख और किसी भी शीर्ष v से प्रारम्भ होने वाली चौड़ाई से पहले एक खोज द्वारा बनाया गया है जिस पर विचार करें कि इस शृंखला के स्तर 0 (v स्वयं) पर 1 शीर्ष है और स्तर 1 (v के निकटतम) पर अधिकांश d शीर्ष हैं। $v$ स्वयं) पर 1 शीर्ष है और स्तर 1 पर अधिकतम $d$ शीर्ष हैं ( $v$ के निकटतम) अगले स्तर में, अधिकतम $d (d - 1)$ शीर्ष हैं: $v$ का प्रत्येक निकटतम भाग $v$ से जुड़ने के लिए यह अपनी एक निकटता का उपयोग करता है और इसलिए स्तर 2 पर अधिकतम $d - 1$ निकटतम शीर्ष हो सकते हैं। सामान्यतः एक समान तर्क दर्शाता है कि किसी भी स्तर $1 \leq i \leq k$ पर, अधिकतम $d (d - 1) i -1$ शीर्ष हो सकते हैं। इस प्रकार, शीर्षों की कुल संख्या अधिक से अधिक हो सकती है:

1+d\sum _{i=0}^{k-1}(d-1)^{i}.

हॉफमैन & सिंगलटन (1960) ने मूल रूप से मूर आरेख को एक आरेख के रूप में परिभाषित किया था जिसके लिए शीर्ष की संख्या पर यह सीमा पूरी तरह से समान है। इसलिए किसी भी मूर आरेख़ में अधिकतम डिग्री $d$ और व्यास $k$ वाले सभी आरेख़ों में अधिकतम संभव शीर्ष होते हैं। बाद में सिंगलटन (1968) ने दिखाया कि मूर आरेख़ को समान रूप से व्यास $k$ और परिधि $2 k + 1$ के रूप में परिभाषित किया जा सकता है ये दो आवश्यकताएं आरेख को डिग्री $d$ के लिए डिग्री $d$ पर नियमित होने के लिए बाध्य करती हैं और शीर्ष के गणनात्मक सूत्र को संतुष्ट करती हैं।

केज आरेख के रूप में मूर रेखांकन

इसकी अधिकतम डिग्री और इसके व्यास के संदर्भ में एक आरेख में शीर्षों की संख्या की ऊपरी सीमा के अतिरिक्त समान विधियों के माध्यम से इसकी न्यूनतम डिग्री और इसकी परिधि के संदर्भ में शीर्षों की संख्या पर एक निचली सीमा की गणना कर सकते हैं।^[2] माना कि $G$ की न्यूनतम डिग्री $d$ और परिधि $2 k + 1$ है। अपेक्षाकृत रूप से एक प्रारंभिक शीर्ष $v$ चुनें और पहले की तरह चौड़ाई प्रथम खोज शीर्ष को $v$ पर इस शीर्ष के स्तर 0 ( $v$ स्वयं) पर एक शीर्ष होना चाहिए और कम से कम d शीर्ष स्तर 1 पर स्तर 2 (k > 1 के लिए), कम से कम $d (d - 1)$ शीर्ष होने चाहिए, क्योंकि स्तर 1 पर प्रत्येक शीर्ष में कम से कम $d - 1$ शेष आसन्नताएं होती हैं और कोई दो शीर्ष नहीं होते हैं। स्तर 1 एक दूसरे के निकट हो सकता है या स्तर 2 पर एक साझा शीर्ष पर हो सकता है क्योंकि यह अनुमानित परिधि से छोटा वृत्त बना देता है व्यापक रूप से समान तर्क दर्शाता है कि किसी भी स्तर $1 \leq i \leq k$ पर कम से कम $d (d - 1) i$ शीर्ष होने चाहिए। इस प्रकार, शीर्षों की कुल संख्या कम से कम होनी चाहिए:

1+d\sum _{i=1}^{k-1}(d-1)^{i}.

मूर आरेख़ में, शीर्षों की संख्या पर निर्धारित यह सीमा पूरी तरह से प्राप्त होती है। प्रत्येक मूर आरेख़ की परिधि ठीक $2 k + 1$ होती है इसमें उच्च परिधि रखने के लिए पर्याप्त शीर्ष नहीं हैं और एक छोटा वृत्त किसी चौड़ाई वाले पहले खोज वृत्त के पहले $k$ स्तरों में बहुत कम शीर्ष होने का कारण था इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री $d$ और परिधि $2 k + 1$ के साथ सभी आरेखों में न्यूनतम संख्या संभव है क्योकि यह एक केज आरेख है।

यहां तक कि $2 k$ परिधि के लिए, एक शीर्ष के मध्य बिंदु से प्रारम्भ होने वाली एक चौड़ाई पहली खोज का वृत्त बना सकती हैं। न्यूनतम डिग्री $d$ के साथ इस परिधि के आरेख में न्यूनतम संख्या में शीर्ष पर परिणामी सीमा है:

2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.

सूत्र के दाहिने हाथ की ओर इसके अतिरिक्त एक शीर्ष से प्रारम्भ होने वाली चौड़ाई वाले पहले खोज वृत्त में शीर्षों की संख्या की गणना करता है इस संभावना के लिए लेखांकन कि वृत्त के अंतिम स्तर में एक शीर्ष पिछले स्तर में $d$ शीर्षों के निकटम हो सकता है। इस प्रकार, मूर आरेख़ को कभी-कभी उन आरेख़ मे सम्मिलित करने के रूप में परिभाषित किया जाता है जो वास्तव में इस सीमा को पूर्ण करते हैं। जिससे ऐसा कोई भी आरेख केज आरेख होता है।

उदाहरण

हॉफमैन-सिंगलटन प्रमेय में कहा गया है कि परिधि 5 के साथ किसी भी मूर आरेख की डिग्री 2, 3, 7 या 57 होना एक मूर आरेख हैं:^[3]

$n > 2$ नोड्स पर पूर्ण रेखांकन $K n$ (व्यास 1, परिधि 3, डिग्री $n - 1$ , क्रम $n$ )
विषम वृत्त आरेख $C 2 n +1$ (व्यास $n$ , परिधि $2 n + 1$ , डिग्री 2, क्रम $2 n + 1$ )
पीटरसन आरेख (व्यास 2, परिधि 5, डिग्री 3, क्रम 10)
हॉफमैन-सिंगलटन आरेख (व्यास 2, परिधि 5, डिग्री 7, क्रम 50)
व्यास 2, परिधि 5, डिग्री 57 और क्रम 3250 का एक काल्पनिक आरेख है जिसका अस्तित्व अज्ञात है।^[4]

हालांकि सभी ज्ञात मूर आरेख़ शीर्ष-सकर्मक आरेख हैं यदि यह काल्पनिक आरेख सम्मिलित है तो शीर्ष-सकर्मक रेखांकन नहीं हो सकता है क्योंकि इसके स्वसमाकृतिकता समूह में अधिकतम अनुक्रम 375 पर हो सकता है जो इसके शीर्षों की संख्या से कम है।^[5]

यदि मूर आरेख़ की सामान्यीकृत परिभाषा जो परिधि आरेख़ की स्वीकृति देती है इसका उपयोग किया जाता है तो सम परिधि मूर आरेख़ सामान्यीकृत बहुभुज (संभावित पतित) के घटना आरेख़ के अनुरूप होता हैं। कुछ उदाहरण मे $C 2 n$ सम वृत्त हैं, पूर्ण द्विभाज्य रेखांकन $K n, n$ परिधि 4 के साथ हीवुड आरेख डिग्री 3 और परिधि 6 के साथ टुट्टे-कॉक्सेटर आरेख डिग्री 3 और परिधि 8 के साथ अधिक सामान्यतः यह ज्ञात है कि ऊपर सूचीबद्ध आरेख़ के अतिरिक्त सभी मूर आरेख़ की परिधि 5, 6, 8, या 12 होती है।^[6] एक सामान्यीकृत $n$ -गॉन के लिए $n$ के संभावित मानों के विषय में प्रयुक्त हिगमैन प्रमेय से सम परिधि की स्थिति का अनुसरण करता है।

यह भी देखें

किसी दिए गए व्यास और अधिकतम डिग्री के सबसे बड़े ज्ञात रेखांकन की तालिका

संदर्भ

Azarija, Jernej; Klavžar, Sandi (2015), "Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles", Journal of Graph Theory, 80: 34–42, arXiv:1210.6342, doi:10.1002/jgt.21837, S2CID 333785
Bannai, E.; Ito, T. (1973), "On finite Moore graphs", Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics, 20: 191–208, MR 0323615, archived from the original on 2012-04-24
Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag.
Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF), Linear Algebra and Its Applications, 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl:2117/127212, MR 3901732, S2CID 126689579
Damerell, R. M. (1973), "On Moore graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 74 (2): 227–236, Bibcode:1973PCPS...74..227D, doi:10.1017/S0305004100048015, MR 0318004
Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235, archived from the original (PDF) on 2016-03-09, retrieved 2010-02-23.
Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437
Mačaj, Martin; Širáň, Jozef (2010), "Search for properties of the missing Moore graph", Linear Algebra and Its Applications, 432 (9): 2381–2398, doi:10.1016/j.laa.2009.07.018.
Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly, 75 (1): 42–43, doi:10.2307/2315106, JSTOR 2315106, MR 0225679

बाहरी संबंध

Brouwer and Haemers: Spectra of graphs
Eric W. Weisstein, Moore Graph (Hoffman-Singleton Theorem) at MathWorld.

[FOOTNOTEAzarijaKlavžar2015-1] Azarija & Klavžar (2015).

[FOOTNOTEErdősRényiSós1966-2] 2.0 ^2.1 Erdős, Rényi & Sós (1966).

[FOOTNOTEBollobás1998Theorem_19,_p._276-3] Bollobás (1998), Theorem 19, p. 276.

[FOOTNOTEDalfó2019-4] Dalfó (2019).

[FOOTNOTEMačajŠiráň2010-5] Mačaj & Širáň (2010).

[6] Bannai & Ito (1973); Damerell (1973)

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 2: / Line 2: @@
 {{unsolved|गणित|क्या मूर ग्राफ 5 और डिग्री 57 के साथ सम्मिलित है?}}
-आरेख़ सिद्धांत में '''मूर आरेख़''' एक [[नियमित ग्राफ|नियमित आरेख]] है जिसकी परिधि (सबसे छोटा चक्र लंबाई) उसके व्यास से दो गुना अधिक होती है (सबसे दूर के दो कोने के बीच की दूरी)। यदि इस प्रकार के आरेख की डिग्री {{mvar|d}} है और इसका व्यास {{mvar|k}} है, तो इसका घेरा {{math|2''k'' + 1}} के बराबर होना चाहिए। यह सच है, डिग्री {{mvar|d}} और व्यास {{mvar|k}} के आरेख के लिए, यदि और केवल यदि इसके शीर्षों की संख्या बराबर होती है
+आरेख़ सिद्धांत में '''मूर आरेख़''' एक [[नियमित ग्राफ|नियमित आरेख]] है जिसकी परिधि (सबसे छोटे वृत्त की लंबाई) उसके व्यास (सबसे दूर के दो शीर्षों के बीच की दूरी) से दो गुना अधिक होती है। यदि इस प्रकार के आरेख की डिग्री {{mvar|d}} है और इसका व्यास {{mvar|k}} है तो इसकी परिधि {{math|2''k'' + 1}} के बराबर होना चाहिए। यह सच है कि डिग्री {{mvar|d}} और व्यास {{mvar|k}} के आरेख के लिए यदि और केवल यदि इसके शीर्षों की संख्या बराबर होती है:
 :<math>1+d\sum_{i=0}^{k-1}(d-1)^i,</math>
-इस डिग्री और व्यास के साथ किसी भी आरेख में वर्टिकल की सबसे बड़ी संभव संख्या पर एक [[ऊपरी सीमा]] इसलिए, ये रेखांकन उनके मापदंडों के लिए [[डिग्री व्यास की समस्या]] को हल करते हैं।
+इस डिग्री और व्यास के साथ किसी भी आरेख में शीर्ष की सबसे बड़ी संभव संख्या पर एक [[ऊपरी सीमा]] होती है इसलिए ये रेखांकन उनके मापदंडों के लिए [[डिग्री व्यास की समस्या]] को हल करते हैं।
-मूर आरेख की एक और समकक्ष परिभाषा {{math|G}} यह है कि इसकी परिधि है {{math|1=''g'' = 2''k'' + 1}} और ठीक {{math|{{sfrac|''n''|''g''}}(''m'' – ''n'' + 1)}} लंबाई का चक्र {{mvar|g}}, कहाँ {{mvar|n}} और {{mvar|m}} क्रमश: शीर्षों और किनारों की संख्या है {{mvar|G}}. वे वास्तव में उन चक्रों की संख्या के संबंध में चरम हैं जिनकी लंबाई आरेख की परिधि है।{{sfnp|Azarija|Klavžar|2015}}
+मूर आरेख {{math|G}} की एक और समतुल्य परिभाषा यह है कि इसकी परिधि {{math|1=''g'' = 2''k'' + 1}} और {{math|{{sfrac|''n''|''g''}}(''m'' – ''n'' + 1)}}, {{mvar|g}} लंबाई का वृत्त है जहाँ {{mvar|n}} और {{mvar|m}} क्रमश: शीर्षों और किनारों की संख्या {{mvar|G}} है वे वास्तव में उन वृत्तों की संख्या के संबंध में शीर्ष पर हैं जिनकी लंबाई आरेख की परिधि है।{{sfnp|Azarija|Klavžar|2015}}
-एडवर्ड एफ. मूर के नाम पर {{harvtxt|हॉफमैन|सिंगलटन|1960}} द्वारा मूर आरेख का नामकरण किया गया था, जिन्होंने इन आरेखों का वर्णन और वर्गीकरण करने का प्रश्न उठाया था।
+एडवर्ड एफ.मूर के नाम पर {{harvtxt|हॉफमैन|सिंगलटन|1960}} द्वारा मूर आरेख का नामकरण किया गया था। जिन्होंने इन आरेखों का वर्णन और वर्गीकरण करने का प्रश्न उठाया था।
-डिग्री और व्यास के दिए गए संयोजन के लिए अधिकतम संभावित संख्या होने के साथ-साथ, मूर आरेख़ में दी गई डिग्री और परिधि के साथ एक नियमित आरेख़ के लिए न्यूनतम संभव संख्या में वर्टिकल होते हैं। अर्थात्, कोई भी मूर आरेख एक [[पिंजरा (ग्राफ सिद्धांत)|पिंजरा (आरेख सिद्धांत)]] है।{{sfnp|Erdős|Rényi|Sós|1966}} मूर आरेख़ में वर्टिकल की संख्या के लिए सूत्र को सामान्यीकृत किया जा सकता है ताकि मूर आरेख़ की परिभाषा के साथ-साथ विषम परिधि भी हो, और फिर से ये आरेख़ पिंजरे हैं।
+डिग्री और व्यास के दिए गए संयोजन के लिए अधिकतम संभावित संख्या होने के साथ-साथ, मूर आरेख़ में दी गई डिग्री और परिधि के साथ एक नियमित आरेख़ के लिए न्यूनतम संभव संख्या में शीर्ष होते हैं। अर्थात्, कोई भी मूर आरेख एक [[पिंजरा (ग्राफ सिद्धांत)|केज (आरेख सिद्धांत)]] है।{{sfnp|Erdős|Rényi|Sós|1966}} मूर आरेख़ में शीर्षों की संख्या के लिए एक सूत्र को सामान्यीकृत किया जा सकता है क्योकि मूर आरेख़ की परिभाषा मे सम परिधि के साथ-साथ विषम परिधि और रेखांकन केज आरेख भी हो सकते हैं।
-== डिग्री और व्यास द्वारा वर्टिकल बाउंडिंग ==
+== डिग्री और व्यास द्वारा शीर्ष सीमांकन ==
-[[Image:Petersen-as-Moore.svg|thumb|मूर आरेख के रूप में [[पीटरसन ग्राफ|पीटरसन आरेख]]। कोई भी चौड़ाई पहले खोज वृक्ष में होती है {{math|''d''(''d'' − 1){{sup|''i''}}}} इसके कोने {{mvar|i}}वां स्तर।]]{{mvar|G}} को अधिकतम डिग्री d और व्यास k के साथ कोई भी आरेख होने दें, और किसी भी शीर्ष v से प्रारम्भ होने वाली चौड़ाई से पहले खोज द्वारा बनाए गए पेड़ पर विचार करें। इस पेड़ के स्तर 0 ({{mvar|v}} स्वयं) पर 1 शीर्ष है, और स्तर 1 पर अधिकतम {{mvar|d}} कोने हैं ( {{mvar|v}} के निकटतम)। अगले स्तर में, अधिकतम {{math|''d''(''d'' − 1)}} शीर्ष हैं: {{mvar|v}} का प्रत्येक निकटतम {{mvar|v}} से जुड़ने के लिए अपनी एक निकटता का उपयोग करता है और इसलिए स्तर 2 पर अधिकतम {{math|''d'' − 1}} निकटतम हो सकते हैं। सामान्यतः एक समान तर्क दर्शाता है कि किसी भी स्तर {{math|1 ≤ ''i'' ≤ ''k''}} पर, अधिकतम {{math|''d''(''d'' − 1){{sup|''i''−1}}}} शीर्ष हो सकते हैं। इस प्रकार, शीर्षों की कुल संख्या अधिक से अधिक हो सकती है
+[[Image:Petersen-as-Moore.svg|thumb|मूर ग्राफ के रूप में [[पीटरसन ग्राफ|पीटरसन आरेख]] किसी चौड़ाई वाले प्रथम खोज वृत्त के iवें स्तर में {{math|''d''(''d'' − 1){{sup|''i''}}}} शीर्ष होते हैं।]]{{mvar|}}माना कि G अधिकतम डिग्री d और व्यास k के साथ कोई भी आरेख और किसी भी शीर्ष v से प्रारम्भ होने वाली चौड़ाई से पहले एक खोज द्वारा बनाया गया है जिस पर विचार करें कि इस शृंखला के स्तर 0 (v स्वयं) पर 1 शीर्ष है और स्तर 1 (v के निकटतम) पर अधिकांश d शीर्ष हैं।{{mvar| v}} स्वयं) पर 1 शीर्ष है और स्तर 1 पर अधिकतम {{mvar|d}} शीर्ष हैं ( {{mvar|v}} के निकटतम) अगले स्तर में, अधिकतम {{math|''d''(''d'' − 1)}} शीर्ष हैं: {{mvar| v}} का प्रत्येक निकटतम भाग{{mvar|v}} से जुड़ने के लिए यह अपनी एक निकटता का उपयोग करता है और इसलिए स्तर 2 पर अधिकतम {{math|''d'' − 1}} निकटतम शीर्ष हो सकते हैं। सामान्यतः एक समान तर्क दर्शाता है कि किसी भी स्तर {{math|1 ≤ ''i'' ≤ ''k''}} पर, अधिकतम {{math|''d''(''d'' − 1){{sup|''i''−1}}}} शीर्ष हो सकते हैं। इस प्रकार, शीर्षों की कुल संख्या अधिक से अधिक हो सकती है:
 :<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>
-{{harvtxt|हॉफमैन|सिंगलटन|1960}} ने मूल रूप से एक मूर आरेख को एक आरेख के रूप में परिभाषित किया था जिसके लिए वर्टिकल की संख्या पर यह सीमा पूरी तरह से मिलती है। इसलिए, किसी भी मूर आरेख़ में अधिकतम डिग्री {{mvar|d}} और व्यास {{mvar|k}} वाले सभी आरेख़ों में अधिकतम संभव वर्टिकल होते हैं।
+{{harvtxt|हॉफमैन|सिंगलटन|1960}} ने मूल रूप से मूर आरेख को एक आरेख के रूप में परिभाषित किया था जिसके लिए शीर्ष की संख्या पर यह सीमा पूरी तरह से समान है। इसलिए किसी भी मूर आरेख़ में अधिकतम डिग्री {{mvar|d}} और व्यास {{mvar|k}} वाले सभी आरेख़ों में अधिकतम संभव शीर्ष होते हैं। बाद में सिंगलटन (1968) ने दिखाया कि मूर आरेख़ को समान रूप से व्यास {{mvar|k}} और परिधि {{math|2''k'' + 1}} के रूप में परिभाषित किया जा सकता है ये दो आवश्यकताएं आरेख को डिग्री {{mvar|d}} के लिए डिग्री {{mvar|d}} पर नियमित होने के लिए बाध्य करती हैं और शीर्ष के गणनात्मक सूत्र को संतुष्ट करती हैं।
-बाद में, सिंगलटन (1968) ने दिखाया कि मूर आरेख़ को समान रूप से व्यास {{mvar|k}} और परिधि {{math|2''k'' + 1}} के रूप में परिभाषित किया जा सकता है ये दो आवश्यकताएं आरेख को कुछ {{mvar|d}} के लिए {{mvar|d}} -नियमित होने के लिए बाध्य करती हैं और वर्टेक्स-काउंटिंग सूत्र को संतुष्ट करती हैं।
+== केज आरेख के रूप में मूर रेखांकन ==
-== पिंजरों के रूप में मूर रेखांकन ==
+इसकी अधिकतम डिग्री और इसके व्यास के संदर्भ में एक आरेख में शीर्षों की संख्या की ऊपरी सीमा के अतिरिक्त समान विधियों के माध्यम से इसकी न्यूनतम डिग्री और इसकी परिधि के संदर्भ में शीर्षों की संख्या पर एक निचली सीमा की गणना कर सकते हैं।{{sfnp|Erdős|Rényi|Sós|1966}} माना कि {{mvar|G}} की न्यूनतम डिग्री {{mvar|d}} और परिधि {{math|2''k'' + 1}} है। अपेक्षाकृत रूप से एक प्रारंभिक शीर्ष {{mvar|v}} चुनें और पहले की तरह चौड़ाई प्रथम खोज शीर्ष को {{mvar|v}} पर इस शीर्ष के स्तर 0 ({{mvar|v}} स्वयं) पर एक शीर्ष होना चाहिए और कम से कम d शीर्ष स्तर 1 पर स्तर 2 (k > 1 के लिए), कम से कम {{math|''d''(''d'' − 1)}} शीर्ष होने चाहिए, क्योंकि स्तर 1 पर प्रत्येक शीर्ष में कम से कम {{math|''d'' − 1}} शेष आसन्नताएं होती हैं और कोई दो शीर्ष नहीं होते हैं। स्तर 1 एक दूसरे के निकट हो सकता है या स्तर 2 पर एक साझा शीर्ष पर हो सकता है क्योंकि यह अनुमानित परिधि से छोटा वृत्त बना देता है व्यापक रूप से समान तर्क दर्शाता है कि किसी भी स्तर {{math|1 ≤ ''i'' ≤ ''k''}} पर कम से कम {{math|''d''(''d'' − 1){{sup|''i''}}}} शीर्ष होने चाहिए। इस प्रकार, शीर्षों की कुल संख्या कम से कम होनी चाहिए:
-इसकी अधिकतम डिग्री और इसके व्यास के संदर्भ में एक आरेख में शीर्षों की संख्या की ऊपरी सीमा के बजाय, हम समान विधियों के माध्यम से इसकी न्यूनतम डिग्री और इसके परिधि के संदर्भ में शीर्षों की संख्या पर एक निचली सीमा की गणना कर सकते हैं।{{sfnp|Erdős|Rényi|Sós|1966}} मान लें कि {{mvar|G}} की न्यूनतम डिग्री {{mvar|d}} और घेरा {{math|2''k'' + 1}} है। मनमाने ढंग से एक प्रारंभिक शीर्ष {{mvar|v}} चुनें, और पहले की तरह चौड़ाई-प्रथम खोज ट्री को {{mvar|v}} पर रूट करें। इस पेड़ के स्तर 0 ({{mvar|v}} स्वयं) पर एक शीर्ष होना चाहिए, और कम से कम d शीर्ष स्तर 1 पर। स्तर 2 पर (k > 1 के लिए), कम से कम {{math|''d''(''d'' − 1)}} कोने होने चाहिए, क्योंकि स्तर 1 पर प्रत्येक शीर्ष में कम से कम {{math|''d'' − 1}} शेष आसन्नताएं हैं और कोई दो कोने नहीं हैं। स्तर 1 एक दूसरे के निकट हो सकता है या स्तर 2 पर एक साझा शीर्ष पर हो सकता है क्योंकि यह अनुमानित परिधि से छोटा चक्र बना देगा। व्यापक रूप से, समान तर्क दर्शाता है कि किसी भी स्तर {{math|1 ≤ ''i'' ≤ ''k''}} पर कम से कम {{math|''d''(''d'' − 1){{sup|''i''}}}} शीर्ष होने चाहिए। इस प्रकार, शीर्षों की कुल संख्या कम से कम होनी चाहिए
 :<math>1+d\sum_{i=1}^{k-1}(d-1)^i.</math>
-मूर आरेख़ में, शीर्षों की संख्या पर बंधी यह सीमा पूरी तरह से मिलती है। प्रत्येक मूर आरेख़ की परिधि बिल्कुल {{math|2''k'' + 1}} है: इसमें उच्च घेरा रखने के लिए पर्याप्त वर्टिकल नहीं हैं, और एक छोटा चक्र किसी चौड़ाई वाले पहले खोज ट्री के पहले {{mvar|k}} स्तरों में बहुत कम वर्टिकल होने का कारण होगा। इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री डी और परिधि {{math|2''k'' + 1}} के साथ सभी आरेखों में न्यूनतम संख्या संभव है: यह एक पिंजरा है।
+मूर आरेख़ में, शीर्षों की संख्या पर निर्धारित यह सीमा पूरी तरह से प्राप्त होती है। प्रत्येक मूर आरेख़ की परिधि ठीक {{math|2''k'' + 1}} होती है इसमें उच्च परिधि रखने के लिए पर्याप्त शीर्ष नहीं हैं और एक छोटा वृत्त किसी चौड़ाई वाले पहले खोज वृत्त के पहले {{mvar|k}} स्तरों में बहुत कम शीर्ष होने का कारण था इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री {{mvar|d}} और परिधि {{math|2''k'' + 1}} के साथ सभी आरेखों में न्यूनतम संख्या संभव है क्योकि यह एक केज आरेख है।
-यहां तक कि {{math|2''k''}} परिधि के लिए, एक किनारे के मध्य बिंदु से प्रारम्भ होने वाली एक चौड़ाई-पहली खोज वृक्ष बना सकते हैं। न्यूनतम डिग्री डी के साथ इस परिधि के आरेख में न्यूनतम संख्या में वर्टिकल पर परिणामी सीमा {{mvar|d}} है
+यहां तक कि {{math|2''k''}} परिधि के लिए, एक शीर्ष के मध्य बिंदु से प्रारम्भ होने वाली एक चौड़ाई पहली खोज का वृत्त बना सकती हैं। न्यूनतम डिग्री {{mvar|d}} के साथ इस परिधि के आरेख में न्यूनतम संख्या में शीर्ष पर परिणामी सीमा है:
 :<math>2\sum_{i=0}^{k-1}(d-1)^i=1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^i.</math>
-(सूत्र के दाहिने हाथ की ओर इसके बजाय एक शीर्ष से प्रारम्भ होने वाले चौड़ाई वाले पहले खोज वृक्ष में शीर्षों की संख्या की गणना करता है, इस संभावना के लिए लेखांकन कि वृक्ष के अंतिम स्तर में एक शीर्ष पिछले स्तर में {{mvar|d}} शीर्षों के निकट हो सकता है ।) इस प्रकार, मूर आरेख़ को कभी-कभी उन आरेख़ को सम्मिलित करने के रूप में परिभाषित किया जाता है जो वास्तव में इस सीमा को पूरा करते हैं। दोबारा, ऐसा कोई भी आरेख पिंजरा होना चाहिए।
+सूत्र के दाहिने हाथ की ओर इसके अतिरिक्त एक शीर्ष से प्रारम्भ होने वाली चौड़ाई वाले पहले खोज वृत्त में शीर्षों की संख्या की गणना करता है इस संभावना के लिए लेखांकन कि वृत्त के अंतिम स्तर में एक शीर्ष पिछले स्तर में {{mvar|d}} शीर्षों के निकटम हो सकता है। इस प्रकार, मूर आरेख़ को कभी-कभी उन आरेख़ मे सम्मिलित करने के रूप में परिभाषित किया जाता है जो वास्तव में इस सीमा को पूर्ण करते हैं। जिससे ऐसा कोई भी आरेख केज आरेख होता है।
 == उदाहरण ==
-हॉफमैन-सिंगलटन प्रमेय में कहा गया है कि परिधि 5 के साथ किसी भी मूर आरेख की डिग्री 2, 3, 7 या 57 होनी चाहिए। मूर आरेख हैं:{{sfnp|Bollobás|1998|loc=Theorem 19, p. 276}}
+हॉफमैन-सिंगलटन प्रमेय में कहा गया है कि परिधि 5 के साथ किसी भी मूर आरेख की डिग्री 2, 3, 7 या 57 होना एक मूर आरेख हैं:{{sfnp|Bollobás|1998|loc=Theorem 19, p. 276}}
 * {{math|''n'' > 2}} नोड्स पर पूर्ण रेखांकन {{mvar|K{{sub|n}}}} (व्यास 1, परिधि 3, डिग्री {{math|''n'' − 1}}, क्रम {{mvar|n}})
-* विषम चक्र आरेख {{math|''C''{{sub|2''n''+1}}}} (व्यास {{mvar|n}}, घेरा {{math|2''n'' + 1}}, डिग्री 2, क्रम {{math|2''n'' + 1}})
+* विषम वृत्त आरेख {{math|''C''{{sub|2''n''+1}}}} (व्यास {{mvar|n}}, परिधि {{math|2''n'' + 1}}, डिग्री 2, क्रम {{math|2''n'' + 1}})
-* पीटरसन आरेख (व्यास 2, घेरा 5, डिग्री 3, क्रम 10)
+* पीटरसन आरेख (व्यास 2, परिधि 5, डिग्री 3, क्रम 10)
-* हॉफमैन-सिंगलटन आरेख (व्यास 2, घेरा 5, डिग्री 7, क्रम 50)
+* हॉफमैन-सिंगलटन आरेख (व्यास 2, परिधि 5, डिग्री 7, क्रम 50)
-* व्यास 2, परिधि 5, डिग्री 57 और क्रम 3250 का एक काल्पनिक आरेख, जिसका अस्तित्व अज्ञात है{{sfnp|Dalfó|2019}}
+* व्यास 2, परिधि 5, डिग्री 57 और क्रम 3250 का एक काल्पनिक आरेख है जिसका अस्तित्व अज्ञात है।{{sfnp|Dalfó|2019}}
-हालांकि सभी ज्ञात मूर आरेख़ [[शीर्ष-सकर्मक ग्राफ|शीर्ष-सकर्मक आरेख]] हैं, अज्ञात एक (यदि यह मौजूद है) वर्टेक्स-ट्रांसिटिव नहीं हो सकता है, क्योंकि इसके ऑटोमोर्फिज़्म समूह में अधिकतम 375 पर ऑर्डर हो सकता है, जो इसके शीर्षों की संख्या से कम है।{{sfnp|Mačaj|Širáň|2010}}
+हालांकि सभी ज्ञात मूर आरेख़ [[शीर्ष-सकर्मक ग्राफ|शीर्ष-सकर्मक आरेख]] हैं यदि यह काल्पनिक आरेख सम्मिलित है तो शीर्ष-सकर्मक रेखांकन नहीं हो सकता है क्योंकि इसके स्वसमाकृतिकता समूह में अधिकतम अनुक्रम 375 पर हो सकता है जो इसके शीर्षों की संख्या से कम है।{{sfnp|Mačaj|Širáň|2010}}
-यदि मूर आरेख़ की सामान्यीकृत परिभाषा जो परिधि आरेख़ की अनुमति देती है, का उपयोग किया जाता है, तो सम परिधि मूर आरेख़ [[सामान्यीकृत बहुभुज]] (संभावित पतित) के घटना आरेख़ के अनुरूप होते हैं। कुछ उदाहरण सम चक्र {{math|''C''{{sub|2''n''}}}} हैं, पूर्ण द्विदलीय रेखांकन {{math|''K''{{sub|''n'',''n''}}}} परिधि चार के साथ, [[ हीवुड ग्राफ |हीवुड आरेख]] डिग्री 3 और परिधि 6 के साथ, और Tutte-Coxeter आरेख डिग्री 3 और परिधि 8 के साथ। अधिक सामान्यतः, यह ज्ञात है कि, ऊपर सूचीबद्ध आरेख़ के अलावा, सभी मूर आरेख़ की परिधि 5, 6, 8, या 12 होनी चाहिए।<ref>{{harvtxt|Bannai|Ito|1973}}; {{harvtxt|Damerell|1973}}</ref> एक सामान्यीकृत {{mvar|n}}-गॉन के लिए {{mvar|n}} के संभावित मानों के बारे में फीट-हिगमैन प्रमेय से सम परिधि का मामला भी अनुसरण करता है।
+यदि मूर आरेख़ की सामान्यीकृत परिभाषा जो परिधि आरेख़ की स्वीकृति देती है इसका उपयोग किया जाता है तो सम परिधि मूर आरेख़ [[सामान्यीकृत बहुभुज]] (संभावित पतित) के घटना आरेख़ के अनुरूप होता हैं। कुछ उदाहरण मे {{math|''C''{{sub|2''n''}}}} सम वृत्त हैं, पूर्ण द्विभाज्य रेखांकन {{math|''K''{{sub|''n'',''n''}}}} परिधि 4 के साथ [[ हीवुड ग्राफ |हीवुड आरेख]] डिग्री 3 और परिधि 6 के साथ टुट्टे-कॉक्सेटर आरेख डिग्री 3 और परिधि 8 के साथ अधिक सामान्यतः यह ज्ञात है कि ऊपर सूचीबद्ध आरेख़ के अतिरिक्त सभी मूर आरेख़ की परिधि 5, 6, 8, या 12 होती है।<ref>{{harvtxt|Bannai|Ito|1973}}; {{harvtxt|Damerell|1973}}</ref> एक सामान्यीकृत {{mvar|n}}-गॉन के लिए {{mvar|n}} के संभावित मानों के विषय में प्रयुक्त हिगमैन प्रमेय से सम परिधि की स्थिति का अनुसरण करता है।
 == यह भी देखें ==

Anonymous

Search

मूर ग्राफ: Difference between revisions

Namespaces

More

Page actions

Revision as of 08:51, 11 May 2023

Contents

डिग्री और व्यास द्वारा शीर्ष सीमांकन

केज आरेख के रूप में मूर रेखांकन

उदाहरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मूर ग्राफ: Difference between revisions

Revision as of 08:51, 11 May 2023

डिग्री और व्यास द्वारा शीर्ष सीमांकन

केज आरेख के रूप में मूर रेखांकन

उदाहरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories