Daraxtzorlik - Arboricity

The daraxtzorlik ning yo'naltirilmagan grafik ning minimal soni o'rmonlar uning chekkalari bo'lishi mumkin taqsimlangan. Bunga teng ravishda bu minimal son tarqalgan o'rmonlar grafaning barcha qirralarini qoplash uchun kerak. The Nesh-Uilyams teoremasi grafik zarur bo'lganda etarli va etarli sharoitlarni ta'minlaydi k-arborik.

Misol

Ning bo'limi to'liq ikki tomonlama grafik K_4,4 daraxtzorligi uchligini ko'rsatib, uchta o'rmonga.

Rasmda to'liq ikki tomonlama grafik K_4,4, qirralarning uchta o'rmonga bo'linishini ko'rsatadigan ranglar bilan. K_4,4 kamroq o'rmonlarga ajratish mumkin emas, chunki sakkizta tepalikdagi har qanday o'rmon ko'pi bilan etti qirraga ega, umumiy grafika esa o'n oltita qirraga ega bo'lib, bitta o'rmondagi qirralarning sonidan ikki baravar ko'p. Shuning uchun, daraxtzorligi K_4,4 uchta.

Daraxtlilik zichlik o'lchovi sifatida

Grafikning daraxtzorligi - bu qanday qilib o'lchovidir zich grafigi quyidagicha: ko'p qirralari bo'lgan grafikalar yuqori daraxtzorga ega va yuqori daraxtzorlarga ega bo'lgan grafikalar zich subgrafaga ega bo'lishi kerak.

Batafsilroq, har qanday n-vertex o'rmonlari ko'pi bilan n-1 qirralarga ega bo'lgani uchun, n n vertikallari va m qirralari bilan grafika daraxtzorligi kamida ${ displaystyle lceil m / (n-1) rceil}$ . Bundan tashqari, har qanday grafika subgrafalarida grafika o'zidan kattaroq daraxtzorlik bo'lishi mumkin emas, yoki shunga o'xshash ravishda grafitning daraxtzorligi hech bo'lmaganda uning har qanday pastki chizig'ining maksimal daraxtzorligi bo'lishi kerak. Nesh-Uilyams daraxtzorlikni tavsiflash uchun ushbu ikkita faktni birlashtirish mumkinligini isbotladi: agar biz n ga yo'l qo'ysak_S va m_S berilgan grafaning har qanday subgrafasining navbati bilan vertikal va qirralarning sonini belgilang, keyin grafitning daraxtzorligi teng ${ displaystyle max _ {S} { lceil m_ {S} / (n_ {S} -1) rceil }.}$

Har qanday planar grafik bilan ${ displaystyle n}$ tepaliklar maksimal darajada ${ displaystyle 3n-6}$ qirralar, undan Nash-Uilyams formulasidan kelib chiqib, planar grafikalar eng ko'p uchta daraxtzorga ega. Shnayder tekislik grafigini a deb nomlangan uchta o'rmonga maxsus dekompozitsiyasidan foydalangan Shnayder daraxti topish a to'g'ri chiziqli ko'mish kichik maydonning panjarasiga har qanday planar grafika.

Algoritmlar

Grafikning arborligi umumiyroq bo'lgan maxsus holat sifatida ifodalanishi mumkin matroid qismlarga ajratish matroid elementlari to'plamini oz sonli mustaqil to'plamlarning birlashmasi sifatida ifodalashni istagan muammo. Natijada, daraxtzorlikni polinom vaqt algoritmi bilan hisoblash mumkin (Gabov va Westermann 1992 yil ).

Tegishli tushunchalar

The anorbozlik grafika - bu grafaning qirralarini ajratish mumkin bo'lgan chekka-bo'linmagan asiklik bo'lmagan subgrafalarning maksimal soni.

