Кореново дърво

[Гост]

Нека T=(V,E,r) е кореново дърво, за което, всеки връх с изключение на листата, има не повече от m наследника. Некa L е броят на листата в T и h е дълбочината на дървото. Да се докаже, че $h \ge \left[ \log_{m}L \right].$

[Петър Евгениев]

Нека T=(V,E,r) е кореново дърво, за което, всеки връх с изключение на листата, има не повече от m наследника. Некa L е броят на листата в T и h е дълбочината на дървото. Да се докаже, че $h \ge \left[ \log_{m}L \right].$

От условието "(...) всеки връх , с изключение на листата, има не повече от $m$ наследника(...)" значи дървото $T$ е $m-$ично дърво. Терминът "branching factor" , (най-известното е 2-ично дърво, там $m=2.$) Ако под $h$ се има предвид височината на дървото - максималната дължина на път от връх от корена.
Е сега очевидно това неравенство ще следва от следното твърдение:
В $Т$ с разклоненост $m$ и височината на $T$ e $h,$ то в $T$ има не повече от $m^{h}$ листа.
Доста очевидно твърдение като си "нарисуваш точно 2 картинки" и помислиш как можеш да максмизираш броя на листата - ами като от всеки връх има максималняит брой наследници, т.е. $m$ и така височината е $h$ на всяка от тези $h$ единици имаме $m$ нови наследници и та листата ще са максимално $m^{h}.$
Т.е. ,ако сме доказали това имаме, че ако $L$ е броят на листата , то:
$$L \leq m^{h}.$$
Оттук пък $$\left[log_{m} L \right]\leq log_{m} L \leq h.$$
И получихме желаното неравенство $\left[log_{m}L \right] \leq L.$
Затова е достатъчно да докажем това твърдение.
И така, например с индукция по височината $h.$
Ако височината е $h=1$ и $T$ е $m-$ично дърво, то най-много може да има $m=m^{1}$ листа. Значи в този случай е в сила (даже равенство) нашето нестрого неравенство($L \leq m^{h}$).
Нека допуснем, че за $m-$ичното дърво $Т$ с височина $h \in \mathbb{N}$ е изпълнено неравенството с броя на листата $L:$ $$L \leq m^{h}.$$
Трябва да докажем, че ако височината на това дърво стане $h+1,$ то отново е в сила, че $L \leq m^{h+1}.$
Ами , разбира се че е така, защото ако височината е била $h$ и за да стане $h+1$ трябва да добавим към поне едно и не повече от $m$ от листата, които имат височина $h$ в $T$ още по поне един и не повече от $m$ наследника. Значи ние искаме да максимализираме броя на листата, т.е. в най-екстремния случай, в който $m$ от листата имат височина $h$ в това дърво $T$ на всяко едно от тях ще добавим още $m$ наследника. Ама тогава това увеличава броя на листата с колкото са били(разглеждаме най-екстремния случай) $m^{h}$ стават на всяко се лепват вече нови $m$ които те вече са листа, значи в най-екстремния случай листата не са повече от $m^{h}.m=m^{h+1}.$
Което трябваше да направим и като индукционна стъпка.
Твърдението е доказано.

[Петър Евгениев]

Нека T=(V,E,r) е кореново дърво, за което, всеки връх с изключение на листата, има не повече от m наследника. Некa L е броят на листата в T и h е дълбочината на дървото. Да се докаже, че $h \ge \left[ \log_{m}L \right].$

От условието "(...) всеки връх , с изключение на листата, има не повече от $m$ наследника(...)" значи дървото $T$ е най-много $m-$ично дърво. Терминът "branching factor" , .

Така , де или разглеждам екстремния случай или просто слагам едно " е най-много $m.$"

[Гост]

Нека T=(V,E,r) е кореново дърво, за което, всеки връх с изключение на листата, има не повече от m наследника. Некa L е броят на листата в T и h е дълбочината на дървото. Да се докаже, че $h \ge \left[ \log_{m}L \right].$

Изразът " с изключение на листата" не е ли излишен? Листата нали нямат наследници? Или???