Cubo parcial

En teoría de grafos , un cubo parcial es un grafo que es un subgrafo isométrico de un hipercubo . ^[1] En otras palabras, un cubo parcial se puede identificar con un subgrafo de un hipercubo de tal manera que la distancia entre dos vértices cualesquiera en el cubo parcial sea la misma que la distancia entre esos vértices en el hipercubo. Equivalentemente, un cubo parcial es un grafo cuyos vértices se pueden etiquetar con cadenas de bits de igual longitud de tal manera que la distancia entre dos vértices en el grafo sea igual a la distancia de Hamming entre sus etiquetas. Tal etiquetado se llama etiquetado de Hamming ; representa una incrustación isométrica del cubo parcial en un hipercubo.

Historia

Firsov (1965) fue el primero en estudiar las incrustaciones isométricas de grafos en hipercubos. Los grafos que admiten tales incrustaciones fueron caracterizados por Djoković (1973) y Winkler (1984), y más tarde se los denominó cubos parciales. Kuzmin y Ovchinnikov (1975) y Falmagne y Doignon (1997), entre otros, siguieron una línea de investigación independiente sobre las mismas estructuras, en la terminología de familias de conjuntos en lugar de etiquetados de hipercubos de grafos. ^[2]

Ejemplos

Todo árbol es un cubo parcial. Supongamos que un árbol $T$ tiene $m$ aristas y numeramos estas aristas (arbitrariamente) de $0$ a $m - 1.$ Elijamos un vértice raíz $r$ para el árbol, arbitrariamente, y etiquetemos cada vértice $v$ con una cadena de $m$ bits que tenga un 1 en la posición $i$ siempre que la arista $i$ se encuentre en el camino de $r$ a $v$ en $T.$ Por ejemplo, el propio $r$ tendrá una etiqueta que constará de todos los bits cero, sus vecinos tendrán etiquetas con un solo bit 1, etc. Entonces, la distancia de Hamming entre dos etiquetas cualesquiera es la distancia entre los dos vértices del árbol, por lo que este etiquetado muestra que $T$ es un cubo parcial.

Cada gráfico de hipercubo es en sí mismo un cubo parcial, que puede etiquetarse con todas las diferentes cadenas de bits de longitud igual a la dimensión del hipercubo.

Ejemplos más complejos incluyen los siguientes:

Consideremos el grafo cuyas etiquetas de vértice consisten en todas las posibles cadenas de bits de $(2 n + 1)$ dígitos que tienen $n$ o $n + 1$ bits distintos de cero, donde dos vértices son adyacentes siempre que sus etiquetas difieran en un solo bit. Este etiquetado define una incrustación de estos grafos en un hipercubo (el grafo de todas las cadenas de bits de una longitud dada, con la misma condición de adyacencia) que resulta ser preservador de la distancia. El grafo resultante es un grafo de Kneser bipartito ; el grafo formado de esta manera con $n = 2$ tiene 20 vértices y 30 aristas, y se llama grafo de Desargues .
Todos los grafos medianos son cubos parciales. ^[3] Los árboles y los grafos de hipercubos son ejemplos de grafos medianos. Dado que los grafos medianos incluyen los grafos cuadrados , los grafos símplex y los cubos de Fibonacci , así como los grafos de cobertura de los retículos distributivos finitos , todos ellos son cubos parciales.
El grafo dual planar de una disposición de líneas en el plano euclidiano es un cubo parcial. En términos más generales, para cualquier disposición de hiperplanos en el espacio euclidiano de cualquier número de dimensiones, el grafo que tiene un vértice para cada celda de la disposición y una arista para cada dos celdas adyacentes es un cubo parcial. ^[4]
Un cubo parcial en el que cada vértice tiene exactamente tres vecinos se conoce como cubo parcial cúbico . Aunque se conocen varias familias infinitas de cubos parciales cúbicos, junto con muchos otros ejemplos esporádicos, el único cubo parcial cúbico conocido que no es un grafo plano es el grafo de Desargues. ^[5]
El gráfico subyacente de cualquier antimatroide , que tiene un vértice para cada conjunto del antimatroide y una arista para cada dos conjuntos que difieren en un solo elemento, es siempre un cubo parcial.
El producto cartesiano de cualquier conjunto finito de cubos parciales es otro cubo parcial. ^[6]
Una subdivisión de un gráfico completo es un cubo parcial si y solo si cada arista del gráfico completo se subdivide en una ruta de dos aristas, o hay un vértice del gráfico completo cuyas aristas incidentes no están subdivididas y todas las aristas no incidentes se han subdividido en rutas de longitud par. ^[7]

La relación Djoković-Winkler

