En teoría de grafos , un cubo parcial es un gráfico que es isométrico a un subgrafo 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. De manera equivalente, un cubo parcial es un gráfico 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 gráfico sea igual a la distancia de Hamming entre sus etiquetas. Este etiquetado se llamaEtiquetado Hamming ; representa una incrustación isométrica del cubo parcial en un hipercubo.
Historia
Firsov (1965) fue el primero en estudiar incrustaciones isométricas de gráficos en hipercubos. Los gráficos que admiten tales incrustaciones fueron caracterizados por Djoković (1973) y Winkler (1984) , y luego fueron nombrados cubos parciales. Kuzmin & Ovchinnikov (1975) y Falmagne & Doignon (1997) , entre otros , siguieron una línea de investigación separada sobre las mismas estructuras, en la terminología de familias de conjuntos en lugar de etiquetas de hipercubo de gráficos . [2]
Ejemplos de
Cada árbol es un cubo parcial. Para, suponga que un árbol T tiene m aristas, y numere estas aristas (arbitrariamente) de 0 am - 1. Elija un vértice raíz r para el árbol, arbitrariamente, y etiquete cada vértice v con una cadena de m bits que tenga un 1 en la posición i siempre borde i se encuentra en el camino de r a v en T . Por ejemplo, r en sí mismo tendrá una etiqueta que es todo cero bits, sus vecinos tendrán etiquetas con un solo 1 bit, etc. Entonces la distancia de Hamming entre dos etiquetas cualesquiera es la distancia entre los dos vértices en el árbol, entonces esto el etiquetado muestra que T es un cubo parcial.
Cada gráfico de hipercubo es en sí mismo un cubo parcial, que se puede etiquetar con todas las diferentes cadenas de bits de longitud igual a la dimensión del hipercubo.
Los ejemplos más complejos incluyen los siguientes:
- Considere el gráfico cuyas etiquetas de vértice consisten en todas las cadenas de bits de dígitos (2 n + 1) posibles que tienen n o n + 1 bits distintos de cero, donde dos vértices son adyacentes siempre que sus etiquetas difieren en un solo bit. Este etiquetado define una incrustación de estos gráficos en un hipercubo (el gráfico de todas las cadenas de bits de una longitud determinada, con la misma condición de adyacencia) que resulta preservar la distancia. El gráfico resultante es un gráfico de Kneser bipartito ; la gráfica así formada con n = 2 tiene 20 vértices y 30 aristas, y se denomina gráfica de Desargues .
- Todas las gráficas de medianas son cubos parciales. [3] Los árboles y los gráficos de hipercubo son ejemplos de gráficos de mediana. Dado que las gráficas de la mediana incluyen las gráficas cuadradas , las gráficas simplex y los cubos de Fibonacci , así como las gráficas de cobertura de las celosías distributivas finitas , todos estos son cubos parciales.
- El gráfico dual plano de una disposición de líneas en el plano euclidiano es un cubo parcial. De manera más general, para cualquier disposición de hiperplano en el espacio euclidiano de cualquier número de dimensiones, el gráfico que tiene un vértice para cada celda de la disposición y un borde para cada dos celdas adyacentes es un cubo parcial. [4]
- Un cubo parcial en la que cada vértice tiene exactamente tres vecinos se conoce como un cúbico cubo parcial. 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 gráfico plano es el gráfico de Desargues. [5]
- El gráfico subyacente de cualquier antimatroide , que tiene un vértice para cada conjunto en el antimatroide y un borde 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 borde completo del gráfico se subdivide en una ruta de dos bordes, o hay un vértice de gráfico completo cuyos bordes incidentes no están subdivididos y todos los bordes no incidentes se han subdividido. en caminos de longitud uniforme. [7]
La relación Djoković-Winkler
Muchos de los teoremas sobre cubos parciales se basan directa o indirectamente en una determinada relación binaria definida en los bordes del gráfico. Esta relación, descrita por primera vez por Djoković (1973) y dada una definición equivalente en términos de distancias por Winkler (1984) , se denota por . Dos aristas y se definen para estar en la relación , escrito , Si . Esta relación es reflexiva y simétrica , pero en general no es transitiva .
Winkler demostró que una gráfica conectada es un cubo parcial si y solo si es bipartita y la relación es transitivo. [8] En este caso, forma una relación de equivalencia y cada clase de equivalencia separa dos subgrafos conectados del gráfico 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 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.
Reconocimiento
Pueden reconocerse cubos parciales y construirse una etiqueta de Hamming, en tiempo, donde es el número de vértices del gráfico. [9] Dado un cubo parcial, es sencillo construir las clases de equivalencia de la relación Djoković-Winkler haciendo una primera búsqueda en amplitud de cada vértice, en tiempo total; laEl algoritmo de reconocimiento de tiempo lo acelera mediante el uso de paralelismo a nivel de bits para realizar búsquedas de amplitud múltiples primero 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 es un etiquetado 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 puede estar incrustado isométricamente, y es igual al número de clases de equivalencia de la relación Djoković-Winkler. Por ejemplo, la dimensión isométrica de un-árbol de vértice es su número de aristas, . La incrustación de un cubo parcial en un hipercubo de esta dimensión es única, hasta las simetrías del hipercubo. [10]
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 celosía de un gráfico es la dimensión mínima de un entramado de números enteros en el que el gráfico se puede incrustar isométricamente. La dimensión de la celosía 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 número entero más cercano). La dimensión de celosía de cualquier gráfico, y una incrustación de celosía de dimensión mínima, se pueden encontrar en tiempo polinomial mediante un algoritmo basado en la coincidencia máxima en un gráfico 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 gráficos en hipercubos tienen una aplicación importante en la teoría de gráficos químicos . Un gráfico bencenoide es un gráfico que consta de todos los vértices y aristas que se encuentran en y en el interior de un ciclo en una red hexagonal . Estos gráficos son los gráficos moleculares de los hidrocarburos bencenoides , una gran clase de moléculas orgánicas. Cada gráfico de este tipo es un cubo parcial. Se puede usar un etiquetado de Hamming de dicho gráfico para calcular el índice de Wiener de la molécula correspondiente, que luego se puede usar para predecir algunas de sus propiedades químicas. [13]
Una estructura molecular diferente formada a partir de carbono, el diamante cúbico , también forma gráficos de cubos parciales. [14]
Notas
- ^ Ovchinnikov (2011) , Definición 5.1, p. 127.
- ^ Ovchinnikov (2011) , p. 174.
- ^ Ovchinnikov (2011) , Sección 5.11, "Gráficos de mediana", págs. 163-165.
- ^ Ovchinnikov (2011) , Capítulo 7, "Arreglos de hiperplano", 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, "Unicidad de las incrustaciones isométricas", págs. 157-162.
- ^ Hadlock y Hoffman (1978) ; Eppstein (2005) ; Ovchinnikov (2011) , Capítulo 6, "Incrustaciones de celosía", 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 el índice de Wiener", págs. 165-168.
- ^ Eppstein (2009) .
Referencias
- Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), " Embeddings isométricos de gráficos completos subdivididos en el hipercubo" (PDF) , SIAM Journal on Discrete Mathematics , 22 (3): 1226-1238, doi : 10.1137 / 070681909 , MR 2424849
- 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.
- 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 CS1 maint: parámetro desalentado ( enlace ).
- Eppstein, David (2006), "Cubos parciales cúbicos de arreglos simples " , Electronic Journal of Combinatorics , 13 (1), R79, arXiv : math.CO/0510263 CS1 maint: parámetro desalentado ( enlace ).
- Eppstein, David (2008), "Reconocimiento de cubos parciales en tiempo cuadrático", Proc. XIX Simposio ACM-SIAM sobre algoritmos discretos , págs. 1258-1266, arXiv : 0705.1025 , Bibcode : 2007arXiv0705.1025E CS1 maint: parámetro desalentado ( enlace ).
- Eppstein, David (2009), "Subgrafos de diamantes isométricos", Proc. 16o Simposio Internacional sobre Dibujo de Gráficos, Heraklion, Creta, 2008 , Lecture Notes in Computer Science, 5417 , Springer-Verlag, págs. 384–389, arXiv : 0807.2218 , doi : 10.1007 / 978-3-642-00219-9_37 CS1 maint: parámetro desalentado ( enlace ).
- Falmagne, J.-C. ; Doignon, J.-P. (1997), "Evolución estocástica de la racionalidad", Teoría y decisión , 43 : 107-138, doi : 10.1023 / A: 1004981430688.
- 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. 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áticas discretas y optimización, Nueva York: John Wiley & Sons, ISBN 978-0-471-37039-0, Señor 1788124.
- Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Etiquetado de sistemas benzenoides que refleja 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 los 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. Consulte especialmente el Capítulo 5, "Partial Cubes", págs. 127-181.
- Winkler, Peter M. (1984), "Integración isométrica en productos de gráficos completos", Matemáticas aplicadas discretas , 7 (2): 221-225, doi : 10.1016 / 0166-218X (84) 90069-6 , MR 0727925 CS1 maint: parámetro desalentado ( enlace ).