Chordal tugashi - Chordal completion

Yilda grafik nazariyasi, matematikaning bir bo'limi, a akkord tugashi berilgan yo'naltirilmagan grafik G a akkord grafigi, xuddi shu tepalik to'plamida, bor G subgraf sifatida akkordning minimal bajarilishi akkord tugashi, shunday qilib qirrani olib tashlash natijasida hosil bo'lgan har qanday grafik endi akkord tugashi bo'lmaydi. A akkordning minimal bajarilishi imkon qadar kam qirralar bilan akkord tugallanishi.

Akkordni bajarishning boshqa turi, ning o'lchamini minimallashtirish maksimal klik olingan akkord grafikasida, ni aniqlash uchun foydalanish mumkin kenglik ning G. Chordal komplektlari bir nechta boshqa grafik sinflarini, shu jumladan ATsiz grafikalarni tavsiflash uchun ham ishlatilishi mumkin, tirnoqsiz ATsiz grafikalar va kograflar.

Eng kam akkord tugallanishi 1979 yilgi kitobda murakkabligi aniqlangan o'n ikkita hisoblash muammosidan biri edi Kompyuterlar va qulaylik.Kordalani bajarish dasturlari bajarilish paytida to'ldirishni minimallashtirish muammosini modellashtirishni o'z ichiga oladi Gaussni yo'q qilish kuni siyrak nosimmetrik matritsalar va qayta qurish filogenetik daraxtlar.

Grafikning Chordal tugallanishi ba'zan uchburchak,[1] ammo bu atama grafik nazariyasi nuqtai nazaridan ham noaniq, chunki u maksimal darajaga ham murojaat qilishi mumkin planar grafikalar.

Tegishli graf oilalari

Grafik G bu ATsiz grafik agar u faqat uning barcha minimal akkord kompilyatsiyalari bo'lsa intervalli grafikalar. G a tirnoqsiz AT-bepul grafik, agar u barcha minimal akkord tugallanishi to'g'ri intervalli grafikalar bo'lsa. Va G a cograf agar u faqat uning barcha minimal akkord kompilyatsiyalari bo'lsa ahamiyatsiz mukammal grafikalar.[1]

Grafik G bor kenglik ko'pi bilan k agar va faqat agar G kamida bitta akkord yakuniga ega maksimal klik hajmi eng ko'p k + 1. Unda bor yo'l kengligi ko'pi bilan k agar va faqat agar G kamida bitta akkord tugallanishiga ega, bu maksimal klik o'lchamiga ega bo'lgan intervalli grafika k + 1. Unda bor tarmoqli kengligi ko'pi bilan k agar va faqat agar G kamida bitta akkord tugallanishiga ega, bu eng yuqori klik o'lchamiga ega bo'lgan to'g'ri oraliq grafigi k + 1.[2] Va bor daraxt chuqurligi k va agar u kamida bitta akkord tugallangan bo'lsa, bu maksimal darajada eng yuqori klik o'lchamiga ega bo'lgan ahamiyatsiz mukammal grafik. k.[3]

Ilovalar

Akkordni yakunlashning asl qo'llanilishi Kompyuterlar va qulaylik o'z ichiga oladi Gaussni yo'q qilish uchun siyrak matritsalar. Gaussni yo'q qilish jarayonida, dastlab matritsaning nolga teng bo'lgan koeffitsientlarini to'ldirishni minimallashtirish istagi paydo bo'ldi, ammo keyinchalik nolga aylandi, chunki bu koeffitsientlarning qiymatlarini hisoblash zarurati algoritmni sekinlashtiradi. Nolinchi nollarning siyrakligi nosimmetrik matritsa yo'naltirilmagan grafika bilan tavsiflanishi mumkin (matritsani o'zi kabi qo'shni matritsa ); to'ldirilgan matritsadagi nollarning naqshlari har doim akkord grafigi bo'lib, har qanday minimal akkord tugashi shu tarzda to'ldirish naqshiga mos keladi. Agar grafikaning akkord tugashi berilgan bo'lsa, natijada olingan akkord grafigini yo'q qilish tartibini hisoblash orqali ushbu to'ldirish naqshiga erishish uchun Gauss eliminatsiyasini bajarish bosqichlari ketma-ketligini topish mumkin. Shu tarzda, minimal to'ldirish muammosini eng kam akkord tugatish muammosiga teng deb hisoblash mumkin.[4] Ushbu dasturda, planar grafikalar ikki o'lchovli cheklangan elementlar tizimining echimida paydo bo'lishi mumkin; dan kelib chiqadi planar ajratuvchi teorema har bir tekislik grafigi bilan n tepaliklar maksimal darajada akkord bilan yakunlanadi O(n jurnal n) qirralar.[5]

