Número de colas de gráfico

El número de colas de gráficos es un gráfico invariable , definido de manera similar al número de pila (grosor del libro) y utilizando el orden FIFO (primero en entrar, primero en salir, cola) en lugar del orden LIFO (último en entrar, primero en salir, pila).

Definición

La representación gráfica en forma de colas (queue layout) para un gráfico dado está determinada por la ordenación completa de los vértices del gráfico , junto con la descomposición de los bordes del gráfico en varias "colas". Se requiere que el conjunto de aristas de cada cola no esté anidado por orden de vértices en el sentido de que si ab y cd son dos aristas en la misma cola, entonces no debe haber a < c < d < b . El número de colas qn( G ) del grafo G es el número mínimo de colas para representar el grafo como colas [1] .

Usando el diseño de la cola del gráfico, es posible enumerar los bordes de una sola cola usando la estructura de cola estándar iterando sobre los vértices en un orden dado y cuando lleguemos a un vértice, seleccione todos los bordes para los cuales el vértice es el segundo vértice. del arco y poner en cola los arcos cuyo vértice es el primero. La condición de no anidamiento asegura que cuando se alcanza un vértice, todos los bordes que tienen ese vértice como terminal están en la cola y listos para ser captados. La descomposición de un gráfico en colas con las propiedades descritas puede considerarse una definición alternativa [1] . Otra definición equivalente de diseño de colas utiliza la noción de incrustar un gráfico dado en un cilindro con vértices ubicados en una línea que está en la superficie del cilindro, y cada borde envuelve el cilindro. Los bordes incluidos en la misma cola no deben cruzarse, pero se permiten las intersecciones de bordes de diferentes colas [2] .

El diseño de las colas fue definido por Heath y Rosenberg [1] por analogía con trabajos previos sobre incrustaciones de gráficos en libros, que se definen de la misma manera usando pilas en lugar de colas. Como señalaron, estos diseños también están relacionados con trabajos anteriores sobre la clasificación de permutaciones mediante colas paralelas. El diseño de la cola fue motivado por los requisitos del diseño de circuitos integrados y la gestión de comunicaciones en algoritmos distribuidos [1] .

Clases de grafos con un número limitado de colas

Cualquier árbol tiene un conteo de cola de 1 con el orden de los vértices dado por la búsqueda en anchura [3] . Los pseudobosques y las celosías también tienen un recuento de cola de 1 [4] . El número de colas de gráficos de planos exteriores es como máximo 2. Un gráfico 3 solar (un triángulo con cada borde reemplazado por un triángulo) es un ejemplo de un gráfico de planos exteriores cuyo número de colas es exactamente 2 [5] [6] . El número de colas de un grafo secuencial paralelo no excede de 3 [6] .

El número de colas para gráficos binarios de Bruijn es 2 [7] . El número de colas en un gráfico de un hipercubo d -dimensional no excede d − 1 [8] . El número de colas de gráficos completos K n y gráficos bipartitos completos K a , b se conoce exactamente: es igual a y respectivamente [9] .

Problemas no resueltos en Matemáticas : ¿Todo gráfico plano tiene un número finito de colas?

Cualquier gráfico con una cola es un gráfico plano con una incrustación plana de "nivel de arco", en el que los vértices están en líneas paralelas (niveles), y cada borde conecta los vértices de dos niveles adyacentes o forma un arco que conecta dos vértices en el mismo nivel. Por el contrario, cualquier gráfico plano de nivel de arco tiene un diseño de cola única [10] . Heath, Layton y Rosenberg [5] sugirieron que cualquier gráfico plano tiene un número limitado de colas, pero aún no hay confirmación de esta afirmación. Si el número de colas de grafos planos es limitado, lo mismo es cierto para grafos 1-planares y, además, para grafos k - planares [11] . El límite más fuerte conocido para el número de colas en gráficos planos no es una constante, es igual a O (log n ) [12] Los límites polilogarítmicos en el número de colas se conocen para gráficos con género acotado y gráficos más generales de menormente cerrados. familias [13] .

