En la teoría de grafos , una incrustación de libros es una generalización de la incrustación plana de un gráfico a incrustaciones en un libro , una colección de semiplanos que tienen la misma línea que su límite. Por lo general, se requiere que los vértices del gráfico se encuentren en esta línea límite, llamada columna vertebral , y los bordes deben permanecer dentro de un solo medio plano. El grosor del libro de un gráfico es el número más pequeño posible de semiplanos para cualquier libro incrustado en el gráfico. El grosor del libro también se denomina número de página , número de pila o espesor fijo. Las incrustaciones de libros también se han utilizado para definir varios otros invariantes de gráficos, incluido el ancho de página y el número de cruce de libros.
Cada gráfico con n vértices tiene un grosor de libro como máximo, y esta fórmula proporciona el grosor exacto del libro para gráficos completos . Las gráficas con grosor de libro uno son las gráficas planas externas . Las gráficas con grosor de libro como máximo dos son las gráficas subhamiltonianas , que siempre son planas ; más generalmente, cada gráfico plano tiene un grosor de libro como máximo cuatro. Todas las familias de gráficos cerrados menores , y en particular los gráficos con ancho de árbol limitado o género limitado , también tienen grosor de libro limitado. Es NP-difícil determinar el grosor exacto del libro de un gráfico dado, con o sin conocer un vértice fijo ordenado a lo largo del lomo del libro.
Una de las motivaciones originales para estudiar incrustaciones de libros involucraba aplicaciones en el diseño VLSI , en el cual los vértices de una incrustación de libros representan componentes de un circuito y los cables representan conexiones entre ellos. La incrustación de libros también tiene aplicaciones en el dibujo de gráficos , donde se pueden construir dos de los estilos de visualización estándar para gráficos, diagramas de arco y diseños circulares mediante incrustaciones de libros.
En la planificación del transporte , las diferentes fuentes y destinos del tráfico peatonal y de vehículos que se encuentran e interactúan en un semáforo se pueden modelar matemáticamente como los vértices de un gráfico, con bordes que conectan diferentes pares fuente-destino. Se puede usar un libro incrustado de este gráfico para diseñar un cronograma que permita que todo el tráfico se mueva a través de la intersección con la menor cantidad de fases de señal posible. En los problemas bioinformáticos que involucran la estructura de plegamiento del ARN , las incrustaciones de libros de una página representan formas clásicas de estructura secundaria de ácido nucleico , y las incrustaciones de libros de dos páginas representan pseudonudos . Otras aplicaciones de incrustaciones de libros incluyen álgebra abstracta y teoría de nudos .
Hay varios problemas abiertos relacionados con el grosor del libro. Se desconoce si el grosor del libro de un gráfico arbitrario puede estar limitado por una función del grosor del libro de sus subdivisiones . Probar la existencia de una incrustación de un gráfico en un libro de tres páginas, dado un orden fijo de los vértices a lo largo de la columna vertebral de la incrustación, tiene una complejidad computacional desconocida: no se sabe que sea solucionable en tiempo polinómico ni se sepa que es NP-hard . Y, aunque cada gráfico plano tiene un grosor máximo de cuatro libros, se desconoce si existe un gráfico plano cuyo grosor sea exactamente cuatro.
Historia [ editar ]
La noción de un libro, como espacio topológico, fue definida por CA Persinger y Gail Atneosen en la década de 1960. [1] [2] Como parte de este trabajo, Atneosen ya consideró incrustaciones de gráficos en libros. Las incrustaciones que estudió utilizaron la misma definición que las incrustaciones de gráficos en cualquier otro espacio topológico: los vértices están representados por puntos distintos, los bordes están representados por curvas y la única forma en que dos bordes pueden cruzarse es que se encuentren en un punto final común.
A principios de la década de 1970, Paul C. Kainen y L. Taylor Ollmann desarrollaron un tipo de inclusión más restringido que se utilizó en la mayoría de las investigaciones posteriores. En su formulación, los vértices del gráfico deben colocarse a lo largo del lomo del libro, y cada borde debe estar en una sola página. [3] [4] Los hitos importantes en el desarrollo posterior de las incrustaciones de libros incluyen la prueba de Mihalis Yannakakis a fines de la década de 1980 de que los gráficos planos tienen un grosor máximo de cuatro libros, [5] [6] y el descubrimiento a finales de la década de 1990 de cierre conexiones entre incrustaciones de libros y bioinformática . [7]
Definiciones [ editar ]
Un libro es un tipo particular de espacio topológico , también llamado fanático de los semiplanos. [1] [8] Consiste en una sola línea ℓ , llamada columna vertebral o parte posterior del libro, junto con una colección de uno o más medios planos , llamados páginas u hojas del libro, [9] cada uno con el columna vertebral como su límite. Los libros con un número finito de páginas se pueden incrustar en un espacio tridimensional, por ejemplo, eligiendo ℓ para ser el eje z de unSistema de coordenadas cartesianas y elección de las páginas para que sean los semiplanos k cuyo ángulo diédrico con respecto al plano xz es un múltiplo entero de 2 π / k . [10]
Un dibujo de libro de un gráfico finito G sobre un libro B es un dibujo de G en B de modo que cada vértice de G se dibuja como un punto en la columna vertebral de B , y cada borde de G se dibuja como una curva que se encuentra dentro de un una sola página de B . El número de cruce de libro de k páginas de G es el número mínimo de cruces en un dibujo de libro de k páginas. [11]
Un libro incrustación de G a B es un libro de dibujo que forma un gráfico de la incorporación de G en B . Es decir, es un dibujo de libro de G en B que no tiene ningún cruce de bordes. Cada gráfico finito tiene un libro incrustado en un libro con un número suficientemente grande de páginas. Por ejemplo, siempre es posible incrustar cada borde del gráfico en su propia página separada. El grosor del libro , el número de pieza o el número de pila de G es el número mínimo de páginas requeridas para una incrustación de libro de G. Otro parámetro que mide la calidad de la incrustación de un libro, más allá de su número de páginas, es su ancho de página . Este es el número máximo de bordes que puede atravesar un rayo perpendicular a la columna en una sola página. De manera equivalente (para las incrustaciones de libros en las que cada borde se dibuja como una curva monotónica), es el tamaño máximo de un subconjunto de bordes dentro de una sola página, de modo que los intervalos definidos en el lomo por pares de puntos finales de los bordes se cruzan entre sí. . [12] [13] [14]
Es crucial para estas definiciones que los bordes solo puedan permanecer dentro de una sola página del libro. Como ya observó Atneosen, si los bordes pueden pasar de una página a otra a través del lomo del libro, entonces cada gráfico puede incrustarse en un libro de tres páginas. [15] [2] [16] Para una incrustación de libros topológicos de tres páginas en la que se permiten los cruces de columna, cada gráfico se puede incrustar como máximo con un número logarítmico de cruces de columna por borde, [15] y algunos gráficos necesitan esto Muchos cruces de columna. [17]
Gráficos específicos [ editar ]
Como se muestra en la primera figura, el grosor del libro del gráfico completo K 5 es tres: como gráfico no plano, el grosor de su libro es mayor que dos, pero existe un libro incrustado con tres páginas. En términos más generales, el grosor del libro de cada gráfico completo con n ≥ 4 vértices es exactamente. Este resultado también proporciona un límite superior en el grosor de libro máximo posible de cualquier gráfico n- vértice. [10]
El número de cruce de dos páginas del gráfico completo K n es
coincidir con una conjetura aún no probada de Anthony Hill sobre cuál debería ser el número de cruce sin restricciones de este gráfico. Es decir, si la conjetura de Hill es correcta, entonces el dibujo de este gráfico que minimiza el número de cruces es un dibujo de dos páginas. [18]
El grosor del libro del gráfico bipartito completo K a , b es como máximo min ( a , b ) . Para construir un dibujo con el grosor de este libro, para cada vértice en el lado más pequeño de la bipartición, uno puede colocar los bordes incidentes con ese vértice en su propia página. Este límite no siempre es apretado; por ejemplo, K 4,4 tiene un grosor de libro de tres, no cuatro. Sin embargo, cuando los dos lados del gráfico están muy desequilibrados, con b > a ( a - 1) , el grosor del libro de K a , b es exactamente a .[10] [19]
Para el gráfico T de Turán ( kr , r ) (un gráfico multipartito completo K k , k , ... formado a partir de r conjuntos independientes de k vértices por conjunto independiente, con un borde entre cada dos vértices de diferentes conjuntos independientes) el grosor del libro t se intercala entre
y cuando r es impar, el límite superior se puede mejorar a
El grosor del libro de gráficos binarios de Bruijn , gráficos de intercambio aleatorio y ciclos conectados en cubos (cuando estos gráficos son lo suficientemente grandes como para no ser planos) es exactamente tres. [21]
Propiedades [ editar ]
Planaridad y exterioridad [ editar ]
El grosor del libro de un gráfico dado G es como máximo uno si y solo si G es un gráfico plano exterior . Un gráfico plano externo es un gráfico que tiene una incrustación plana en la que todos los vértices pertenecen a la cara externa de la incrustación. Para tal gráfico, colocar los vértices en el mismo orden a lo largo de la columna vertebral a medida que aparecen en la cara externa proporciona una incrustación de libro de una página del gráfico dado. (Un punto de articulacióndel gráfico necesariamente aparecerá más de una vez en el orden cíclico de los vértices alrededor de la cara externa, pero solo una de esas copias debe incluirse en la incrustación de libros.) Por el contrario, una incrustación de libros de una página es automáticamente una incrustación de planos externos. Por ejemplo, si un gráfico está incrustado en una sola página y otro medio plano está unido a la columna para extender su página a un plano completo, entonces la cara externa de la incrustación incluye todo el semiplano agregado, y todos los vértices se encuentran en esta cara exterior [10] [12]
Cada incrustación de libros de dos páginas es un caso especial de una incrustación plana, porque la unión de dos páginas de un libro es un espacio topológicamente equivalente a todo el plano. Por lo tanto, cada gráfico con un grosor de libro dos es automáticamente un gráfico plano . Más precisamente, el grosor del libro de un gráfico G es como máximo dos si y solo si G es un subgrafo de un gráfico plano que tiene un ciclo hamiltoniano . [10] Si a un gráfico se le incrusta dos páginas, se puede aumentar a un gráfico hamiltoniano plano agregando (en cualquier página) bordes adicionales entre dos vértices consecutivos a lo largo de la columna vertebral que no son adyacentes, y entre los primeros y los últimos vértices de la columna vertebral. losEl gráfico Goldner-Harary proporciona un ejemplo de un gráfico plano que no tiene un grosor de libro dos: es un gráfico plano máximo , por lo que no es posible agregarle bordes mientras se conserva la planaridad, y no tiene un ciclo hamiltoniano. [10] Debido a esta caracterización por ciclos hamiltonianos, los gráficos que tienen incrustaciones de libros de dos páginas también se conocen como gráficos subhamiltonianos . [12]
 | Problema no resuelto en matemáticas :
