Hrabě z Hamminga

hrabě z Hamminga

Pojmenoval podle	Richard Hamming
Vrcholy	$q^{d}$
žebra	${\frac {d(q-1)q^{d}}{2}}$
Průměr	$d$
Spektrum	$\{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots ,d\}$
Vlastnosti	$d(q-1)$ -pravidelný vrchol-tranzitivní vzdálenost-pravidelný [1]

Hammingovy grafy jsou speciální třída grafů pojmenovaná po Richardu Hammingovi a používaná v některých oblastech matematiky a informatiky .

Definice

Nechť S je množina q prvků a d je kladné číslo. Hammingův graf H ( d , q ) má množinu vrcholů S d , množinu uspořádaných d - tic prvků množiny S (posloupnosti délek d prvků z S ). Dva vrcholy sousedí, pokud se liší právě o jednu souřadnici, tedy pokud je Hammingova vzdálenost rovna jedné. Hammingův graf H ( d , q ) je roven přímému součinu d úplných grafů K q [1] .

V některých případech lze Hammingovy grafy definovat jako přímý součin úplných grafů, které mohou mít různé velikosti [2] . Na rozdíl od grafů H ( d , q ) nebudou tyto grafy širší třídy nutně regulární na vzdálenost , ale zůstanou pravidelné a vertexově tranzitivní .

Zvláštní příležitosti

H (2,3) je zobecněný čtyřúhelník G Q (2,1) [3]
H (1, q ) je úplný graf K q [4] .
H (2, q ) je mřížkový graf L q,q , stejně jako věžový graf [5] .
H ( d ,1) je graf s jedním vrcholem K 1
H ( d ,2) je graf hyperkrychle Q d [1]
H (3,3) je jednotkový graf vzdálenosti s n = 27 vrcholy a n 4 /3 = 81 hran (na obrázku)

Aplikace

Hammingovy grafy jsou zajímavé svou souvislostí s kódy pro opravu chyb [6] a schématy vztahů [7] . Jsou také přijímány jako topologie sítě v distribuovaných výpočtech [4] .

Výpočetní složitost

Můžete zkontrolovat, zda je graf Hammingův graf, a pokud ano, najít n-ticové označení vrcholů, které implementuje Hammingův graf v lineárním čase [2] .

Poznámky

↑ 1 2 3 Brouwer, Haemers, 2012 , str. 178.
↑ 1 2 Imrich, Klavžar, 2000 , str. 104–106.
↑ ( Blokhuis, Brouwer, Haemers 2007 ). Viz poznámka na straně 300.
↑ 1 2 Dekker, Colbert, 2004 , str. 359–368.
↑ Bailey, Cameron, 2011 , str. 209–242.
↑ Sloane, 1989 , str. 11–20.
↑ ( Koolen, Lee, Martin 2010 ) Na str. 224 autoři píší, že "pečlivé studium úplných regulárních kódů v Hammingových grafech je ústředním bodem studia asociačních schémat."

Literatura

Andries E. Brouwer, Willem H. Haemers. Spektra grafů . - New York: Springer, 2012. - S. 178 . — (Univerzitní text). — ISBN 978-1-4614-1938-9 . - doi : 10.1007/978-1-4614-1939-6 .
Wilfried Imrich, Sandi Klavzar. produktové grafy. - Wiley-Interscience, New York, 2000. - S. 104-106. - (Wiley-Interscience Series v diskrétní matematice a optimalizaci). - ISBN 0-471-37039-8 .
Aart Blokhuis, Andries E. Brouwer, Willem H. Haemers. Na 3-chromatických grafech s pravidelnou vzdáleností // Designs, Codes and Cryptography. - 2007. - T. 44 , č. 1-3 . - S. 293-305 . - doi : 10.1007/s10623-007-9100-7 .
Anthony H. Dekker, Bernard D. Colbert. Sborník příspěvků z 27. australské konference o informatice - Volume 26 . - Darlinghurst, Austrálie, Austrálie: Australian Computer Society, Inc., 2004. - S. 359-368. — (ACSC '04).
Robert F. Bailey, Peter J. Cameron. Základní velikost, metrický rozměr a další invarianty skupin a grafů // Bulletin of the London Mathematical Society. - 2011. - T. 43 , č. 2 . - S. 209-242 . - doi : 10.1112/blms/bdq096 .
NJA Sloane. Nevyřešené problémy v teorii grafů vyplývající ze studia kódů // Graph Theory Notes of New York. - 1989. - T. 18 . - S. 11-20 .
Jacobus H. Koolen, Woo Sun Lee, William J. Martin. kombinatoria a grafy. — Providence, R.I.: Amer. Matematika. Soc., 2010. - T. 531. - S. 223-242. - (Contemp. Math.). - doi : 10.1090/conm/531/10470 .

Odkazy

Weisstein, Eric W. Hamming Graph (anglicky) na webových stránkách Wolfram MathWorld .
Brouwer, Andries E. Hammingovy grafy . Získáno 23. března 2017. Archivováno z originálu 2. července 2016. (neurčitý)