Cirkulær bue graf

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

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

- mange buer. Så er den tilsvarende cirkelbuegraf G = ( V , E ), hvor

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

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

Familien af buer svarende til grafen G kaldes buemodellen .

Anerkendelse

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 . ${\mathcal {O}}(n^{3})$ $({\mathcal {O}}(n+m))$

Relation til andre klasser af grafer

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.

Nogle underklasser

Lad være en vilkårlig graf nedenfor. $G=(V,E)$

Grafer af enhedsbuer i en cirkel

$G$ er en enhedscirkelbuegraf, hvis der findes en buemodel, hvor alle buer har samme længde.

Regulære buegrafer

$G$ 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] $({\mathcal {O}}(n+m))$

Cirkulære Helly bue grafer

$G$ 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 . ${{\mathcal {O}}(n^{3})}$

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 .

Ansøgninger

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.