Gráfico circular
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Para ver el gráfico, consulte Gráfico circular .
Un círculo con cinco cuerdas y el gráfico circular correspondiente.

En la teoría de grafos , un gráfico circular es el gráfico de intersección de un diagrama de cuerdas . Es decir, es un grafo no dirigido cuyos vértices se pueden asociar a un sistema finito de cuerdas de un círculo de manera que dos vértices son adyacentes si y solo si las cuerdas correspondientes se cruzan entre sí.

Complejidad algorítmica

Spinrad (1994) proporciona un algoritmo de tiempo O ( n 2 ) que prueba si un gráfico no dirigido de n- vértices dado es un gráfico circular y, si lo es, construye un conjunto de cuerdas que lo representa.

Varios otros problemas que son NP-completos en gráficos generales tienen algoritmos de tiempo polinomial cuando se restringen a gráficos circulares. Por ejemplo, Kloks (1996) mostró que se puede determinar el ancho de árbol de un gráfico circular y construir una descomposición óptima del árbol en un tiempo O ( n 3 ). Además, un relleno mínimo (es decir, un gráfico cordal con el menor número posible de aristas que contiene el gráfico circular dado como un subgráfico) se puede encontrar en el tiempo O ( n 3 ). [1] Tiskin (2010) ha demostrado que una camarilla máximo de un gráfico de círculo se puede encontrar en O ( n log 2 n) tiempo, mientras que Nash y Gregg (2010) han demostrado que un conjunto máximo independiente de un gráfico circular no ponderado se puede encontrar en O ( n min { d , α }) tiempo, donde d es un parámetro del gráfico conocido como su densidad. y α es el número de independencia del gráfico circular.

Sin embargo, también hay problemas que permanecen NP-completos cuando se restringen a gráficos circulares. Estos incluyen el conjunto dominante mínimo, el conjunto dominante mínimo conectado y los problemas de conjunto dominante mínimo total. [2]

Número cromático

Los acordes que forman el gráfico circular libre de triángulos cromáticos de 220 vértices y 5 de Ageev (1996) , dibujados como una disposición de líneas en el plano hiperbólico .

El número cromático de un gráfico circular es el número mínimo de colores que se pueden usar para colorear sus acordes de modo que no haya dos acordes cruzados del mismo color. Dado que es posible formar gráficos circulares en los que conjuntos de cuerdas arbitrariamente grandes se cruzan entre sí, el número cromático de un gráfico circular puede ser arbitrariamente grande, y determinar el número cromático de un gráfico circular es NP-completo. [3] Queda NP-completo probar si un gráfico circular se puede colorear con cuatro colores. [4] Unger (1992) afirmó que encontrar una coloración con tres colores se puede hacer en tiempo polinomial, pero su redacción de este resultado omite muchos detalles. [5]

Varios autores han investigado los problemas de colorear subclases restringidas de gráficos circulares con pocos colores. En particular, para gráficos circulares en los que ningún conjunto de k o más acordes se cruzan entre sí, es posible colorear el gráfico con tan solo colores. Una forma de decir esto es que las gráficas circulares están limitadas . [6] En el caso particular cuando k  = 3 (es decir, para gráficos circulares sin triángulos ) el número cromático es como máximo cinco, y esto es ajustado: todos los gráficos circulares sin triángulos se pueden colorear con cinco colores, y no existen gráficos circulares sin triángulos que requieren cinco colores. [7] Si un gráfico circular tiene circunferenciaal menos cinco (es decir, no tiene triángulos y no tiene ciclos de cuatro vértices) se puede colorear con un máximo de tres colores. [8] El problema de colorear gráficos cuadrados sin triángulos es equivalente al problema de representar gráficos cuadrados como subgráficos isométricos de productos cartesianos de árboles ; en esta correspondencia, el número de colores en la coloración corresponde al número de árboles en la representación del producto. [9]

Aplicaciones

