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

Revision as of 21:27, 10 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] मूर आरेख़ में वर्टिकल की संख्या के लिए सूत्र को सामान्यीकृत किया जा सकता है ताकि मूर आरेख़ की परिभाषा के साथ-साथ विषम परिधि भी हो, और फिर से ये आरेख़ पिंजरे हैं।

डिग्री और व्यास द्वारा वर्टिकल बाउंडिंग

मूर आरेख के रूप में पीटरसन आरेख। कोई भी चौड़ाई पहले खोज वृक्ष में होती है

d (d - 1) i

इसके कोने

i

वां स्तर।

$G$ को अधिकतम डिग्री d और व्यास k के साथ कोई भी आरेख होने दें, और किसी भी शीर्ष v से प्रारम्भ होने वाली चौड़ाई से पहले खोज द्वारा बनाए गए पेड़ पर विचार करें। इस पेड़ के स्तर 0 ( $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$ स्तरों में बहुत कम वर्टिकल होने का कारण होगा। इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री डी और परिधि $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$ परिधि चार के साथ, हीवुड आरेख डिग्री 3 और परिधि 6 के साथ, और Tutte-Coxeter आरेख डिग्री 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 1: / Line 1: @@
 {{short description|Regular graph with girth more than twice its diameter}}
-{{unsolved|mathematics|Does a Moore graph with girth 5 and degree 57 exist?}}
+{{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|Hoffman|Singleton|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}} अधिकतम डिग्री वाला कोई भी ग्राफ हो {{mvar|d}} और व्यास {{mvar|k}}, और चौड़ाई से बने पेड़ पर विचार करें, किसी भी शीर्ष से शुरू करते हुए पहली खोज करें {{mvar|v}}. इस पेड़ का 1 शीर्ष स्तर 0 पर है ({{mvar|v}} स्वयं), और अधिक से अधिक {{mvar|d}} स्तर 1 पर शिखर (के पड़ोसी {{mvar|v}}). अगले स्तर में, अधिकतम हैं {{math|''d''(''d'' − 1)}} कोने: के प्रत्येक पड़ोसी {{mvar|v}} कनेक्ट करने के लिए इसके किसी एक समीपस्थ भाग का उपयोग करता है {{mvar|v}} और अधिक से अधिक हो सकता है {{math|''d'' − 1}} पड़ोसी स्तर 2 पर। सामान्य तौर पर, एक समान तर्क किसी भी स्तर पर दिखाता है {{math|1 ≤ ''i'' ≤ ''k''}}, अधिक से अधिक हो सकता है {{math|''d''(''d'' − 1){{sup|''i''−1}}}} शिखर। इस प्रकार, शीर्षों की कुल संख्या अधिक से अधिक हो सकती है
+[[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}}}} शीर्ष हो सकते हैं। इस प्रकार, शीर्षों की कुल संख्या अधिक से अधिक हो सकती है
 :<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>
-{{harvtxt|Hoffman|Singleton|1960}} मूल रूप से एक मूर ग्राफ़ को एक ग्राफ़ के रूप में परिभाषित किया गया था, जिसके लिए वर्टिकल की संख्या पर यह सीमा पूरी तरह से मिलती है। इसलिए, किसी भी मूर ग्राफ़ में अधिकतम डिग्री वाले सभी ग्राफ़ों में अधिकतम वर्टिकल संभव हैं {{mvar|d}} और व्यास {{mvar|k}}.
+{{harvtxt|हॉफमैन|सिंगलटन|1960}} ने मूल रूप से एक मूर आरेख को एक आरेख के रूप में परिभाषित किया था जिसके लिए वर्टिकल की संख्या पर यह सीमा पूरी तरह से मिलती है। इसलिए, किसी भी मूर आरेख़ में अधिकतम डिग्री {{mvar|d}} और व्यास {{mvar|k}} वाले सभी आरेख़ों में अधिकतम संभव वर्टिकल होते हैं।
-बाद में, {{harvtxt|Singleton|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}} ही), और कम से कम {{mvar|d}} शीर्ष स्तर 1 पर। स्तर 2 पर (के लिए {{math|''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}} है: इसमें उच्च घेरा रखने के लिए पर्याप्त वर्टिकल नहीं हैं, और एक छोटा चक्र किसी चौड़ाई वाले पहले खोज ट्री के पहले {{mvar|k}} स्तरों में बहुत कम वर्टिकल होने का कारण होगा। इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री डी और परिधि {{math|2''k'' + 1}} के साथ सभी आरेखों में न्यूनतम संख्या संभव है: यह एक पिंजरा है।
-इसलिए, किसी भी मूर ग्राफ़ में न्यूनतम डिग्री वाले सभी ग्राफ़ों के बीच न्यूनतम संख्या संभव है {{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}}
-* पूरा रेखांकन {{mvar|K{{sub|n}}}} पर {{math|''n'' > 2}} नोड्स (व्यास 1, परिधि 3, डिग्री {{math|''n'' − 1}}, आदेश {{mvar|n}})
+* {{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 के साथ, और टट्टे-कॉक्सेटर ग्राफ डिग्री 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''}}}} परिधि चार के साथ, [[ हीवुड ग्राफ |हीवुड आरेख]] डिग्री 3 और परिधि 6 के साथ, और Tutte-Coxeter आरेख डिग्री 3 और परिधि 8 के साथ। अधिक सामान्यतः, यह ज्ञात है कि, ऊपर सूचीबद्ध आरेख़ के अलावा, सभी मूर आरेख़ की परिधि 5, 6, 8, या 12 होनी चाहिए।<ref>{{harvtxt|Bannai|Ito|1973}}; {{harvtxt|Damerell|1973}}</ref> एक सामान्यीकृत {{mvar|n}}-गॉन के लिए {{mvar|n}} के संभावित मानों के बारे में फीट-हिगमैन प्रमेय से सम परिधि का मामला भी अनुसरण करता है।
 == यह भी देखें ==
@@ Line 51: / Line 49: @@
 ==टिप्पणियाँ==
 {{reflist}}
 == संदर्भ ==
 * {{citation

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:27, 10 May 2023

Contents

डिग्री और व्यास द्वारा वर्टिकल बाउंडिंग

पिंजरों के रूप में मूर रेखांकन

उदाहरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 21:27, 10 May 2023

डिग्री और व्यास द्वारा वर्टिकल बाउंडिंग

पिंजरों के रूप में मूर रेखांकन

उदाहरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories