Minimal darajali daraxt daraxti - Minimum degree spanning tree

Yilda grafik nazariyasi, ulangan grafik uchun ${ displaystyle G}$, a yoyilgan daraxt ${ displaystyle T}$ ning subgrafasi ${ displaystyle G}$ hali ham cho'zilgan eng kam qirralarning soni bilan ${ displaystyle G}$. Bir qator xususiyatlar haqida isbotlash mumkin ${ displaystyle T}$. ${ displaystyle T}$ asiklik, bor (${ displaystyle | V | -1}$) qayerda ${ displaystyle V}$ - bu tepaliklar soni ${ displaystyle G}$ va boshqalar.

A minimal darajadagi daraxt ${ displaystyle T '}$ eng kam maksimal darajaga ega bo'lgan daraxt daraxti. Maksimal darajadagi tepalik ${ displaystyle T '}$ mumkin bo'lgan daraxtlar orasida eng kami ${ displaystyle G}$.

Topish minimal darajadagi daraxt NP qiyin, lekin mahalliy qidirish algoritmi daraxtni berishi mumkin, uning maksimal darajasi maksimal darajaga va eng maqbul daraxtga teng bo'ladi.

Qarang Darajali cheklangan daraxt.

Bu maqola emas keltirish har qanday manbalar. Iltimos yordam bering ushbu maqolani yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Manbaga ega bo'lmagan materialga qarshi chiqish mumkin va olib tashlandi. Manbalarni toping: "Daraxtning minimal darajasi"  – Yangiliklar  · gazetalar  · kitoblar  · olim  · JSTOR (2009 yil aprel) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)