¿Cuál es el grosor máximo de libro de un gráfico plano?
(Más problemas no resueltos en matemáticas) |
Todos los gráficos planos cuyo grado máximo es como máximo cuatro tienen grosor de libro como máximo dos. [22] Los 3 árboles planos tienen un grosor máximo de tres libros. [23] Más generalmente, todos los gráficos planos tienen un grosor de libro como máximo cuatro. [5] [6] Mihalis Yannakakis ha afirmado en 1986 [6] que existen algunos gráficos planos que tienen un grosor de libro exactamente cuatro. Sin embargo, una prueba detallada de esta afirmación, anunciada en un artículo posterior de la revista, [5] nunca se ha publicado. Por esta razón, Dujmović y Wood (2007) enumeran el problema de determinar el grosor máximo de libro de los gráficos planos como aún sin resolver. [24]
Comportamiento bajo subdivisiones [ editar ]
| Problema no resuelto en matemáticas :
¿Puede el grosor del libro de un gráfico estar limitado por una función del grosor del libro de su subdivisión?
(Más problemas no resueltos en matemáticas) |
Subdividir cada borde de un gráfico en trazados de dos bordes, agregando nuevos vértices dentro de cada borde, a veces puede aumentar el grosor de su libro. Por ejemplo, el gráfico de diamante tiene un grosor de libro uno (es plano exterior) pero su subdivisión tiene un grosor de libro dos (es plano y subhamiltoniano pero no plano exterior). Sin embargo, este proceso de subdivisión también a veces puede reducir significativamente el grosor del libro del gráfico subdividido. Por ejemplo, el grosor del libro del gráfico completo K n es proporcional a su número de vértices, pero subdividir cada uno de sus bordes en una ruta de dos bordes produce una subdivisión cuyo grosor del libro es mucho más pequeño, solo. [25] A pesar de la existencia de ejemplos como este, Blankenship y Oporowski (1999) conjeturaron que el grosor del libro de una subdivisión no puede ser mucho más pequeño que el del gráfico original. Específicamente, conjeturaron que existe una función f tal que, para cada gráfico G y para el gráfico H formado reemplazando cada borde en G por una ruta de dos bordes, si el grosor del libro de H es t, entonces el grosor del libro de G es a lo sumo f ( t ) . [16] A partir de 2013, la conjetura de Blankenship-Oporowskipermanece sin probar. [26]
Relación con otros invariantes de grafos [ editar ]
El grosor del libro está relacionado con el grosor , el número de gráficos planos necesarios para cubrir los bordes del gráfico dado. Un gráfico G tiene un grosor θ si se puede dibujar en el plano, y sus bordes se colorean con θ colores, de tal manera que los bordes del mismo color que el otro no se crucen. De manera análoga, un gráfico G tiene un grosor de libro θ si se puede dibujar en un medio plano , con sus vértices en el límite del medio plano, con sus bordes coloreados con θcolores sin cruce entre dos bordes del mismo color. En esta formulación del grosor del libro, los colores de los bordes corresponden a las páginas de la incrustación del libro. Sin embargo, el grosor y el grosor del libro pueden ser muy diferentes entre sí: existen gráficos ( subdivisiones de gráficos completos ) que tienen un grosor de libro ilimitado, [25] [15] [16] a pesar de tener un grosor dos. [25]
Los gráficos de ancho de árbol k tienen un grosor de libro como máximo k + 1 [24] [27] y este límite es ajustado para k > 2 . [24] Los gráficos con m bordes tienen grosor de libro, [28] y gráficos del género g tienen grosor de libro. [29] Más generalmente, cada familia de grafos cerrados menores tiene un grosor de libro limitado. [30] [31] Por otro lado, los gráficos de 1 plano , que no están cerrados bajo menores, [30] también han limitado el grosor del libro, [32] pero algunos gráficos de 1 plano incluyendo K 2,2,2, 2 tienen un espesor de libro de al menos cuatro. [33]
Cada menor superficial de un gráfico de grosor de libro limitado es un gráfico escaso , cuya relación de bordes a vértices está limitada por una constante que depende solo de la profundidad del menor y del grosor del libro. Es decir, en la terminología de Nešetřil y Ossona de Méndez (2012) , las gráficas del grosor del libro limitado tienen una expansión limitada . [30] Sin embargo, incluso los gráficos de grado acotado , un requisito mucho más fuerte que tener una expansión acotada, pueden tener un grosor de libro ilimitado. [34]
Debido a que las gráficas del grosor del libro dos son gráficas planas, obedecen el teorema del separador plano : tienen separadores, subconjuntos de vértices cuya eliminación divide la gráfica en pedazos con un máximo de 2 n / 3 vértices cada uno, con solovértices en el separador. Aquí, n se refiere al número de vértices en el gráfico. Sin embargo, existen gráficos de grosor de libro tres que no tienen separadores de tamaño sublineal. [35]
Los bordes dentro de una sola página de la incrustación de un libro se comportan de alguna manera como una estructura de datos de pila . Esto se puede formalizar considerando una secuencia arbitraria de operaciones push y pop en una pila, y formando un gráfico en el que las operaciones de pila corresponden a los vértices del gráfico, colocados en orden de secuencia a lo largo del lomo de una incrustación de libros. Luego, si uno dibuja un borde de cada operación emergente que saca un objeto x de la pila, a la operación de inserción previa que empujó x , el gráfico resultante automáticamente tendrá una incrustación de una página. Por esta razón, el número de página de un gráfico también se ha llamado su número de pila . De la misma manera, uno puede considerar una secuencia arbitraria de operaciones en cola y en cola de uncoloque en cola la estructura de datos y forme un gráfico que tenga estas operaciones como sus vértices, colocados en orden en el lomo de una sola página, con un borde entre cada operación en cola y la cola correspondiente. Luego, en este gráfico, cada dos bordes se cruzarán o cubrirán intervalos separados en la columna vertebral. Por analogía, los investigadores han definido una incrustación en la cola de un gráfico como una incrustación en un libro topológico de modo que cada vértice se encuentra en la columna vertebral, cada borde se encuentra en una sola página y cada dos bordes en la misma página se cruzan o se disuelven intervalos en la columna vertebral. El número mínimo de páginas necesarias para la incrustación en cola de un gráfico se denomina número de cola . [30] [36] [37]
Complejidad computacional [ editar ]
Encontrar el grosor del libro de un gráfico es NP-difícil . Esto se deduce del hecho de que encontrar ciclos hamiltonianos en gráficos planos máximos es NP-completo . En un gráfico plano máximo, el grosor del libro es dos si y solo si existe un ciclo hamiltoniano. Por lo tanto, también es NP-complete probar si el grosor del libro de un gráfico plano máximo dado es dos. [38]
Si se arregla un orden de los vértices de un gráfico a lo largo de la columna vertebral de una incrustación, entonces se puede encontrar una incrustación de dos páginas (si existe) en tiempo lineal , como una instancia de prueba de planaridad para un gráfico formado al aumentar el dado gráfico con un ciclo que conecta los vértices en su ordenamiento de la columna. [7] Unger (1992) afirmó que encontrar incrustaciones de tres páginas con un orden fijo de columna también se puede realizar en tiempo polinómico, aunque su descripción de este resultado omite muchos detalles. [39] Sin embargo, para gráficos que requieren cuatro o más páginas, el problema de encontrar una incrustación con el mínimo número posible de páginas sigue siendo NP-hard, a través de una equivalencia al problema NP-hard de colorear gráficos circulares , los gráficos de intersección de acordes de un círculo . Dado un gráfico G con un ordenamiento columna fija por sus vértices, dibujo estos vértices en el mismo orden alrededor de un círculo y el dibujo de los bordes de G como segmentos de línea produce una colección de acordes que representan G . Entonces se puede formar un gráfico circular que tiene los acordes de este diagrama como vértices y pares de acordes cruzados como bordes. Una coloración del gráfico circular representa una partición de los bordes de Gen subconjuntos que se pueden dibujar sin cruzar en una sola página. Por lo tanto, una coloración óptima es equivalente a una incrustación óptima de libros. Dado que la coloración del gráfico circular con cuatro o más colores es NP-hard, y dado que cualquier gráfico circular se puede formar de esta manera a partir de algún problema de incrustación de libros, se deduce que la incrustación óptima de libros también es NP-hard. [40] [41] [42] Para un orden de vértice fijo en el lomo de un dibujo de libro de dos páginas, también es NP-difícil minimizar el número de cruces cuando este número no es cero. [41]
Si se desconoce el orden del lomo pero se da una partición de los bordes en dos páginas, entonces es posible encontrar una incrustación de 2 páginas (si existe) en tiempo lineal mediante un algoritmo basado en árboles SPQR . [43] [44] Sin embargo, es NP-completo encontrar una incrustación de 2 páginas cuando no se conoce el orden del lomo ni la partición del borde. Encontrar el número de cruce de libro de un gráfico también es NP-difícil, debido a la integridad de NP del caso especial de probar si el número de cruce de 2 páginas es cero.
Como consecuencia de la expansión limitada, el problema del isomorfismo del subgrafo , de encontrar si existe un gráfico de patrón de tamaño acotado como un subgrafo de un gráfico más grande, puede resolverse en tiempo lineal cuando el gráfico más grande tiene un grosor de libro acotado. Lo mismo es cierto para detectar si el gráfico de patrón es un subgrafo inducido del gráfico más grande, o si tiene un homomorfismo gráfico con el gráfico más grande. [45] [46] Por la misma razón, el problema de probar si un gráfico de grosor de libro acotado obedece a una fórmula dada de lógica de primer orden es manejable con parámetros fijos . [47]
Bekos, Kaufmann y Zielke (2015) describen un sistema para encontrar incrustaciones óptimas de libros transformando el problema en una instancia del problema de satisfacción booleana y aplicando un solucionador SAT al problema resultante. Afirman que su sistema es capaz de encontrar una incrustación óptima para gráficos planos máximos de 400 vértices en aproximadamente 20 minutos, y que se aplicó con éxito a un gráfico de 600 vértices que Yannakakis había propuesto que requería cuatro páginas, pero que resultó ser Requiere solo tres páginas. [33]
Aplicaciones [ editar ]
Multiprocesamiento tolerante a fallas [ editar ]
Una de las principales motivaciones para estudiar la incrustación de libros citada por Chung, Leighton y Rosenberg (1987) implica una aplicación en el diseño VLSI , a la organización de multiprocesadores tolerantes a fallas . En el sistema DIOGENES desarrollado por estos autores, las CPU de un sistema multiprocesador están dispuestas en una secuencia lógica correspondiente al lomo de un libro (aunque esta secuencia no necesariamente se puede colocar a lo largo de una línea en el diseño físico de este sistema). Los enlaces de comunicación que conectan estos procesadores se agrupan en "paquetes" que corresponden a las páginas de un libro y actúan como pilas: la conexión de uno de los procesadores al inicio de un nuevo enlace de comunicaciones empuja todos los enlaces anteriores hacia arriba en el paquete, y la conexión de otro procesador al final de un enlace de comunicación lo conecta al que está en la parte inferior del paquete y muestra todos los enlaces otros abajo. Debido a este comportamiento de la pila, un solo paquete puede manejar un conjunto de enlaces de comunicaciones que forman los bordes de una sola página en una incrustación de libros. Al organizar los enlaces de esta manera, se puede implementar una amplia variedad de topologías de red diferentes, independientemente de qué procesadores se hayan vuelto defectuosos, siempre y cuando haya suficientes procesadores no defectuosos para implementar la red. Las topologías de red que puede implementar este sistema son exactamente las que tienen un grosor de libro como máximo igual al número de paquetes disponibles.[38] La incrustación de libros también puede usarse para modelar la colocación de cables que conectan componentes VLSI en las capas de un circuito. [48]
Clasificación de pila [ editar ]
Otra aplicación citada por Chung, Leighton y Rosenberg (1987) se refiere a la clasificación de permutaciones utilizando pilas . Un resultado influyente de Donald Knuth ( 1968 ) demostró que un sistema que procesa un flujo de datos empujando los elementos entrantes a una pila y luego, en los momentos elegidos adecuadamente, sacándolos de la pila a un flujo de salida puede ordenar los datos si y solo si su orden inicial se describe mediante una permutación que evita el patrón de permutación 231. [49]Desde entonces, se ha trabajado mucho en problemas similares de clasificación de flujos de datos por sistemas más generales de pilas y colas. En el sistema considerado por Chung, Leighton y Rosenberg (1987) , cada elemento de un flujo de datos de entrada debe insertarse en una de varias pilas. Luego, una vez que todos los datos se han enviado de esta manera, los elementos se extraen de estas pilas (en un orden apropiado) en una secuencia de salida. Como Chung et al. observe, una permutación dada puede clasificarse por este sistema si y solo si un determinado gráfico, derivado de la permutación, tiene un libro incrustado con los vértices en un cierto orden fijo a lo largo de la columna vertebral y con una cantidad de páginas como máximo a la cantidad de pilas. [38]
Control de tráfico [ editar ]
Como describió Kainen (1990) , se puede usar una incrustación de libros para describir las fases de una señal de tráficoen una intersección controlada. En una intersección, los carriles de tráfico entrantes y salientes (incluidos los extremos de los cruces peatonales y los carriles para bicicletas, así como los carriles para vehículos de motor) pueden representarse como los vértices de un gráfico, colocados en el lomo de un libro incrustado en el sentido de las agujas del reloj. orden alrededor de la unión. Los caminos a través de la intersección tomada por el tráfico para llegar desde un carril entrante a un carril saliente pueden representarse como los bordes de un gráfico no dirigido. Por ejemplo, este gráfico puede tener un borde de un carril de tráfico entrante a uno saliente que ambos pertenecen al mismo segmento de la carretera, representando un giro en U desde ese segmento de regreso a ese segmento, solo si se permiten giros en U en el unión. Para un subconjunto dado de estos bordes, el subconjunto representa una colección de caminos que pueden atravesarse sin interferencia entre sí si y solo si el subconjunto no incluye ningún par de bordes que se cruzarían si los dos bordes se colocan en una sola página de un libro incrustado. Por lo tanto, un libro incrustado de este gráfico describe una partición de las rutas en subconjuntos que no interfieren, y el grosor del libro de este gráfico (con su incrustación fija en el lomo) proporciona el número mínimo de fases distintas necesarias para un programa de señalización que incluye todas las posibles rutas de tráfico a través del cruce.[50]
Dibujo gráfico [ editar ]
La incrustación de libros también se ha aplicado con frecuencia en la visualización de datos de red. Dos de los diseños estándar en dibujo gráfico , diagramas de arco [51] y diseños circulares, [52] pueden verse como incrustaciones de libros, y la incrustación de libros también se ha aplicado en la construcción de diseños agrupados, [43] incrustaciones simultáneas, [53 ] y dibujos de gráficos tridimensionales. [54]
Un diagrama de arco [51] o incrustación lineal [41] coloca los vértices de un gráfico a lo largo de una línea y dibuja los bordes del gráfico como semicírculos sobre o debajo de esta línea, a veces también permite dibujar bordes en segmentos de la línea. Este estilo de dibujo corresponde a un libro incrustado con una página (si todos los semicírculos están por encima de la línea) o dos páginas (si se usan ambos lados de la línea), y se introdujo originalmente como una forma de estudiar los números cruzados de gráficos. [55] [56]Los gráficos planos que no tienen incrustaciones de libros de dos páginas también se pueden dibujar de manera similar, permitiendo que sus bordes estén representados por múltiples semicírculos encima y debajo de la línea. Tal dibujo no es una incrustación de libros según la definición habitual, sino que se ha denominado incrustación de libros topológicos . [57] Para cada gráfico plano, siempre es posible encontrar una incrustación de este tipo en la que cada borde cruza la columna como máximo una vez. [58]
En otro estilo de dibujo, el diseño circular , los vértices de un gráfico se colocan en un círculo y los bordes se dibujan dentro o fuera del círculo. [52] Una vez más, una ubicación de los bordes dentro del círculo (por ejemplo, como segmentos de línea recta) corresponde a un dibujo de libro de una página, mientras que una ubicación tanto dentro como fuera del círculo corresponde a un dibujo de libro de dos páginas. [59]
Para los dibujos de una página de cualquier estilo, es importante mantener el número de cruces pequeño como una forma de reducir el desorden visual del dibujo. Minimizar el número de cruces es NP-completo , [41] pero puede aproximarse con una relación de aproximación de O (log 2 n ) donde n es el número de vértices. [60] Minimizar el número de cruce de una o dos páginas es manejable con parámetros fijos cuando se parametriza por el número ciclomático del gráfico dado, o por una combinación del número de cruce y el ancho del árbol del gráfico. [61] [62]También se han ideado métodos heurísticos para reducir la complejidad del cruce, basados, por ejemplo, en un orden de inserción de vértices cuidadoso y en la optimización local . [52]
Las incrustaciones de libros de dos páginas con una partición fija de los bordes en páginas se pueden interpretar como una forma de planaridad agrupada , en la que el gráfico dado debe dibujarse de tal manera que se coloquen partes del gráfico (los dos subconjuntos de bordes) en el dibujo de una manera que refleje su agrupación. [43] La incrustación de libros de dos páginas también se ha utilizado para encontrar incrustaciones simultáneas de gráficos, en los que dos gráficos se dan en el mismo conjunto de vértices y uno debe encontrar una ubicación para los vértices en los que ambos gráficos se dibujan de forma plana con bordes rectos. [53]
Las incrustaciones de libros con más de dos páginas también se han utilizado para construir dibujos tridimensionales de gráficos. En particular, Wood (2002) utilizó una construcción para incrustaciones de libros que mantiene bajo el grado de cada vértice dentro de cada página, como parte de un método para incrustar gráficos en una cuadrícula tridimensional de bajo volumen. [54]
ARN plegado [ editar ]
En el estudio de cómo las moléculas de ARN se pliegan para formar su estructura, la forma estándar de la estructura secundaria de ácido nucleico puede describirse esquemáticamente como una cadena de bases (la secuencia de ARN en sí), dibujada a lo largo de una línea, junto con una colección de arcos sobre el línea que describe los pares de bases de la estructura. Es decir, aunque estas estructuras en realidad tienen una forma tridimensional complicada, su conectividad (cuando existe una estructura secundaria) puede describirse mediante una estructura más abstracta, una incrustación de libros de una página. Sin embargo, no todos los pliegues de ARN se comportan de esta manera simple. Haslinger y Stadler (1999) han propuesto una llamada "estructura bi-secundaria" para ciertos pseudonudos de ARNque toma la forma de una incrustación de libros de dos páginas: la secuencia de ARN se dibuja nuevamente a lo largo de una línea, pero los pares de bases se dibujan como arcos tanto encima como debajo de esta línea. Para formar una estructura bi-secundaria, un gráfico debe tener un grado máximo como máximo tres: cada base solo puede participar en un arco del diagrama, además de los dos enlaces a sus vecinos en la secuencia de bases. Las ventajas de esta formulación incluyen el hecho de que excluye estructuras que en realidad están anudadas en el espacio y que coincide con los pseudonudos de ARN más conocidos. [7]
Debido a que el orden de la columna vertebral se conoce de antemano para esta aplicación, la prueba de la existencia de una estructura bi-secundaria para un emparejamiento de bases dado es sencilla. El problema de asignar bordes a las dos páginas de manera compatible puede formularse como una instancia de satisfacción de 2 o como un problema de probar la bipartita del gráfico circular cuyos vértices son los pares de bases y cuyos bordes describen los cruces entre pares de bases. [7] Alternativamente y de manera más eficiente, como muestran Haslinger y Stadler (1999) , existe una estructura bi-secundaria si y solo si el gráfico del diagramade la entrada (un gráfico formado conectando las bases en un ciclo en su orden de secuencia y agregando los pares de bases dados como bordes) es un gráfico plano . [7] Esta caracterización permite que las estructuras bi-secundarias sean reconocidas en tiempo lineal como una instancia de prueba de planaridad .
Blin y col. (2007) utilizaron la conexión entre las estructuras secundarias y las incorporaciones de libros como parte de una prueba de la dureza NP de ciertos problemas en la comparación de estructuras secundarias de ARN. [63] Y si una estructura de ARN es terciaria en lugar de bi-secundaria (es decir, si requiere más de dos páginas en su diagrama), entonces determinar el número de página es NP-hard nuevamente. [64]
Teoría de la complejidad computacional [ editar ]
Pavan, Tewari y Vinodchandran (2012) utilizaron la incrustación de libros para estudiar la teoría de la complejidad computacional del problema de accesibilidad en gráficos dirigidos . Como han observado, la accesibilidad para gráficos dirigidos de dos páginas puede resolverse en un espacio logarítmico inequívoco (el análogo, para la complejidad del espacio logarítmico , de la clase UP de problemas de tiempo polinómico inequívoco). Sin embargo, la accesibilidad para gráficos dirigidos de tres páginas requiere toda la potencia del espacio logarítmico no determinista . Por lo tanto, las incrustaciones de libros parecen estar íntimamente relacionadas con la distinción entre estas dos clases de complejidad. [sesenta y cinco]
La existencia de gráficos expansores con número de página constante [35] es el paso clave para demostrar que no existe una simulación de tiempo subcuadrático de máquinas Turing no deterministas de dos cintas por máquinas Turing no deterministas de una cinta. [66]
Otras áreas de las matemáticas [ editar ]
McKenzie y Overbay (2010) estudian aplicaciones de grosor de libros en álgebra abstracta , utilizando gráficos definidos a partir de los divisores cero de un anillo local finito al hacer un vértice para cada divisor cero y un borde para cada par de valores cuyo producto es cero. [67]
No hay comentarios:
Publicar un comentario