به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
600 بازدید
در دبیرستان و دانشگاه توسط OXIDE

ثابت کنید در یک درخت با راس های غیر آویزان $v_i$ تعداد برگ برابر است با:

$2+ \sum (degv_i-2) $

البته خود برگ ها را در این فرمول نمیگذاریم.

1 پاسخ

+1 امتیاز
توسط erfanm

اگر تعداد راس هایی که از درجه یک هستند را با $ 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)$

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...