हैमिंग ग्राफ
| 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".