Boshqa dastur keladi filogeniya, evolyutsion daraxtlarni rekonstruksiya qilish muammosi, masalan, genetik mutatsiyalarga uchragan organizmlar daraxtlari yoki qadimiy qo'lyozmalar to'plamlari daraxtlari bir-biridan skribal xatolarga ko'chirilgan. Agar har bir genetik mutatsiya yoki skribal xato faqat bir marta sodir bo'ladi deb hisoblasa, u holda a mukammal filogeniya, har qanday o'ziga xos xususiyatga ega bo'lgan turlar yoki qo'lyozmalar har doim bir-biriga bog'langan subtree hosil qiladigan daraxt. Sifatida Buneman (1974) mukammal filogeniyaning mavjudligini akkord tugatish muammosi sifatida modellashtirish mumkin. Bittasi "bir-biriga o'xshash grafik" chizadi G bunda tepaliklar atribut qiymatlari (tur yoki qo'lyozma uchun ba'zi bir xususiyatlar uchun aniq tanlovlar) va qirralar kamida bitta tur bilan bo'lishadigan atribut qiymatlari juftligini ifodalaydi. Grafikning tepalari bo'lishi mumkin rangli har bir atribut qiymati kelib chiqadigan xususiyatlarning o'ziga xosligi bilan, shuning uchun ranglarning umumiy soni filogeniyani olish uchun ishlatiladigan xususiyatlar soniga teng bo'ladi. Shunda mukammal filogeniya mavjud bo'ladi va agar mavjud bo'lsa G rang berishni hurmat qiladigan akkord tugashiga ega.[6]

Hisoblashning murakkabligi

Ro'yxatiga kiritilgan bo'lsa-da ochiq muammo 1979 yilgi kitobda Kompyuterlar va qulaylik,[7] akkordni bajarish bo'yicha minimal muammoning hisoblash murakkabligi (shuningdek, minimal to'ldirish muammo) tezda hal qilindi: Yannakakis (1981) buni ko'rsatdi To'liq emas.[8] Agar minimal akkord tugashi qo'shilsa k grafaga qirralar G, keyin ko'pi bilan akkord tugallanishini topish mumkin 8k2 polinom vaqtida qirralarning qo'shilishi.[9] Optimal to'plamini topish muammosi k qo'shish uchun qirralarni a bilan ham hal qilish mumkin sobit parametrlarga yo'naltirilgan algoritm, vaqt ichida polinom grafik o'lchamida va subeksponential ichidak.[10]

