علوم کامپیوتر۸۶
تعداد زیر درخت فراگیر شکل زیر کدام است؟
جواب :۲۱
چه جوری میشه ۲۱؟
روش اول: فایل پیوست
---------------------------------
روش دوم:
۵ رأس داریم... باید ۴ یال انتخاب کنیم...
حالات مختلف زیردرخت فراگیر رو بر اساس یال های منتهی به رأس بالایی گراف دسته بندی می کنیم:
۱- هر ۴ یال منتهی به رأس بالایی در زیردرخت قرار دارند ---> 1 حالت
۲- ۳ یال از ۴ یال منتهی به رأس بالایی در زیردرخت قرار دارند ---> 2 + 2 + 1 + 1 = 6 حالت
۳- ۲ یال از ۴ یال منتهی به رأس بالایی در زیردرخت قرار دارند ---> 3 + 2 + 2 + 1 + 1 + 1 = 10 حالت
۴- ۱ یال از ۴ یال منتهی به رأس بالایی در زیردرخت قرار دارند ---> 4 حالت
۱ + ۶ + ۱۰ + ۴ = ۲۱ حالت
تو هر دسته بندی میایم باتوجه به یال های انتخاب شده، حالت های ممکن بقیه ی یال ها رو به گونه ای که دور ایجاد نشه، در نظر می گیریم...