Número de cola

En el campo matemático de la teoría de grafos , el número de cola de un grafo es un invariante de grafo definido de forma análoga al número de pila (grosor del libro) utilizando ordenamientos de primero en entrar, primero en salir (cola) en lugar de ordenamientos de último en entrar, primero en salir (pila).

La disposición en colas de un grafo dado se define mediante un ordenamiento total de los vértices del grafo junto con una partición de las aristas en varias "colas". El conjunto de aristas en cada cola debe evitar aristas anidadas correctamente: si ab y cd son dos aristas en la misma cola, entonces no debería ser posible tener a < c < d < b en el ordenamiento de vértices. El número de colas qn( G ) de un grafo G es el número mínimo de colas en una disposición en colas. ^{[ 1 ]}

De forma equivalente, a partir de una disposición de cola, se podrían procesar las aristas en una sola cola utilizando una estructura de datos de cola , considerando los vértices en su orden dado y, al llegar a un vértice, desencolando todas las aristas para las que es el segundo extremo, seguido de encolando todas las aristas para las que es el primer extremo. La condición de anidamiento garantiza que, cuando se llega a un vértice, todas las aristas para las que es el segundo extremo estén listas para ser desencoladas. ^{[ 1 ]} Otra definición equivalente de disposiciones de cola implica incrustaciones del grafo dado en un cilindro , con los vértices colocados en una línea en el cilindro y con cada arista dando una vuelta completa alrededor del cilindro. Las aristas que están asignadas a la misma cola no pueden cruzarse entre sí, pero se permiten cruces entre aristas que pertenecen a diferentes colas. ^{[ 2 ]}

Heath y Rosenberg (1992) definieron diseños de colas por analogía con trabajos previos sobre incrustaciones de grafos en libros , que pueden definirse de la misma manera utilizando pilas en lugar de colas. Como observaron, estos diseños también están relacionados con trabajos anteriores sobre permutaciones de ordenación mediante sistemas de colas paralelas, y pueden estar motivados por aplicaciones en el diseño VLSI y en la gestión de comunicaciones para algoritmos distribuidos . ^{[ 1 ]}

Cada árbol tiene un número de cola de 1, con un ordenamiento de vértices dado por un recorrido en anchura . ^{[ 3 ]} Los pseudobosques y los grafos de cuadrícula también tienen un número de cola de 1. ^{[ 4 ]} Los grafos outerplanares tienen un número de cola de como máximo 2; el grafo 3-sun (un triángulo con cada una de sus aristas reemplazada por un triángulo) es un ejemplo de un grafo outerplanar cuyo número de cola es exactamente  2. ^{[ 5 ]} Los grafos serie-paralelo tienen un número de cola de como máximo  3, ^{[ 6 ]} mientras que el número de cola de los 3-árboles planares es de como máximo 5. ^{[ 7 ]}

Los grafos binarios de De Bruijn tienen número de cola  2. ^{[ 8 ]} El grafo hipercubo d -dimensional tiene número de cola como máximo${\displaystyle d-\lfloor \log _{2}d\rfloor }$. ^{[ 9 ]} Los números de cola de los grafos completos K _n y los grafos bipartitos completos K _{a , b} se conocen exactamente: son${\displaystyle \lfloor n/2\rfloor }$y${\displaystyle \min\{\lceil a/2\rceil ,\lceil b/2\rceil \}}$ respectivamente. ^{[ 10 ]}

Cada grafo de 1 cola es un grafo planar , con una incrustación planar "nivelada arqueada" en la que los vértices se colocan en líneas paralelas (niveles) y cada arista conecta vértices en dos niveles consecutivos o forma un arco que conecta dos vértices en el mismo nivel al recorrer todos los niveles anteriores. Por el contrario, cada grafo planar nivelado arqueado tiene una disposición de 1 cola. ^{[ 11 ]} En 1992, Heath, Leighton y Rosenberg (1992) conjeturaron que cada grafo planar tiene un número de cola acotado. Esta conjetura fue resuelta positivamente en 2019 por Dujmović et al. (2020) quienes demostraron que los grafos planares y, más generalmente, cada clase propia cerrada de grafos tiene un número de cola acotado. En particular, Dujmović et al. (2020) demostraron que el número de colas de los grafos planares es como máximo 49, una cota que fue reducida a 42 por Bekos, Gronemann y Raftopoulou (2021) .

Utilizando una variación del número de cola denominada número de cola fuerte, el número de cola de un producto de grafos puede acotarse mediante una función de los números de cola y los números de cola fuertes de los factores del producto. ^{[ 12 ]}