The kenglik (akkord tugashining minimal klik kattaligi) va yo'lning kengligi va daraxt chuqurligini o'z ichiga olgan tegishli parametrlarni hisoblash uchun NP tugallangan va (agar P = NP bo'lmasa) polinom vaqtida ularning maqbul qiymatlarining doimiy koeffitsientiga yaqinlashtirilmaydi; ammo, taxminiy algoritmlar logaritmik yaqinlashish nisbati ular uchun ma'lum.[11]

Minimal to'ldirish va kenglik muammolarini echish mumkin eksponent vaqt. Aniqrog'i, uchun n- vertex grafigi, vaqt O(1.9601n).[12]

Adabiyotlar

  1. ^ a b Parra, Andreas; Sheffler, Petra (1997), "Xordal grafik birikmalarining tavsiflari va algoritmik qo'llanmalari", Graflar va kombinatoriya optimallashtirish bo'yicha Tventning 4-seminari (Enshed, 1995), Diskret amaliy matematika, 79 (1–3): 171–188, doi:10.1016 / S0166-218X (97) 00041-3, JANOB  1478250.
  2. ^ Kaplan, Xaym; Shamir, Ron (1996), "Kichik klivlar bilan to'g'ri intervalli grafikalar uchun kenglik, o'tkazuvchanlik va tugatish muammolari", Hisoblash bo'yicha SIAM jurnali, 25 (3): 540–561, doi:10.1137 / S0097539793258143, JANOB  1390027.
  3. ^ Eppshteyn, Devid (2012 yil 15-noyabr), Grafik parametrlari va supergrafadagi kliklar.
  4. ^ Rose, Donald J. (1972), "Chiziqli tenglamalarning siyrak musbat aniqlangan tizimlarining sonli echimini grafik-nazariy o'rganish", Grafika nazariyasi va hisoblash, Academic Press, Nyu-York, 183–217 betlar, JANOB  0341833.
  5. ^ Chung, F. R. K.; Mumford, Devid (1994), "Planar grafikalarning xordal komplektlari", Kombinatorial nazariya jurnali, B seriyasi, 62 (1): 96–106, doi:10.1006 / jctb.1994.1056, JANOB  1290632.
  6. ^ Buneman, Piter (1974), "Qattiq elektron grafikalar tavsifi", Diskret matematika, 9 (3): 205–212, doi:10.1016 / 0012-365X (74) 90002-8, JANOB  0357218.
  7. ^ Garey, Maykl R.; Jonson, Devid S. (1979), Kompyuterlar va echib bo'lmaydiganlik: NP to'liqligi nazariyasi uchun qo'llanma, W. H. Freeman, ISBN  0-7167-1045-5, [OPEN4], p. 286; yangilash, p. 339.
  8. ^ Yannakakis, Mixalis (1981), "Minimal to'ldirishni hisoblash NP bilan yakunlandi", SIAM algebraik va diskret usullar jurnali, 2 (1): 77–79, CiteSeerX  10.1.1.128.192, doi:10.1137/0602010, hdl:10338.dmlcz / 140775, JANOB  0604513.
  9. ^ Natanzon, Assaf; Shamir, Ron; Sharan, Roded (2000), "Minimal to'ldirish masalasi uchun polinomlarni taxminiy algoritmi", Hisoblash bo'yicha SIAM jurnali, 30 (4): 1067–1079, doi:10.1137 / S0097539798336073, JANOB  1786752.
  10. ^ Fomin, Fedor V.; Villanger, Yngve (2013), "Minimal to'ldirish uchun subxponential parametrlangan algoritm", Hisoblash bo'yicha SIAM jurnali, 42 (6): 2197–2216, arXiv:1104.2230, doi:10.1137 / 11085390X, JANOB  3138120.
  11. ^ Bodlaender, Xans L.; Gilbert, Jon R.; Xafsteynsson, Xalmtir; Kloks, Ton (1995), "Kenglik, yo'lning kengligi, frontsize va eng qisqa eliminatsiya daraxtini yaqinlashtirish", Algoritmlar jurnali, 18 (2): 238–255, doi:10.1006 / jagm.1995.1009, JANOB  1317666.
  12. ^ Fomin, Fedor V.; Kratsch, Diter; Todinca, Ioan (2004), "Kenglik va minimal to'ldirish uchun aniq (eksponent) algoritmlar", Avtomatika, tillar va dasturlash: 31-xalqaro kollokvium, ICALP 2004, Turku, Finlyandiya, 2004 yil 12-16 iyul, Ish yuritish., Kompyuter fanidan ma'ruza matnlari, 3142, Springer-Verlag, 568-580 betlar, doi:10.1007/978-3-540-27836-8_49.