سلام...
توی اصل شمول و عدم شمول باید تعداد کل حالات را از حالات تکی کم کنیم، با حالات دوتایی جمع کنیم، از حالات ۳ تایی کم کنیم و ... (زوج ها مثبت و فردها منفی اند) ... خوب حالا تعداد کل حالات که ۲ به توان ۱۰ هست چجوری بدست امده؟ طبق نکته زیر:
تعداد کل گراف های ساده با n راس برابر:

[align=center][tex]2^{\binom{n}{2}}[/tex]


اثبات فرمول بالا: اون انتخاب ۲ از n که توی توان هست از اینجا امده: فرض کنیم گراف کامل باشه، پس تعداد یال ها میشه: انتخاب ۲ از n.... حاا این یال ها میتونن توی گراف باشن یا نباشن! یعنی کلا انتخاب ۲ از n تا یال داریم حالا این یال ها یا هستن توی گراف یا نیستن! چجوری میشه اینا گفت: ۲ به توان اون تعداد یال ها! (دو حالت: بودن یا نبودن! )
پس تعداد حالات کل شد: ۲ به توان انتخاب ۲ از ۵ که میشه همون ۲ به توان ۱۰///
انتخاب ۱ از ۵ یعنی میایم ۱ راس از بین ۵ تا انتخاب میکنیم و اونا کنار میزاریم! و از ۴ تا راس باقیمانده تعداد گراف هایی که میتونیم بسازیم را با فرمول بالا حساب میکنیم.
انتخاب ۲ از ۵ یعنی میایم ۲ راس از بین ۵ تا انتخاب میکنیم و اونا را کنار میزاریم! و از ۳ تای باقیمانده تعداد گراف هایی که میتونیم بسازیم را با فرمول بالا حساب میکنیم.
انتخاب ۳ از ۵ هم همینطور...
انتخاب ۴ از ۵، چون فقط ۱ راس میمونه و ۱ حالت داره (یعنی با ۱ راس دیگه نمیتونیم بگیم یال داریم یا نداریم! یک حالته! یال نداریم! )
انتخاب ۵ از ۵ هم چون همه انتخاب شدن یه حالته
حالا با استفاده از اصل شمول یک در میان اینا را مثبت منفی میزاریم! و از تعداد کل کم میکنیم... ( که در واقع میشه همون قاعده که فرد عضوی ها علامت منفی میخورن و زوج عضوی ها علامت مثبت! )
--------
این استدلال خودم کردم! فکر کنم درست باشه

(۱۳ بهمن ۱۳۹۳ ۰۲:۲۴ ق.ظ)s0r0ush666 نوشته شده توسط:  سلام...
توی اصل شمول و عدم شمول باید تعداد کل حالات را از حالات تکی کم کنیم، با حالات دوتایی جمع کنیم، از حالات ۳ تایی کم کنیم و ... (زوج ها مثبت و فردها منفی اند) ... خوب حالا تعداد کل حالات که ۲ به توان ۱۰ هست چجوری بدست امده؟ طبق نکته زیر:
تعداد کل گراف های ساده با n راس برابر:

[align=center][tex]2^{\binom{n}{2}}[/tex]


اثبات فرمول بالا: اون انتخاب ۲ از n که توی توان هست از اینجا امده: فرض کنیم گراف کامل باشه، پس تعداد یال ها میشه: انتخاب ۲ از n.... حاا این یال ها میتونن توی گراف باشن یا نباشن! یعنی کلا انتخاب ۲ از n تا یال داریم حالا این یال ها یا هستن توی گراف یا نیستن! چجوری میشه اینا گفت: ۲ به توان اون تعداد یال ها! (دو حالت: بودن یا نبودن! )
پس تعداد حالات کل شد: ۲ به توان انتخاب ۲ از ۵ که میشه همون ۲ به توان ۱۰///
انتخاب ۱ از ۵ یعنی میایم ۱ راس از بین ۵ تا انتخاب میکنیم و اونا کنار میزاریم! و از ۴ تا راس باقیمانده تعداد گراف هایی که میتونیم بسازیم را با فرمول بالا حساب میکنیم.
انتخاب ۲ از ۵ یعنی میایم ۲ راس از بین ۵ تا انتخاب میکنیم و اونا را کنار میزاریم! و از ۳ تای باقیمانده تعداد گراف هایی که میتونیم بسازیم را با فرمول بالا حساب میکنیم.
انتخاب ۳ از ۵ هم همینطور...
انتخاب ۴ از ۵، چون فقط ۱ راس میمونه و ۱ حالت داره (یعنی با ۱ راس دیگه نمیتونیم بگیم یال داریم یا نداریم! یک حالته! یال نداریم! )
انتخاب ۵ از ۵ هم چون همه انتخاب شدن یه حالته
حالا با استفاده از اصل شمول یک در میان اینا را مثبت منفی میزاریم! و از تعداد کل کم میکنیم... ( که در واقع میشه همون قاعده که فرد عضوی ها علامت منفی میخورن و زوج عضوی ها علامت مثبت! )
--------
این استدلال خودم کردم! فکر کنم درست باشه

