(۲۰ آبان ۱۳۹۵ ۰۲:۲۹ ب.ظ)*ahoo نوشته شده توسط:  سلام
من نمیفهمم این سوالو
میشه کمک کنید


سیستمی که ۵ شهر را به وسیله جاده های دوطرفه به هم وصل میکند را در نظر بگیرید، تعداد سیستمهایی از جاده های دوطرفه که دقیقاً
دو شهرستان را تنها بگذارند، کدام است؟
۱۱۰ (۴ ۲۰ (۳ ۴۰ (۲ ۵۱ (۱

فکر کنم منظورش این هست که ۵ تا رأس داریم و تعداد گراف‌هایی که دو گره ایزوله بمونند رو خواسته.
در اون دو گره‌ای که تنها می‌مونند اگه منظورش از تنها موندن این هست که حتی به هم دیگه هم وصل نشن، جواب میشه انتخاب ۲ شهرستانی که تنها میمونند (از ۵ شهرستان)، ضربدر تعداد حالاتی که اون ۳ شهرستان (که تنها نموندند) میتونند به هم وصل بشن.
اون ۳ شهرستان هم یه میتونند به صورت درخت به هم وصل بشن (یعنی ۱ به ۲ وصل بشه، ۲ هم به ۳)، یا اینکه دور هم داشته باشند (یعنی ۱ به ۳ هم وصل بشه، به صورت مثلث مثلاً). پس دو حالت خواهد داشت. در نتیجه:
[tex]\binom{5}{2}\times2=20[/tex]

(۲۰ آبان ۱۳۹۵ ۰۳:۲۹ ب.ظ)Behnam‌ نوشته شده توسط:  فکر کنم منظورش این هست که ۵ تا رأس داریم و تعداد گراف‌هایی که دو گره ایزوله بمونند رو خواسته.
در اون دو گره‌ای که تنها می‌مونند اگه منظورش از تنها موندن این هست که حتی به هم دیگه هم وصل نشن، جواب میشه انتخاب ۲ شهرستانی که تنها میمونند (از ۵ شهرستان)، ضربدر تعداد حالاتی که اون ۳ شهرستان (که تنها نموندند) میتونند به هم وصل بشن.
اون ۳ شهرستان هم یه میتونند به صورت درخت به هم وصل بشن (یعنی ۱ به ۲ وصل بشه، ۲ هم به ۳)، یا اینکه دور هم داشته باشند (یعنی ۱ به ۳ هم وصل بشه، به صورت مثلث مثلاً). پس دو حالت خواهد داشت. در نتیجه:
[tex]\binom{5}{2}\times2=20[/tex]

جواب ۴۰ میشه ولی

---

پاسخنامش اینطوریه(پیوست)

(۲۰ آبان ۱۳۹۵ ۰۴:۰۶ ب.ظ)*ahoo نوشته شده توسط:  

(20 آبان ۱۳۹۵ ۰۳:۲۹ ب.ظ)Behnam‌ نوشته شده توسط:  فکر کنم منظورش این هست که ۵ تا رأس داریم و تعداد گراف‌هایی که دو گره ایزوله بمونند رو خواسته.
در اون دو گره‌ای که تنها می‌مونند اگه منظورش از تنها موندن این هست که حتی به هم دیگه هم وصل نشن، جواب میشه انتخاب ۲ شهرستانی که تنها میمونند (از ۵ شهرستان)، ضربدر تعداد حالاتی که اون ۳ شهرستان (که تنها نموندند) میتونند به هم وصل بشن.
اون ۳ شهرستان هم یه میتونند به صورت درخت به هم وصل بشن (یعنی ۱ به ۲ وصل بشه، ۲ هم به ۳)، یا اینکه دور هم داشته باشند (یعنی ۱ به ۳ هم وصل بشه، به صورت مثلث مثلاً). پس دو حالت خواهد داشت. در نتیجه:
[tex]\binom{5}{2}\times2=20[/tex]

جواب ۴۰ میشه ولی

---

پاسخنامش اینطوریه(پیوست)

بله ۴۰ میشه چون من تعداد حالات اون ۳ شهری که با هم هستند رو ۲ گرفتم، ولی در اصل ۴ هست. فرض کنید این ۳ شهر، a و b و c هستند. پس به این طریق میتونند به هم وصل بشن:
b_a_c
a_b_c
a_c_b
یعنی اینکه در هر حالت، یکی از شهرها در بین اون دو شهر دیگه هست. حالت چهارم هم این هست که دو شهر کناری هم به هم وصل بشند و مثلث مانند بشه. دقت کنید که ترتیب مهم نیست. در واقع مکان اون شهرها ثابت هست و شما فقط خطوط رو تغییر میدید که میشه ۴ حالت (۳ تا نقطه روی کاغذ بکشید و اسم‌گذاری کنید، میشه ۴ حالت اتصال).

اون فرمول رو هم حفظ نیستم ولی به نظر اشتباه هست. در جمله‌ی آخر عبارت داخل آخرین پرانتز [tex]t-1[/tex] هست و اندیس S هم [tex]t[/tex] هست یعنی یکی بیشتر، ولی در خط آخر، جفتشون ۶ هستند. S هم مشخص نیست چیه. در کل این فرمول‌ها به درد نمیخورن و باید مفهوم رو یاد بگیرید.
علاوه بر این، اینجا ما مجبور شدیم تعداد گراف‌های مختلفی که با ۳ رأس میشه ساخت (رأس‌ها از هم مجزا هستند) رو پیدا کنیم که شد ۴/ طبق این فرمول که ظاهراً از راه حل دیگه‌ای میره، میشه مهندسی معکوس کرد و فرمولی برای پیدا کردن تعداد گراف‌های همبند با n رأس پیدا کرد که گمونم مسأله‌ی باز هست و روشی براش پیدا نشده. در نتیجه به این فرمول مشکوک هستم مگه اینکه مسأله چیز دیگه‌ای باشه غیر از چیزی که من فکر میکنم ولی خب فعلاً که جوابی که رسیدیم درست هست.