در چند درخت فراگیر از [tex]K_5[/tex] با مجموعه رئوس {a,b,c,d,e}=V فاصله دو راس a و b برابر ۲ است؟
۱)۲۷
۲)۳۶
۳)۴۲
۴)۴۵
جواب :گزینه ۴
سلام. وقت بخیر.
باید حالت های مختلف این شکل رو رسم کنید و بعد برچسب بزنید. بین a و b باید یه گره مثل x باشه (x یکی از ۳ گره باقی موندست. پس ۳ حالت اینجا داریم.) حالتهای مختلف اتصال دو گره دیگه به این سه گره رو هم باید درنظر بگیریم. فرض کنید این دو گره، y و z باشن.
۱- اینکه هر دو گره y و z به یکی از ۳ گره a,b,x وصل بشن. یعنی ۳ حالت برای انتخاب محل اتصال این دو گره داریم. این خودش دو حالت داره:
۱-۱ گره y به z وصل باشه. یعنی حالت برای ترتیب این دو گره داریم.
۱-۲ گره های y و z به هم وصل نباشن. ترتیبی برای این دو گره قائل نیستیم.
۲- دو گره y و z به دو گره مختلف متصل شده باشن. برای یه گره ۳ انتخاب و برای گره دوم، ۲ انتخاب داریم. (چون قراره کنار هم نباشن.)
حالت ۱ در مجموع شد [tex]3\times(2+10)=9[/tex]
حالت ۲ هم در مجموع شد ۶ حالت.
مجموع دو مقدار فوق رو باید در ۳ ضرب کنیم که جواب میشه ۴۵