Qisman daraxt - Partial k-tree - Wikipedia

Yilda grafik nazariyasi, a qisman k-daraxt a ning subgrafasi sifatida aniqlangan grafik turidir k-daraxt yoki bilan grafik sifatida kenglik ko'pi bilank. Ko'pchilik Qattiq-qattiq grafikalar bo'yicha kombinatorial masalalar, qisman bilan cheklangan bo'lsa, polinom vaqtida echiladi k-ning chegaralangan qiymatlari uchun daraxtlark.

Voyaga etmaganlarning grafigi

Qisman 3 ta daraxt uchun voyaga etmaganlarga taqiqlangan

Har qanday sobit doimiy uchun k, qisman k- daraxtlar operatsiya ostida yopiladi voyaga etmaganlar va shuning uchun Robertson-Seymur teoremasi, bu oilani cheklangan to'plamlar jihatidan tavsiflash mumkin taqiqlangan voyaga etmaganlar. Qisman 1 daraxtlar to'liq o'rmonlar, va ularning bitta taqiqlangan kichigi uchburchak, qisman 2 daraxtlari uchun bitta taqiqlangan minorasi to'liq grafik to'rtta tepada. Biroq, kattaroq qiymatlari uchun taqiqlangan voyaga etmaganlar soni ko'paymoqda k. Qisman 3 daraxtlar uchun to'rtta taqiqlangan voyaga etmaganlar mavjud: beshta tepalikdagi to'liq grafika, sekizli grafik oltita tepalik bilan, sakkizta vertikal Vagner grafigi, va beshburchak prizma o'nta tepalik bilan.[1]

Dinamik dasturlash

Ko'pgina algoritmik muammolar To'liq emas chunki o'zboshimchalik bilan grafikalar qisman uchun samarali echilishi mumkin k- tomonidan daraxtlar dinamik dasturlash yordamida daraxtlarning parchalanishi ushbu grafiklardan.[2]

Grafiklarning turdosh oilalari

Agar grafikalar oilasi chegaralangan bo'lsa kenglik, keyin u qisman oiladir k- daraxtlar, qaerda k Bu kenglik bo'yicha bog'langan.Bu xususiyatga ega bo'lgan grafikalar oilalariga quyidagilar kiradi kaktus grafikalari, qalbaki o'rmonlar, ketma-ket parallel grafikalar, tashqi planli grafikalar, Halin grafikalar va Apolloniya tarmoqlari.[1] Masalan, ketma-ket parallel grafikalar qisman 2 daraxtlarning subfamilasi bo'lib, kuchliroq grafika qisman 2 daraxt bo'lib, agar ularning har biri bo'lsa bir-biriga bog'langan komponentlar ketma-ket parallel.

The oqim grafiklarini boshqarish paydo bo'lgan jamlama ning tuzilgan dasturlar kabi aniq vazifalarni bajarishga imkon beradigan cheklangan kenglik mavjud ro'yxatdan o'tkazishni taqsimlash ular ustida samarali bajarilishi kerak.[3]

Izohlar

  1. ^ a b Bodlaender (1998).
  2. ^ Arnborg va Proskurovski (1989); Bern, Lawler va Vong (1987); Bodlaender (1988).
  3. ^ Torup (1998).

Adabiyotlar

  • Arnborg, S .; Proskurowski, A. (1989), "NP qattiq muammolari uchun chiziqli vaqt algoritmlari qisman cheklangan k- daraxtlar ", Diskret amaliy matematika, 23 (1): 11–24, doi:10.1016 / 0166-218X (89) 90031-0.
  • Bern, M. V.; Lawler, E. L.; Vong, A. L. (1987), "Parchalanadigan grafiklarning optimal subgrafalarini chiziqli vaqt bo'yicha hisoblash", Algoritmlar jurnali, 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3.
  • Bodlaender, Xans L. (1988), "Kengligi chegaralangan grafikalar bo'yicha dinamik dasturlash", Proc. Avtomatika, tillar va dasturlash bo'yicha 15-xalqaro kollokvium, Kompyuter fanidan ma'ruza matnlari, 317, Springer-Verlag, 105-118 betlar, doi:10.1007/3-540-19488-6_110, ISBN  978-3-540-19488-0.
  • Bodlaender, Xans L. (1998), "Qisman k- cheklangan kengligi bilan grafikalar arboretum ", Nazariy kompyuter fanlari, 209 (1–2): 1–45, doi:10.1016 / S0304-3975 (97) 00228-4, hdl:1874/18312.
  • Torup, Mikkel (1998), "Barcha tuzilgan dasturlarda daraxtlar kengligi kichik va registr yaxshi ajratilgan", Axborot va hisoblash, 142 (2): 159–181, doi:10.1006 / inco.1997.2697.