Gráfico de arco circular

Gráfico de intersección para un conjunto de arcos en un círculo.

Un gráfico de arco circular (izquierda) y un modelo de arco correspondiente (derecha).

En teoría de grafos , una gráfica de arco circular es la gráfica de intersección de un conjunto de arcos en el círculo. Tiene un vértice para cada arco del conjunto y un borde entre cada par de vértices correspondiente a los arcos que se cruzan.

Formalmente, dejemos

${\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}$

ser un conjunto de arcos. Entonces la gráfica de arco circular correspondiente es G = ( V ,  E ) donde

${\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}}$

y

${\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}$

Una familia de arcos que corresponde a G se llama modelo de arco .

Reconocimiento

Tucker (1980) demostró el primer algoritmo de reconocimiento polinómico para gráficos de arco circular, que se ejecuta en el tiempo. McConnell (2003) presentó el primer algoritmo de reconocimiento de tiempo lineal, 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. ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle ({\mathcal {O}}(n+m))}$ ${\displaystyle m}$

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 algún punto del círculo descubierto, el círculo se puede cortar en ese punto y estirar hasta formar 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 cuerdas C ₅ , C ₇ , etc., son gráficos de arco circular.

Algunas subclases

En lo sucesivo, sea un gráfico arbitrario. ${\displaystyle G=(V,E)}$

Gráficas unitarias de arco circular

${\displaystyle G}$es un gráfico de arco circular unitario si existe un modelo de arco correspondiente tal que cada arco tenga la misma longitud.

El número de gráficos de arco circular unitario etiquetados en n vértices viene dado por . ^[2] ${\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}}$

Gráficos de arco circular adecuados

${\displaystyle G}$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 tal que ningún arco contenga adecuadamente otro. Reconocer estos gráficos y construir un modelo de arco adecuado se pueden realizar en tiempo lineal. ^[4] Forman una de las subclases fundamentales de los gráficos sin garras . ^[3] ${\displaystyle ({\mathcal {O}}(n+m))}$

Gráficos de arco circular de Helly

${\displaystyle G}$es un gráfico de arco circular de Helly si existe un modelo de arco correspondiente tal que los arcos constituyan una familia Helly . Gavril (1974) da una caracterización de esta clase que implica un algoritmo de reconocimiento. ${\displaystyle {{\mathcal {O}}(n^{3})}}$

Joeris et al. (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, entonces el algoritmo devuelve un certificado de este hecho en forma de un subgrafo inducido prohibido. También dieron un algoritmo de tiempo O(n) para determinar si un modelo de arco circular dado tiene la propiedad de Helly.

Aplicaciones

Los gráficos de arco circular son útiles para modelar problemas periódicos de asignación de recursos en la investigación de operaciones . Cada intervalo representa una solicitud de un recurso para un período específico repetido en el tiempo.

Notas

1. Kaplan, Haim; Nussbaum, Yahav (1 de noviembre de 2011). "Un reconocimiento en tiempo lineal más simple de gráficos de arco circular". Algorítmica . 61 (3): 694–737. CiteSeerX  10.1.1.76.2480 . doi :10.1007/s00453-010-9432-y. ISSN  0178-4617.
2. Alexandersson, por; Panova, Greta (diciembre de 2018). "Polinomios LLT, funciones cuasisimé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.
3. Descrito con una definición diferente pero equivalente por Chudnovsky & Seymour (2008).
4. Deng, infierno y Huang (1996) pág. ?

Referencias

• Chudnovsky, María ; 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 , señor  2418774.
• Deng, Xiaotie; Demonios, Pavol ; Huang, Jing (1996), "Algoritmos de representación en 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 en gráficos de arco circular", Redes , 4 (4): 357–369, doi :10.1002/net.3230040407.
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos 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 gráficos y modelos de arco circular de 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