این سوال چه جوری حل میشه؟؟
اگر گرافی ۱۳۸۷ راسی و فقد دور باشد و دقیقا ۴۲۱ مولفه همبند داشته باشد در این صورت تعداد یال های آن برابر است با؟؟
۱۳۸۶
۱۰۰۰
۹۶۶
۲۰۰۹
ببخشید من سوالام زیاده
لطفا کمکم کنید
فرض کنید P10 مسیر ۱۰ راسی باشد به چند طریق میتوان ۴ یال از P10 انتخاب کرد به طوری که هیچ یک از ۴ یال راس مشترک نداشته باشند؟
[tex]\binom{9}{4}[/tex]
[tex]\binom{7}{4}[/tex]
[tex]\binom{6}{4}[/tex]
[tex]\binom{10}{4}[/tex]
چون گفته بدون دور پس درخت است.در یک درخت با n راس و k تا مولفه همبندی و e تا یال داریم:
n=k+e
e=966
این سوال گزینه را اشتباه زده و کلیدشم تصحیح نشد یکی از سوالای سالهای پیش تو داده هم هست
سوال دوم:
مسیر ۱۰ راسی ۹ یال دارد
شما باید ۴ یال رو انتخاب کنید یعنی ۵ یال رو انتخاب نمیکنید چون ۴ یال نباید اشتراک داشته باشند یعنی پشت سر هم نباشند چون اینجوری اشتراک پیدا میکنن یعنی این ۴ یال باید در فضای بین این ۵ یالی که انتخاب نمیشوند قرار بگیرند یعنی ۶ فضا داریم که ۴ تا از آنها انتخاب میشود.
اگر یالهایی که نباید انتخاب شود را با حرف a نشان دهیم -a-a-a-a-a-
باید ۴ تا از - را انتخاب کنیم.
این مسئله شبیه مسئله تعداد حالت های کنار هم گذاشتن ۴ مهره قرمز و ۵ مهره سبز به صورتی که مهره های قرمز کنار هم قرار نگیرند می باشد .
البته مسئله سختیه توی کتاب هم خوب توضیح نداده بود!