۰
subtitle
ارسال: #۱
مثالی از فصل شمول و طرد (راهها و شهرها)
با سلام
دوستان درباره فصل شمول و طرد یک سوالی داشتم. ممنون میشم راهنمایی کنید.
توی کتاب گریمالدی٬ در این فصل٬ یک مثالی هست که میگه میخواهیم بین ۵ روستا٬ جادههای دوطرفه بکشیم. یک شرکت به چند طریق میتونه این کار رو انجام بده به شرطی که هیچکدام از روستاها بدون جاده نمانند.
جواب این مثال هم توی کتاب گریمالدی اومده.
حالا خواستم سؤال رو به این طریق در واقع تغییر بدیم. فرض کنید که نخواهیم جادههای دوطرفه داشته باشیم. فرض کنید راههای ما ۳ بانده بشه (فرض). بنابراین گراف ما در اینجا میتونه به گراف جهتدار تغییر کنه. و برای مثال از شهر الف تا شهر ب٬ میتونیم راههای مختلفی بکشیم.
حالا به نظر شما شرایط مسئله تغییر میکنه؟ اساساً در کل مراحل٬ به نظر شما چند مسیر میشه (بدون تکرار) کشید؟
دوستان درباره فصل شمول و طرد یک سوالی داشتم. ممنون میشم راهنمایی کنید.
توی کتاب گریمالدی٬ در این فصل٬ یک مثالی هست که میگه میخواهیم بین ۵ روستا٬ جادههای دوطرفه بکشیم. یک شرکت به چند طریق میتونه این کار رو انجام بده به شرطی که هیچکدام از روستاها بدون جاده نمانند.
جواب این مثال هم توی کتاب گریمالدی اومده.
حالا خواستم سؤال رو به این طریق در واقع تغییر بدیم. فرض کنید که نخواهیم جادههای دوطرفه داشته باشیم. فرض کنید راههای ما ۳ بانده بشه (فرض). بنابراین گراف ما در اینجا میتونه به گراف جهتدار تغییر کنه. و برای مثال از شهر الف تا شهر ب٬ میتونیم راههای مختلفی بکشیم.
حالا به نظر شما شرایط مسئله تغییر میکنه؟ اساساً در کل مراحل٬ به نظر شما چند مسیر میشه (بدون تکرار) کشید؟