हैमिंग ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
| 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)}} एक [[इकाई दूरी ग्राफ]] के रूप में तैयार किया गया]]हैमिंग ग्राफ़ [[रिचर्ड हैमिंग]] के नाम पर ग्राफ़ (असतत गणित) का एक विशेष वर्ग है और गणित (ग्राफ़ सिद्धांत) और [[कंप्यूटर विज्ञान]] की कई शाखाओं में उपयोग किया जाता है। मान लीजिए कि {{mvar|S}}, {{mvar|q}} अवयवों का [[सेट (गणित)|समुच्चय (गणित)]] है और {{mvar|d}} एक धनात्मक [[पूर्णांक]] है। हैमिंग ग्राफ {{math|''H''(''d'',''q'')}} ने {{mvar|S}} के तत्वों के | [[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 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 91: | Line 91: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
त्रुटि-सुधार कोड | त्रुटि-सुधार कोड<ref>{{citation | ||
| last = Sloane | first = N. J. A. | author-link = Neil Sloane | | last = Sloane | first = N. J. A. | author-link = Neil Sloane | ||
| journal = Graph Theory Notes of New York | | journal = Graph Theory Notes of New York | ||
| Line 98: | Line 98: | ||
| url = http://neilsloane.com/doc/pace2.pdf | | url = http://neilsloane.com/doc/pace2.pdf | ||
| volume = 18 | | volume = 18 | ||
| year = 1989}}.</ref> और एसोसिएशन | | year = 1989}}.</ref> और एसोसिएशन योजनाओं,<ref>{{citation | ||
| last1 = Koolen | first1 = Jacobus H. | | last1 = Koolen | first1 = Jacobus H. | ||
| last2 = Lee | first2 = Woo Sun | | last2 = Lee | first2 = Woo Sun | ||
| Line 114: | Line 114: | ||
| isbn = 9780821848654 | | isbn = 9780821848654 | ||
| s2cid = 8197351 | | 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".</ref> दो क्षेत्रों के नाम के | }}. 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".</ref> दो क्षेत्रों के नाम के संबंध में हैमिंग ग्राफ रोचक हैं। वितरित कंप्यूटिंग में उन्हें संचार नेटवर्क टोपोलॉजी के रूप में भी माना जाता है।<ref name="dc04"/> | ||
== कम्प्यूटेशनल जटिलता == | == कम्प्यूटेशनल जटिलता == | ||
रेखीय समय में यह परीक्षण करना संभव है कि क्या एक ग्राफ एक हैमिंग ग्राफ है, और इस | रेखीय समय में यह परीक्षण करना संभव है कि क्या एक ग्राफ एक हैमिंग ग्राफ है, और इस स्थितियाँ में, इसे टपल्स के साथ लेबलिंग खोजें जो इसे एक हैमिंग ग्राफ के रूप में अनुभव करता है।<ref name="ik00"/> | ||
| Line 135: | Line 135: | ||
}} | }} | ||
[[Category:Created On 08/05/2023]] | [[Category:Created On 08/05/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 10:10, 22 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".