Los grafos con un número de cola bajo son grafos dispersos : los grafos de 1 cola con n vértices tienen como máximo 2 n – 3 aristas, ^{[ 13 ]} y, más generalmente, los grafos con número de cola q tienen como máximo 2 qn – q (2 q + 1) aristas. ^{[ 14 ]} Esto implica que estos grafos también tienen un número cromático pequeño : en particular, los grafos de 1 cola son 3-coloreables, y los grafos con número de cola q pueden necesitar al menos 2 q + 1 y como máximo 4 q colores. ^{[ 14 ]} En la otra dirección, una cota en el número de aristas implica una cota mucho más débil en el número de cola: los grafos con n vértices y m aristas tienen como máximo un número de cola ${\displaystyle O({\sqrt {m}})}$⁠ . ^{[ 15 ]} Esta cota es casi ajustada, porque para grafos d -regulares aleatorios el número de cola es, con alta probabilidad ,

${\displaystyle \Omega \left({\frac {\sqrt {dn}}{n^{1/d}}}\right).}$^{[ 16 ]}

Los grafos con número de cola 1 tienen un grosor de libro como máximo 2. ^{[ 17 ]} Para cualquier orden de vértices fijo, el producto del grosor del libro y los números de cola para ese orden es al menos tan grande como el ancho de corte del grafo dividido por su grado máximo. ^{[ 18 ]} El grosor del libro puede ser mucho mayor que el número de cola: los grafos de Hamming ternarios tienen un número de cola logarítmico pero un grosor de libro polinomialmente grande ^{[ 18 ]} y hay grafos con número de cola 4 que tienen un grosor de libro arbitrariamente grande. ^{[ 17 ]} Heath, Leighton y Rosenberg (1992) conjeturaron que el número de cola es como máximo una función lineal del grosor del libro, pero no se conoce ninguna cota funcional en esta dirección. Se sabe que, si todos los grafos bipartitos con incrustaciones de libro de 3 páginas tienen un número de cola acotado, entonces todos los grafos con grosor de libro acotado tienen un número de cola acotado. ^{[ 19 ]}

Ganley y Heath (2001) se preguntaron si el número de colas de un grafo podía estar acotado en función de su ancho de árbol , y citaron una tesis doctoral inédita de SV Pemmaraju como evidencia de que la respuesta era no: según esta evidencia , los 3-árboles planares parecían tener un número de colas ilimitado. Sin embargo, posteriormente se demostró que el número de colas estaba acotado por una función (doblemente exponencial) del ancho de árbol. ^{[ 20 ]} Desde entonces, se ha demostrado que los grafos planares, y por lo tanto los 3-árboles planares, tienen un número de colas acotado por una constante. ^{[ 21 ]}

Es NP-completo determinar el número de cola de un grafo dado, o incluso comprobar si este número es 1. ^{[ 22 ]}

Sin embargo, si el orden de los vértices de una disposición de colas se proporciona como parte de la entrada, entonces el número óptimo de colas para la disposición es igual al número máximo de aristas en un k -arcoíris , un conjunto de k aristas, cada dos de las cuales forman un par anidado. Se puede realizar una partición de aristas en colas asignando una arista e que sea la arista exterior de un i -arcoíris (y de ningún arcoíris mayor) a la i -ésima cola. Es posible construir una disposición óptima en tiempo O ( m log(log n )) , donde n denota el número de vértices del grafo de entrada y m denota el número de aristas. ^{[ 23 ]}

Los grafos con número de colas limitado también tienen expansión limitada , lo que significa que sus menores poco profundos son grafos dispersos con una relación de aristas a vértices (o equivalentemente degeneración o arboricidad ) limitada por una función del número de colas y la profundidad del menor. Como consecuencia, varios problemas algorítmicos, incluido el isomorfismo de subgrafos para grafos de patrones de tamaño limitado, tienen algoritmos de tiempo lineal para estos grafos. ^{[ 24 ]} De manera más general, debido a su expansión limitada, es posible comprobar si cualquier sentencia en la lógica de primer orden de los grafos es válida para un grafo dado con número de colas limitado, en tiempo lineal. ^{[ 25 ]}

Aunque las disposiciones de colas no necesariamente producen buenos dibujos de grafos bidimensionales , se han utilizado para dibujar grafos tridimensionales. En particular, una clase de grafos X tiene un número de colas acotado si y solo si para cada grafo G de n vértices en X , es posible colocar los vértices de G en una cuadrícula tridimensional de dimensiones O ( n ) × O (1) × O (1) de modo que no haya dos aristas (cuando se dibujan rectas) que se crucen entre sí. ^{[ 26 ]} Así, por ejemplo, los grafos de De Bruijn , los grafos de ancho de árbol acotado, los grafos planares y las familias de grafos cerrados por menores propios tienen incrustaciones tridimensionales de volumen lineal. ^{[ 27 ] [ 28 ] [ 29 ]}

• Diseños de pilas y colas Archivados el 2 de abril de 2015 en Wayback Machine , Problemas presentados en el verano de 2009, Experiencias de investigación para estudiantes de posgrado, Douglas B. West