Cubo parcial

En la teoría de grafos, un cubo parcial es un subgráfico de un hipercubo que conserva las distancias (en términos de gráficos): la distancia entre dos vértices cualesquiera del subgráfico es la misma que en el gráfico original [1] . De manera equivalente, un cubo parcial es un gráfico cuyos vértices se pueden etiquetar con cadenas de bits de la misma longitud, de modo que la distancia entre dos vértices en el gráfico es igual a la distancia de Hamming entre las dos etiquetas. Este marcado se llama marcado de Hamming y representa una incrustación isométrica de un cubo parcial en un hipercubo.


Historia

V. Firsov [2] fue el primero en estudiar incrustaciones isométricas de gráficos en hipercubos. Los gráficos que permiten tales incrustaciones fueron descritos por D. Djokovic [3] y P. Winkler [4] y luego se denominaron "cubos parciales". V. Kuzmin y S. Ovchinnikov [5] , así como Falmagnet y Doinon [6] desarrollaron, entre otros, una línea de investigación independiente sobre las mismas estructuras en la terminología de familias de conjuntos , en lugar del etiquetado de hipercubos. [7] .

Ejemplos

Cualquier árbol es un cubo parcial. Supongamos que un árbol T tiene m aristas y los números de estas aristas (en orden arbitrario) de 0 a m  − 1. Elegimos un vértice raíz arbitrario r para el árbol, y asignamos a cada vértice v una etiqueta (cadena de bits) m bits long, que contiene 1 en la posición i si el borde i se encuentra en el camino de r a v en el árbol T. Por ejemplo, el propio vértice r tendrá una etiqueta de ceros, y todos los vértices adyacentes a él tendrán un 1 en la misma posición, y así sucesivamente. Entonces, la distancia de Hamming entre dos etiquetas cualquiera será igual a la distancia entre los vértices correspondientes del árbol, por lo que este etiquetado muestra que el árbol T es un cubo parcial.

Cualquier gráfico de hipercubo es en sí mismo un cubo parcial, que se puede marcar con diferentes cadenas de bits con una longitud igual a la dimensión del hipercubo.

Ejemplos más complejos:

Relación Djokovic-Winkler

Muchos teoremas sobre cubos parciales se basan directa o indirectamente en alguna relación binaria definida en los bordes del gráfico. Esta relación, descrita por primera vez por Djokovic [3] , se denota por . Winkler dio una definición equivalente de la relación en términos de distancia [4] . Dos aristas y están en relación (escrito ) si . Esta relación es reflexiva y simétrica , pero, en general, no transitiva .

Winkler demostró que un grafo conexo es un cubo parcial si y solo si es bipartito y la relación es transitiva [12] [13] . En este caso, la relación forma una relación de equivalencia y cada clase de equivalencia separa dos subgrafos conectados del gráfico entre sí. Se puede obtener una etiqueta de Hamming asignando un bit en cada etiqueta para cada clase de equivalencia de la relación Djokovic-Winkler. En uno de los dos subgrafos conexos separados por una relación de equivalencia de aristas, las etiquetas tienen 0 en la posición correspondiente, y en el otro subgrafo conexo, todas las etiquetas en la misma posición tienen 1.

Reconocimiento

Los cubos parciales se pueden reconocer y el marcado de Hamming para ellos se construye en el tiempo , donde es el número de vértices del gráfico [14] . Dado un cubo parcial, uno puede construir directamente clases de equivalencia Djokovic-Winkler utilizando la búsqueda primero en amplitud de cada vértice en el tiempo total . El algoritmo de reconocimiento acelera la búsqueda a lo largo del tiempo mediante el uso de paralelismo a nivel de bits para realizar múltiples búsquedas en anchura en una sola pasada de gráfico y, a continuación, utiliza un algoritmo independiente para comprobar que el resultado es un diseño de cubo parcial válido.

Dimensión