Surgen gráficas circulares en VLSI diseño físico como una representación abstracta de un caso especial para el enrutamiento de alambre , conocida como "de dos terminales de conmutación de encaminamiento ". En este caso, el área de enrutamiento es un rectángulo, todas las redes son de dos terminales y los terminales se colocan en el perímetro del rectángulo. Se ve fácilmente que el gráfico de intersección de estas redes es un gráfico circular. [10] Entre los objetivos de la etapa de encaminamiento de alambre es asegurar que las diferentes redes permanecen desconectados eléctricamente, y sus partes de intersección potenciales deben ser dispuestas en diferentes capas conductoras. Por lo tanto, los gráficos circulares capturan varios aspectos de este problema de enrutamiento.

Los colorantes de gráficos circulares también se pueden usar para encontrar incrustaciones de libros de gráficos arbitrarios: si los vértices de un gráfico dado G están dispuestos en un círculo, con los bordes de G formando cuerdas del círculo, entonces la gráfica de intersección de estos acordes es una El gráfico circular y los colores de este gráfico circular son equivalentes a las incrustaciones de libros que respetan el diseño circular dado. En esta equivalencia, el número de colores en la coloración corresponde al número de páginas del libro incrustado. [4]

Clases de grafos relacionados

Un sistema de intervalos con cinco intervalos y el gráfico de superposición correspondiente.

Un gráfico es un gráfico circular si y solo si es el gráfico superpuesto de un conjunto de intervalos en una línea. Este es un gráfico en el que los vértices corresponden a los intervalos, y dos vértices están conectados por un borde si los dos intervalos se superponen, sin que ninguno contenga al otro.

El gráfico de intersección de un conjunto de intervalos en una línea se llama gráfico de intervalo .

Los gráficos de cadena , los gráficos de intersección de curvas en el plano, incluyen los gráficos circulares como un caso especial.

Cada gráfico hereditario de distancia es un gráfico circular, al igual que todo gráfico de permutación y todo gráfico de indiferencia . Cada gráfico del plano exterior es también un gráfico circular. [11]

Los gráficos circulares se generalizan mediante los gráficos polígono-círculo , gráficos de intersección de polígonos, todos inscritos en el mismo círculo. [12]

Notas

  1. ^ Kloks, Kratsch y Wong (1998) .
  2. ^ Keil (1993)
  3. ^ Garey y col. (1980) .
  4. ↑ a b Unger (1988) .
  5. ^ Unger (1992) .
  6. ^ Davies y McCarty (2021) . Para límites anteriores, ver Černý (2007) , Gyárfás (1985) , Kostochka (1988) y Kostochka & Kratochvíl (1997) .
  7. ↑ Véase Kostochka (1988) para el límite superior y Ageev (1996) para el límite inferior correspondiente. Karapetyan (1984) y Gyárfás y Lehel (1985) dan límites más débiles anteriores al mismo problema.
  8. ^ Ageev (1999) .
  9. ^ Bandelt, Chepoi y Eppstein (2010) .
  10. ^ Naveed Sherwani, "Algoritmos para la automatización del diseño físico VLSI"
  11. ^ Wessel y Pöschel (1985) ; Unger (1988) .
  12. ^ "Gráfico circular" , Sistema de información sobre clases de gráficos y sus inclusiones

