زمان کنونی: ۲۷ مهر ۱۳۹۷, ۰۳:۲۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مثالی از فصل شمول و طرد (راه‌ها و شهرها)

ارسال:
  

Mohammad-A پرسیده:

مثالی از فصل شمول و طرد (راه‌ها و شهرها)

با سلام
دوستان درباره فصل شمول و طرد یک سوالی داشتم. ممنون میشم راهنمایی کنید.
توی کتاب گریمالدی٬ در این فصل٬ یک مثالی هست که میگه می‌خواهیم بین ۵ روستا٬ جاده‌های دوطرفه بکشیم. یک شرکت به چند طریق می‌تونه این کار رو انجام بده به شرطی که هیچکدام از روستاها بدون جاده نمانند.

جواب این مثال هم توی کتاب گریمالدی اومده.

حالا خواستم سؤال رو به این طریق در واقع تغییر بدیم. فرض کنید که نخواهیم جاده‌های دوطرفه داشته باشیم. فرض کنید راه‌های ما ۳ بانده بشه (فرض). بنابراین گراف ما در اینجا میتونه به گراف جهت‌دار تغییر کنه. و برای مثال از شهر الف تا شهر ب٬ می‌تونیم راه‌های مختلفی بکشیم.

حالا به نظر شما شرایط مسئله تغییر می‌کنه؟ اساساً در کل مراحل٬ به نظر شما چند مسیر میشه (بدون تکرار) کشید؟

۰
ارسال:
  

Jooybari پاسخ داده:

مثالی از فصل شمول و طرد (راه‌ها و شهرها)

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تست علوم کامپیوتر سال ۸۶ تعداد روابط هم ارزی (سوال ۲۳ فصل مجموعه پوران) so@ ۲ ۱,۴۴۳ ۲۶ آبان ۱۳۹۳ ۰۵:۱۰ ب.ظ
آخرین ارسال: so@
  تست علوم کامپیوتر سال ۸۴ فصل مجموعه و روابط (سوال۴ کتاب پوران ص ۱۴۹) so@ ۲ ۱,۱۳۲ ۲۵ آبان ۱۳۹۳ ۰۸:۴۰ ب.ظ
آخرین ارسال: so@
Question سوال ۱۴ فصل ۲ ساختمانهای گسسته قلی زاده nrique ۷ ۱,۹۸۸ ۱۹ مهر ۱۳۹۳ ۰۷:۲۴ ب.ظ
آخرین ارسال: nrique
  مثالهای ۲۹و۳۱ فصل شمارش کتاب پارسه pooyaa ۱ ۸۳۲ ۲۰ مرداد ۱۳۹۳ ۱۱:۵۸ ب.ظ
آخرین ارسال: Jooybari
  ترکیبهای با تکرار - تعداد راه های سفارش ساندویچ Doctorwho ۳ ۸۳۲ ۰۲ تیر ۱۳۹۳ ۱۰:۴۵ ب.ظ
آخرین ارسال: Morris
  سوال۴۱ سنجش جامع ۳ - تعداد راه های چیدن اعداد در دو ردیف بصورت سعودی. hosein_khoshdel ۱ ۷۶۷ ۱۳ بهمن ۱۳۹۲ ۰۵:۴۴ ب.ظ
آخرین ارسال: Jooybari
  فصل لاتیس گسسته رو باید خوند ؟ ezra ۱ ۸۴۷ ۲۱ آذر ۱۳۹۲ ۰۹:۴۵ ق.ظ
آخرین ارسال: izadan11
  اصل شمول وطرد (مسئله ی تولد مادربزرگ) ghasem.n ۴ ۱,۲۵۶ ۲۸ آبان ۱۳۹۲ ۰۷:۵۱ ق.ظ
آخرین ارسال: Jooybari
  سوال ۵ تمرینات تکمیلی فصل اول گسسته گریمالدی fa_karoon ۱ ۱,۰۰۴ ۱۳ مهر ۱۳۹۲ ۰۶:۰۷ ب.ظ
آخرین ارسال: Jooybari
  عملگر های کامل در گسسته فصل اول منطق Doctorwho ۳ ۱,۹۱۱ ۰۹ مهر ۱۳۹۲ ۱۰:۰۰ ب.ظ
آخرین ارسال: black_knight

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close