Hammingin kreivi

Hammingin kreivi

Nimetty	Richard Hamming
Huiput	${\displaystyle q^{d))$
kylkiluut	${\frac {d(q-1)q^{d}}{2}}$
Halkaisija	$d$
Spektri	$\{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots ,d\}$
Ominaisuudet	$d(q-1)$ -säännöllinen vertex-transitiivinen etäisyys-säännöllinen [1]

Hamming - graafit ovat erikoisluokka kaavioita , jotka on nimetty Richard Hammingin mukaan ja joita käytetään joillakin matematiikan ja tietojenkäsittelytieteen aloilla .

Määritelmä

Olkoon S joukko q alkioita ja d positiivinen luku. Hamming-graafissa H ( d , q ) on joukko pisteitä S d , joukko joukon S elementtien järjestettyjä d - monikoisia (pituisia d alkioita S :stä ). Kaksi kärkeä ovat vierekkäisiä, jos ne eroavat täsmälleen yhdellä koordinaatilla, eli jos Hamming-etäisyys on yhtä suuri kuin yksi. Hamming-graafi H ( d , q ) on yhtä suuri kuin d täydellisen graafin K q suora tulo [1] .

Joissakin tapauksissa Hamming-graafit voidaan määritellä kokonaisten graafien suoriksi tuloiksi, joilla voi olla eri kokoja [2] . Toisin kuin graafit H ( d , q ), nämä laajemmat luokkagraafit eivät välttämättä ole etäisyyssäännöllisiä , vaan pysyvät säännöllisinä ja kärkitransitiivisinä .

Erikoistilaisuudet

H (2,3) on yleistetty nelikulmio G Q (2,1) [3]
H (1, q ) on täydellinen graafi K q [4] .
H (2, q ) on hilagraafi L q,q sekä pylväsgraafi [5] .
H ( d ,1) on graafi, jossa on yksi kärki K 1
H ( d ,2) on hyperkuutiograafi Q d [1]
H (3,3) on yksikköetäisyysgraafi , jossa on n =27 kärkeä ja n 4 /3 =81 reunaa (kuvassa)

Sovellukset

Hamming-graafit ovat mielenkiintoisia, koska ne liittyvät virheenkorjauskoodeihin [6] ja suhdekaavioihin [7] . Ne hyväksytään myös verkkotopologiaksi hajautetussa laskennassa [4] .

Laskennallinen monimutkaisuus

Voit tarkistaa, onko graafi Hamming-graafi, ja jos on, löytää pisteiden monikkonimiö, joka toteuttaa Hamming-graafin lineaarisessa ajassa [2] .

Muistiinpanot

↑ 1 2 3 Brouwer, Haemers, 2012 , s. 178.
↑ 1 2 Imrich, Klavžar, 2000 , s. 104–106.
↑ ( Blokhuis, Brouwer, Haemers 2007 ). Katso huomautus sivulla 300.
↑ 1 2 Dekker, Colbert, 2004 , s. 359-368.
↑ Bailey, Cameron, 2011 , s. 209–242.
↑ Sloane, 1989 , s. 11–20.
↑ ( Koolen, Lee, Martin 2010 ) Sivulla 224 kirjoittajat kirjoittavat, että "täydellisten säännöllisten koodien huolellinen tutkiminen Hamming-graafissa on keskeistä assosiaatiokaavioiden tutkimisessa."

Kirjallisuus

Andries E. Brouwer, Willem H. Haemers. Graafisten spektrit . - New York: Springer, 2012. - S. 178 . — (Yliopistoteksti). — ISBN 978-1-4614-1938-9 . - doi : 10.1007/978-1-4614-1939-6 .
Wilfried Imrich, Sandi Klavzar. tuotekaavioita. - 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-kromaattisilla etäisyyssäännöllisillä kaavioilla // Suunnittelut, koodit ja kryptografia. - 2007. - T. 44 , no. 1-3 . - S. 293-305 . - doi : 10.1007/s10623-007-9100-7 .
Anthony H. Dekker, Bernard D. Colbert. Australasian 27. tietojenkäsittelytieteen konferenssin aineisto - 26. osa . - Darlinghurst, Australia, Australia: Australian Computer Society, Inc., 2004. - P. 359-368. — (ACSC '04).
Robert F. Bailey, Peter J. Cameron. Ryhmien ja kaavioiden peruskoko, metrinen ulottuvuus ja muut muuttujat // Bulletin of the London Mathematical Society. - 2011. - T. 43 , no. 2 . - S. 209-242 . - doi : 10.1112/blms/bdq096 .
NJA Sloane. Ratkaisemattomia ongelmia graafiteoriassa, jotka johtuvat koodien tutkimuksesta // Graph Theory Notes of New York. - 1989. - T. 18 . - S. 11-20 .
Jacobus H. Koolen, Woo Sun Lee, William J. Martin. kombinatoriaalit ja graafit. - Providence, R.I.: Amer. Matematiikka. Soc., 2010. - T. 531. - S. 223-242. - (Ajatteleva matematiikka). - doi : 10.1090/conm/531/10470 .

Linkit

Weisstein, Eric W. Hamming Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .
Brouwer, Andries E. Hamming-kaaviot . Haettu 23. maaliskuuta 2017. Arkistoitu alkuperäisestä 2. heinäkuuta 2016. (määrätön)