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

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

ارسال:
  

Mohammad-A پرسیده:

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

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

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

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

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

۰
ارسال:
  

Jooybari پاسخ داده:

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مشکل در حل تست ۲۲ فصل اول کتاب گسسته یوسفی pure.yaser ۷ ۲,۴۳۹ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۵۴ ب.ظ
آخرین ارسال: mohsentafresh
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۱۷,۵۵۲ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  مهمترین فصل های ذخیره و بازیابی مقسمی enofcom ۱۰ ۱,۲۶۴ ۲۵ آبان ۱۳۹۸ ۰۵:۲۳ ب.ظ
آخرین ارسال: alma1988
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۸۴۴ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
  فصل Np , Np hard nazanin2020 ۰ ۴۰۵ ۰۱ اسفند ۱۳۹۷ ۰۳:۲۱ ب.ظ
آخرین ارسال: nazanin2020
  چند راه برای این که پرواز طولانی راحت تری را تجربه کنید - خبرگزاری فارس abolfazlda ۰ ۸ ۲۴ بهمن ۱۳۹۷ ۱۱:۰۵ ق.ظ
آخرین ارسال: abolfazlda
Rainbow رنگین‌ترین شهرها در سرتاسر دنیا αɾια ۱۰ ۱,۵۹۳ ۰۲ تیر ۱۳۹۷ ۱۰:۰۱ ق.ظ
آخرین ارسال: hivakish
  فصل " حل معادله دیفرانسیل با کمک سری ها" در معادلات دیفرانسیل را نمی فهمم!! saeid4x ۳ ۱,۴۳۳ ۲۷ اردیبهشت ۱۳۹۷ ۱۰:۵۳ ق.ظ
آخرین ارسال: CSX
Information فصل یک تا پنج پایان نامه αɾια ۳ ۱,۲۴۴ ۲۷ اسفند ۱۳۹۶ ۱۱:۴۲ ق.ظ
آخرین ارسال: αɾια
  راه حلی برای یافتن تداخل در روشهای تقدم Sepideh96 ۱ ۶۸۲ ۰۷ بهمن ۱۳۹۶ ۱۱:۵۹ ب.ظ
آخرین ارسال: alilash

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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