Gráfico de arco circular - Circular-arc graph

Um gráfico de arco circular (esquerda) e um modelo de arco correspondente (direita).

Na teoria dos grafos , um gráfico de arco circular é o gráfico de interseção de um conjunto de arcos no círculo. Ele tem um vértice para cada arco do conjunto e uma aresta entre cada par de vértices correspondendo aos arcos que se cruzam.

Formalmente, deixe

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

ser um conjunto de arcos. Então, o gráfico de arco circular correspondente é G = ( V ,  E ), onde

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

e

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

Uma família de arcos que corresponde a G é chamada de modelo de arco .

Reconhecimento

Tucker (1980) demonstrou o primeiro algoritmo de reconhecimento polinomial para gráficos de arco circular, que funciona no tempo. McConnell (2003) deu o primeiro algoritmo de reconhecimento de tempo linear , onde é o número de arestas. Mais recentemente, Kaplan e Nussbaum desenvolveram um algoritmo de reconhecimento de tempo linear mais simples. ${\ displaystyle {\ mathcal {O}} (n ^ {3})}$${\ displaystyle ({\ mathcal {O}} (n + m))}$${\ displaystyle m}$

Relação com outras classes de gráfico

Os gráficos de arco circular são uma generalização natural dos gráficos de intervalo . Se um gráfico de arco circular G tem um modelo de arco que deixa algum ponto do círculo descoberto, o círculo pode ser cortado naquele ponto e esticado até uma linha, o que resulta em uma representação de intervalo. Ao contrário dos gráficos de intervalo, no entanto, os gráficos de arco circular nem sempre são perfeitos , pois os ciclos ímpares sem corda C ₅ , C ₇ , etc., são gráficos de arco circular.

Algumas subclasses

A seguir, deixe ser um gráfico arbitrário. ${\ displaystyle G = (V, E)}$

Gráficos de arco circular unitário

${\ displaystyle G}$é um gráfico de arco circular unitário se houver um modelo de arco correspondente, de modo que cada arco tenha o mesmo comprimento.

O número de gráficos de arco circular unitário rotulados em n vértices é dado por . ${\ displaystyle (n + 2) {\ binom {2n-1} {n-1}} - 2 ^ {2n-1}}$

Gráficos de arco circular adequados

${\ displaystyle G}$é um gráfico de arco circular adequado (também conhecido como gráfico de intervalo circular ) se houver um modelo de arco correspondente de forma que nenhum arco contenha outro. O reconhecimento desses gráficos e a construção de um modelo de arco adequado podem ser realizados em tempo linear . Eles formam uma das subclasses fundamentais dos gráficos sem garras . ${\ displaystyle ({\ mathcal {O}} (n + m))}$

Gráficos de arco circular helly

${\ displaystyle G}$é um gráfico de arco circular de Helly se houver um modelo de arco correspondente de forma que os arcos constituam uma família de Helly . Gavril (1974) fornece uma caracterização desta classe que implica um algoritmo de reconhecimento. ${\ displaystyle {{\ mathcal {O}} (n ^ {3})}}$

Joeris et al. (2009) fornecem outras caracterizações desta classe, que implicam em um algoritmo de reconhecimento que roda em tempo O (n + m) quando a entrada é um gráfico. Se o grafo de entrada não for um grafo de arco circular de Helly, então o algoritmo retorna um certificado desse fato na forma de um subgrafo induzido proibido. Eles também forneceram um algoritmo de tempo O (n) para determinar se um determinado modelo de arco circular tem a propriedade Helly.

Formulários

Os gráficos de arco circular são úteis na modelagem de problemas periódicos de alocação de recursos em pesquisa operacional . Cada intervalo representa uma solicitação de um recurso por um período específico repetido no tempo.

Notas

Referências

• Chudnovsky, Maria ; Seymour, Paul (2008), "Claw-free graphs. III. Circular interval graphs" (PDF) , Journal of Combinatorial Theory , Series B, 98 (4): 812–834, doi : 10.1016 / j.jctb.2008.03. 001 , MR  2418774.
• Deng, Xiaotie; Inferno, Pavol ; Huang, Jing (1996), "Linear-Time Representation algoritms for Proper circular-arc graphs and proper interval graphs", SIAM Journal on Computing , 25 (2): 390-403, doi : 10.1137 / S0097539792269095.
• Gavril, Fanica (1974), "Algorithms on circular-arc graphs", Networks , 4 (4): 357–369, doi : 10.1002 / net.3230040407.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs , Academic Press, ISBN 978-0-444-51530-8, arquivado do original em 22/05/2010 , recuperado em 21/05/2008. Segunda edição, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Joeris, Benson L .; Lin, Min Chih; McConnell, Ross M .; Spinrad, Jeremy P .; Szwarcfiter, Jayme L. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica , 59 (2): 215–239, CiteSeerX  10.1.1.298.3038 , doi : 10.1007 / s00453-009- 9304-5.
• McConnell, Ross (2003), "Linear-time recognition of circular-arc graphs", Algorithmica , 37 (2): 93-147, CiteSeerX  10.1.1.22.4725 , doi : 10.1007 / s00453-003-1032-7.
• Tucker, Alan (1980), "Um teste eficiente para gráficos de arco circular", SIAM Journal on Computing , 9 (1): 1-24, doi : 10.1137 / 0209001.

links externos

• Gráfico de arco circular , Sistema de Informação sobre Inclusões de Classe de Gráfico