Hispanopedia Wiki
Articulo de referencia

Gráfico de arco circular

Un gráfico de arco circular (izquierda) y un modelo de arco correspondiente (derecha). En teoría de grafos , un grafo de arcos circulares es el grafo de intersección de un conju...

Hispanopedia WikiContenido en espanolLectura gratuita
Un gráfico de arco circular (izquierda) y un modelo de arco correspondiente (derecha).

En teoría de grafos , un grafo de arcos circulares es el grafo de intersección de un conjunto de arcos en la circunferencia. Tiene un vértice por cada arco del conjunto y una arista entre cada par de vértices que corresponden a arcos que se intersecan.

Formalmente, dejemos

I1,I2,…,Inorte⊂do1{\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}

Sea un conjunto de arcos. Entonces, el grafo de arcos circulares correspondiente es G = ( V , E ) donde 

V={I1,I2,…,Inorte}{\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}}

y

{Iα,Iβ}∈mi⟺Iα∩Iβ≠∅.{\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}

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

Reconocimiento

Tucker (1980) demostró el primer algoritmo de reconocimiento polinomial para grafos de arcos circulares, que se ejecuta enO(norte3){\displaystyle {\mathcal {O}}(n^{3})}tiempo. McConnell (2003) dio el primer lineal(O(norte+metro)){\displaystyle ({\mathcal {O}}(n+m))}algoritmo de reconocimiento de tiempo, dondemetro{\displaystyle m}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 grafos

Los grafos de arco circular son una generalización natural de los grafos de intervalo . Si un grafo de arco circular G tiene un modelo de arco que deja algún punto del círculo sin cubrir, 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 grafos de intervalo, los grafos de arco circular no siempre son perfectos , ya que los ciclos impares sin acordes C5 , C7 , etc., son grafos de arco circular.

Algunas subclases

A continuación, dejemosGRAMO=(V,mi){\displaystyle G=(V,E)}sea ​​un grafo arbitrario.

Gráficos de arco circular unitario

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

El número de grafos de arco circular unitarios etiquetados en n vértices viene dado por(norte+2)(2norte−1norte−1)−22norte−1{\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}}. [ 2 ]

Gráficas de arcos circulares adecuadas

GRAMO{\displaystyle G}Un gráfico es un grafo de arco circular propio (también conocido como grafo de intervalo circular ) [ 3 ] si existe un modelo de arco correspondiente tal que ningún arco contiene propiamente a otro. Tanto el reconocimiento de estos gráficos como la construcción de un modelo de arco propio pueden realizarse de forma lineal.(O(norte+metro)){\displaystyle ({\mathcal {O}}(n+m))}tiempo. [ 4 ] Forman una de las subclases fundamentales de los grafos libres de garras . [ 3 ]

Gráficos de arco circular de Helly

GRAMO{\displaystyle G}es un grafo 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 unO(norte3){\displaystyle {{\mathcal {O}}(n^{3})}}algoritmo de reconocimiento.

Joeris et al. (2009) ofrecen otras caracterizaciones de esta clase, que implican un algoritmo de reconocimiento que se ejecuta en tiempo O(n+m) cuando la entrada es un grafo. Si el grafo de entrada no es un grafo 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 posee la propiedad de Helly.

Aplicaciones

Los gráficos de arcos circulares son útiles para modelar problemas de asignación periódica de recursos en la investigación operativa . Cada intervalo representa una solicitud de un recurso durante un período específico que se repite en el tiempo.

Notas

  1. ↑ Kaplan, Haim; Nussbaum, Yahav (2011-11-01). "Un reconocimiento lineal más simple de grafos de arcos circulares". Algorithmica . 61 (3): 694– 737. CiteSeerX 10.1.1.76.2480 . doi : 10.1007/s00453-010-9432-y . ISSN 0178-4617 .  
  2. ↑ Alexandersson, Per; 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. 1 2 Descrito con una definición diferente pero equivalente por Chudnovsky y Seymour (2008) .
  4. ↑ Deng, Hell y Huang (1996) pág. ?

Referencias

  • Chudnovsky, Maria ; Seymour, Paul (2008), "Grafos sin garras. III. Grafos de intervalos circulares" (PDF) , Journal of Combinatorial Theory , Serie B, 98 (4): 812–834 , doi : 10.1016/j.jctb.2008.03.001 , MR 2418774 .
  • Deng, Xiaotie ; Hell, Pavol ; Huang, Jing (1996), "Algoritmos de representación en tiempo lineal para grafos de arcos circulares propios y grafos de intervalos propios", SIAM Journal on Computing , 25 (2): 390–403 , doi : 10.1137/S0097539792269095.
  • Gavril, Fanica (1974), "Algoritmos en grafos de arcos circulares", Networks , 4 (4): 357– 369, doi : 10.1002/net.3230040407.
  • Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y grafos perfectos , Academic Press, ISBN 978-0-444-51530-8Archivado del original el 22/05/2010 , consultado el 21/05/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 grafos 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 grafos de arcos circulares", 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 grafos de arcos circulares", SIAM Journal on Computing , 9 (1): 1– 24, doi : 10.1137/0209001.
  • Gráfico de arco circular , sistema de información sobre inclusiones de clases de gráficos