Si usamos una variante del número de colas llamada "número fuerte de colas", el número de colas del producto de grafos puede estar limitado por una función del número de colas y el número estricto de colas de factores del producto [14] .

Invariantes relacionados

Los gráficos con un pequeño número de colas son escasos : los gráficos con n vértices y una cola no tienen más de 2 n  − 3 aristas [15] , y los gráficos más generales con  q colas no tienen más de 2 qn − q (2 q + 1 ) bordes [16] . De ello se deduce que estos gráficos tienen un número cromático pequeño . En particular, los gráficos con una cola tienen una coloración de 3 colores, y los gráficos con q colas pueden requerir al menos 2 q + 1 y como máximo 4 q colores [16] . Por el contrario, el límite del número de aristas implica un límite inferior en el número de colas de gráficos: el número de colas para gráficos con n vértices y m aristas no supera O (√ m ) [17] . El límite es casi estricto, ya que para gráficos d -regulares aleatorios, el número de colas con alta probabilidad es [5] [18]

Problemas no resueltos en matemáticas : ¿Debería cualquier gráfico con un número limitado de colas tener un grosor de libro limitado y viceversa?

Los gráficos con una cola tienen un ancho de libro que no excede dos [5] . Para cualquier orden fijo de vértices, el producto del grosor del libro y el número de colas para ese orden de vértices es al menos el ancho de la sección del gráfico dividido por el grado máximo de vértices [5] . El grosor de un libro puede ser mucho mayor que el número de colas: los gráficos ternarios de Hamming tienen un número logarítmico de colas, pero un grosor polinomial de libros [5] . Se desconoce si el grosor del libro está limitado por alguna función del número de colas. Heath, Leighton y Rosenberg [5] sugirieron que el número de colas es, como mucho, lineal con el grosor de los libros, pero no se han hecho progresos en esta dirección. Se sabe que si todos los gráficos bipartitos con incrustaciones de libros de 3 páginas tienen un número limitado de colas, entonces todos los gráficos con un grosor de libro limitado tienen un número limitado de colas [11] .

Ganley y Heath 19] preguntaron si el número de colas en un gráfico está limitado por una función de su ancho de árbol , y citaron una disertación inédita de S. V. Sin embargo, se ha demostrado que el número de colas está limitado por una función (doblemente exponencial) del ancho del árbol [20]

Complejidad computacional

Determinar el número de colas en un gráfico es un problema NP-completo . Incluso comprobar que el número de colas es igual a uno es NP-completo [21] .

Sin embargo, si el orden de los vértices está predeterminado, entonces el número óptimo de colas es igual al número máximo de aristas en un arco iris k , un conjunto de aristas k , cada par de las cuales tiene una arista anidada dentro de otra (en el sentido descrito arriba). La división de los bordes en colas se puede realizar incluyendo el borde e , que es el borde exterior del i -rainbow (pero no el arcoíris más grande) en la i -ésima cola. Es posible construir un diseño óptimo en tiempo O ( m log log n ) , donde n es el número de vértices del gráfico y m es el número de aristas [22] .

Los gráficos enlazados a cola también tienen una expansión limitada , lo que significa que sus menores superficiales son gráficos dispersos con una proporción de borde a vértice (o, de manera equivalente, degeneración o arborescencia ) limitada por una función del número de colas y la profundidad del menor. Como consecuencia, algunos problemas algorítmicos, incluido el problema de isomorfismo de gráficos para gráficos de tamaño acotado, tienen algoritmos de tiempo lineal para tales gráficos [23] [24] . De manera más general, debido a la extensión acotada, se puede verificar en tiempo lineal si una declaración lógica de primer orden es verdadera para un gráfico con un número acotado de colas [25] .

Aplicación en la visualización de gráficos

