ثابت کنید که تعداد برگها در یک درخت با کمک درجهٔ گره های نابرگ با فرمول $2+\sum_{i=1}^r(\deg v_i-2)$ بدست می آید.

Question

یک درخت را در نظر بگیرید. یک گره از درجهٔ یک را برگ می‌نامیم و گره‌ای که برگ نیست را گرهٔ ناآویزان بنامید. گره‌های ناآویزان را با $v_1$ و $v_2$ و ... و $v_r$ نام‌گذاری کنید که $r$ تعداد گره‌های ناآویزان است. ثابت کنید که تعداد برگ‌ها برابر است با

$$2+\sum_{i=1}^r(\deg v_i-2)$$

Answer 1

اگر تعداد راس هایی که از درجه یک هستند را با $k$ و بقیه را با $k'$ نمایش دهیم آنگاه $p=k+k'$ که در آن $p$ تعداد کل رئوس است می دانیم که $2q= \sum deg(v_{i} )$ و چون درخت داریم لذا $q=p-1$ پس داریم

$$2q=2p-2=2 k+2k'-2= \sum deg(v_{i} )=$$ $$\sum_{deg(v_{i} )=1} deg(v_{i} )+\sum_{deg(v_{i} ) > 1} deg(v_{i} )=\sum_{deg(v_{i} )=1} 1+\sum_{deg(v_{i} ) > 1} deg(v_{i} )=$$ $$k+\sum_{deg(v_{i} ) > 1} deg(v_{i} )$$ لذا $2 k+2k'-2=k+\sum_{deg(v_{i} ) > 1} deg(v_{i} )$ پس $k-2=\sum_{deg(v_{i} ) > 1} deg(v_{i} ) -2k'$ اما می دانیم $\sum_{deg(v_{i} ) > 1} 1=k'$ که با جایگذاری داریم: $$k-2=\sum_{deg(v_{i} ) > 1} deg(v_{i} ) -2\sum_{deg(v_{i} ) > 1} 1=\sum_{deg(v_{i} ) > 1} (deg(v_{i} )-2)$$ و لذا $k=2+\sum_{deg(v_{i} ) > 1} (deg(v_{i} )-2)$