تالار گفتمان مانشت

سلام
دوتا سوال ساده ازآزمونهای پارسه قسمت طراحی الگوریتم دارم
که متوجه روش حل نمیشم
یعنی نمیدونم طبق چه قانون ومنطقی حلش میکنه اگر لطف کنن دوستان توضیح بدن ممنون میشم
[attachment=15337]
[attachment=15338]

سوال 97 فقط از C به D نمی تونه یال وجود داشته باشه چون اون موقع جستجوی عمقیش فرق می کنه بجای این که برگرده به گره B و از اونجا بره D مستقیم می ره D بقیه اگر هم موجود باشن فرقی تو جستجوی عمقی پیش نمی یاد
پس جواب می شه گزینه 2

---

سوال 112 گزینه 1 می شه
اگه بر حسب ملاقات گره ها درختش رو رسم کنی متوجه می شی که اگه از E به F یال موجود باشه شکل درخت فرق می کنه و زمان اول ملاقات گره F می شد 5

(21 بهمن 1392 01:38 ب.ظ)mehdi.m2 نوشته شده توسط: [ -> ]سوال ۹۷ فقط از C به D نمی تونه یال وجود داشته باشه چون اون موقع جستجوی عمقیش فرق می کنه بجای این که برگرده به گره B و از اونجا بره D مستقیم می ره D بقیه اگر هم موجود باشن فرقی تو جستجوی عمقی پیش نمی یاد
پس جواب می شه گزینه ۲

---

سوال ۱۱۲ گزینه ۱ می شه
اگه بر حسب ملاقات گره ها درختش رو رسم کنی متوجه می شی که اگه از E به F یال موجود باشه شکل درخت فرق می کنه و زمان اول ملاقات گره F می شد ۵

سلام
سوال 112 آره گزینه 1 میشه
ولی سوال قبلیش گفته میتونه وجود داشته باشه احتمالا سوالش غلطه ولی اگه سوالش همون که شما میگی بوده باشه حرفتون درسته

(21 بهمن 1392 01:58 ب.ظ)hosshah نوشته شده توسط: [ -> ]

(21 بهمن 1392 01:38 ب.ظ)mehdi.m2 نوشته شده توسط: [ -> ]سوال ۹۷ فقط از C به D نمی تونه یال وجود داشته باشه چون اون موقع جستجوی عمقیش فرق می کنه بجای این که برگرده به گره B و از اونجا بره D مستقیم می ره D بقیه اگر هم موجود باشن فرقی تو جستجوی عمقی پیش نمی یاد
پس جواب می شه گزینه ۲

---

سوال ۱۱۲ گزینه ۱ می شه
اگه بر حسب ملاقات گره ها درختش رو رسم کنی متوجه می شی که اگه از E به F یال موجود باشه شکل درخت فرق می کنه و زمان اول ملاقات گره F می شد ۵

سلام
سوال ۱۱۲ آره گزینه ۱ میشه
ولی سوال قبلیش گفته میتونه وجود داشته باشه احتمالا سوالش غلطه ولی اگه سوالش همون که شما میگی بوده باشه حرفتون درسته

دوستان سطح گیرایی من و باخودتون یکی نکنین
توروخدا واضح بگین من متوجه نمیشم

سوال 97: اول اینکه توجه داشته باشید که گراف جهت داره و یالهایی توی گزینه ها رو به ترتیب توی درخت پوشا میزاریم. اگر با در نظر گرفتن اون یال توی درخت ترتیب درخت پوشا به هم نریزه پس یعنی اون یال میتونه توی گراف اصلی باشه
یال DC: این یال اگه توی گراف اصلی وجود داشته باشه باز هم این درخت پوشا میتونه به وجود بیاد چون اول گره C دیده شده و هنگامیکه گره D دیده میشه این یال تاثیری نداره
یال CD: این یال نمیتونه تو گراف موجود باشه. چون اگر این یال تو گراف بود گره ای که بعد از C ملاقات میشد توی پیمایش DFS گره D بود در حالی که توی این درخت پوشا اینطوری نیست
یال FA: به همون دلیلی که یال DC میتونست باشه این یال هم میتونه
یال AF: این یال هم میتونه تو گراف باشه چون منافاتی با درخت پوشای به دست اومده نداره و وقتی برمیگردیم به گره A و یال AF رو میبینیم چون گره F قبلا ملاقات شده دیگه سراغش نمیریم

سوال دوم: برای این سوال هم بهتره بر اساس ترتیب ملاقات گره ها که اعدادش داده شده شکل بکشید (شکل زیر) و همون کارهایی که برای سوال قبل انجام دادیم این جا هم انجام بدیم



یال ef: اگر این یال وجود داشت ما میتونستیم بعد از گره e گره f رو ملاقات کنیم ولی میبینید که نشده پس این یال توی گراف وجود نداره
یال ce: چون یال e قبلا ملاقات شده پس این یال تاثیری در ترتیب ملاقات نداره و میتونه تو گراف اصلی باشه
یال ea: مانند بالا چون گره a قبل از e ملاقات شده وجود این یال در گراف تاثیری روی درخت پوشا نداره پس میتونه تو گراف باشه
یال ag: از اونجایی که ما ابتدا از یال ab شروع به پیمایش کردیم پس وقتی دوباره به گره a برگردیم و یال ag رو مشاهده کنیم چون گره g قبلا ملاقات شده این یال تاثیری نداره پس میتونه تو گراف باشه


اووووووووف

سوال 97:
یال DC : این یال میتونه وجود داشته باشه. فرض کن این یال در گراف اصلی وجود داشت. ما از گره B که میرفتیم پایین C رو ملاقات میکردیم و کارمون تموم میشد . حالا میرفتیم سرغ گره بعدی . از D که بریم پایین ، با یال DC بر میخوریم که چون C قبلا ملاقات شده ، ازش رد میشیم. بنابراین این بال در DFS نهایی نمیاد. پس کلا وجود این یال تو گراف اصلی مشکلی نداره.

یال FA : گره A اولین گره ای که ما داریم ملاقات میکنیم . بنابراین اگر یالی از F به A وجود داشته باشه. وقتی داریم گره F رو بررسی میکنیم چون A قبلا ملاقات شده دیگه این بال در DFS نهایی نمیاد. پس کلا وجود این یال تو گراف اصلی مشکلی نداره.

یال CD : اگر از C به D یالی وجود میداشت ، وقتی داشتیم گره C رو بررسی میکردیم باید بعد از C گره D رو هم ملاقات می کردیم و این یعنی بال CD باید تو گراف DFS نهایی میومد. که نیومده . پس این یال نمیتونسته در گراف اصلی وجود داشته باشه.

یال AF : اولین گره ای که بعد از A بررسی میکنیم B هست. این گره رو تا انتها که بریم F ملاقات میشه و وقتی بر میگردیم بالا که بریم فرزند بعدی A رو بررسی کنیم ، در صورت وجود این یال ، این فرزند میشه همون F که قبلا ملاقات شده ، پس این بال در DFS نهایی نمیاد. پس کلا وجود این یال تو گراف اصلی مشکلی نداره.

مرسی از همه دوستان لطف کردین