हैमिंग ग्राफ: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Cartesian product of complete graphs}} {{Infobox graph | name = Hamming graph | namesake = Richard Hamming | vertices = {{mvar|q{{sup|d}}}} | edges...") |
No edit summary |
||
| Line 10: | Line 10: | ||
| notation = {{math|''H''(''d'',''q'')}} | | notation = {{math|''H''(''d'',''q'')}} | ||
}} | }} | ||
[[File:Hamming 3-3 unit distance.svg|thumb|{{math|''H''(3,3)}} एक [[इकाई दूरी ग्राफ]] के रूप में तैयार किया गया]]हैमिंग ग्राफ़ [[रिचर्ड हैमिंग]] के नाम पर ग्राफ़ (असतत गणित) का एक विशेष वर्ग है और गणित (ग्राफ़ सिद्धांत) और [[कंप्यूटर विज्ञान]] की कई शाखाओं में उपयोग किया जाता है। | [[File:Hamming 3-3 unit distance.svg|thumb|{{math|''H''(3,3)}} एक [[इकाई दूरी ग्राफ]] के रूप में तैयार किया गया]]हैमिंग ग्राफ़ [[रिचर्ड हैमिंग]] के नाम पर ग्राफ़ (असतत गणित) का एक विशेष वर्ग है और गणित (ग्राफ़ सिद्धांत) और [[कंप्यूटर विज्ञान]] की कई शाखाओं में उपयोग किया जाता है। मान लीजिए कि {{mvar|S}}, {{mvar|q}} अवयवों का [[सेट (गणित)|समुच्चय (गणित)]] है और {{mvar|d}} एक धनात्मक [[पूर्णांक]] है। हैमिंग ग्राफ {{math|''H''(''d'',''q'')}} ने {{mvar|S}} के तत्वों के ऑर्डर किए गए {{mvar|d}}-टुपल्स के सेट या {{mvar|S}} से लंबाई {{mvar|d}} के अनुक्रमों को शीर्ष (ग्राफ़ सिद्धांत) सेट {{mvar|S{{sup|d}}}} किया है। दो कोने ग्राफ़ (असतत गणित) होते हैं यदि वे ठीक एक निर्देशांक में भिन्न होते हैं; अर्थात् यदि उनकी [[हैमिंग दूरी]] एक है। हैमिंग ग्राफ {{math|''H''(''d'',''q'')}}, समान रूप से {{mvar|d}} पूर्ण ग्राफ {{mvar|K{{sub|q}}}} का कार्तीय गुणनफल है।<ref name="bh12">{{citation | ||
| last1 = Brouwer | first1 = Andries E. | author1-link = Andries Brouwer | | last1 = Brouwer | first1 = Andries E. | author1-link = Andries Brouwer | ||
| last2 = Haemers | first2 = Willem H. | | last2 = Haemers | first2 = Willem H. | ||
| Line 25: | Line 25: | ||
| title = Spectra of graphs | | title = Spectra of graphs | ||
| year = 2012}}.</ref> | | year = 2012}}.</ref> | ||
कुछ | कुछ स्थितियों में, हैमिंग ग्राफ़ को अधिक आम तौर पर पूर्ण ग्राफ़ के निर्देशांक उत्पाद के रूप में माना जा सकता है जो अलग-अलग आकार के हो सकते हैं।<ref name="ik00">{{citation | ||
| last1 = Imrich | first1 = Wilfried | | last1 = Imrich | first1 = Wilfried | ||
| last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar | | last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar | ||
| Line 35: | Line 35: | ||
| series = Wiley-Interscience Series in Discrete Mathematics and Optimization | | series = Wiley-Interscience Series in Discrete Mathematics and Optimization | ||
| title = Product graphs | | title = Product graphs | ||
| year = 2000}}.</ref> हैमिंग रेखांकन के विपरीत {{math|''H''(''d'',''q'')}}, इस अधिक सामान्य वर्ग के ग्राफ़ आवश्यक रूप से दूरी-[[नियमित ग्राफ]] | | year = 2000}}.</ref> हैमिंग रेखांकन के विपरीत {{math|''H''(''d'',''q'')}}, इस अधिक सामान्य वर्ग के ग्राफ़ आवश्यक रूप से दूरी-[[नियमित ग्राफ|नियमित ग्राफ़]] नहीं हैं | दूरी-नियमित हैं, किन्तु वे नियमित ग्राफ़ और [[शीर्ष-सकर्मक ग्राफ]] बने रहते हैं। | ||
== विशेष मामले == | == विशेष मामले == | ||
Revision as of 20:51, 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".
