I grafteori er en graf over cirkelbuer en graf over skæringspunkter mellem et sæt af cirkelbuer . Grafen har et toppunkt for hver cirkelbue og en kant mellem to toppunkter, hvis de tilsvarende buer skærer hinanden.
Formelt, lad
- mange buer. Så er den tilsvarende cirkelbuegraf G = ( V , E ), hvor
og
Familien af buer svarende til grafen G kaldes buemodellen .
Tooker [1] fandt den første polynomiumgenkendelsesalgoritme til cirkulære buegrafer, der kører i tid . Senere fandt McConnell [2] den første lineære genkendelsesalgoritme i tiden .
Cirkulære buegrafer er en naturlig generalisering af intervalgrafer . Hvis cirkelbuegrafen G har en buemodel, der ikke dækker nogle punkter på cirklen, kan cirklen brydes på det punkt og rettes ud i et linjestykke, hvilket giver en intervalrepræsentation. Men i modsætning til intervalgrafer er cirkelbuegrafer ikke altid perfekte , da ulige cyklusser uden akkorder C 5 , C 7 osv. er cirkelbuegrafer.
Lad være en vilkårlig graf nedenfor.
er en enhedscirkelbuegraf, hvis der findes en buemodel, hvor alle buer har samme længde.
er en regulær cirkelbuegraf (eller en cyklusintervalgraf [3] ), hvis der findes en tilsvarende buemodel, hvor ingen bue fuldstændigt indeholder en anden. Genkendelsen af sådanne grafer og konstruktionen af en korrekt buemodel kan ske i lineær tid . [fire]
er en cirkulær Helly-buegraf, hvis der findes en tilsvarende buemodel, således at buerne danner en Helly-familie . Gavril [5] giver en beskrivelse af denne klasse, hvorfra der følger genkendelsesalgoritmen i tid .
Joris et al . [6] giver andre karakteristika (herunder opregning af forbudte genererede subgrafer) af denne klasse, hvorfra der følger en genkendelsesalgoritme, der kører i O(n+m) tid . Hvis inputgrafen ikke er en cirkulær Helly-buegraf, returnerer algoritmen en bekræftelse af dette faktum i form af en forbudt genereret subgraf. De gav også en algoritme til at bestemme, om en given cirkulær buemodel danner en Helly-familie i O(n) tid .
Cirkulære buegrafer er nyttige til modellering af periodiske ressourceallokeringsproblemer i operationsforskning . Hvert interval repræsenterer en anmodning for en bestemt periode, der gentages i tid.