Cirkulär bågegraf

I grafteorin är en graf av cirkelbågar en graf av skärningspunkter för en uppsättning cirkelbågar . Grafen har en vertex för varje cirkelbåge och en kant mellan två hörn om motsvarande bågar skär varandra.

Formellt, låt

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

- många bågar. Då är motsvarande cirkelbågsgraf G = ( V , E ), där

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

och

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

Familjen av bågar som motsvarar grafen G kallas bågmodellen .

Erkännande

Tooker [1] hittade den första polynomigenkänningsalgoritmen för cirkelbågsgrafer som går i tid . Senare hittade McConnell [2] den första linjära igenkänningsalgoritmen i tid . ${\mathcal {O}}(n^{3})$ $({\mathcal {O}}(n+m))$

Relation till andra klasser av grafer

Cirkulärbågsgrafer är en naturlig generalisering av intervallgrafer . Om cirkelbågsgrafen G har en bågmodell som inte täcker vissa punkter på cirkeln, kan cirkeln brytas vid den punkten och rätas ut till ett linjesegment, vilket ger en intervallrepresentation. Men till skillnad från intervallgrafer är cirkelbågsgrafer inte alltid perfekta , eftersom udda cykler utan ackord C 5 , C 7 , etc. är cirkelbågsgrafer.

Vissa underklasser

Låt vara en godtycklig graf nedan. $G=(V,E)$

Grafer av enhetsbågar i en cirkel

$G$ är en enhetscirkelbågsgraf om det finns en bågmodell där alla bågar har samma längd.

Reguljära båggrafer

$G$ är en vanlig cirkelbågsgraf (eller en cykelintervallgraf [3] ) om det finns en motsvarande bågmodell där ingen båge helt innehåller en annan. Identifieringen av sådana grafer och konstruktionen av en korrekt bågmodell kan göras i linjär tid . [fyra] $({\mathcal {O}}(n+m))$

Circular Helly arc graphs

$G$ är en cirkulär Helly-bågegraf om det finns en motsvarande bågmodell så att bågarna bildar en Helly-familj . Gavril [5] ger en beskrivning av denna klass, från vilken följer igenkänningsalgoritmen i tid . ${{\mathcal {O}}(n^{3})}$

Joris et al [6] ger andra egenskaper (inklusive uppräkning av förbjudna genererade subgrafer) av denna klass, från vilka följer en igenkänningsalgoritm som körs i O(n+m) tid . Om ingångsgrafen inte är en cirkulär Helly-bågegraf, returnerar algoritmen en bekräftelse på detta faktum i form av en förbjuden genererad subgraf. De gav också en algoritm för att bestämma om en given cirkelbågsmodell bildar en Helly-familj i O(n) -tid .

Applikationer

Cirkulärbågsgrafer är användbara vid modellering av periodiska resursallokeringsproblem i operationsforskning . Varje intervall representerar en begäran för en viss period, som upprepas i tid.

Länkar

Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Linjär-tidsigenkänning av Helly Circular-Arc-modeller och grafer // Algoritmik. - 2009. - T. 59 , nr. 2 . — S. 215–239 . - doi : 10.1007/s00453-009-9304-5 . .
Alan Tucker. Ett effektivt test för cirkelbågsgrafer // SIAM Journal on Computing. - 1980. - T. 9 , nr. 1 . — S. 1–24 . - doi : 10.1137/0209001 . .
Ross McConnell. Linjär-tidsigenkänning av cirkelbågsgrafer // Algorithmica. - 2003. - T. 37 , nr. 2 . — s. 93–147 . - doi : 10.1007/s00453-003-1032-7 .
Martin Charles Golumbic. Algoritmisk grafteori och perfekta grafer. - Academic Press, 1980. - ISBN 0-444-51530-5 . Andra upplagan, Annals of Discrete Mathematics 57, Elsevier, 2004.
Xiaotie Deng, Pavol Hell, Jing Huang. Linjär-tidsrepresentationsalgoritmer för korrekta cirkelbågsgrafer och korrekta intervallgrafer // SIAM Journal on Computing. - 1996. - T. 25 , nr. 2 . — S. 390–403 . - doi : 10.1137/S0097539792269095 . .
Fanica Gavril. Algoritmer på cirkelbågsgrafer // Nätverk. - 1974. - T. 4 , nr. 4 . — S. 357–369 . - doi : 10.1002/net.3230040407 .
bågcirkulär graf . Informationssystem om grafklassinneslutningar . Datum för åtkomst: 14 december 2013. Arkiverad från originalet 21 december 2013. (obestämd)
Maria Chudnovsky, Paul Seymour. Klofria grafer. III. Cirkulära intervallgrafer // Journal of Combinatorial Theory . - 2008. - T. 98 , nr. 4 . — S. 812–834 . - doi : 10.1016/j.jctb.2008.03.001 . .