View source for हैमिंग ग्राफ

{{Short description|Cartesian product of complete graphs}}
{{Infobox graph
 | name = Hamming graph
 | namesake = [[Richard Hamming]]
 | vertices = {{mvar|q{{sup|d}}}}
 | edges = <math> \frac{d(q-1)q^d}{2}</math>
 | diameter = {{mvar|d}}
 | spectrum = <math>\{(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i};</math><math>i = 0, \ldots, d\}</math>
 | properties = {{math|''d''(''q'' – 1)}}-[[Regular graph|regular]]<br/>[[Vertex-transitive graph|Vertex-transitive]]<br/>[[Distance-regular graph|Distance-regular]]<ref name="bh12"/>
 | 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}} के तत्वों के क्रमित किए गए {{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
 | last2 = Haemers | first2 = Willem H.
 | doi = 10.1007/978-1-4614-1939-6
 | isbn = 978-1-4614-1938-9
 | location = New York
 | mr = 2882891
 | chapter = 12.3.1 Hamming graphs
 | chapter-url = https://www.win.tue.nl/~aeb/2WF05/spectra.pdf
 | access-date = 2022-08-08
 | page = 178
 | publisher = Springer
 | series = Universitext
 | title = Spectra of graphs
 | year = 2012}}.</ref>
कुछ स्थितियों में, हैमिंग ग्राफ़ को अधिक सामान्यतः पूर्ण ग्राफ़ के निर्देशांक उत्पाद के रूप में माना जा सकता है जो अलग-अलग आकार के हो सकते हैं।<ref name="ik00">{{citation
 | last1 = Imrich | first1 = Wilfried
 | last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar
 | contribution = Hamming graphs
 | isbn = 978-0-471-37039-0
 | mr = 1788124
 | pages = 104–106
 | publisher = Wiley-Interscience, New York
 | series = Wiley-Interscience Series in Discrete Mathematics and Optimization
 | title = Product graphs
 | year = 2000}}.</ref> हैमिंग रेखांकन के विपरीत {{math|''H''(''d'',''q'')}}, इस अधिक सामान्य वर्ग के ग्राफ़ आवश्यक रूप से दूरी-[[नियमित ग्राफ|नियमित ग्राफ़]] नहीं हैं | दूरी-नियमित हैं, किन्तु वे नियमित ग्राफ़ और [[शीर्ष-सकर्मक ग्राफ]] बने रहते हैं।

== विशेष स्थितियाँ ==

*{{math|''H''(2,3)}}, जो सामान्यीकृत [[पूर्ण चतुर्भुज]] {{math|''G'' ''Q'' (2,1)}} है<ref>{{citation
 | last1 = Blokhuis | first1 = Aart
 | last2 = Brouwer | first2 = Andries E. | author2-link = Andries Brouwer
 | last3 = Haemers | first3 = Willem H.
 | doi = 10.1007/s10623-007-9100-7
 | issue = 1–3
 | journal = Designs, Codes and Cryptography
 | mr = 2336413
 | pages = 293–305
 | title = On 3-chromatic distance-regular graphs
 | volume = 44
 | year = 2007| doi-access = free
 }}. See in particular note (e) on p.&nbsp;300.</ref>
*{{math|''H''(1,''q'')}}, जो पूरा ग्राफ {{mvar|K{{sub|q}}}} है<ref name="dc04">{{citation
 | last1 = Dekker | first1 = Anthony H.
 | last2 = Colbert | first2 = Bernard D.
 | contribution = Network robustness and graph topology
 | location = Darlinghurst, Australia, Australia
 | pages = 359–368
 | publisher = Australian Computer Society, Inc.
 | series = ACSC '04
 | title = Proceedings of the 27th Australasian conference on Computer science - Volume 26
 | url = http://dl.acm.org/citation.cfm?id=979922.979965
 | year = 2004}}.</ref>
