Conde de Hamming

Conde de Hamming

Lleva el nombre de	ricardo hamming
picos	${\ Displaystyle q^ {d}}$
costillas	${\frac {d(q-1)q^{d}}{2}}$
Diámetro	$d$
Espectro	$\{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots,d\}$
Propiedades	${\ estilo de visualización d (q-1)}$ -regular vértice-distancia transitiva -regular [1]

Los gráficos de Hamming son una clase especial de gráficos que llevan el nombre de Richard Hamming y se utilizan en algunas áreas de las matemáticas y la informática .

Definición

Sea S un conjunto de q elementos y d un número positivo. El gráfico de Hamming H ( d , q ) tiene un conjunto de vértices S d , un conjunto de d -tuplas ordenadas de elementos del conjunto S (secuencias de longitud d elementos de S ). Dos vértices son adyacentes si difieren exactamente en una coordenada, es decir, si la distancia de Hamming es igual a uno. El gráfico de Hamming H ( d , q ) es igual al producto directo de d gráficos completos K q [1] .

En algunos casos, los gráficos de Hamming se pueden definir como el producto directo de gráficos completos, que pueden tener diferentes tamaños [2] . A diferencia de los gráficos H ( d , q ), estos gráficos de clase más amplia no serán necesariamente de distancia regular , sino que seguirán siendo regulares y de vértice transitivo .

Ocasiones especiales

H (2,3) es un cuadrilátero generalizado G Q (2,1) [3]
H (1, q ) es el grafo completo K q [4] .
H (2, q ) es un gráfico de celosía L q,q , así como un gráfico de torre [5] .
H ( d ,1) es un gráfico con un vértice K 1
H ( d ,2) es el gráfico de hipercubo Q d [1]
H (3,3) es un gráfico de unidad de distancia con n =27 vértices y n 4/3 =81 aristas (en la figura)

Aplicaciones

Los gráficos de Hamming son interesantes por su conexión con los códigos de corrección de errores [6] y los esquemas de relaciones [7] . También se aceptan como topología de red en computación distribuida [4] .

Complejidad computacional

Puede verificar si un gráfico es un gráfico de Hamming y, si lo es, encontrar un etiquetado de tupla de vértices que implemente un gráfico de Hamming en tiempo lineal [2] .

Notas

↑ 1 2 3 Brouwer, Haemers, 2012 , pág. 178.
↑ 1 2 Imrich, Klavžar, 2000 , p. 104–106.
↑ ( Blokhuis, Brouwer, Haemers 2007 ). Ver nota en la página 300.
↑ 1 2 Dekker, Colbert, 2004 , pág. 359–368.
↑ Bailey, Cameron, 2011 , pág. 209–242.
↑ Sloane, 1989 , pág. 11–20.
↑ ( Koolen, Lee, Martin 2010 ) En la página 224, los autores escriben que "el estudio cuidadoso de los códigos regulares completos en los gráficos de Hamming es fundamental para el estudio de los esquemas de asociación".

Literatura

Andries E. Brouwer, Willem H. Haemers. Espectros de grafos . - Nueva York: Springer, 2012. - Pág . 178 . — (Texto universitario). — ISBN 978-1-4614-1938-9 . -doi : 10.1007 / 978-1-4614-1939-6 .
Wilfried Imrich, Sandi Klavzar. gráficos de productos - Wiley-Interscience, Nueva York, 2000. - S. 104-106. - (Serie Wiley-Interscience en Matemática Discreta y Optimización). - ISBN 0-471-37039-8 .
Aart Blokhuis, Andries E. Brouwer, Willem H. Haemers. Sobre grafos tricromáticos regulares a distancia // Diseños, Códigos y Criptografía. - 2007. - T. 44 , núm. 1-3 . - S. 293-305 . -doi : 10.1007/ s10623-007-9100-7 .
Anthony H. Dekker, Bernard D. Colbert. Actas de la 27.ª conferencia de Australasia sobre informática - Volumen 26 . - Darlinghurst, Australia, Australia: Australian Computer Society, Inc., 2004. - P. 359-368. — (ACSC '04).
Robert F. Bailey, Peter J. Cameron. Tamaño base, dimensión métrica y otras invariantes de grupos y gráficos // Boletín de la London Mathematical Society. - 2011. - T. 43 , núm. 2 . - S. 209-242 . -doi : 10.1112 / blms/bdq096 .
NJA Sloane. Problemas no resueltos en teoría de grafos que surgen del estudio de códigos // Graph Theory Notes of New York. - 1989. - T. 18 . - S. 11-20 .
Jacobus H. Koolen, Woo Sun Lee, William J. Martin. combinatorias y grafos. — Providence, Rhode Island: Amer. Matemáticas. Soc., 2010. - T. 531. - S. 223-242. - (Matemáticas Contemporáneas). -doi : 10.1090 / conm/531/10470 .

Enlaces

Weisstein, Eric W. Hamming Graph (inglés) en el sitio web de Wolfram MathWorld .
Brouwer, Andries E. Hamming gráficos . Consultado el 23 de marzo de 2017. Archivado desde el original el 2 de julio de 2016. (indefinido)