The yulduz daraxtzorligi grafika - har bir daraxt daraxti a bo'lgan minimal o'rmonning kattaligi Yulduz (eng ko'pi bargsiz tugunli daraxt), unga grafaning qirralarini ajratish mumkin. Agar daraxt o'zi yulduz bo'lmasa, uning yulduz daraxtzorligi ikkitadir, chunki qirralarni navbati bilan daraxt ildizidan toq va juft masofada ikkita kichik to'plamga bo'lish orqali ko'rish mumkin. Shuning uchun har qanday grafadagi yulduz daraxtzorligi hech bo'lmaganda daraxtzorlikka, ko'pi bilan ikki baravarga teng bo'ladi.

The chiziqli daraxtzorlik Grafikning minimal soni chiziqli o'rmonlar (yo'llarning to'plami) ichiga grafaning qirralarini ajratish mumkin. Grafikning chiziqli daraxtzorligi uning maksimal darajasi bilan chambarchas bog'liq daraja va uning Nishab raqami.

The pseudoarboricity Grafikning minimal soni qalbaki o'rmonlar uning qirralarini ajratish mumkin. Bunga teng ravishda, bu butun songa qadar yaxlitlangan grafikning har qanday subgrafasidagi qirralarning tepalikka maksimal nisbati. Arboricity-da bo'lgani kabi, pseudoarboricity matroid tuzilishga ega bo'lib, uni samarali hisoblashga imkon beradi (Gabov va Westermann 1992 yil ).

The qalinligi grafika - bu qirralarning bo'linishi mumkin bo'lgan planar subgrafalarning minimal soni. Har qanday planar grafada daraxtzorlik uchligi bo'lganligi sababli, har qanday grafaning qalinligi hech bo'lmaganda daraxtzorlikning uchdan bir qismiga, ko'pi bilan daraxtzorlikka teng.

The degeneratsiya grafigi hamma uchun maksimal hisoblanadi induktsiya qilingan subgraflar grafika, minimal daraja subgrafadagi tepalikning. Daraxtzor bilan grafikaning degeneratsiyasi ${ displaystyle a}$ hech bo'lmaganda teng ${ displaystyle a}$ , va eng ko'piga teng ${ displaystyle 2a-1}$ . Grafikning bo'yash raqami, shuningdek Sekeres-Vilf raqami (Szekeres & Wilf 1968 yil ) har doim uning degeneratsiyasiga teng va 1 (Jensen va Toft 1995 yil, p. 77f.).

The kuch grafika - bu butun son qismi grafada chizish mumkin bo'lgan eng ko'p ajratilgan daraxtlar sonini beradigan qismli qiymatdir. Bu daraxtzorlik tufayli yuzaga keladigan qoplama muammosiga ikki tomonlama bo'lgan qadoqlash muammosi. Ikki parametr Tutte va Nash-Uilyams tomonidan birgalikda o'rganilgan.

The fraksional daraxtzorlik grafika uchun belgilanganidek, daraxtzorlikni takomillashtirishdir ${ displaystyle G}$ kabi ${ displaystyle max {m_ {S} / (n_ {S} -1) mid S subseteq G }.}$ Boshqacha qilib aytganda, grafning daraxtzorligi - bu fraksiyonel daraxtzorning shiftidir.

The (a, b) -kompozitsiya daraxtzorlikni umumlashtiradi. Grafik ${ displaystyle (a, b)}$ - agar uning qirralarini ajratish mumkin bo'lsa, ajraladigan ${ displaystyle a + 1}$ to'plamlar, ularning har biri o'rmonni qo'zg'atadi, faqat maksimal darajadagi grafikani induktsiyadan tashqari ${ displaystyle b}$ . Arboricity bilan grafik ${ displaystyle a}$ bu ${ displaystyle (a, 0)}$ - ajraladigan.

The daraxt raqami bu grafaning chekkalarini qoplaydigan minimal daraxtlar soni.

Maxsus ko'rinishlar

Daraxtlilik paydo bo'ladi Goldberg - Seymur gumoni.

Adabiyotlar

Alon, N. (1988). "Grafiklarning chiziqli daraxtzorligi". Isroil matematika jurnali. 62 (3): 311–325. doi:10.1007 / BF02783300. JANOB 0955135.CS1 maint: ref = harv (havola)
Chen, B .; Matsumoto, M.; Vang, J .; Chjan, Z.; Zhang, J. (1994). "Nash-Uilyamsning grafikaning arborligi uchun teoremasining qisqa isboti". Grafika va kombinatorika. 10 (1): 27–28. doi:10.1007 / BF01202467. JANOB 1273008.CS1 maint: ref = harv (havola)
Erdos, P.; Hajnal, A. (1966). "Grafiklarning va set tizimlarining xromatik soni to'g'risida" (PDF). Acta Mathematica Hungarica. 17 (1–2): 61–99. doi:10.1007 / BF02020444. JANOB 0193025. Arxivlandi asl nusxasi (PDF) 2013-05-24. Olingan 2011-05-30.CS1 maint: ref = harv (havola)
Gabov, H. N .; Westermann, H. H. (1992). "O'rmonlar, ramkalar va o'yinlar: matroid summasi va dasturlari algoritmlari". Algoritmika. 7 (1): 465–497. doi:10.1007 / BF01758774. JANOB 1154585.CS1 maint: ref = harv (havola)
Hakimi, S. L.; Mitchem, J .; Shmeyxel, E. E. (1996). "Grafiklarning yulduzcha daraxtzorligi". Diskret matematika. 149: 93–98. doi:10.1016 / 0012-365X (94) 00313-8. JANOB 1375101.CS1 maint: ref = harv (havola)
Jensen, T. R .; Toft, B. (1995). Grafikni bo'yash muammolari. Nyu-York: Vili-Interscience. ISBN 0-471-02865-7. JANOB 1304254.CS1 maint: ref = harv (havola)
Seynt J. A. Nash-Uilyams (1961). "Cheklangan grafikli daraxtlar". London Matematik Jamiyati jurnali. 36 (1): 445–450. doi:10.1112 / jlms / s1-36.1.445. JANOB 0133253.CS1 maint: ref = harv (havola)
Seynt J. A. Nash-Uilyams (1964). "Sonli grafiklarning o'rmonlarga parchalanishi". London Matematik Jamiyati jurnali. 39 (1): 12. doi:10.1112 / jlms / s1-39.1.12. JANOB 0161333.CS1 maint: ref = harv (havola)
V. Shnayder (1990). "Tarmoqqa planar grafikalarni kiritish". Proc. Diskret algoritmlar bo'yicha 1-ACM / SIAM simpoziumi (SODA). 138–148 betlar.
Sekeres, G.; Wilf, H. S. (1968). "Grafikning xromatik soni uchun tengsizlik". Kombinatorial nazariya jurnali. doi:10.1016 / s0021-9800 (68) 80081-x. JANOB 0218269.CS1 maint: ref = harv (havola)
Tutte, V. T. (1961). "Grafikni n bog'liq bo'lgan omillarga ajratish muammosi to'g'risida". London Matematik Jamiyati jurnali. 36 (1): 221–230. doi:10.1112 / jlms / s1-36.1.221. JANOB 0140438.CS1 maint: ref = harv (havola)