La dimensión isométrica de un cubo parcial es la dimensión mínima de un hipercubo en el que se puede incrustar isométricamente un gráfico y es igual al número de clases de equivalencia de la relación Djokovic-Winkler. Por ejemplo, la dimensión isométrica de un árbol con vértices es igual al número de sus aristas, . La incrustación de un cubo parcial en un hipercubo de esta dimensión es única hasta las simetrías del hipercubo [15] [16] .

Cualquier hipercubo y, por lo tanto, cualquier cubo parcial, se puede incrustar isométricamente en una red de enteros , y la dimensión de red de un cubo parcial es la dimensión mínima de una red de enteros en la que se puede incrustar un cubo parcial. La dimensión de la red puede resultar significativamente menor que la dimensión isométrica. Por ejemplo, para un árbol, es igual a la mitad del número de hojas del árbol (redondeado al entero más cercano). La dimensión de un retículo para cualquier gráfico y la incrustación en un retículo de dimensión mínima se pueden encontrar en tiempo polinomial mediante un algoritmo basado en encontrar la coincidencia más grande en un gráfico auxiliar [17] .

Se definen otros tipos de dimensiones parciales del cubo, basados ​​en estructuras más específicas [18] [19] .

Aplicaciones a la teoría de grafos químicos

Las incrustaciones isométricas de gráficos en un hipercubo tienen aplicaciones importantes en la teoría de gráficos químicos . Un gráfico benzoide es un gráfico que consta de vértices y aristas que se encuentran en un ciclo y dentro de un ciclo en una red hexagonal . Estos gráficos son los gráficos moleculares de los hidrocarburos benzoides , una gran clase de moléculas orgánicas. Cada gráfico de este tipo es un cubo parcial. El etiquetado de Hamming de dicho gráfico se puede utilizar para calcular el índice de Wiener de la molécula correspondiente, que se puede utilizar para predecir algunas propiedades químicas [20] . Otra estructura molecular formada por carbono, la estructura de diamante , también corresponde a cubos parciales [18] .

Notas

  1. ↑ Ovchinnikov, 2011 , pág. 127, Definición 5.1.
  2. ↑ Firsov, 1965 .
  3. ↑ 1 2 Djokovic, 1973 .
  4. ↑ 12 Winkler , 1984 .
  5. ↑ Kuzmin, Ovchinnikov, 1975 .
  6. ↑ Falmagne, Doignon, 1997 .
  7. ↑ Ovchinnikov, 2011 , pág. 174.
  8. ↑ Ovchinnikov, 2011 , pág. 163–165, Sección 5.11, "Gráficos de la mediana".
  9. ↑ Ovchinnikov, 2011 , pág. 207–235, Capítulo 7, "Arreglos de hiperplanos".
  10. ↑ Epstein, 2006 .
  11. ↑ Ovchinnikov, 2011 , pág. 144–145, Sección 5.7, "Productos cartesianos de cubos parciales".
  12. ↑ Winkler, 1984 , pág. Teorema 4.
  13. ↑ Ovchinnikov, 2011 , pág. 29, 139, Definición 2.13, Teorema 5.19.
  14. ↑ Epstein, 2008 .
  15. ↑ Ovchinnikov, 2011 , pág. 142–144, Sección 5.6, "Dimensión isométrica".
  16. ↑ Ovchinnikov, 2011 , pág. 157–162, Sección 5.10, "Singularidad de las incrustaciones isométricas".
  17. ↑ Hadlock, Hoffman, 1978 ; Epstein, 2005 ; Ovchinnikov, 2011 , Capítulo 6, "Incrustaciones de celosía", págs. 183–205.
  18. ↑ 12 Epstein , 2009 .
  19. ↑ Cabello, Eppstein, Klavžar, 2011 .
  20. ↑ Klavžar, Gutman, Mohar, 1995 , Proposiciones 2.1 y 3.1; Imrich, Klavžar, 2000 , página 60; Ovchinnikov, 2011 , Sección 5.12, "Longitud promedio y el índice de Wiener", págs. 165–168.

Literatura