حل تشریحی سوال شماره 36 دروس مشترک

فرض کنید T یک درخت دودویی دلخواه با $n>5$ گره است که هر گره غیربرگ دقیقا دو فرزند دارد. به ازای هر گره v فرض کنید d(v) برابر فاصله v تا نزدیکترین برگ باشد. برای برگ‌ها این مقدار برابر صفر است. فرض کنید $H=\sum d\left(v\right)$ که جمع روی همه گره‌های T است. کدام گزینه در خصوص گزاره‌های زیر، به‌ترتیب درست است؟

الف) همواره داریم: $H\ge n$

ب) به‌ازای هر گره v از T داریم: $d\left(v\right)\le {\log }_{2}n$