سلام این سوال از آزمون مدرسان هست که من متوجه جوابش نمیشم ممنون اگه توضیح بدید:
سیستمی که ۵ شهر را با جاده های دو طرفه به هم وصل میکند تعداد سیستمهایی از جاده های ۲ طرفه که دقیقا ۲ شهر را تنها بگذارد؟
گزینه ها: ۵۱ ۴۰ ۲۰ ۱۱۰
جوابشو ۴۰ درآورده با یه فرمول عجیب غریب.
سلام. درست نمیفهمم سوالش چی میگه. اگه منظورش این باشه که تمام جاده ها دوطرفه هستن و تعداد راه هایی که دقیقاً دو تا شهر، جاده نداشته باشن رو بخاد میشه انتخاب ۲ از ۵ برای شهرهای بدون جاده و ۴ حالت برای وجود حداقل ۲ جاده از ۳ جاده بین ۳ شهر که میشه ۴ حالت.
این مسئله مربوط به تعمیم اصل شمول و طرد میباشد و عین مثال صفحه ۵۳۳ کتاب گریمالدی است و منظور از جاده دوطرفه، در نظرگرفتن یک یال ساده مابین رئوس (روستاها) در صورت وجود مسیر بین آنهاست.
در اینجا میخواهیم
و حال برای این مسئله با توجه به معادله بالا داریم:
اگر فرمول را محاسبه کنیم به جواب ۴۰ خواهیم رسید.
جزئیات:
یعنی دو روستا از ۵ روستا تنها باشد و بقیه ۳ روستا نیز به ۳^۲ طریق وصل میگردند(یعنی تعداد یالهای گراف کاملی که توسط این رئوس ایجاد میشوند و هریک از این یالها میتوانند انتخاب شوند یا خیر).
(۱۲ دى ۱۳۹۲ ۰۱:۴۲ ق.ظ)wokesh نوشته شده توسط: این مسئله مربوط به تعمیم اصل شمول و طرد میباشد و عین مثال صفحه ۵۳۳ کتاب گریمالدی است و منظور از جاده دوطرفه، در نظرگرفتن یک یال ساده مابین رئوس (روستاها) در صورت وجود مسیر بین آنهاست.
در اینجا میخواهیمیعنی تعداد عنصرهایی را که دقیقا در m شرط صدق میکنند بیابیم. که فرمول ان بصورت زیر است:
و حال برای این مسئله با توجه به معادله بالا داریم:
اگر فرمول را محاسبه کنیم به جواب ۴۰ خواهیم رسید.
جزئیات:
یعنی دو روستا از ۵ روستا تنها باشد و بقیه ۳ روستا نیز به ۳^۲ طریق وصل میگردند(یعنی تعداد یالهای گراف کاملی که توسط این رئوس ایجاد میشوند و هریک از این یالها میتوانند انتخاب شوند یا خیر).
ممنون.