Referencias

  • Ageev, AA (1996), "Un gráfico circular sin triángulos con número cromático 5", Matemáticas discretas , 152 (1-3): 295-298, doi : 10.1016 / 0012-365X (95) 00349-2.
  • Ageev, AA (1999), "Cada gráfico circular de circunferencia de al menos 5 es tricolor", Matemáticas discretas , 195 (1-3): 229-233, doi : 10.1016 / S0012-365X (98) 00192-7.
  • Bandelt, H.-J .; Chepoi, V .; Eppstein, D. (2010), "Combinatoria y geometría de gráficos cuadrados finitos e infinitos", SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301.
  • Černý, Jakub (2007), "Colorear gráficos circulares", Electronic Notes in Discrete Mathematics , 29 : 357–361, doi : 10.1016 / j.endm.2007.07.072.
  • Davies, James; McCarty, Rose (2021), "Las gráficas circulares están cuadráticamente acotadas por χ", Boletín de la London Mathematical Society , 53 (3): 673–679, arXiv : 1905.11578 , doi : 10.1112 / blms.12447 , MR  4275079.
  • Garey, MR ; Johnson, DS ; Miller, GL ; Papadimitriou, C. (1980), "La complejidad de colorear arcos circulares y acordes", SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216-227, doi : 10.1137 / 0601025.
  • Gyárfás, A. (1985), "Sobre el número cromático de gráficos de intervalo múltiple y gráficos superpuestos", Matemáticas discretas , 55 (2): 161-166, doi : 10.1016 / 0012-365X (85) 90044-5. Como lo cita Ageev (1996) .
  • Gyárfás, A .; Lehel, J. (1985), "Problemas de cobertura y coloración para parientes de intervalos", Matemáticas discretas , 55 (2): 167–180, doi : 10.1016 / 0012-365X (85) 90045-7. Como lo cita Ageev (1996) .
  • Karapetyan, A. (1984), On perfect arc and chord intersection graphs , Ph.D. tesis (en ruso), Inst. de Matemáticas, Novosibirsk. Como lo cita Ageev (1996) .
  • Keil, J. Mark (1993), "La complejidad de los problemas de dominación en gráficos circulares", Matemáticas aplicadas discretas , 42 (1): 51–63, doi : 10.1016 / 0166-218X (93) 90178-Q.
  • Kloks, Ton (1996), "Treewidth of Circle Graphs", Int. J. Encontrado. Computación. Sci. , 7 (2): 111–120, doi : 10.1142 / S0129054196000099.
  • Kloks, T .; Kratsch, D .; Wong, CK (1998), "Relleno mínimo en gráficos circulares y de arco circular", Journal of Algorithms , 28 (2): 272-289, doi : 10.1006 / jagm.1998.0936.
  • Kostochka, AV (1988), "Límites superiores del número cromático de gráficos", Trudy Instituta Mathematiki (en ruso), 10 : 204–226, MR  0945704. Como lo cita Ageev (1996) .
  • Kostochka, AV; Kratochvíl, J. (1997), "Cubrir y colorear gráficos poligonales-circulares", Matemáticas discretas , 163 (1-3): 299-305, doi : 10.1016 / S0012-365X (96) 00344-5.
  • Nash, Nicholas; Gregg, David (2010), "Un algoritmo sensible a la salida para calcular un conjunto máximo independiente de un gráfico circular", Information Processing Letters , 116 (16): 630–634, doi : 10.1016 / j.ipl.2010.05.016 , hdl : 10344/2228.
  • Spinrad, Jeremy (1994), "Reconocimiento de gráficos circulares", Journal of Algorithms , 16 (2): 264-282, doi : 10.1006 / jagm.1994.1012.
  • Tiskin, Alexander (2010), "Multiplicación a distancia rápida de matrices unitarias de Monge", Actas de ACM-SIAM SODA 2010 , págs. 1287–1296.
  • Unger, Walter (1988), "On the k -colouring of circle-graphs", STACS 88: 5to Simposio anual sobre aspectos teóricos de la informática, Burdeos, Francia, 11 al 13 de febrero de 1988, Actas , Notas de conferencias en informática , 294 , Berlín: Springer, págs. 61–72, doi : 10.1007 / BFb0035832.
  • Unger, Walter (1992), "La complejidad de colorear gráficos circulares", STACS 92: Noveno Simposio anual sobre aspectos teóricos de la informática, Cachan, Francia, 13-15 de febrero de 1992, Actas , Lecture Notes in Computer Science, 577 , Berlín: Springer, págs. 389–400, doi : 10.1007 / 3-540-55210-3_199.
  • Wessel, W .; Pöschel, R. (1985), "On circle graphs", en Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory celebrada en Eyba, 1 al 5 de octubre de 1984 , Teubner-Texte zur Mathematik, 73 , BG Teubner, págs. 207–210. Como lo cita Unger (1988) .
Obtenido de " https://en.wikipedia.org/w/index.php?title=Circle_graph&oldid=1052171394 "
Contribute a better translation