Hamming graf

Hamming graf
Döpt efter	Richard Hamming
Vertices	q d
Kanter	${\frac {d(q-1)q^{d}}{2}}$
Diameter	d
Spektrum	${\displaystyle \{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};} i = ,$$i =0,\ldots ,d\}}$
Egenskaper	d ( q – 1) - regelbunden Vertex-transitiv Avstånd-regelbunden
Notation	H ( d , q )
Tabell över grafer och parametrar

H (3,3) ritad som en enhetsdistansgraf

Hamming-grafer är en speciell klass av grafer som är uppkallade efter Richard Hamming och används inom flera grenar av matematik ( grafteori ) och datavetenskap . Låt S vara en uppsättning av q element och d ett positivt heltal . Hamming-grafen H ( d , q ) har vertexuppsättningen Sd ^av , uppsättningen av ordnade d - tuplar element av S , eller sekvenser med längden d från S. Två hörn ligger intill varandra om de skiljer sig åt i exakt en koordinat; det vill säga om deras Hamming-avstånd är ett. Hamminggrafen H ( d , q ) är på motsvarande sätt den kartesiska produkten av d kompletta grafer K _q .

I vissa fall kan Hamming-grafer betraktas mer allmänt som de kartesiska produkterna av kompletta grafer som kan vara av varierande storlek. Till skillnad från Hamming-graferna H ( d , q ) är graferna i denna mer allmänna klass inte nödvändigtvis avståndsregelbundna , men de fortsätter att vara regelbundna och vertextransitiva .

Speciella fall

• H (2,3) , som är den generaliserade fyrkanten G Q (2,1)
• H (1, q ) , vilket är hela grafen K _q
• H (2, q ) , som är gittergrafen L _q,q och även tornets graf
• H ( d , 1 ) , vilket är singelgrafen K ₁
• H ( d , 2 ) , som är hyperkubgrafen Q _d . Hamiltonska banor i dessa grafer bildar grå koder .
• Eftersom kartesiska produkter av grafer bevarar egenskapen att vara en enhetsdistansgraf , är Hamming-graferna H ( d ,2) och H ( d ,3) alla enhetsdistansgrafer.

Ansökningar

Hamming-graferna är intressanta i samband med felkorrigerande koder och associationsscheman , för att nämna två områden. De har också betraktats som en kommunikationsnätstopologi inom distribuerad datoranvändning .

Beräkningskomplexitet

Det är möjligt i linjär tid att testa om en graf är en Hamming-graf, och i så fall hitta en märkning av den med tuplar som realiserar den som en Hamming-graf.

externa länkar

• Weisstein, Eric W. "Hamming Graph" . MathWorld .
• Brouwer, Andries E. "Hamming grafer" .