Los gráficos de Hamming son una clase especial de gráficos que llevan el nombre de Richard Hamming y se utilizan en varias ramas de las matemáticas y la informática . Sea S un conjunto de q elementos yd un entero positivo. El Hamming gráfico H ( d , q ) tiene conjunto de vértices S d , el conjunto de ordenadas d -tuplas de elementos de S , o secuencias de longitud d de S . Dos vértices son adyacentes si difieren precisamente en una coordenada; es decir, si suLa distancia de Hamming es una. La gráfica de Hamming H ( d , q ) es, de manera equivalente, el producto cartesiano de d gráficas completas K q . [1]
Gráfico de Hamming | |
---|---|
Lleva el nombre de | Richard Hamming |
Vértices | |
Bordes | |
Diámetro | |
Espectro | |
Propiedades | -regular Vertex-transitivo Distancia-regular [1] |
Notación | |
Tabla de gráficos y parámetros |
En algunos casos, los gráficos de Hamming se pueden considerar de manera más general como los productos cartesianos de gráficos completos que pueden ser de diferentes tamaños. [2] A diferencia de las gráficas de Hamming H ( d , q ), las gráficas de esta clase más general no son necesariamente regulares a la distancia , pero continúan siendo regulares y transitivas a los vértices .
Casos especiales
- H (2,3), que es el cuadrángulo generalizado G Q (2,1) [3]
- H (1, q ), que es el gráfico completo K q [4]
- H (2, q ), que es el gráfico de celosía L q, q y también el gráfico de la torre [5]
- H ( d , 1), que es el gráfico singleton K 1
- H ( d , 2), que es el gráfico del hipercubo Q d . [1] Los caminos hamiltonianos en estos gráficos forman códigos de Gray .
- Debido a que los productos cartesianos de las gráficas conservan la propiedad de ser una gráfica de unidad de distancia , [6] las gráficas de Hamming H ( d , 2) y H ( d , 3) son todas gráficas de unidad de distancia.
Aplicaciones
Los gráficos de Hamming son interesantes en relación con los códigos de corrección de errores [7] y los esquemas de asociación , [8] por nombrar dos áreas. También se han considerado como una topología de red de comunicaciones en la computación distribuida . [4]
Complejidad computacional
Es posible en tiempo lineal probar si una gráfica es una gráfica de Hamming, y en el caso de que lo sea, encontrar un etiquetado de la misma con tuplas que la realice como una gráfica de Hamming. [2]
Referencias
- ^ a b c Brouwer, Andries E .; Haemers, Willem H. (2012), Espectros de gráficos , Universitext, Nueva York: Springer, p. 178, doi : 10.1007 / 978-1-4614-1939-6 , ISBN 978-1-4614-1938-9, MR 2882891.
- ^ a b Imrich, Wilfried; Klavžar, Sandi (2000), "Gráficos de Hamming", Gráficos de productos , Serie Wiley-Interscience en Matemáticas discretas y optimización, Wiley-Interscience, Nueva York, págs. 104-106, ISBN 978-0-471-37039-0, Señor 1788124.
- ^ Blokhuis, Aart; Brouwer, Andries E .; Haemers, Willem H. (2007), "On 3-chromatic distance-regular graphs", Designs, Codes and Cryptography , 44 (1-3): 293-305, doi : 10.1007 / s10623-007-9100-7 , MR 2336413. Ver en particular la nota (e) en la p. 300.
- ^ a b Dekker, Anthony H .; Colbert, Bernard D. (2004), "Red robustez y topología de gráficos", Actas de la 27a conferencia de Australasia sobre ciencias de la computación - Volumen 26 , ACSC '04, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., págs. 359 –368.
- ^ Bailey, Robert F .; Cameron, Peter J. (2011), "Tamaño base, dimensión métrica y otras invariantes de grupos y gráficos", Boletín de la London Mathematical Society , 43 (2): 209–242, doi : 10.1112 / blms / bdq096 , MR 2781204.
- ^ Horvat, Boris; Pisanski, Tomaž (2010), "Productos de gráficos de distancia unitaria", Matemáticas discretas , 310 (12): 1783–1792, doi : 10.1016 / j.disc.2009.11.035 , MR 2610282
- ^ Sloane, NJA (1989), "Problemas no resueltos en teoría de grafos derivados del estudio de códigos" (PDF) , Notas de teoría de grafos de Nueva York , 18 : 11-20.
- ^ Koolen, Jacobus H .; Lee, Woo Sun; Martin, William J. (2010), "Caracterización de códigos completamente regulares desde un punto de vista algebraico", Combinatoria y gráficas , Contemp. Math., 531 , Providence, RI: Amer. Matemáticas. Soc., Págs. 223–242, arXiv : 0911.1828 , doi : 10.1090 / conm / 531/10470 , ISBN 9780821848654, MR 2757802. En P. 224, los autores escriben que "un estudio cuidadoso de los códigos completamente regulares en los gráficos de Hamming es fundamental para el estudio de los esquemas de asociación".
enlaces externos
- Weisstein, Eric W. "Gráfico de Hamming" . MathWorld .
- Brouwer, Andries E. "Gráficos de Hamming" .