سلام
جواب گزینه ۱ هست.
من اینجا نمیتونم یال هایی رو که خواسته بدست بیارم چون اگر یال هارو میدادو میشد شکل درختو کشید بعد با پیمایش به این رسید بعدش یالهایی رو که خواسته بدست اورد ولی الان که گراف اصلی رو ندارم چطوری بدست بیارم ممنون میشم کسی میتونه کمک کنه؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام توی شکل که پیوست شده همه ی یال های ۴ تا گزینه رو رسم کردم منظور از a:1-4 یعنی یالی از گره ۱ به گره ۴/و به همین ترتیب برای بقیه موارد ذکر شده.فک کنم الان بتونید جواب رو پیدا کنید.
توی اینجور سوالا هر گزینه رو جدا جدا یال هاشو رسم کن و هرکدوم جواب بود انتخاب کن ،یال a:3-4 و a:9-10 یک یال forward نیست پس میتونی به راحتی گزینه ی ۲ و ۴ رو توی نگاه اول حذف کنی و به همین ترتیب...
ممنون از جوابتون ولی باز نمیفهمم .میشه بیشتر توضیح بدید؟؟
سلام. قبل از همه چیز اینو بدونید که یالی که پیشرو باشه، همیشه از گره قبلی به پایینیه. پس اونایی که از بزرگ اومده به کوچیک حذف میشه. مثل ۶,۱ .
حالا باید بر اساس درخت گزینه ها رو چک کنیم. در ضمن اول یال پیشرو رو چک میکنیم چون آسون تره. گزینه ۲ گفته ۳,۴/ خوب اگه یالی از ۳ به ۴ بود، حتما توی پیمایش آورده میشد. ولی اینجا میبینیم که گره ۴ وصله به ۲! پس این هم رد میشه.
گزینه ۴ هم به همین استدلال حذف میشه.
گزینه ۱ درسته. چون ممکنه یالی از ۱ به ۴ باشه. ولی چون گره ۴ قبلا ملاقات شده، دیگه اون یال تاثیری نداره و توی درخت نمیاد.
پس بدون در نظر گرفتن یال ضربدری سوال حل میشه
یال ضربدری یالیه که هیچ که نه درختی باشه، نه پیشرو، نه پسرو. یا یالی که توی جنگل dfs هیچ کدوم پدر اونیکی نیست.
اینجا ۹ به ۱۰ میتونه باشه. اما ۱۰ به ۹ نه. ۱۰به ۹ یال عقب رونده است.
۶ به ۷ میتونه باشه اما ۷ به ۶ یال عقب رونده است.
۶ به ۲ یال عقب رونده است.
۷ به ۱ هم عقب رونده است.
Sent from my SM-T210R using Tapatalk
بسیار عالی توضیح دادید.
از شما ممنونم.
من یه سوالی دارم اونم اینکه مثلا اگر بین ۳و ۴ یال باشه چون تو پیمایش نیومده پس این نمیشه .سوال من اینه خوب این شکل یک درخته وجود این یال دور ایجاد میکنه در زیر درخت چپ ممکنه قبلا بوده باشه ما حذفش کردیم برا اینکه دور ایجاد نکنه کلا همین تکیشو من نمیفهمم؟؟ میشه توضیح بدید چطور میتونه نباشه؟
(۱۸ دى ۱۳۹۲ ۱۰:۲۷ ب.ظ)tarane1992 نوشته شده توسط: بسیار عالی توضیح دادید.
از شما ممنونم.
من یه سوالی دارم اونم اینکه مثلا اگر بین ۳و ۴ یال باشه چون تو پیمایش نیومده پس این نمیشه .سوال من اینه خوب این شکل یک درخته وجود این یال دور ایجاد میکنه در زیر درخت چپ ممکنه قبلا بوده باشه ما حذفش کردیم برا اینکه دور ایجاد نکنه کلا همین تکیشو من نمیفهمم؟؟ میشه توضیح بدید چطور میتونه نباشه؟
ببینید دوست عزیز،برای بدست آوردن یال های صلیبی و پیشرو و امثالهم به این صورت عمل کنین:
برای بدست آوردن Back و Forward دنبال روابط پدر فرزندی بگردین.اگه یال از پدر به فرزند بود میشه Forward،اگه از فرزند به پدر بود میشه Back. اگه هیچ رابطه ارث بری بینشون نبود،میشه Cross. روابط پدر فرزندی رو هم برا اساس درخت میشه به راحتی دید.البته من صورت سوال رو نخوندم.فقط این نکته یادم اومد که خلاصه و مفید بود خواستم بگم.
اگه بین از ۳ به ۴ یالی وجود داشته باشه، حتما توی درخت میاد.
اگه از ۴ به ۳ یالی باشه، چون ۳ قبلا ملاقات شده، این یال عقب رو هست و در درخت نمیاد.
وقتی میخوایم یال ضربدری رو بررسی کنیم، اول ببینید تو درخت هست یا نه. اگه نبود، ببینید عقب رو یا پیش رو هست یا نه. اگه باز هم نبود. حالا بیاید بررسی کنید آیا اجداد (نه پدر) دو راس یال به هم میرسن یا نه. اگه نرسیدن، یال بین اون ها ضربدریه. البته این ها شرط لازمند ولی کافی نیستن. یعنی ممکنه اجداد به هم برسن ولی یال بین دو راس ضربدری باشه. تنها راهی که میمونه تحلیل کردنه. اما حالات کلیش همیناست.
این متن شاید کمی کمکتون بکنه.
![[تصویر: 235806_unemymy6.jpg]](https://img.manesht.ir/235806_unemymy6.jpg)
![[تصویر: 235806_za9avesu.jpg]](https://img.manesht.ir/235806_za9avesu.jpg)
Sent from my SM-T210R using Tapatalk