Muchos de los teoremas sobre cubos parciales se basan directa o indirectamente en una cierta relación binaria definida en las aristas del grafo. Esta relación, descrita por primera vez por Djoković (1973) y a la que Winkler (1984) dio una definición equivalente en términos de distancias, se denota por . Se define que dos aristas y están en la relación , escrita , si . Esta relación es reflexiva y simétrica , pero en general no es transitiva . ${\estilo de visualización \Theta}$ $e=\{x,y\}$ $f=\{u,v\}$ ${\estilo de visualización \Theta}$ $e{\mathrel {\Theta }}f$ $d(x,u)+d(y,v)\no =d(x,v)+d(y,u)$

Winkler demostró que un grafo conexo es un cubo parcial si y solo si es bipartito y la relación es transitiva. ^[8] En este caso, forma una relación de equivalencia y cada clase de equivalencia separa dos subgrafos conexos del grafo entre sí. Se puede obtener un etiquetado de Hamming asignando un bit de cada etiqueta a cada una de las clases de equivalencia de la relación de Djoković–Winkler; en uno de los dos subgrafos conexos separados por una clase de equivalencia de aristas, todos los vértices tienen un 0 en esa posición de sus etiquetas, y en el otro subgrafo conexo todos los vértices tienen un 1 en la misma posición. ${\estilo de visualización \Theta}$

Reconocimiento

Se pueden reconocer cubos parciales y construir un etiquetado de Hamming en el tiempo, donde es el número de vértices en el gráfico. ^[9] Dado un cubo parcial, es sencillo construir las clases de equivalencia de la relación de Djoković–Winkler haciendo una búsqueda en amplitud desde cada vértice, en un tiempo total ; el algoritmo de reconocimiento en tiempo acelera esto usando paralelismo a nivel de bit para realizar múltiples búsquedas en amplitud en una sola pasada a través del gráfico, y luego aplica un algoritmo separado para verificar que el resultado de este cálculo sea un etiquetado de cubo parcial válido. $O(n^{2})$ ${\estilo de visualización n}$ $O(nm)$ $O(n^{2})$

Dimensión

La dimensión isométrica de un cubo parcial es la dimensión mínima de un hipercubo en el que puede incrustarse isométricamente, y es igual al número de clases de equivalencia de la relación de Djoković–Winkler. Por ejemplo, la dimensión isométrica de un árbol de vértices es su número de aristas, . Una incrustación de un cubo parcial en un hipercubo de esta dimensión es única, hasta las simetrías del hipercubo. ^[10] ${\estilo de visualización n}$ ${\estilo de visualización n-1}$

Cada hipercubo y, por lo tanto, cada cubo parcial se puede incrustar isométricamente en una red de números enteros . La dimensión de red de un grafo es la dimensión mínima de una red de números enteros en la que el grafo se puede incrustar isométricamente. La dimensión de red puede ser significativamente menor que la dimensión isométrica; por ejemplo, para un árbol es la mitad del número de hojas del árbol (redondeado al entero más cercano). La dimensión de red de cualquier grafo, y una incrustación de red de dimensión mínima, se pueden encontrar en tiempo polinomial mediante un algoritmo basado en la coincidencia máxima en un grafo auxiliar. ^[11]

También se han definido otros tipos de dimensión de cubos parciales, basados en incrustaciones en estructuras más especializadas. ^[12]

Aplicación a la teoría de grafos químicos

Las incrustaciones isométricas de grafos en hipercubos tienen una aplicación importante en la teoría de grafos químicos . Un grafo bencenoide es un grafo que consta de todos los vértices y aristas que se encuentran sobre y en el interior de un ciclo en una red hexagonal . Dichos grafos son los grafos moleculares de los hidrocarburos bencenoides , una gran clase de moléculas orgánicas. Cada uno de estos grafos es un cubo parcial. Se puede utilizar un etiquetado de Hamming de un grafo de este tipo para calcular el índice de Wiener de la molécula correspondiente, que luego se puede utilizar para predecir algunas de sus propiedades químicas. ^[13]

Una estructura molecular diferente formada a partir del carbono, el diamante cúbico , también forma gráficos cúbicos parciales. ^[14]

Notas

