हैमिंग ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 37: | Line 37: | ||
| year = 2000}}.</ref> हैमिंग रेखांकन के विपरीत {{math|''H''(''d'',''q'')}}, इस अधिक सामान्य वर्ग के ग्राफ़ आवश्यक रूप से दूरी-[[नियमित ग्राफ|नियमित ग्राफ़]] नहीं हैं | दूरी-नियमित हैं, किन्तु वे नियमित ग्राफ़ और [[शीर्ष-सकर्मक ग्राफ]] बने रहते हैं। | | year = 2000}}.</ref> हैमिंग रेखांकन के विपरीत {{math|''H''(''d'',''q'')}}, इस अधिक सामान्य वर्ग के ग्राफ़ आवश्यक रूप से दूरी-[[नियमित ग्राफ|नियमित ग्राफ़]] नहीं हैं | दूरी-नियमित हैं, किन्तु वे नियमित ग्राफ़ और [[शीर्ष-सकर्मक ग्राफ]] बने रहते हैं। | ||
== विशेष | == विशेष स्थितियाँ == | ||
*{{math|''H''(2,3)}}, जो सामान्यीकृत [[पूर्ण चतुर्भुज]] | *{{math|''H''(2,3)}}, जो सामान्यीकृत [[पूर्ण चतुर्भुज]] {{math|''G'' ''Q'' (2,1)}} है<ref>{{citation | ||
| last1 = Blokhuis | first1 = Aart | | last1 = Blokhuis | first1 = Aart | ||
| last2 = Brouwer | first2 = Andries E. | author2-link = Andries Brouwer | | last2 = Brouwer | first2 = Andries E. | author2-link = Andries Brouwer | ||
| Line 52: | Line 52: | ||
| year = 2007| doi-access = free | | year = 2007| doi-access = free | ||
}}. See in particular note (e) on p. 300.</ref> | }}. See in particular note (e) on p. 300.</ref> | ||
*{{math|''H''(1,''q'')}}, जो पूरा ग्राफ | *{{math|''H''(1,''q'')}}, जो पूरा ग्राफ {{mvar|K{{sub|q}}}} है<ref name="dc04">{{citation | ||
| last1 = Dekker | first1 = Anthony H. | | last1 = Dekker | first1 = Anthony H. | ||
| last2 = Colbert | first2 = Bernard D. | | last2 = Colbert | first2 = Bernard D. | ||
| Line 63: | Line 63: | ||
| url = http://dl.acm.org/citation.cfm?id=979922.979965 | | url = http://dl.acm.org/citation.cfm?id=979922.979965 | ||
| year = 2004}}.</ref> | | year = 2004}}.</ref> | ||
*{{math|''H''(2,''q'')}}, जो | *{{math|''H''(2,''q'')}}, जो लैटिस ग्राफ {{mvar|L{{sub|q,q}}}} है और रूक का ग्राफ भी है<ref>{{citation | ||
| last1 = Bailey | first1 = Robert F. | | last1 = Bailey | first1 = Robert F. | ||
| last2 = Cameron | first2 = Peter J. | | last2 = Cameron | first2 = Peter J. | ||
| Line 75: | Line 75: | ||
| year = 2011| s2cid = 6684542 | | year = 2011| s2cid = 6684542 | ||
}}.</ref> | }}.</ref> | ||
*{{math|''H''(''d'',1)}}, जो कि सिंगलटन ग्राफ | *{{math|''H''(''d'',1)}}, जो कि सिंगलटन ग्राफ {{math|''K''{{sub|1}}}} है | ||
*{{math|''H''(''d'',2)}}, जो [[हाइपरक्यूब ग्राफ]] | *{{math|''H''(''d'',2)}}, जो [[हाइपरक्यूब ग्राफ]] {{mvar|Q{{sub|d}}}} हैं।<ref name="bh12"/>इन रेखांकन में [[हैमिल्टनियन पथ]] [[ग्रे कोड]] बनाते हैं। | ||
*चूंकि रेखांकन का कार्तीय गुणनफल एक इकाई दूरी ग्राफ होने के गुण को संरक्षित रखता है,<ref>{{citation | *चूंकि रेखांकन का कार्तीय गुणनफल एक इकाई दूरी ग्राफ होने के गुण को संरक्षित रखता है,<ref>{{citation | ||
| last1 = Horvat | first1 = Boris | | last1 = Horvat | first1 = Boris | ||
| Line 118: | Line 118: | ||
== कम्प्यूटेशनल जटिलता == | == कम्प्यूटेशनल जटिलता == | ||
रेखीय समय में यह परीक्षण करना संभव है कि क्या एक ग्राफ एक हैमिंग ग्राफ है, और इस | रेखीय समय में यह परीक्षण करना संभव है कि क्या एक ग्राफ एक हैमिंग ग्राफ है, और इस स्थितियाँ में, इसे टपल्स के साथ लेबलिंग खोजें जो इसे एक हैमिंग ग्राफ के रूप में महसूस करता है।<ref name="ik00"/> | ||
Revision as of 20:57, 16 May 2023
| Hamming graph | |
|---|---|
| Named after | Richard Hamming |
| Vertices | qd |
| Edges | |
| Diameter | d |
| Spectrum | |
| Properties | d(q – 1)-regular Vertex-transitive Distance-regular[1] |
| Notation | H(d,q) |
| Table of graphs and parameters | |
हैमिंग ग्राफ़ रिचर्ड हैमिंग के नाम पर ग्राफ़ (असतत गणित) का एक विशेष वर्ग है और गणित (ग्राफ़ सिद्धांत) और कंप्यूटर विज्ञान की कई शाखाओं में उपयोग किया जाता है। मान लीजिए कि S, q अवयवों का समुच्चय (गणित) है और d एक धनात्मक पूर्णांक है। हैमिंग ग्राफ H(d,q) ने S के तत्वों के ऑर्डर किए गए d-टुपल्स के सेट या S से लंबाई d के अनुक्रमों को शीर्ष (ग्राफ़ सिद्धांत) सेट Sd किया है। दो कोने ग्राफ़ (असतत गणित) होते हैं यदि वे ठीक एक निर्देशांक में भिन्न होते हैं; अर्थात् यदि उनकी हैमिंग दूरी एक है। हैमिंग ग्राफ H(d,q), समान रूप से d पूर्ण ग्राफ Kq का कार्तीय गुणनफल है।[1]
कुछ स्थितियों में, हैमिंग ग्राफ़ को अधिक आम तौर पर पूर्ण ग्राफ़ के निर्देशांक उत्पाद के रूप में माना जा सकता है जो अलग-अलग आकार के हो सकते हैं।[2] हैमिंग रेखांकन के विपरीत H(d,q), इस अधिक सामान्य वर्ग के ग्राफ़ आवश्यक रूप से दूरी-नियमित ग्राफ़ नहीं हैं | दूरी-नियमित हैं, किन्तु वे नियमित ग्राफ़ और शीर्ष-सकर्मक ग्राफ बने रहते हैं।
विशेष स्थितियाँ
- H(2,3), जो सामान्यीकृत पूर्ण चतुर्भुज G Q (2,1) है[3]
- H(1,q), जो पूरा ग्राफ Kq है[4]
- H(2,q), जो लैटिस ग्राफ Lq,q है और रूक का ग्राफ भी है[5]
- H(d,1), जो कि सिंगलटन ग्राफ K1 है
- H(d,2), जो हाइपरक्यूब ग्राफ Qd हैं।[1]इन रेखांकन में हैमिल्टनियन पथ ग्रे कोड बनाते हैं।
- चूंकि रेखांकन का कार्तीय गुणनफल एक इकाई दूरी ग्राफ होने के गुण को संरक्षित रखता है,[6] हैमिंग रेखांकन H(d,2) और H(d,3) सभी इकाई दूरी के ग्राफ़ हैं।
अनुप्रयोग
त्रुटि-सुधार कोड के संबंध में हैमिंग ग्राफ दिलचस्प हैं[7] और एसोसिएशन योजनाएं,[8] दो क्षेत्रों के नाम के लिए। वितरित कंप्यूटिंग में उन्हें संचार नेटवर्क टोपोलॉजी के रूप में भी माना जाता है।[4]
कम्प्यूटेशनल जटिलता
रेखीय समय में यह परीक्षण करना संभव है कि क्या एक ग्राफ एक हैमिंग ग्राफ है, और इस स्थितियाँ में, इसे टपल्स के साथ लेबलिंग खोजें जो इसे एक हैमिंग ग्राफ के रूप में महसूस करता है।[2]
संदर्भ
- ↑ 1.0 1.1 1.2 Brouwer, Andries E.; Haemers, Willem H. (2012), "12.3.1 Hamming graphs" (PDF), Spectra of graphs, Universitext, New York: Springer, p. 178, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR 2882891, retrieved 2022-08-08.
- ↑ 2.0 2.1 Imrich, Wilfried; Klavžar, Sandi (2000), "Hamming graphs", Product graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, pp. 104–106, ISBN 978-0-471-37039-0, MR 1788124.
- ↑ Blokhuis, Aart; Brouwer, Andries E.; Haemers, Willem H. (2007), "On 3-chromatic distance-regular graphs", Designs, Codes and Cryptography, 44 (1–3): 293–305, doi:10.1007/s10623-007-9100-7, MR 2336413. See in particular note (e) on p. 300.
- ↑ 4.0 4.1 Dekker, Anthony H.; Colbert, Bernard D. (2004), "Network robustness and graph topology", Proceedings of the 27th Australasian conference on Computer science - Volume 26, ACSC '04, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 359–368.
- ↑ Bailey, Robert F.; Cameron, Peter J. (2011), "Base size, metric dimension and other invariants of groups and graphs", Bulletin of the London Mathematical Society, 43 (2): 209–242, doi:10.1112/blms/bdq096, MR 2781204, S2CID 6684542.
- ↑ Horvat, Boris; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics, 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035, MR 2610282
- ↑ Sloane, N. J. A. (1989), "Unsolved problems in graph theory arising from the study of codes" (PDF), Graph Theory Notes of New York, 18: 11–20.
- ↑ Koolen, Jacobus H.; Lee, Woo Sun; Martin, W (2010), "Characterizing completely regular codes from an algebraic viewpoint", Combinatorics and graphs, Contemp. Math., vol. 531, Providence, RI: Amer., pp. 223–242, arXiv:0911.1828, doi:10.1090/conm/531/10470, ISBN 9780821848654, MR 2757802, S2CID 8197351. On p. 224, the authors write that "a careful study of completely regular codes in Hamming graphs is central to the study of association schemes".
