stringtranslate.com

Gráfico de Hamming

H (3,3) dibujado como un gráfico de distancia unitaria

Los grafos de Hamming son una clase especial de grafos que reciben su nombre de Richard Hamming y se utilizan en varias ramas de las matemáticas ( teoría de grafos ) y la informática . Sea S un conjunto de q elementos y d un entero positivo . El grafo de Hamming H ( d , q ) tiene como conjunto de vértices S d , el conjunto de d - tuplas ordenadas de elementos de S , o secuencias de longitud d a partir de S . Dos vértices son adyacentes si difieren precisamente en una coordenada; es decir, si su distancia de Hamming es uno. El grafo de Hamming H ( d , q ) es, equivalentemente, el producto cartesiano de d grafos completos K q . [1]

En algunos casos, los gráficos de Hamming pueden considerarse de manera más general como los productos cartesianos de gráficos completos que pueden tener distintos tamaños. [3] A diferencia de los gráficos de Hamming H ( d , q ) , los gráficos de esta clase más general no son necesariamente regulares en cuanto a distancias , pero siguen siendo regulares y transitivos en cuanto a vértices .

Casos especiales

Aplicaciones

Los grafos de Hamming son interesantes en relación con los códigos de corrección de errores [8] y los esquemas de asociación [9] , por nombrar dos áreas. También se han considerado como una topología de red de comunicaciones en computación distribuida [5] .

Complejidad computacional

Es posible en tiempo lineal comprobar si un gráfico es un gráfico de Hamming y, en caso de que lo sea, encontrar un etiquetado del mismo con tuplas que lo realice como un gráfico de Hamming. [3]

Referencias

  1. ^ abc Brouwer, Andries E. ; Haemers, Willem H. (2012), "12.3.1 Gráficos de Hamming" (PDF) , 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 , consultado el 8 de agosto de 2022.
  2. ^ Karami, Hamed (2022), "Gráficos de Hamming equilibrados en función de la distancia de los bordes", Journal of Discrete Mathematical Sciences and Cryptography , 25 : 2667–2672, doi :10.1080/09720529.2021.1914363.
  3. ^ ab Imrich, Wilfried; Klavžar, Sandi (2000), "Gráficos de Hamming", Gráficos de productos , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, Nueva York, págs. 104-106, ISBN 978-0-471-37039-0, Sr.  1788124.
  4. ^ Blokhuis, Aart; Brouwer, Andries E .; Haemers, Willem H. (2007), "Sobre grafos de distancia regular de 3 cromatismos", Designs, Codes and Cryptography , 44 (1–3): 293–305, doi : 10.1007/s10623-007-9100-7 , MR  2336413. Véase en particular la nota (e) de la pág. 300.
  5. ^ ab Dekker, Anthony H.; Colbert, Bernard D. (2004), "Robustez de la red y topología de grafos", Actas de la 27.ª Conferencia Australasiana sobre Ciencias de la Computación, volumen 26, ACSC '04, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., págs. 359-368.
  6. ^ Bailey, Robert F.; Cameron, Peter J. (2011), "Tamaño de la base, dimensión métrica y otros invariantes de grupos y gráficos", Boletín de la Sociedad Matemática de Londres , 43 (2): 209–242, doi :10.1112/blms/bdq096, MR  2781204, S2CID  6684542.
  7. ^ 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
  8. ^ Sloane, NJA (1989), "Problemas no resueltos en la teoría de grafos que surgen del estudio de códigos" (PDF) , Graph Theory Notes of New York , 18 : 11–20.
  9. ^ Koolen, Jacobus H.; Lee, Woo Sun; Martin, W (2010), "Caracterización de códigos completamente regulares desde un punto de vista algebraico", Combinatoria y gráficos , Contemp. Math., vol. 531, Providence, RI: Amer., págs. 223–242, arXiv : 0911.1828 , doi : 10.1090/conm/531/10470, ISBN 9780821848654, MR  2757802, S2CID  8197351En la página 224, los autores escriben que "un estudio cuidadoso de códigos completamente regulares en gráficos de Hamming es fundamental para el estudio de los esquemas de asociación".

Enlaces externos