چرا تعداد درخت های پوشا در گراف کامل n^(n-2) میشه؟ نتونستم اثبات کنم
سلام. به نظرم باید یالها رو به ترتیب انتخاب کنیم. برای گراف n راسی باید n-1 یال بگیریم. هر یال از دو راس تشکیل میشه. از یک راس شروع کنید و سعی کنید یک راس یک راس به مجموعه اضافه کنید.
عذرخواهی میکنم. توی این روش شمول و طرد زیادی داریم که نمیشه رفعش کرد.
به نظرم به جواب رسیدن سخته. برای هر درخت کامل میشه یه رابطه بازگشتی سنگین بدست آورد که بدست آوردن فرمول کلیش مشکله. بدست آوردن رابطه بازگشتیش میشه مجموع حالات زیر: (چون راس ها شماره دارن، گراف با n+1 راس میشه گراف حاصل از اصافه کردن راس با شماره n+1 به گراف nراسی. پس درمورد درجه راس n+1 بحث میکنیم. توجه داشته باشید که مجموعه ها شماره ندارن پس مثل روش استرلینگ عمل میکنیم.)
راس اضافه شده از درجه ۱ باشه.
راس اضافه شده از درجه ۲ باشه.
...
راس اضافه شده از درجه n باشه.
توی هر حالت باید یه تعداد راس از مجموعه n راس برای تقسیم کردن به k قسمت (با توجه به درجه راس جدید) انتخاب کنیم و در جملات قبلی دنباله ضرب کنیم. برای مثال برای گراف ۴ راسی داریم:
راس چهارم از درجه ۱ باشه. تعداد حالات میشه انتخاب ۳ از ۳ ضربدر جمله سوم دنباله که ۳ هست ضربدر انتخاب ۱ از ۳ برای انتخاب اینکه راس چهرم به کدوم وصل باشه. جواب میشه ۹
راس چهارم از درجه ۲ باشه. تعداد حالات میشه انتخاب ۲ از ۳ ضربدر جمله اول و دوم دنباله ضربدر انتخاب ۱ از ۲ و ۱ از ۱ برای انتخاب راس متصل به راس چهارم از هر زیرگراف. جواب میشه ۶
راس چهارم از درجه ۳ باشه. باید ۳ عضو رو به ۳ مجموعه تقسیم کنیم. پس فقط یه حالت داریم. ضربدر جمله اول دنباله به توان ۳ و ضربدر انتخاب ۱ از ۱ به توان ۳ میکنیم. جواب میشه ۱
پس حاصل کل ۱۶ میشه.
یه نمونه از محاسبه بازگشتی این بود. ولی محاسبه حالت کلی به این روش به تنهایی خیلی سخته. بهتره از استقرا استفاده بشه. میشه فرض کرد جمله n ام و رابطه مذکور درسته. بعد باید ثابت کرد رابطه برای جمله n+1 یه مضرب از جمله n ام میشه که با رابطه اصلی میرسه.
راهی ساده تر به ذهنم نرسید.
خیلی ممنون
