Contele de Hamming

Contele de Hamming

Numit după	Richard Hamming
Vârfurile	$q^{d}$
coaste	${\frac {d(q-1)q^{d}}{2}}$
Diametru	$d$
Spectru	$\{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots, d\}$
Proprietăți	$d(q-1)$ -regular vertex-tranzitiv distanta-regular [1]

Graficele Hamming sunt o clasă specială de grafice numite după Richard Hamming și utilizate în unele domenii ale matematicii și informaticii .

Definiție

Fie S o mulțime de q elemente și d un număr pozitiv. Graficul Hamming H ( d , q ) are o mulțime de vârfuri S d , o mulțime de d -tuple ordonate de elemente ale mulțimii S (secvențe de lungime d elemente din S ). Două vârfuri sunt adiacente dacă diferă cu exact o coordonată, adică dacă distanța Hamming este egală cu unu. Graficul Hamming H ( d , q ) este egal cu produsul direct al d grafice complete K q [1] .

În unele cazuri, graficele Hamming pot fi definite ca produsul direct al graficelor complete, care pot avea dimensiuni diferite [2] . Spre deosebire de graficele H ( d , q ), aceste grafice de clasă mai largi nu vor fi neapărat regulate la distanță , dar rămân regulate și tranzitive la vârf .

Ocazii speciale

H (2,3) este un patrulater generalizat G Q (2,1) [3]
H (1, q ) este graficul complet K q [4] .
H (2, q ) este un grafic reticulat L q,q , precum și un grafic rook [5] .
H ( d ,1) este un grafic cu un vârf K 1
H ( d ,2) este graficul hipercub Q d [1]
H (3,3) este un grafic de distanță unitară cu n =27 vârfuri și n 4 /3 =81 muchii (în figură)

Aplicații

Graficele Hamming sunt interesante datorită conexiunii lor cu codurile de corectare a erorilor [6] și schemele de relații [7] . Ele sunt de asemenea acceptate ca topologie de rețea în calculul distribuit [4] .

Complexitate computațională

Puteți verifica dacă un grafic este un grafic Hamming și, dacă este, găsiți o etichetare de tuplu a vârfurilor care implementează un grafic Hamming în timp liniar [2] .

Note

↑ 1 2 3 Brouwer, Haemers, 2012 , p. 178.
↑ 1 2 Imrich, Klavžar, 2000 , p. 104–106.
↑ ( Blokhuis, Brouwer, Haemers 2007 ). Vezi nota de la pagina 300.
↑ 1 2 Dekker, Colbert, 2004 , p. 359–368.
↑ Bailey, Cameron, 2011 , p. 209–242.
↑ Sloane, 1989 , p. 11–20.
↑ ( Koolen, Lee, Martin 2010 ) La p. 224, autorii scriu că „studiul atent al codurilor regulate complete în graficele Hamming este esențial pentru studiul schemelor de asociere”.

Literatură

Andries E. Brouwer, Willem H. Haemers. Spectrele graficelor . - New York: Springer, 2012. - P. 178 . — (text universitar). — ISBN 978-1-4614-1938-9 . - doi : 10.1007/978-1-4614-1939-6 .
Wilfried Imrich, Sandi Klavzar. grafice de produs. - Wiley-Interscience, New York, 2000. - S. 104-106. - (Seria Wiley-Interscience în matematică discretă și optimizare). - ISBN 0-471-37039-8 .
Aart Blokhuis, Andries E. Brouwer, Willem H. Haemers. Pe grafice 3-cromatice distanță-regulată // Design-uri, coduri și criptografie. - 2007. - T. 44 , nr. 1-3 . - S. 293-305 . - doi : 10.1007/s10623-007-9100-7 .
Anthony H. Dekker, Bernard D. Colbert. Proceedings of the 27th Australasian Conference on Computer Science - Volumul 26 . - Darlinghurst, Australia, Australia: Australian Computer Society, Inc., 2004. - P. 359-368. — (ACSC '04).
Robert F. Bailey, Peter J. Cameron. Dimensiunea de bază, dimensiunea metrică și alte invariante ale grupurilor și graficelor // Buletinul Societății de Matematică din Londra. - 2011. - T. 43 , nr. 2 . - S. 209-242 . - doi : 10.1112/blms/bdq096 .
NJA Sloane. Probleme nerezolvate în teoria grafurilor care decurg din studiul codurilor // Graph Theory Notes of New York. - 1989. - T. 18 . - S. 11-20 .
Jacobus H. Koolen, Woo Sun Lee, William J. Martin. combinatorii și grafice. — Providence, R.I.: Amer. Matematică. Soc., 2010. - T. 531. - S. 223-242. - (Contemp. Matematică). - doi : 10.1090/conm/531/10470 .

Link -uri

Weisstein, Eric W. Hamming Graph (engleză) pe site-ul Wolfram MathWorld .
Brouwer, Andries E. Hamming graphs . Preluat la 23 martie 2017. Arhivat din original la 2 iulie 2016. (nedefinit)