Kruhový oblouk graf - Circular-arc graph

v teorie grafů, a kruhový obloukový graf je průsečíkový graf sady oblouky na kruhu. Má jednu vrchol pro každý oblouk v sadě a okraj mezi každou dvojicí vrcholů odpovídajících obloukům, které se protínají.
Formálně, pojďme
být soubor oblouků. Pak je odpovídající graf kruhového oblouku G = (PROTI, E) kde
a
Rodina oblouků, která odpovídá G, se nazývá model oblouku.
Uznání
Tucker (1980) demonstroval první algoritmus rozpoznávání polynomů pro kruhové obloukové grafy, který běží dovnitř čas. McConnell (2003) dal první lineární algoritmus rozpoznávání času, kde je počet hran. V poslední době Kaplan a Nussbaum[1] vyvinul jednodušší algoritmus lineárního rozpoznávání času.
Vztah k jiným třídám grafů
Kruhové obloukové grafy jsou přirozeným zobecněním intervalové grafy. Pokud kruhový oblouk graf G má model oblouku, který ponechává určitý bod kruhu nekrytý, lze kruh v tomto bodě oříznout a natáhnout na čáru, což má za následek reprezentaci intervalu. Na rozdíl od intervalových grafů však kruhové obloukové grafy nejsou vždy perfektní, jako liché cykly bez akordů C5, C7atd. jsou grafy kruhového oblouku.
Některé podtřídy
V následujícím textu pojďme být libovolný graf.
Jednotkové kruhové obloukové grafy
je jednotkový kruhový obloukový graf pokud existuje odpovídající model oblouku, takže každý oblouk má stejnou délku.
Počet označených jednotkových kruhových oblouků n vrcholy jsou dány .[2]
Správné kruhové obloukové grafy
je správný kruhový oblouk (také známý jako kruhový intervalový graf)[3] pokud existuje odpovídající model oblouku tak, že žádný oblouk správně neobsahuje jiný. Rozpoznání těchto grafů a vytvoření správného modelu oblouku lze provést lineárně čas.[4]Tvoří jednu ze základních podtříd skupiny grafy bez drápů.[3]
Helly kruhové obloukové grafy
je Helly kruhový obloukový graf pokud existuje odpovídající model oblouku tak, že oblouky tvoří a Helly rodina. Gavril (1974) dává charakteristiku této třídy, která implikuje algoritmus rozpoznávání.
Joeris a kol. (2009) dát další charakterizace této třídy, což znamená algoritmus rozpoznávání, který běží dovnitř O (n + m) čas, kdy je vstupem graf. Pokud vstupní graf není graf Helly kruhového oblouku, pak algoritmus vrátí certifikát této skutečnosti ve formě zakázaného indukovaného podgrafu. Také dali Na) časový algoritmus pro určení, zda daný model kruhového oblouku má vlastnost Helly.
Aplikace
Kruhové obloukové grafy jsou užitečné při periodickém modelování přidělení zdrojů problémy v operační výzkum. Každý interval představuje požadavek na prostředek pro konkrétní období opakovaný v čase.
Poznámky
- ^ Kaplan, Haim; Nussbaum, Yahav (2011-11-01). „Jednodušší rozpoznávání grafů kruhového oblouku v lineárním čase“. Algorithmica. 61 (3): 694–737. CiteSeerX 10.1.1.76.2480. doi:10.1007 / s00453-010-9432-r. ISSN 0178-4617.
- ^ Alexandersson, Per; Panova, Greta (Prosinec 2018). Msgstr "LLT polynomy, chromatické kvazimetrické funkce a grafy s cykly". Diskrétní matematika. 341 (12): 3453–3482. arXiv:1705.10353. doi:10.1016 / j.disc.2018.09.001.
- ^ A b Popsáno jinou, ale ekvivalentní definicí Chudnovsky & Seymour (2008).
- ^ Deng, Hell & Huang (1996) str. ?
Reference
- Chudnovský, Maria; Seymour, Paule (2008), „Grafy bez drápů. III. Kruhové intervalové grafy“ (PDF), Journal of Combinatorial Theory, Řada B, 98 (4): 812–834, doi:10.1016 / j.jctb.2008.03.001, PAN 2418774.
- Deng, Xiaotie; Sakra, Pavol; Huang, Jing (1996), „Algoritmy reprezentace lineárního času pro správné kruhové a obloukové grafy“, SIAM Journal on Computing, 25 (2): 390–403, doi:10.1137 / S0097539792269095.
- Gavril, Fanica (1974), „Algoritmy na grafech kruhového oblouku“, Sítě, 4 (4): 357–369, doi:10,1002 / net.3230040407.
- Golumbic, Martin Charles (1980), Algoritmická teorie grafů a dokonalé grafy Akademický tisk, ISBN 978-0-444-51530-8, archivovány z originál dne 22. 05. 2010, vyvoláno 2008-05-21. Druhé vydání, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Joeris, Benson L .; Lin, Min Chih; McConnell, Ross M .; Spinrad, Jeremy P .; Szwarcfiter, Jayme L. (2009), „Lineární rozpoznávání modelů a grafů Helly Circle-Arc“, Algorithmica, 59 (2): 215–239, CiteSeerX 10.1.1.298.3038, doi:10.1007 / s00453-009-9304-5.
- McConnell, Ross (2003), „Lineární rozpoznávání grafů kruhového oblouku“, Algorithmica, 37 (2): 93–147, CiteSeerX 10.1.1.22.4725, doi:10.1007 / s00453-003-1032-7.
- Tucker, Alan (1980), "Efektivní test pro kruhové obloukové grafy", SIAM Journal on Computing, 9 (1): 1–24, doi:10.1137/0209001.