*{{math|''H''(2,''q'')}}, जो लैटिस ग्राफ {{mvar|L{{sub|q,q}}}} है और रूक का ग्राफ भी है<ref>{{citation
 | last1 = Bailey | first1 = Robert F.
 | last2 = Cameron | first2 = Peter J.
 | doi = 10.1112/blms/bdq096
 | issue = 2
 | journal = Bulletin of the London Mathematical Society
 | mr = 2781204
 | pages = 209–242
 | title = Base size, metric dimension and other invariants of groups and graphs
 | volume = 43
 | year = 2011| s2cid = 6684542
 }}.</ref>
*{{math|''H''(''d'',1)}}, जो कि सिंगलटन ग्राफ {{math|''K''{{sub|1}}}} है
*{{math|''H''(''d'',2)}}, जो [[हाइपरक्यूब ग्राफ]] {{mvar|Q{{sub|d}}}} हैं।<ref name="bh12"/>इन रेखांकन में [[हैमिल्टनियन पथ]] [[ग्रे कोड]] बनाते हैं।
*चूंकि रेखांकन का कार्तीय गुणनफल एक इकाई दूरी ग्राफ होने के गुण को संरक्षित रखता है,<ref>{{citation
 | last1 = Horvat | first1 = Boris
 | last2 = Pisanski | first2 = Tomaž | author2-link = Tomaž Pisanski
 | doi = 10.1016/j.disc.2009.11.035
 | issue = 12
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2610282
 | pages = 1783–1792
 | title = Products of unit distance graphs
 | volume = 310
 | year = 2010| doi-access = free
 }}</ref> हैमिंग रेखांकन {{math|''H''(''d'',2)}} और {{math|''H''(''d'',3)}} सभी इकाई दूरी के ग्राफ़ हैं।

== अनुप्रयोग ==
त्रुटि-सुधार कोड<ref>{{citation
 | last = Sloane | first = N. J. A. | author-link = Neil Sloane
 | journal = Graph Theory Notes of New York
 | pages = 11–20
 | title = Unsolved problems in graph theory arising from the study of codes
 | url = http://neilsloane.com/doc/pace2.pdf
 | volume = 18
 | year = 1989}}.</ref> और एसोसिएशन योजनाओं,<ref>{{citation
 | last1 = Koolen | first1 = Jacobus H.
 | last2 = Lee | first2 = Woo Sun
 | last3 = Martin | first3= W
 | contribution = Characterizing completely regular codes from an algebraic viewpoint
 | doi = 10.1090/conm/531/10470
 | location = Providence, RI
 | mr = 2757802
 | pages = 223–242
 | publisher = Amer. 
 | series = Contemp. Math.
 | title = Combinatorics and graphs
 | volume = 531
 | year = 2010| arxiv = 0911.1828
 | isbn = 9780821848654
 | 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> दो क्षेत्रों के नाम के संबंध में हैमिंग ग्राफ रोचक हैं। वितरित कंप्यूटिंग में उन्हें संचार नेटवर्क टोपोलॉजी के रूप में भी माना जाता है।<ref name="dc04"/>


== कम्प्यूटेशनल जटिलता ==
रेखीय समय में यह परीक्षण करना संभव है कि क्या एक ग्राफ एक हैमिंग ग्राफ है, और इस स्थितियाँ में, इसे टपल्स के साथ लेबलिंग खोजें जो इसे एक हैमिंग ग्राफ के रूप में अनुभव करता है।<ref name="ik00"/>


==संदर्भ==
{{Reflist}}


==बाहरी संबंध==
*{{MathWorld | title = Hamming Graph | id = HammingGraph}}
*{{cite web
| url         = http://www.win.tue.nl/~aeb/graphs/Hamming.html
| title       = Hamming graphs
| first       = Andries E.
| last        = Brouwer
| authorlink  = Andries E. Brouwer
}}

[[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:रेखांकन के पैरामीट्रिक परिवार]]