Kruhový obloukový graf

V teorii grafů je graf oblouků kruhu grafem průsečíků sady oblouků kruhu . Graf má jeden vrchol pro každý kruhový oblouk a hranu mezi dvěma vrcholy, pokud se příslušné oblouky protínají.

Formálně, nech

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

- mnoho oblouků. Potom odpovídající kruhový obloukový graf je G = ( V , E ), kde

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

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

Rodina oblouků odpovídajících grafu G se nazývá obloukový model .

Rozpoznávání

Tooker [1] našel první polynomiální rozpoznávací algoritmus pro kruhové obloukové grafy, který běží v čase . Později McConnell [2] našel první lineární rozpoznávací algoritmus v čase . ${\mathcal {O}}(n^{3})$ $({\mathcal {O}}(n+m))$

Vztah k jiným třídám grafů

Kruhové obloukové grafy jsou přirozeným zobecněním intervalových grafů . Pokud má kruhový obloukový graf G model oblouku, který nepokrývá některé body na kružnici, lze kružnici v tomto bodě přerušit a narovnat na úsečku, čímž vznikne intervalová reprezentace. Na rozdíl od intervalových grafů však kruhové obloukové grafy nejsou vždy dokonalé , protože liché cykly bez tětiv C 5 , C 7 atd. jsou kruhové obloukové grafy.

Některé podtřídy

Nechť je libovolný graf níže. $G=(V,E)$

Grafy jednotkových oblouků kružnice

$G$ je jednotkový kruhový obloukový graf , pokud existuje model oblouku, ve kterém mají všechny oblouky stejnou délku.

Pravidelné obloukové grafy

$G$ je graf pravidelného kruhového oblouku (nebo graf intervalu cyklu [3] ), pokud existuje odpovídající model oblouku, ve kterém žádný oblouk zcela neobsahuje jiný. Rozpoznání takových grafů a sestavení správného modelu oblouku lze provádět v lineárním čase . [čtyři] $({\mathcal {O}}(n+m))$

Kruhové Hellyho obloukové grafy

$G$ je kruhový graf Hellyho oblouku , pokud existuje odpovídající model oblouku, takže oblouky tvoří rodinu Helly . Gavril [5] uvádí popis této třídy, ze kterého plyne rozpoznávací algoritmus v čase . ${{\mathcal {O}}(n^{3})}$

Joris et al [6] uvádějí další charakteristiky (včetně výčtu zakázaných generovaných podgrafů) této třídy, z nichž vyplývá rozpoznávací algoritmus, který běží v čase O(n+m) . Pokud vstupní graf není kruhový Hellyho obloukový graf, pak algoritmus vrátí potvrzení této skutečnosti ve formě zakázaného generovaného podgrafu. Poskytli také algoritmus pro určení, zda daný model kruhového oblouku tvoří rodinu Helly v O(n) čase .

Aplikace

Kruhové obloukové grafy jsou užitečné při modelování problémů s periodickou alokací zdrojů v operačním výzkumu . Každý interval představuje požadavek na určité období, který se v čase opakuje.

Odkazy

Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Lineární rozpoznávání modelů a grafů Helly Circular-Arc // Algorithmica. - 2009. - T. 59 , č.p. 2 . — S. 215–239 . - doi : 10.1007/s00453-009-9304-5 . .
Alan Tucker. Účinný test pro kruhové obloukové grafy // SIAM Journal on Computing. - 1980. - T. 9 , no. 1 . — S. 1–24 . - doi : 10.1137/0209001 . .
Ross McConnell. Rozpoznávání kruhových obloukových grafů v lineárním čase // Algorithmica. - 2003. - T. 37 , no. 2 . — s. 93–147 . - doi : 10.1007/s00453-003-1032-7 .
Martin Charles Golumbic. Algoritmická teorie grafů a dokonalé grafy. - Academic Press, 1980. - ISBN 0-444-51530-5 . Druhé vydání, Annals of Discrete Mathematics 57, Elsevier, 2004.
Xiaotie Deng, Pavol Hell, Jing Huang. Algoritmy zobrazení lineárního času pro správné kruhové obloukové grafy a správné intervalové grafy // SIAM Journal on Computing. - 1996. - T. 25 , no. 2 . — S. 390–403 . - doi : 10.1137/S0097539792269095 . .
Fanica Gavril. Algoritmy na kruhových grafech // Sítě. - 1974. - T. 4 , no. 4 . — S. 357–369 . - doi : 10.1002/net.3230040407 .
oblouk kruhový graf . Informační systém o zařazení grafových tříd . Datum přístupu: 14. prosince 2013. Archivováno z originálu 21. prosince 2013. (neurčitý)
Maria Chudnovsky, Paul Seymour. Grafy bez drápů. III. Kruhové intervalové grafy // Journal of Combinatorial Theory . - 2008. - T. 98 , č.p. 4 . — S. 812–834 . - doi : 10.1016/j.jctb.2008.03.001 . .