Hamming grófja

Hamming grófja

Valaki után elnevezve	Richard Hamming
Csúcsok	${\displaystyle q^{d))$
borda	${\frac {d(q-1)q^{d}}{2}}$
Átmérő	$d$
Spectrum	$\{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots ,d\}$
Tulajdonságok	$d(q-1)$ -szabályos vertex-tranzitív távolság-szabályos [1]

A Hamming -gráfok a gráfok egy speciális osztálya , amelyet Richard Hammingről neveztek el , és a matematika és a számítástechnika egyes területein használják .

Definíció

Legyen S q elemből álló halmaz, d pedig pozitív szám. A H ( d , q ) Hamming-gráfnak van egy S d csúcskészlete , az S halmaz elemeinek rendezett d -sorai ( S -ből származó d elemek hosszúságú sorozatai ). Két csúcs akkor szomszédos, ha pontosan egy koordinátával különböznek egymástól, vagyis ha a Hamming-távolság eggyel egyenlő. A H ( d , q ) Hamming-gráf egyenlő d teljes K q gráf közvetlen szorzatával [1] .

Egyes esetekben a Hamming-gráfok a teljes gráfok közvetlen szorzataként definiálhatók, amelyek különböző méretűek lehetnek [2] . A H ( d , q ) gráfokkal ellentétben ezek a szélesebb osztálygráfok nem feltétlenül távolságszabályosak , hanem regulárisak és csúcstranzitívak maradnak .

Különleges alkalmak

H (2,3) egy általánosított G Q (2,1) négyszög [3]
H (1, q ) a K q [4] teljes gráf .
H (2, q ) egy L q,q rácsgráf , valamint egy rook gráf [5] .
H ( d ,1) egy K 1 csúcsú gráf
H ( d ,2) a Q d hiperkocka gráf [1]
H (3,3) egy egységnyi távolság gráf n =27 csúcsgal és n 4 / 3 =81 éllel (az ábrán)

Alkalmazások

A Hamming gráfok a hibajavító kódokkal [6] és kapcsolati sémákkal [7] való kapcsolatuk miatt érdekesek . Az elosztott számítástechnikában hálózati topológiaként is elfogadottak [4] .

Számítási összetettség

Ellenőrizheti, hogy egy gráf Hamming-gráf-e, és ha igen, keresse meg a csúcsok címkéjét, amely Hamming-gráfot valósít meg lineáris időben [2] .

Jegyzetek

↑ 1 2 3 Brouwer, Haemers, 2012 , p. 178.
↑ 1 2 Imrich, Klavžar, 2000 , p. 104–106.
↑ ( Blokhuis, Brouwer, Haemers 2007 ). Lásd a megjegyzést a 300. oldalon.
↑ 1 2 Dekker, Colbert, 2004 , p. 359–368.
↑ Bailey, Cameron, 2011 , p. 209–242.
↑ Sloane, 1989 , p. 11–20.
↑ ( Koolen, Lee, Martin 2010 ) A 224. oldalon a szerzők azt írják, hogy "a Hamming-gráfok teljes szabályos kódjainak gondos tanulmányozása központi szerepet játszik az asszociációs sémák tanulmányozásában".

Irodalom

Andries E. Brouwer, Willem H. Haemers. Grafikonok spektruma . - New York: Springer, 2012. - 178. o . — (Egyetemi szöveg). — ISBN 978-1-4614-1938-9 . - doi : 10.1007/978-1-4614-1939-6 .
Wilfried Imrich, Sandi Klavzar. termékgrafikonok. - Wiley-Interscience, New York, 2000. - S. 104-106. - (Wiley-Interscience Series in Discrete Mathematics and Optimization). - ISBN 0-471-37039-8 .
Aart Blokhuis, Andries E. Brouwer, Willem H. Haemers. 3-kromatikus távolságszabályos gráfokon // Tervek, kódok és kriptográfia. - 2007. - T. 44 , sz. 1-3 . - S. 293-305 . - doi : 10.1007/s10623-007-9100-7 .
Anthony H. Dekker, Bernard D. Colbert. A 27. ausztráliai informatikai konferencia anyaga - 26. kötet . - Darlinghurst, Ausztrália, Ausztrália: Australian Computer Society, Inc., 2004. - P. 359-368. – (ACSC '04).
Robert F. Bailey, Peter J. Cameron. Az alapméret, a metrikus dimenzió és a csoportok és grafikonok egyéb változatai // Bulletin of the London Mathematical Society. - 2011. - T. 43 , sz. 2 . - S. 209-242 . - doi : 10.1112/blms/bdq096 .
NJA Sloane. Megoldatlan problémák a gráfelméletben a kódok tanulmányozásából // Graph Theory Notes of New York. - 1989. - T. 18 . - S. 11-20 .
Jacobus H. Koolen, Woo Sun Lee, William J. Martin. kombinatoriálok és gráfok. - Providence, R.I.: Amer. Math. Szoc., 2010. - T. 531. - S. 223-242. - (Contemp. Math.). - doi : 10.1090/conm/531/10470 .

Linkek

Weisstein, Eric W. Hamming Graph (angol) a Wolfram MathWorld webhelyén .
Brouwer, Andries E. Hamming grafikonok . Letöltve: 2017. március 23. Az eredetiből archiválva : 2016. július 2. (határozatlan)