Hammingův graf - Hamming graph
| Hammingův graf | |
|---|---|
| Pojmenoval podle | Richard Hamming |
| Vrcholy | |
| Hrany | |
| Průměr | |
| Spektrum | |
| Vlastnosti | -pravidelný Vrchol-tranzitivní Vzdálenost-pravidelná[1] |
| Zápis | |
| Tabulka grafů a parametrů | |
Hammingovy grafy jsou speciální třídou grafy pojmenoval podle Richard Hamming a používá se v několika odvětvích matematika a počítačová věda. Nechat S být soubor q prvky a d kladné celé číslo. Hammingův graf H(d,q) má nastavený vrchol Sd, sada objednaných d- n-tice prvků Snebo sekvence délky d z S. Dva vrcholy jsou přilehlý pokud se liší přesně v jedné souřadnici; to znamená, pokud jejich Hammingova vzdálenost je jedna. Hammingův graf H(d,q) je ekvivalentně kartézský součin z d kompletní grafy K.q.[1]
V některých případech mohou být Hammingovy grafy považovány obecněji za kartézské produkty úplných grafů, které mohou mít různé velikosti.[2] Na rozdíl od Hammingových grafů H(d,q), grafy v této obecnější třídě nemusí být nutně vzdálenost-pravidelná, ale zůstávají pravidelný a vrchol-tranzitivní.
Speciální případy
- H(2,3), což je zobecněný čtyřúhelník G Q (2,1)[3]
- H(1,q), což je kompletní graf K.q[4]
- H(2,q), což je mřížkový graf Lq, q a také věžní graf[5]
- H(d, 1), což je singletonový graf K.1
- H(d, 2), což je hyperkrychlový graf Qd.[1] Hamiltonovské cesty v těchto grafech Šedé kódy.
- Protože kartézské produkty grafů zachovávají vlastnost bytí a graf jednotkové vzdálenosti,[6] Hammingovy grafy H(d, 2) a H(d, 3) jsou všechny grafy jednotkové vzdálenosti.
Aplikace
Hammingovy grafy jsou zajímavé v souvislosti s kódy opravující chyby[7] a asociační schémata,[8] abychom pojmenovali dvě oblasti. Byly také považovány za topologii komunikační sítě v distribuované výpočty.[4]
Výpočetní složitost
Je to možné v lineární čas otestovat, zda je graf Hammingův graf, a v případě, že je, najít jeho označení n-ticemi, které jej realizují jako Hammingův graf.[2]
Reference
- ^ A b C Brouwer, Andries E.; Haemers, Willem H. (2012), Spektra grafů, Universitext, New York: Springer, s. 178, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, PAN 2882891.
- ^ A b Imrich, Wilfried; Klavžar, Sandi (2000), „Hammingovy grafy“, Grafy produktů, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, str. 104–106, ISBN 978-0-471-37039-0, PAN 1788124.
- ^ Blokhuis, Aart; Brouwer, Andries E.; Haemers, Willem H. (2007), „On 3-chromatical distance-regular graphs“, Designy, kódy a kryptografie, 44 (1–3): 293–305, doi:10.1007 / s10623-007-9100-7, PAN 2336413. Viz zejména poznámka (e) na str. 300.
- ^ A b Dekker, Anthony H .; Colbert, Bernard D. (2004), „Robustnost sítě a topologie grafů“, Sborník 27. australasské konference o informatice - svazek 26, ACSC '04, Darlinghurst, Austrálie, Austrálie: Australian Computer Society, Inc., str. 359–368.
- ^ Bailey, Robert F .; Cameron, Peter J. (2011), „Základní velikost, metrická dimenze a další invarianty skupin a grafů“, Bulletin of London Mathematical Society, 43 (2): 209–242, doi:10.1112 / blms / bdq096, PAN 2781204.
- ^ Horvat, Boris; Pisanski, Tomaž (2010), „Produkty grafů jednotkových vzdáleností“, Diskrétní matematika, 310 (12): 1783–1792, doi:10.1016 / j.disc.2009.11.035, PAN 2610282
- ^ Sloane, N. J. A. (1989), „Nevyřešené problémy v teorii grafů vyplývající ze studia kódů“ (PDF), Teorie grafů z New Yorku, 18: 11–20.
- ^ Koolen, Jacobus H .; Lee, Woo Sun; Martin, William J. (2010), „Charakterizace zcela běžných kódů z algebraického hlediska“, Kombinatorika a grafy, Contemp. Matematika., 531„Providence, RI: Amer. Matematika. Soc., S. 223–242, arXiv:0911.1828, doi:10.1090 / conm / 531/10470, ISBN 9780821848654, PAN 2757802. Na str. 224, autoři píší, že „pečlivé studium zcela pravidelných kódů v Hammingových grafech je ústředním bodem studia asociačních schémat“.