Hrabě z Hamminga
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
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