Pyöreä kaarikaavio

Graafiteoriassa ympyrän kaarien kuvaaja on kaavio ympyrän kaarien joukon leikkauspisteistä . Graafissa on yksi kärki kullekin ympyräkaarelle ja reuna kahden kärjen välillä, jos vastaavat kaaret leikkaavat.

Muodollisesti, anna

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

- monta kaaria. Tällöin vastaava ympyräkaaren graafi on G = ( V , E ), missä

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

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

Kuvaajaa G vastaavaa kaariperhettä kutsutaan kaarimalliksi .

Tunnustus

Tooker [1] löysi ensimmäisen polynomin tunnistusalgoritmin ympyräkaareille, joka kulkee ajassa . Myöhemmin McConnell [2] löysi ensimmäisen lineaarisen tunnistusalgoritmin ajallaan . ${\mathcal {O}}(n^{3})$ ${\näyttötyyli ({\mathcal {O}}(n+m))}$

Suhde muihin graafiluokkiin

Ympyränkaarikaaviot ovat luonnollinen yleistys intervallikaavioista . Jos ympyränkaarikaaviossa G on kaarimalli, joka ei kata joitain ympyrän pisteitä, ympyrä voidaan katkaista kyseisestä pisteestä ja suoristaa janaksi, jolloin saadaan intervalliesitys. Toisin kuin intervallikaaviot, ympyränkaarikaaviot eivät kuitenkaan aina ole täydellisiä , koska parittomat jaksot ilman sointuja C 5 , C 7 jne. ovat ympyrän kaarikaavioita.

Jotkut alaluokat

Antaa olla mielivaltainen kaavio alla. $G=(V,E)$

Kaaviot ympyrän yksikkökaareista

$G$ on yksikköympyrän kaarikaavio, jos on olemassa kaarimalli, jossa kaikilla kaarilla on sama pituus.

Säännölliset kaarikaaviot

$G$ on säännöllinen ympyräkaarikuvaaja (tai syklin intervallikaavio [3] ), jos on olemassa vastaava kaarimalli, jossa mikään kaari ei sisällä kokonaan toista. Tällaisten kuvaajien tunnistus ja oikean kaarimallin rakentaminen voidaan tehdä lineaarisessa ajassa . [neljä] ${\näyttötyyli ({\mathcal {O}}(n+m))}$

Hellyn pyöreät kaarikaaviot

$G$ on pyöreä Helly-kaarikuvaaja, jos on olemassa vastaava kaarimalli siten, että kaaret muodostavat Helly-perheen . Gavril [5] antaa kuvauksen tästä luokasta, josta seuraa tunnistusalgoritmi ajassa . ${{\mathcal {O}}(n^{3})}$

Joris ym . [6] antavat muita tämän luokan ominaisuuksia (mukaan lukien kiellettyjen generoitujen aligraafien luettelointi), josta seuraa tunnistusalgoritmi, joka suoritetaan O(n+m) ajassa . Jos syötetty graafi ei ole ympyrämäinen Helly-kaarigraafi, niin algoritmi palauttaa vahvistuksen tälle tosiasialle kielletyn generoidun aligraafin muodossa. He antoivat myös algoritmin sen määrittämiseksi, muodostaako tietty ympyräkaaren malli Helly-perheen O(n) ajassa .

Sovellukset

Ympyräkaaret ovat hyödyllisiä mallinnettaessa jaksottaisia resurssien allokointiongelmia [ operaatiotutkimuksessa . Jokainen aikaväli edustaa tietyn ajanjakson pyyntöä, joka toistuu ajassa.

Linkit

Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Hellyn ympyräkaaren mallien ja graafien lineaarinen tunnistus // Algorithmica. - 2009. - T. 59 , no. 2 . — S. 215–239 . - doi : 10.1007/s00453-009-9304-5 . .
Alan Tucker. Tehokas testi ympyräkaarikaavioille // SIAM Journal on Computing. - 1980. - T. 9 , no. 1 . - S. 1-24 . - doi : 10.1137/0209001 . .
Ross McConnell. Ympyräkaaren graafien lineaarinen tunnistus // Algorithmica. - 2003. - T. 37 , no. 2 . — s. 93–147 . - doi : 10.1007/s00453-003-1032-7 .
Martin Charles Golumbic. Algoritminen graafiteoria ja täydelliset kuvaajat. - Academic Press, 1980. - ISBN 0-444-51530-5 . Toinen painos, Annals of Discrete Mathematics 57, Elsevier, 2004.
Xiaotie Deng, Pavol Hell, Jing Huang. Lineaarisen ajan esitysalgoritmit oikeille ympyräkaareille ja oikeille intervallikaavioille // SIAM Journal on Computing. - 1996. - T. 25 , no. 2 . — S. 390–403 . - doi : 10.1137/S0097539792269095 . .
Fanica Gavril. Algoritmit ympyräkaareilla // Verkot. - 1974. - T. 4 , no. 4 . — S. 357–369 . - doi : 10.1002/net.3230040407 .
kaari pyöreä kaavio . Tietojärjestelmä kaavioluokkien sisällyttämisestä . Käyttöpäivä: 14. joulukuuta 2013. Arkistoitu alkuperäisestä 21. joulukuuta 2013. (määrätön)
Maria Chudnovsky, Paul Seymour. Kynsittömät kaaviot. III. Pyöreät intervallikaaviot // Journal of Combinatorial Theory . - 2008. - T. 98 , no. 4 . — S. 812–834 . - doi : 10.1016/j.jctb.2008.03.001 . .