Aunque los diseños de cola no necesariamente brindan buenas visualizaciones en 2D , se utilizan para representar gráficos en 3D. En particular, un grafo G tiene un número acotado de colas si y solo si es posible ordenar los vértices del grafo G en una red tridimensional de tamaño O ( n ) × O (1) × O (1) en de tal manera que no se crucen dos bordes [26] Por ejemplo, los gráficos de Bruijn y los gráficos de ancho de árbol acotado tienen un volumen lineal tridimensional incrustado [27] [28] .

Los límites logarítmicos o polilogarítmicos en el número de colas se transforman con tales inversiones en redes tridimensionales en volúmenes casi lineales, la red en una dirección tendrá un tamaño lineal y en las otras dos, polilogarítmica. Los gráficos planos, los gráficos con género acotado y los gráficos con ancho de árbol local acotado tienen incrustaciones de tamaño O ( n log n ) [12] , mientras que los gráficos de familias cerradas menores tienen tamaño O ( n log O (1) n ) [13 ] .

Notas

  1. ↑ 1 2 3 4 Heath, Rosenberg, 1992 .
  2. ↑ Auer, Bachmaier, Brandeburgo, Brunner, 2011 .
  3. ↑ Heath y Rosenberg 1992 , pág. Proposición 4.1.
  4. ↑ Heath y Rosenberg 1992 , pág. Proposiciones 4.2, 4.3.
  5. ↑ 1 2 3 4 5 6 7 Heath, Leighton, Rosenberg, 1992 .
  6. ↑ 1 2 Rengarajan, Veni Madhavan, 1995 .
  7. ↑ Heath y Rosenberg 1992 , pág. Proposición 4.6.
  8. ↑ Heath, Rosenberg, 1992 , Proposición 4.10; Hasunuma, Hirota, 2007 ; Pai, Chang, Wang, 2008 ; Gregor, Škrekovski, Vukašinović, 2011 .
  9. ↑ Heath y Rosenberg 1992 , pág. Proposiciones 4.7, 4.8.
  10. ↑ Heath y Rosenberg 1992 , pág. Teorema 3.2.
  11. ↑ 1 2 Dujmovic, Wood, 2005 .
  12. ↑ 1 2 Dujmović ( Dujmović 2015 ), una mejora en el límite anterior de Di Battista, Frati y Pach ( Di Battista, Frati, Pach 2013 ).
  13. ↑ 1 2 Dujmovic, Morin, Wood, 2013 .
  14. ↑ Madera, 2005 .
  15. ↑ Heath y Rosenberg 1992 , pág. Teorema 3.6.
  16. ↑ 1 2 Dujmovic, Wood, 2004 .
  17. ↑ Heath, Leighton, Rosenberg, 1992 . Shahrokhi y Shi ( Shahrokhi, Shi 2000 ) proporcionaron un algoritmo de tiempo polinomial para encontrar un diseño con cerca de este número de colas . Dujmovic y Wood ( Dujmović, Wood 2004 ) mejoraron la constante en este límite a e √ m , donde e es la base del logaritmo natural .
  18. ↑ Madera, 2008 .
  19. ↑ Ganley, Heath, 2001 .
  20. ↑ Dujmovic, Madera, 2003 ; Dujmovic, Morin, Wood, 2005 . Consulte Wood 2002 para obtener un resultado preliminar más débil que limita el número de colas por ancho de ruta o una combinación de ancho de árbol y grado de gráfico.
  21. ↑ Heath y Rosenberg 1992 , pág. Corolario 3.9.
  22. ↑ Heath y Rosenberg 1992 , pág. Teorema 2.3.
  23. ↑ Nešetřil, Ossona de Méndez, Wood, 2012 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 321–327.
  25. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 401, Teorema 18.2.
  26. ↑ Madera, 2002 ; Dujmović, Por, Wood, 2004 ; Dujmovic, Morin, Wood, 2005 . Consulte Di Giacomo, Meijer, 2004 para conocer límites más estrictos en las dimensiones de la cuadrícula para gráficos de números de cola pequeños.
  27. ↑ Dujmovic, Madera, 2003 .
  28. ↑ Dujmovic, Morin, Wood, 2005 .

Literatura

Enlaces