با سلام
دوستان درباره فصل شمول و طرد یک سوالی داشتم. ممنون میشم راهنمایی کنید.
توی کتاب گریمالدی٬ در این فصل٬ یک مثالی هست که میگه می‌خواهیم بین ۵ روستا٬ جاده‌های دوطرفه بکشیم. یک شرکت به چند طریق میتونه این کار رو انجام بده به شرطی که هیچکدام از روستاها بدون جاده نمانند.
جواب این مثال هم توی کتاب گریمالدی اومده.
حالا خواستم سؤال رو به این طریق در واقع تغییر بدیم. فرض کنید که نخواهیم جاده‌های دوطرفه داشته باشیم. فرض کنید راه‌های ما ۳ بانده بشه (فرض). بنابراین گراف ما در اینجا میتونه به گراف جهت‌دار تغییر کنه. و برای مثال از شهر الف تا شهر ب٬ می‌تونیم راه‌های مختلفی بکشیم.
حالا به نظر شما شرایط مسئله تغییر می‌کنه؟ اساساً در کل مراحل٬ به نظر شما چند مسیر میشه (بدون تکرار) کشید؟
ببخشید من سوالتونو خوب متوجه نشدم. اگه منظورتون از وجود راه حداقل یکی از راه های ورودی یا خروجی باشه و راه دوطرفه هم ممکن باشه(هم بشه از شهر اول به دوم و هم از شهر دوم به اول بطور مستقیم و بدون واسطه رفت) جواب مسئله تقریبا همون جواب مسئله قبل میشه با این تفاوت که توان عدد ۲ توی همه‌ی جمله‌ها ۲ برابر میشه. (اولین جملمون ۲ به توان ۲۰ میشه.) با این فرض شکل ب کتاب ۳ به توان ۴ یا همون ۸۱ حالت داره.
حالت دیگ مسئله عدم وجود راه دوطرفست. جواب این مسئله هم مشابه جواب کتابه فقط باید بجای ۲ به توان هر عدد، ۳ به توان همون عدد رو جایگزین کنمی. یعنی جمله اولمون ۳ به توان ۱۰ میشه.
یه حالت اینه که از هر روستا حتماً راه خروجی داشته باشیم. که جواب این مسئله با شرط وجود راه دوطرفه میشه: [tex](2^{4}-1)^{5}[/tex]
یعنی از هر شهر حداقل ۱ خروجی داشته باشیم. (با توجه به ماتریس مجاورت ۲ به توان ۴ منهای یک یا همون ۱۵ حالت برای هر راس داریم.)
اگه برای این حالت راه دوطرفه تعریف نشه شکل ب کتاب به هیچ وجه نمیتونه جواب مسئلمون باشه. چون یکی از رئوس a یا b یال خروجی ندارن.