ग्रेसफुल लेबलिंग: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Type of graph vertex labeling}} | {{short description|Type of graph vertex labeling}} | ||
[[Image:Graceful labeling.svg|thumb|एक | [[Image:Graceful labeling.svg|thumb|एक ग्रेसफुल लेबलिंग। वर्टेक्स (ग्राफ़ थ्योरी) लेबल काले रंग में हैं, किनारे वाले लेबल लाल रंग में हैं।|176x176px]][[ग्राफ सिद्धांत]] में [[ग्राफ (असतत गणित)|ग्राफ असतत गणित]] का आकर्षक सिद्धांत है जो वर्टेक्स पर आधारित ग्राफ लेबलिंग है जिसमें 0 से लेकर [[पूर्णांक]] के सबसेट स्थित हैंI ग्राफ के अनुसार कोई भी दो कोने एक समान स्तर साझा नहीं करते हैंI जैसे m के प्रत्येक प्रत्येक किनारे को उसके समापन बिंदुओं के बीच [[पूर्ण अंतर]] से विशिष्ट रूप से पहचाना जा सकता है जैसे कि यह परिमाण 1 और 0 के बीच होता हैI <ref name="Vas2001">[[Virginia Vassilevska Williams|Virginia Vassilevska]], "Coding and Graceful Labeling of trees." SURF 2001. [https://www.cs.cmu.edu/~virgi/final1.ps PostScript]</ref> जो ग्राफ़ ग्रेसफुल लेबलिंग को स्वीकार करता है ग्रेसफुल ग्राफ़ कहलाता है। | ||
ग्रेसफुल लेबलिंग का नाम सोलोमन डब्ल्यू गोलोम्ब के नाम पर पड़ा हैI इस प्रकार की लेबलिंग को मूल रूप से अलेक्जेंडर रोजा द्वारा 1967 में ग्राफ लेबलिंग पर β-लेबलिंग नाम दिया गया था।<ref name="Ros1967">{{citation | ग्रेसफुल लेबलिंग का नाम सोलोमन डब्ल्यू गोलोम्ब के नाम पर पड़ा हैI इस प्रकार की लेबलिंग को मूल रूप से अलेक्जेंडर रोजा द्वारा 1967 में ग्राफ लेबलिंग पर β-लेबलिंग नाम दिया गया था।<ref name="Ros1967">{{citation | ||
| Line 14: | Line 14: | ||
ग्रेसफुल लेबलिंग का संस्करण नियर-ग्रेसफुल लेबलिंग है जिसमें पूर्णांकों के कुछ सबसेट का उपयोग करके ग्राफ के कोनों को लेबल किया जा सकता हैI जैसे {{math|[0, ''m'' + 1]}} कोई भी दो कोने समान लेबल को साझा नहीं करते हैं और प्रत्येक किनारे को इसके समापन बिंदुओं के बीच पूर्ण अंतर से विशिष्ट रूप से पहचाना जाता हैI इस ग्राफ का परिमाण {{math|[1, ''m'' + 1]}}) में निहित हैI | ग्रेसफुल लेबलिंग का संस्करण नियर-ग्रेसफुल लेबलिंग है जिसमें पूर्णांकों के कुछ सबसेट का उपयोग करके ग्राफ के कोनों को लेबल किया जा सकता हैI जैसे {{math|[0, ''m'' + 1]}} कोई भी दो कोने समान लेबल को साझा नहीं करते हैं और प्रत्येक किनारे को इसके समापन बिंदुओं के बीच पूर्ण अंतर से विशिष्ट रूप से पहचाना जाता हैI इस ग्राफ का परिमाण {{math|[1, ''m'' + 1]}}) में निहित हैI | ||
ग्राफ सिद्धांत में एक और अनुमान है "रोजा अनुमान" जिसका नाम "अलेक्जेंडर रोजा" के नाम पर रखा गया है जो कहता है कि सभी कैक्टस ग्राफ # त्रिकोणीय कैक्टस | ग्राफ सिद्धांत में एक और अनुमान है "रोजा अनुमान" जिसका नाम "अलेक्जेंडर रोजा" के नाम पर रखा गया है जो कहता है कि सभी कैक्टस ग्राफ # त्रिकोणीय कैक्टस ग्रेसफुल या लगभग-ग्रेसफुल हैं।<ref name="Rosa1988">{{citation|last=Rosa|first=A.|title=Cyclic Steiner Triple Systems and Labelings of Triangular Cacti|journal=Scientia|volume=1|pages=87–95|year=1988}}.</ref> शिखर से संबंधित [[विरल शासक|विरल]] परिणामों के कारण 0 से किनारों के साथ ग्राफ {{mvar|m}} से कम नहीं होने का अनुमान है <math> \left\lceil \sqrt{3 m+\tfrac{9}{4}} \right\rfloor </math>। यह अनुमान 213 या उससे कम किनारों वाले सभी ग्राफ़ के लिए सत्यापित किया गया है। | ||
[[File:Toroidal6.png|thumb|27 किनारों और 9 शीर्षों वाला एक | [[File:Toroidal6.png|thumb|27 किनारों और 9 शीर्षों वाला एक ग्रेसफुल ग्राफ़|202x202px]] | ||
== चयनित परिणाम == | == चयनित परिणाम == | ||
* अपने मूल पेपर में, रोजा ने साबित किया कि किनारों की संख्या m ≡ 1 (mod 4) या m ≡ 2 (mod 4) के साथ एक Eulerian ग्राफ | * अपने मूल पेपर में, रोजा ने साबित किया कि किनारों की संख्या m ≡ 1 (mod 4) या m ≡ 2 (mod 4) के साथ एक Eulerian ग्राफ ग्रेसफुल नहीं हो सकता।<ref name="Ros1967"/> | ||
*साथ ही अपने मूल पत्र में, रोजा ने सिद्ध किया कि चक्र ''' | *साथ ही अपने मूल पत्र में, रोजा ने सिद्ध किया कि चक्र '''''C<sub>n</sub>''''' ग्रेसफुल है अगर और केवल अगर n ≡ 0 (mod 4) या n ≡ 3 (mod 4)। | ||
* सभी पथ रेखांकन और कैटरपिलर रेखांकन | * सभी पथ रेखांकन और कैटरपिलर रेखांकन ग्रेसफुल हैं। | ||
*बिल्कुल मिलान वाले सभी [[लॉबस्टर ग्राफ]] आकर्षक रूप से प्रदर्शित होता है I<ref name="Morgan">{{citation | *बिल्कुल मिलान वाले सभी [[लॉबस्टर ग्राफ]] आकर्षक रूप से प्रदर्शित होता है I<ref name="Morgan">{{citation | ||
| last = Morgan | first = David | | last = Morgan | first = David | ||
| Line 49: | Line 49: | ||
| title = Graceful Trees: Statistics and Algorithms | | title = Graceful Trees: Statistics and Algorithms | ||
| url = http://eprints.utas.edu.au/19/ | | url = http://eprints.utas.edu.au/19/ | ||
| year = 2003}}.</ref> 2010 में वेंजी फैंग के नेतृत्व में एक वितरित कंप्यूटिंग परियोजना ग्रेसफुल ट्री वेरिफिकेशन प्रोजेक्ट द्वारा 35 वर्टीकल वाले | | year = 2003}}.</ref> 2010 में वेंजी फैंग के नेतृत्व में एक वितरित कंप्यूटिंग परियोजना ग्रेसफुल ट्री वेरिफिकेशन प्रोजेक्ट द्वारा 35 वर्टीकल वाले ट्री तक इस परिणाम के एक और विस्तार का दावा किया गया था।<ref>{{citation | ||
| last = Fang | first = Wenjie | | last = Fang | first = Wenjie | ||
| arxiv = 1003.3045| title = A Computational Approach to the Graceful Tree Conjecture | | arxiv = 1003.3045| title = A Computational Approach to the Graceful Tree Conjecture | ||
| year = 2010| bibcode = 2010arXiv1003.3045F}}. See also [https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html Graceful Tree Verification Project]</ref> | | year = 2010| bibcode = 2010arXiv1003.3045F}}. See also [https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html Graceful Tree Verification Project]</ref> | ||
*सभी | *सभी n-डायमेंशनल ग्रेसफुल हैं। | ||
*चार या उससे कम शीर्षों वाले सभी साधारण ग्राफ़ | *चार या उससे कम शीर्षों वाले सभी साधारण ग्राफ़ ग्रेसफुल हैं। पांच कोने वाले गैर-सुशोभित [[सरल ग्राफ]] 5-[[चक्र ग्राफ]] [[पंचकोण]] हैंI | ||
== यह भी देखें == | == यह भी देखें == | ||
*[[एज-ग्रेसफुल लेबलिंग]] | *[[एज-ग्रेसफुल लेबलिंग]] | ||
| Line 61: | Line 61: | ||
==संदर्भ== | ==संदर्भ== | ||
<references/> | <references/> | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
* [https://www.youtube.com/watch?v=v5KWzOOhZrw Numberphile video about graceful tree conjecture] | * [https://www.youtube.com/watch?v=v5KWzOOhZrw Numberphile video about graceful tree conjecture] | ||
==अग्रिम पठन== | ==अग्रिम पठन== | ||
* (K. Eshghi) [http://sharif.edu/~eshghi/Graceful%20Graphs-Final%20Edition-89-12-15.pdf Introduction to Graceful Graphs], Sharif University of Technology, 2002. | * (K. Eshghi) [http://sharif.edu/~eshghi/Graceful%20Graphs-Final%20Edition-89-12-15.pdf Introduction to Graceful Graphs], Sharif University of Technology, 2002. | ||
| Line 73: | Line 69: | ||
* (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015. | * (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015. | ||
* ([[Ping Zhang (graph theorist)|Ping Zhang]]), A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 – Springer | * ([[Ping Zhang (graph theorist)|Ping Zhang]]), A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 – Springer | ||
[[Category: | [[Category:CS1 English-language sources (en)]] | ||
[[Category:Created On 18/04/2023]] | [[Category:Created On 18/04/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:अनुमान]] | |||
[[Category:ग्राफ सिद्धांत वस्तुओं]] | |||
Latest revision as of 17:18, 1 May 2023
ग्राफ सिद्धांत में ग्राफ असतत गणित का आकर्षक सिद्धांत है जो वर्टेक्स पर आधारित ग्राफ लेबलिंग है जिसमें 0 से लेकर पूर्णांक के सबसेट स्थित हैंI ग्राफ के अनुसार कोई भी दो कोने एक समान स्तर साझा नहीं करते हैंI जैसे m के प्रत्येक प्रत्येक किनारे को उसके समापन बिंदुओं के बीच पूर्ण अंतर से विशिष्ट रूप से पहचाना जा सकता है जैसे कि यह परिमाण 1 और 0 के बीच होता हैI [1] जो ग्राफ़ ग्रेसफुल लेबलिंग को स्वीकार करता है ग्रेसफुल ग्राफ़ कहलाता है।
ग्रेसफुल लेबलिंग का नाम सोलोमन डब्ल्यू गोलोम्ब के नाम पर पड़ा हैI इस प्रकार की लेबलिंग को मूल रूप से अलेक्जेंडर रोजा द्वारा 1967 में ग्राफ लेबलिंग पर β-लेबलिंग नाम दिया गया था।[2]हालाँकि ग्राफ़ थ्योरी में प्रमुख अनुमान या रिंगेल-कोटज़िग अनुमान का नाम गेरहार्ड रिंगेल और एंटोन कोटज़िग के नाम पर रखा गया हैI यह अनुमान स्पष्ट रूप हैI रिंगेल के अनुमान के रूप में जाना जाने वाला संबंधित अनुमान 2020 में आंशिक रूप से सिद्ध किया गया था।[3][4][5]
ग्रेसफुल लेबलिंग का संस्करण नियर-ग्रेसफुल लेबलिंग है जिसमें पूर्णांकों के कुछ सबसेट का उपयोग करके ग्राफ के कोनों को लेबल किया जा सकता हैI जैसे [0, m + 1] कोई भी दो कोने समान लेबल को साझा नहीं करते हैं और प्रत्येक किनारे को इसके समापन बिंदुओं के बीच पूर्ण अंतर से विशिष्ट रूप से पहचाना जाता हैI इस ग्राफ का परिमाण [1, m + 1]) में निहित हैI
ग्राफ सिद्धांत में एक और अनुमान है "रोजा अनुमान" जिसका नाम "अलेक्जेंडर रोजा" के नाम पर रखा गया है जो कहता है कि सभी कैक्टस ग्राफ # त्रिकोणीय कैक्टस ग्रेसफुल या लगभग-ग्रेसफुल हैं।[6] शिखर से संबंधित विरल परिणामों के कारण 0 से किनारों के साथ ग्राफ m से कम नहीं होने का अनुमान है । यह अनुमान 213 या उससे कम किनारों वाले सभी ग्राफ़ के लिए सत्यापित किया गया है।
चयनित परिणाम
- अपने मूल पेपर में, रोजा ने साबित किया कि किनारों की संख्या m ≡ 1 (mod 4) या m ≡ 2 (mod 4) के साथ एक Eulerian ग्राफ ग्रेसफुल नहीं हो सकता।[2]
- साथ ही अपने मूल पत्र में, रोजा ने सिद्ध किया कि चक्र Cn ग्रेसफुल है अगर और केवल अगर n ≡ 0 (mod 4) या n ≡ 3 (mod 4)।
- सभी पथ रेखांकन और कैटरपिलर रेखांकन ग्रेसफुल हैं।
- बिल्कुल मिलान वाले सभी लॉबस्टर ग्राफ आकर्षक रूप से प्रदर्शित होता है I[7]
- अधिकतम 27 शीर्षों वाले सभी शीर्ष ग्राफ आकर्षक हैंI यह परिणाम एल्ड्रेड और ब्रेंडन मैके द्वारा 1998 में कंप्यूटर प्रोग्राम का उपयोग करके दिखाया गया था।[8][9] इसे माइकल हॉर्टन के ऑनर्स थीसिस में अधिकतम 29 शीर्ष तक विस्तारित किया गया था।[10] 2010 में वेंजी फैंग के नेतृत्व में एक वितरित कंप्यूटिंग परियोजना ग्रेसफुल ट्री वेरिफिकेशन प्रोजेक्ट द्वारा 35 वर्टीकल वाले ट्री तक इस परिणाम के एक और विस्तार का दावा किया गया था।[11]
- सभी n-डायमेंशनल ग्रेसफुल हैं।
- चार या उससे कम शीर्षों वाले सभी साधारण ग्राफ़ ग्रेसफुल हैं। पांच कोने वाले गैर-सुशोभित सरल ग्राफ 5-चक्र ग्राफ पंचकोण हैंI
यह भी देखें
संदर्भ
- ↑ Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript
- ↑ 2.0 2.1 Rosa, A. (1967), "On certain valuations of the vertices of a graph", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 349–355, MR 0223271.
- ↑ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "रिंगेल के अनुमान का प्रमाण" (in English). arXiv:2001.02665 [math.CO].
- ↑ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
- ↑ Hartnett, Kevin. "रेनबो प्रूफ से पता चलता है कि ग्राफ़ में एकसमान भाग होते हैं". Quanta Magazine (in English). Retrieved 2020-02-29.
- ↑ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", Scientia, 1: 87–95.
- ↑ Morgan, David (2008), "All lobsters with perfect matchings are graceful", Bulletin of the Institute of Combinatorics and Its Applications, 53: 82–85, hdl:10402/era.26923.
- ↑ Gallian, Joseph A. (1998), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics, 5: Dynamic Survey 6, 43 pp. (389 pp. in 18th ed.) (electronic), MR 1668059.
- ↑ Aldred, R. E. L.; McKay, Brendan D. (1998), "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications, 23: 69–72, MR 1621760.
- ↑ Horton, Michael P. (2003), Graceful Trees: Statistics and Algorithms.
- ↑ Fang, Wenjie (2010), A Computational Approach to the Graceful Tree Conjecture, arXiv:1003.3045, Bibcode:2010arXiv1003.3045F. See also Graceful Tree Verification Project
बाहरी संबंध
अग्रिम पठन
- (K. Eshghi) Introduction to Graceful Graphs, Sharif University of Technology, 2002.
- (U. N. Deshmukh and Vasanti N. Bhat-Nayak), New families of graceful banana trees – Proceedings Mathematical Sciences, 1996 – Springer
- (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
- (Ping Zhang), A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 – Springer