^ Ovchinnikov (2011), Definición 5.1, p. 127.
^ Ovchinnikov (2011), pág. 174.
^ Ovchinnikov (2011), Sección 5.11, "Gráficos medianos", págs. 163-165.
^ Ovchinnikov (2011), Capítulo 7, "Disposiciones de hiperplanos", págs. 207-235.
^ Eppstein (2006).
^ Ovchinnikov (2011), Sección 5.7, "Productos cartesianos de cubos parciales", págs. 144-145.
^ Beaudou, Gravier y Meslem (2008).
^ Winkler (1984), Teorema 4. Véase también Ovchinnikov (2011), Definición 2.13, p.29, y Teorema 5.19, p.136.
^ Eppstein (2008).
^ Ovchinnikov (2011), Sección 5.6, "Dimensión isométrica", págs. 142-144, y Sección 5.10, "Singularidad de las incrustaciones isométricas", págs. 157-162.
^ Hadlock y Hoffman (1978); Eppstein (2005); Ovchinnikov (2011), Capítulo 6, "Incrustaciones en red", págs. 183-205.
^ Eppstein (2009); Cabello, Eppstein y Klavžar (2011).
^ Klavžar, Gutman y Mohar (1995), Proposiciones 2.1 y 3.1; Imrich y Klavžar (2000), pág. 60; Ovchinnikov (2011), sección 5.12, "Longitud promedio y índice de Wiener", págs. 165-168.
^ Eppstein (2009).

Referencias

Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), "Incrustaciones isométricas de gráficos completos subdivididos en el hipercubo" (PDF) , SIAM Journal on Discrete Mathematics , 22 (3): 1226–1238, doi :10.1137/070681909, MR 2424849, S2CID 6332951
Cabello, S.; Eppstein, D .; Klavžar, S. (2011), "La dimensión de Fibonacci de un gráfico", Electronic Journal of Combinatorics , 18 (1), P55, arXiv : 0903.2507 , Bibcode :2009arXiv0903.2507C, doi :10.37236/542, S2CID 9363180.
Djoković, Dragomir Ž. (1973), "Subgrafos de hipercubos que preservan la distancia", Journal of Combinatorial Theory , Serie B, 14 (3): 263–267, doi : 10.1016/0095-8956(73)90010-5 , MR 0314669.
Eppstein, David (2005), "La dimensión reticular de un gráfico", European Journal of Combinatorics , 26 (6): 585–592, arXiv : cs.DS/0402028 , doi :10.1016/j.ejc.2004.05.001, S2CID 7482443.
Eppstein, David (2006), "Cubos parciales cúbicos a partir de arreglos simpliciales", Electronic Journal of Combinatorics , 13 (1), R79, arXiv : math.CO/0510263 , doi :10.37236/1105, S2CID 8608953.
Eppstein, David (2008), "Reconocimiento de cubos parciales en tiempo cuadrático", Proc. 19th ACM-SIAM Symposium on Discrete Algorithms , pp. 1258–1266, arXiv : 0705.1025 , Bibcode :2007arXiv0705.1025E.
Eppstein, David (2009), "Subgrafos de diamante isométricos", Proc. 16.° Simposio internacional sobre dibujo de grafos, Heraklion, Creta, 2008 , Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, págs. 384–389, arXiv : 0807.2218 , doi :10.1007/978-3-642-00219-9_37, S2CID 14066610.
Falmagne, J.-C. ; Doignon, J.-P. (1997), "Evolución estocástica de la racionalidad" (PDF) , Theory and Decision , 43 (2): 107–138, doi :10.1023/A:1004981430688, S2CID 117983644.
Firsov, VV (1965), "Sobre la incrustación isométrica de un gráfico en un cubo booleano", Cybernetics , 1 : 112-113, doi : 10.1007/bf01074705, S2CID 121572742. Como lo cita Ovchinnikov (2011).
Hadlock, F.; Hoffman, F. (1978), "Árboles de Manhattan", Utilitas Mathematica , 13 : 55–67. Como lo cita Ovchinnikov (2011).
Imrich, Wilfried; Klavžar, Sandi (2000), Gráficos de productos: estructura y reconocimiento , Serie Wiley-Interscience en Matemática discreta y optimización, Nueva York: John Wiley & Sons, ISBN 978-0-471-37039-0, Sr. 1788124.
Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Etiquetado de sistemas bencenoides que reflejan las relaciones vértice-distancia" (PDF) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593, doi :10.1021/ci00025a030.
Kuzmin, V.; Ovchinnikov, S. (1975), "Geometría de espacios de preferencias I", Automatización y control remoto , 36 : 2059–2063. Como lo cita Ovchinnikov (2011).
Ovchinnikov, Sergei (2011), Gráficos y cubos , Universitext, Springer. Véase especialmente el Capítulo 5, "Cubos parciales", págs. 127-181.
Winkler, Peter M. (1984), "Incrustación isométrica en productos de gráficos completos", Discrete Applied Mathematics , 7 (2): 221–225, doi : 10.1016/0166-218X(84)90069-6 , MR 0727925.