Dumaloq grafika grafigi - Circular-arc graph

Dumaloq yoyli grafika (chapda) va mos keladigan yoy modeli (o'ngda).

Yilda grafik nazariyasi, a yoy grafigi bo'ladi kesishish grafigi to'plamining yoylar doira bo'yicha. Unda bitta bor tepalik to'plamdagi har bir kamon uchun va chekka kesishgan yoylarga to'g'ri keladigan har bir tepalik juftligi o'rtasida.

Rasmiy ravishda, ruxsat bering

{displaystyle I_ {1}, I_ {2}, ldots, I_ {n} kichik to'plam C_ {1}}

yoylarning to'plami bo'ling. Unda mos keladigan aylana-grafika grafigi G = (V, E) qayerda

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

va

{displaystyle {I_ {alpha}, I_ {eta}} in Eiff I_ {alpha} cap I_ {eta} eq varnothing.}

G ga to'g'ri keladigan yoylar oilasi an deyiladi boshq modeli.

E'tirof etish

Taker (1980) dumaloq grafika uchun birinchi polinomlarni aniqlash algoritmini namoyish etdi ${displaystyle {mathcal {O}} (n ^ {3})}$ vaqt. Makkonnell (2003) birinchi chiziqli berdi ${displaystyle ({mathcal {O}} (n + m))}$ vaqtni aniqlash algoritmi, qaerda ${displaystyle m}$ qirralarning soni. Yaqinda Kaplan va Nussbaum^[1] oddiyroq vaqtni aniqlash algoritmini ishlab chiqdi.

Boshqa grafik sinflari bilan aloqasi

Dumaloq-yoyli grafikalar tabiiy umumlashma hisoblanadi intervalli grafikalar. Agar aylana-grafika grafigi bo'lsa G yoy modeliga ega bo'lib, aylananing biron bir nuqtasini yopiq holda qoldiradi, aylana shu nuqtada kesilib, chiziqqa cho'zilishi mumkin, natijada intervalli tasvir paydo bo'ladi. Biroq, intervalli grafikalardan farqli o'laroq, dumaloq grafika har doim ham mavjud emas mukammal, toq akkordsiz tsikllar sifatida C₅, C₇va boshqalar, dumaloq yoyli grafikalardir.

Ba'zi pastki sinflar

Quyidagilarga ruxsat bering ${displaystyle G = (V, E)}$ o'zboshimchalik bilan grafik bo'lishi.

Birgalikda dairesel grafika

${displaystyle G}$ a birlik dairesel grafigi agar mos keladigan yoy modeli mavjud bo'lsa, unda har bir kamon teng uzunlikda bo'ladi.

Belgilangan birlik dairesel grafika soni n tepaliklar tomonidan berilgan ${displaystyle (n + 2) {inom {2n-1} {n-1}} - 2 ^ {2n-1}}$ .^[2]

To'g'ri dairesel grafika

${displaystyle G}$ a to'g'ri dairesel grafika (a nomi bilan ham tanilgan dumaloq intervalli grafik)^[3] agar tegishli kamon modeli mavjud bo'lsa, unda hech qanday boshq boshqasini o'z ichiga olmaydi. Ushbu grafikalarni tanib olish va to'g'ri yoy modelini yaratish ikkalasi ham chiziqli bajarilishi mumkin ${displaystyle ({mathcal {O}} (n + m))}$ vaqt.^[4]Ular. Ning asosiy subklasslaridan birini tashkil qiladi tirnoqsiz grafikalar.^[3]

Helli dumaloq grafika

${displaystyle G}$ a Helli dairesel-grafika grafigi agar mos keladigan yoy modeli mavjud bo'lsa, yoylar a ni tashkil qiladi Helli oilasi. Gavril (1974) degan ma'noni anglatuvchi ushbu sinfning xarakteristikasini beradi ${displaystyle {{mathcal {O}} (n ^ {3})}}$ tanib olish algoritmi.

Joeris va boshq. (2009) ishga tushadigan algoritmni nazarda tutadigan ushbu sinfning boshqa tavsiflarini bering O (n + m) kirish grafik bo'lgan vaqt. Agar kirish grafasi Helli dairesel-grafigi bo'lmasa, u holda algoritm ushbu fakt to'g'risidagi guvohnomani taqiqlangan induktsiya shaklida qaytaradi. Ular shuningdek O (n) berilgan aylana-arqon modeli Helly xususiyatiga ega yoki yo'qligini aniqlash uchun vaqt algoritmi.

Ilovalar

Doira shaklidagi grafika davriy modellashtirishda foydalidir resurslarni taqsimlash muammolar operatsiyalarni o'rganish. Har bir interval o'z vaqtida takrorlangan ma'lum bir davr uchun resurs so'rovini anglatadi.

Izohlar

^ Kaplan, Xaym; Nussbaum, Yahav (2011-11-01). "Dumaloq kamonli grafikalarni chiziqli-vaqt bo'yicha oddiyroq tanib olish". Algoritmika. 61 (3): 694–737. CiteSeerX 10.1.1.76.2480. doi:10.1007 / s00453-010-9432-y. ISSN 0178-4617.
^ Aleksandersson, Per; Panova, Greta (Dekabr 2018). "LLT polinomlari, kromatik kvazimimetrik funktsiyalari va tsikllari bo'lgan grafikalar". Diskret matematika. 341 (12): 3453–3482. arXiv:1705.10353. doi:10.1016 / j.disc.2018.09.001.
^ ^a ^b Tomonidan boshqacha, ammo ekvivalent ta'rifi bilan tavsiflangan Chudnovskiy va Seymur (2008).
^ Deng, Hell & Huang (1996) pg. ?

Adabiyotlar

Chudnovskiy, Mariya; Seymur, Pol (2008), "Tirnoqsiz grafikalar. III. Dumaloq intervalli grafikalar" (PDF), Kombinatorial nazariya jurnali, B seriyasi, 98 (4): 812–834, doi:10.1016 / j.jctb.2008.03.001, JANOB 2418774.
Deng, Xiaotie; Jahannam, Pavol; Xuang, Jing (1996), "To'g'ri dairesel-grafika va to'g'ri intervalli grafikalar uchun chiziqli vaqtni ko'rsatish algoritmlari", Hisoblash bo'yicha SIAM jurnali, 25 (2): 390–403, doi:10.1137 / S0097539792269095.
Gavril, Fanika (1974), "Dumaloq yoyli grafikalar bo'yicha algoritmlar", Tarmoqlar, 4 (4): 357–369, doi:10.1002 / net.3230040407.
Golumbich, Martin Charlz (1980), Algoritmik grafik nazariyasi va mukammal grafikalar, Academic Press, ISBN 978-0-444-51530-8, dan arxivlangan asl nusxasi 2010-05-22, olingan 2008-05-21. Ikkinchi nashr, Diskret matematika yilnomalari 57, Elsevier, 2004 yil.
Jeris, Benson L.; Lin, Min Chih; Makkonnell, Ross M.; Spinrad, Jeremi P.; Schwarcfiter, Jayme L. (2009), "Helli Circular-Arc modellari va grafikalarini chiziqli vaqt ichida tanib olish", Algoritmika, 59 (2): 215–239, CiteSeerX 10.1.1.298.3038, doi:10.1007 / s00453-009-9304-5.
Makkonnell, Ross (2003), "Dumaloq yoyli grafikalarni chiziqli vaqtda tan olish", Algoritmika, 37 (2): 93–147, CiteSeerX 10.1.1.22.4725, doi:10.1007 / s00453-003-1032-7.
Taker, Alan (1980), "Dumaloq yoyli grafikalar uchun samarali sinov", Hisoblash bo'yicha SIAM jurnali, 9 (1): 1–24, doi:10.1137/0209001.

Tashqi havolalar

Dumaloq yoy grafigi, Grafik sinfi qo'shimchalari to'g'risida ma'lumot tizimi

[1] Kaplan, Xaym; Nussbaum, Yahav (2011-11-01). "Dumaloq kamonli grafikalarni chiziqli-vaqt bo'yicha oddiyroq tanib olish". Algoritmika. 61 (3): 694–737. CiteSeerX 10.1.1.76.2480. doi:10.1007 / s00453-010-9432-y. ISSN 0178-4617.

[2] Aleksandersson, Per; Panova, Greta (Dekabr 2018). "LLT polinomlari, kromatik kvazimimetrik funktsiyalari va tsikllari bo'lgan grafikalar". Diskret matematika. 341 (12): 3453–3482. arXiv:1705.10353. doi:10.1016 / j.disc.2018.09.001.

[claw3-3] Tomonidan boshqacha, ammo ekvivalent ta'rifi bilan tavsiflangan Chudnovskiy va Seymur (2008).

[4] Deng, Hell & Huang (1996) pg. ?

[1]

[2]

[3]

[4]