[attachment=22366]
جواب:گزینه ۴
سلام
اینچنین سوالاتو میتوان با مقدار دادن به n حل کرد.مثلا برای n=2 که [tex]k_2[/tex] می شود خودش درخت پوشا است یعنی یک درخت پوشا داریم پس رد گزینه ی ۱.برای n=4 که [tex]k_4[/tex] می شود که دارای ۶ یال است.باید توجه کنیم چون صحبت از افراز شده پس یال ها رو باید متمایز بگیرم تا بتوانیم در زیرمجوعه های افراز قرار دهیم از طرفی میدانیم که در هر افراز هیچ دو زیر مجموعه ای نباید با هم اشتراک داشته باشند.از طرفی برای اینکه درخت پوشا برای ۴ راس داشته باشیم نیاز به ۳ یال از ۶ یال داریم .۳ یال باقی مانده هم درخت پوشای دیگری را تولید می کند .گفتیم که زیر مجموعه های افراز نباید اشتراک داشته باشند.پس برای n=4 یال های [tex]k_4[/tex] به دو درخت پوشا افراز شد یعنی رد گرینه های ۲ و ۳
(۲۵ بهمن ۱۳۹۶ ۰۳:۰۴ ب.ظ)ss311 نوشته شده توسط: جواب:گزینه ۴
گراف کامل Kn دارای [tex]\frac{n(n-1)}{2}[/tex] یال است. برای برای هر درخت پوشا به n-1 یال نیاز داریم.
چون افرازها با هم اشتراک ندارند حداکثر تعداد افرازها برابر است با : [tex]\frac{\frac{n(n-1)}{2}}{n-1}=\frac{n}{2}[/tex]