ممنونم
دقیقا به فرمولی یادم نبود اشاره کردین
بیشتر سوال من رو شرطی بود که تو پاسخ نامه هم بیانش کرده که یک شهر نمیتونه تک باشه ولی ۲ شهر میتونن تک باشن،
تو پاسخ نامه گفته که اگه یک عضو رو بذاریم کنار مجاز نیست پس یک عضو رو بذاریم کنار و ۴ عضو رو بذاریم کنار و ۵ عضو رو بذاریم کنار رو از حالت کلی کم کرده
حالا ۲ عضو رو بذاریم کنار و ۳ عضو رو بذاریم کنار مجاز باید جمع بشن ولی یکیشو جمع کرده یکیشو منها !! چرا؟!
فک نمیکنم مربوط به اون مطلب باشه که فرد عضوی ها منفی و زوج عضوی ها مثبت باشن چون اینجا همه منفی هستن به جز یکی

---

(۱۳ بهمن ۱۳۹۳ ۰۲:۱۵ ق.ظ)Jooybari نوشته شده توسط:  سلام. لطفاً تو عنوان سوال سال کنکور رو هم ذکر کنید.

سوال سختی نیست. فقط توضیحاتش یه مقدار پیش زمینه میخاد. ارتباط بین این ۵ شهر رو میشه با یه ماتریس دودویی متقارن که درایه های قطر اصلیش صفر هستن نمایش داد. اگه مقدار یه درایه ۱ بود یعنی بین اون دو شهر راه داریم. تعداد حالاتی که هیچ شهری تکی (بدون مسیر) نباشه میشه کل حالات منهای تعداد حالاتی که حداقل یک شهر تکی باشه بعلاوه تعداد حالاتی که حداقل ۲ تا شهر تکی باشن و الی آخر (طبق اصل شمول و طرد). حالا تعداد هر کدوم از حالت ها رو با توجه به ماتریسش باید حساب کرد. توی حالتی که قراره یک هر تکی باشه یه انتخاب ۱ از ۵ برای تشخیص شهر تکی داریم. از مجموع ۱۰ بیتی که توی ماتریس تعیین کننده مسیرها هستن چهارتا باید صفر باشن که اون شهر تکی باشه.

ممنون میدونم سوال سختی نیست ولی یه فرمول شو فراموش کرده بودم و دلیل اصلی سوالم شرطیه که تو پاسخ نامه ذکر کرده
سوال کنکور نبود وگرنه مثل سوالای قبلی که پرسیدم اطلاعات کاملشو میذاشتم

سلام. لطفاً تو عنوان سوال سال کنکور رو هم ذکر کنید.

سوال سختی نیست. فقط توضیحاتش یه مقدار پیش زمینه میخاد. ارتباط بین این ۵ شهر رو میشه با یه ماتریس دودویی متقارن که درایه های قطر اصلیش صفر هستن نمایش داد. اگه مقدار یه درایه ۱ بود یعنی بین اون دو شهر راه داریم. تعداد حالاتی که هیچ شهری تکی (بدون مسیر) نباشه میشه کل حالات منهای تعداد حالاتی که حداقل یک شهر تکی باشه بعلاوه تعداد حالاتی که حداقل ۲ تا شهر تکی باشن و الی آخر (طبق اصل شمول و طرد). حالا تعداد هر کدوم از حالت ها رو با توجه به ماتریسش باید حساب کرد. توی حالتی که قراره یک هر تکی باشه یه انتخاب ۱ از ۵ برای تشخیص شهر تکی داریم. از مجموع ۱۰ بیتی که توی ماتریس تعیین کننده مسیرها هستن چهارتا باید صفر باشن که اون شهر تکی باشه.