En teoría de grafos , un gráfico de arco circular es el gráfico de intersección de un conjunto de arcos en el círculo. Tiene un vértice para cada arco del conjunto y una arista entre cada par de vértices correspondiente a los arcos que se cruzan.
Formalmente, deja
ser un conjunto de arcos. Entonces el gráfico de arco circular correspondiente es G = ( V , E ) donde
y
Una familia de arcos que corresponde a G se llama modelo de arco .
Reconocimiento
Tucker (1980) demostró el primer algoritmo de reconocimiento de polinomios para gráficos de arco circular, que se ejecuta enhora. McConnell (2003) dio la primera algoritmo de reconocimiento de tiempo, donde es el número de aristas. Más recientemente, Kaplan y Nussbaum [1] desarrollaron un algoritmo de reconocimiento de tiempo lineal más simple.
Relación con otras clases de gráficos
Los gráficos de arco circular son una generalización natural de los gráficos de intervalo . Si un gráfico de arco circular G tiene un modelo de arco que deja al descubierto algún punto del círculo, el círculo se puede cortar en ese punto y estirarlo en una línea, lo que da como resultado una representación de intervalo. Sin embargo, a diferencia de los gráficos de intervalo, los gráficos de arco circular no siempre son perfectos , ya que los ciclos impares sin cuerda C 5 , C 7 , etc., son gráficos de arco circular.
Algunas subclases
A continuación, dejemos ser un gráfico arbitrario.
Gráficos unitarios de arco circular
es un gráfico de arco circular unitario si existe un modelo de arco correspondiente tal que cada arco tiene la misma longitud.
El número de gráficos de arco circular unitarios etiquetados en n vértices viene dado por. [2]
Gráficos de arco circular adecuados
es un gráfico de arco circular adecuado (también conocido como gráfico de intervalo circular ) [3] si existe un modelo de arco correspondiente de modo que ningún arco contenga otro correctamente. El reconocimiento de estos gráficos y la construcción de un modelo de arco adecuado se pueden realizar de forma lineal.hora. [4] Forman una de las subclases fundamentales de los gráficos sin garras . [3]
Gráficos de arco circular Helly
es un gráfico de arco circular de Helly si existe un modelo de arco correspondiente tal que los arcos constituyen una familia de Helly . Gavril (1974) da una caracterización de esta clase que implica una algoritmo de reconocimiento.
Joeris y col. (2009) dan otras caracterizaciones de esta clase, que implican un algoritmo de reconocimiento que se ejecuta en tiempo O (n + m) cuando la entrada es un gráfico. Si el gráfico de entrada no es un gráfico de arco circular de Helly, el algoritmo devuelve un certificado de este hecho en forma de un subgrafo inducido prohibido. También proporcionaron un algoritmo de tiempo O (n) para determinar si un modelo de arco circular dado tiene la propiedad Helly.
Aplicaciones
Los gráficos de arco circular son útiles para modelar problemas de asignación de recursos periódicos en la investigación de operaciones . Cada intervalo representa una solicitud de un recurso durante un período específico repetido en el tiempo.
Notas
- ^ Kaplan, Haim; Nussbaum, Yahav (1 de noviembre de 2011). "Un reconocimiento de tiempo lineal más simple de gráficos de arco circular". Algoritmica . 61 (3): 694–737. CiteSeerX 10.1.1.76.2480 . doi : 10.1007 / s00453-010-9432-y . ISSN 0178-4617 .
- ^ Alexandersson, Per; Panova, Greta (diciembre de 2018). "Polinomios LLT, funciones cuasimétricas cromáticas y gráficas con ciclos". Matemáticas discretas . 341 (12): 3453–3482. arXiv : 1705.10353 . doi : 10.1016 / j.disc.2018.09.001 .
- ^ a b Descrito con una definición diferente pero equivalente por Chudnovsky y Seymour (2008) .
- ^ Deng, Hell y Huang (1996) pág. ?
Referencias
- Chudnovsky, Maria ; Seymour, Paul (2008), "Gráficos sin garras. III. Gráficos de intervalo circular" (PDF) , Journal of Combinatorial Theory , Serie B, 98 (4): 812–834, doi : 10.1016 / j.jctb.2008.03. 001 , MR 2418774.
- Deng, Xiaotie; Infierno, Pavol ; Huang, Jing (1996), "Algoritmos de representación de tiempo lineal para gráficos de arco circular adecuados y gráficos de intervalo adecuados", SIAM Journal on Computing , 25 (2): 390–403, doi : 10.1137 / S0097539792269095.
- Gavril, Fanica (1974), "Algoritmos sobre gráficos de arco circular", Redes , 4 (4): 357–369, doi : 10.1002 / net.3230040407.
- Golumbic, Martin Charles (1980), Teoría algorítmica de gráficos y gráficos perfectos , Academic Press, ISBN 978-0-444-51530-8, archivado desde el original el 22 de mayo de 2010 , consultado el 21 de mayo de 2008. Segunda edición, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Joeris, Benson L .; Lin, Min Chih; McConnell, Ross M .; Spinrad, Jeremy P .; Szwarcfiter, Jayme L. (2009), "Reconocimiento en tiempo lineal de modelos y gráficos de arco circular Helly", Algorithmica , 59 (2): 215-239, CiteSeerX 10.1.1.298.3038 , doi : 10.1007 / s00453-009- 9304-5.
- McConnell, Ross (2003), "Reconocimiento en tiempo lineal de gráficos de arco circular", Algorithmica , 37 (2): 93–147, CiteSeerX 10.1.1.22.4725 , doi : 10.1007 / s00453-003-1032-7.
- Tucker, Alan (1980), "Una prueba eficiente para gráficos de arco circular", SIAM Journal on Computing , 9 (1): 1–24, doi : 10.1137 / 0209001.
enlaces externos
- Gráfico de arco circular , sistema de información sobre inclusiones de clases de gráficos