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 puede identificarse con un subgrafo de un hipercubo de tal manera que la distancia entre dos vértices cualesquiera del cubo parcial es la misma que la distancia entre esos vértices en el hipercubo. De forma equivalente, un cubo parcial es un grafo cuyos vértices pueden etiquetarse con cadenas de bits de igual longitud de tal manera que la distancia entre dos vértices en el grafo es igual a la distancia de Hamming entre sus etiquetas. Este etiquetado se denomina etiquetado de Hamming y representa una incrustación isométrica del cubo parcial en un hipercubo.

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 posteriormente se denominaron cubos parciales. Una línea de investigación independiente sobre las mismas estructuras, en la terminología de familias de conjuntos en lugar de etiquetas de hipercubos de grafos, fue seguida por Kuzmin y Ovchinnikov (1975) y Falmagne y Doignon (1997) , entre otros. ^{[ 2 ]}

Todo árbol es un cubo parcial. Supongamos que un árbol T tiene m aristas, numeradas arbitrariamente del 0 al m – 1. Elegimos arbitrariamente un vértice raíz r para el árbol y etiquetamos cada vértice v con una cadena de m bits que tiene 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, r tendrá una etiqueta con todos los bits en cero, sus vecinos tendrán etiquetas con un solo bit en 1, etc. Entonces, la distancia de Hamming entre dos etiquetas cualesquiera es la distancia entre los dos vértices en el árbol, por lo que este etiquetado muestra que T es un cubo parcial.

Cada grafo 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.

Algunos ejemplos más complejos incluyen los siguientes:

• Consideremos el grafo cuyos vértices están formados por 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 un grafo que preserva 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 denomina grafo de Desargues .
• Todos los grafos medianos son cubos parciales. ^{[ 3 ]} Los árboles y los grafos hipercubos son ejemplos de grafos medianos. Dado que los grafos medianos incluyen los grafos cuadrados , los grafos simplex y los cubos de Fibonacci , así como los grafos de recubrimiento de 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. De forma más general, para cualquier disposición de hiperplanos en el espacio euclidiano de cualquier número de dimensiones, el grafo que tiene un vértice por cada celda de la disposición y una arista por 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 planar es el grafo de Desargues. ^{[ 5 ]}
• El grafo subyacente de cualquier antimatroide , que tiene un vértice por cada conjunto del antimatroide y una arista por 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 grafo completo es un cubo parcial si y solo si cada arista del grafo completo se subdivide en un camino de dos aristas, o hay un vértice del grafo completo cuyas aristas incidentes no se subdividen y todas las aristas no incidentes se han subdividido en caminos de longitud par. ^{[ 7 ]}

Muchos de los teoremas sobre cubos parciales se basan directa o indirectamente en una determinada relación binaria definida en las aristas del grafo. Esta relación, descrita por primera vez por Djoković (1973) y definida de forma equivalente en términos de distancias por Winkler (1984) , se denota por ${\displaystyle \Theta }$Dos bordes${\displaystyle e=\{x,y\}}$y${\displaystyle f=\{u,v\}}$se definen como estar en la relación ${\displaystyle \Theta }$, escrito${\displaystyle e{\mathrel {\Theta }}f}$, si ${\displaystyle d(x,u)+d(y,v)\not =d(x,v)+d(y,u)}$Esta relación es reflexiva y simétrica , pero en general no es transitiva .

Winkler demostró que un grafo conexo es un cubo parcial si y solo  si es bipartito y la relación ${\displaystyle \Theta }$es transitivo. ^{[ 8 ]} En este caso, forma una relación de equivalencia y cada clase de equivalencia separa dos subgrafos conectados 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 conectados 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 conectado todos los vértices tienen un 1 en la misma posición.

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

La dimensión isométrica de un cubo parcial es la dimensión mínima de un hipercubo sobre el cual 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${\displaystyle n}$-El árbol de vértices es su número de aristas,${\displaystyle n-1}$. Una incrustación de un cubo parcial sobre un hipercubo de esta dimensión es única, salvo simetrías del hipercubo. ^{[ 10 ]}

Todo hipercubo, y por lo tanto todo cubo parcial, puede incrustarse isométricamente en una red entera . La dimensión de red de un grafo es la dimensión mínima de una red entera en la que el grafo puede incrustarse 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, pueden hallarse en tiempo polinomial mediante un algoritmo basado en el emparejamiento máximo en un grafo auxiliar. ^{[ 11 ]}

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

Las incrustaciones isométricas de grafos en hipercubos tienen una importante aplicación en la teoría de grafos químicos . Un grafo bencenoide es un grafo formado por 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 amplia clase de moléculas orgánicas. Cada uno de estos grafos es un cubo parcial. Una etiqueta de Hamming de dicho grafo puede utilizarse para calcular el índice de Wiener de la molécula correspondiente, que a su vez puede emplearse para predecir algunas de sus propiedades químicas. ^{[ 13 ]}

Una estructura molecular diferente formada a partir del carbono, el cúbico de diamante , también forma gráficos de cubo parcial. ^{[ 14 ]}

• Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), "Incrustaciones isométricas de grafos 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 que preservan la distancia de hipercubos", 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", Actas del 19.º Simposio ACM-SIAM sobre Algoritmos Discretos , págs. 1258–1266 , arXiv : 0705.1025 , Bibcode : 2007arXiv0705.1025E .
• Eppstein, David (2009), "Subgrafos de diamante isométricos", Actas del 16.º Simposio Internacional sobre Dibujo de Grafos, Heraklion, Creta, 2008 , Lecture Notes in Computer Science, vol.  5417, Springer-Verlag, pp. 384–389 , arXiv : 0807.2218 , doi : 10.1007/978-3-642-00219-9_37 , ISBN  978-3-642-00218-2, 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 , hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/303273 , S2CID 117983644 .
• Firsov, VV (1965), "Sobre la incrustación isométrica de un grafo en un cubo booleano", Cibernética , 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), Product Graphs: Structure and Recognition , Wiley-Interscience Series in Discrete Mathematics and Optimization, Nueva York: John Wiley & Sons, ISBN 978-0-471-37039-0, MR 1788124 .
• Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Etiquetado de sistemas bencenoides que refleja las relaciones de distancia entre vértices" (PDF) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593 , doi : 10.1021/ci00025a030.
• Kuzmin, V.; Ovchinnikov, S. (1975), "Geometría de los espacios de preferencias I", Automatización y control remoto , 36 : 2059–2063. Como lo cita Ovchinnikov (2011) .
• Ovchinnikov, Sergei (2011), Grafos y cubos , Universitext, SpringerVéase especialmente el capítulo 5, "Cubos parciales", págs. 127-181.
• Winkler, Peter  M. (1984), "Incrustación isométrica en productos de grafos completos", Matemáticas Aplicadas Discretas , 7 (2): 221– 225, doi : 10.1016/0166-218X(84)90069-6 , MR 0727925 .