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

سلام
جدول زیر زمان نخستین ملاقات و زمان آخرین ملاقات را در جستجوی DFS یک گراف نمایش می دهد.در این صورت در این گراف کدامیک از یالهای زیر نمیتواند وجود داشته باشد؟

1-d,e
2-a,g
3-h,b
4-f,e
اینم پاسخ :

برای کشیدن گراف مشکلی ندارم , فقط میخوام بدونم چجوری از روی این گراف تشخیص داده که h,b نمی تونه یال این گراف باشه ؟

دقیقا منم با این نوع سوال مشکل دارم
اگه کسی از دوستان میتونه توضیح بده ممنون میشم

چون اگه یال hb وجود داشته باشه وقتی که ما به h میرسیم از اونجا میریم و b رو ملاقات میکنیم و دیگه زمان های f,d گره b 13 14 نمیشن و میشن 10و11 و زمان f گره h هم میشه 13. البته فکر کنم!

(25 دى 1392 09:51 ب.ظ)Riemann نوشته شده توسط: [ -> ]چون اگه یال hb وجود داشته باشه وقتی که ما به h میرسیم از اونجا میریم و b رو ملاقات میکنیم و دیگه زمان های f,d گره b 13 14 نمیشن و میشن ۱۰و۱۱ و زمان f گره h هم میشه ۱۳/ البته فکر کنم!

ببخشید من فراموش کردم گزینه هاشو بذارم..با توجه به گزینه ها , میتونید بگید چرا مثلا" d,e یا f,e میتونه یال گراف باشه ؟؟

یه نکته داره که باید بهش توجه بشه. زمان خروج از یه گره یا همون آخرین ملاقاتش باید بیشتر از زمان خروج از یالهای مجاورش باشه.یعنی ما لیست مجاورای گره u رو داریم.آخرین ملاقات وقتیه که اون لیست رو تمام کرده باشیمو تمام مجاوراشو ملاقات کرده باشیم و دیگه کاری با گره u و مجاوراش نداشته باشیم. مثلا در de بررسی کنیم. به d میتونیم در زمان ورود 2 وارد شیم و بررسی میکنیم میبینیم زمان آخرین ملاقات d بیشتر از زمان اولین ملاقات e هست. و چون زمان آخرین ملاقات e کمتر از زمان خروج از dهست یعنی قبل از اینکه d وقتش تموم شه e رو هم میتونیم ببینیم.پس این یال میتونه باشه. نباید زمان آخرین ملاقات d کمتر از e باشه چون در جستجوی عمقی وقتی d رو ملاقات میکنیم تموم مجاوراش میرن تو پشته تا وقتی یکی از مجاوراش یعنی e رو بررسی کنیم خود e هم باید کامل مجاوراش بررسی شده باشن و بعدا برگردیم و به گره مجاور بعدی d.
امیدوارم خوب توضیح داده باشم.



Sent from my GT-S5660 using Tapatalk 2

(26 دى 1392 09:37 ق.ظ)Arshad93 نوشته شده توسط: [ -> ]یه نکته داره که باید بهش توجه بشه. زمان خروج از یه گره یا همون آخرین ملاقاتش باید بیشتر از زمان خروج از یالهای مجاورش باشه.یعنی ما لیست مجاورای گره u رو داریم.آخرین ملاقات وقتیه که اون لیست رو تمام کرده باشیمو تمام مجاوراشو ملاقات کرده باشیم و دیگه کاری با گره u و مجاوراش نداشته باشیم. مثلا در de بررسی کنیم. به d میتونیم در زمان ورود ۲ وارد شیم و بررسی میکنیم میبینیم زمان آخرین ملاقات d بیشتر از زمان اولین ملاقات e هست. و چون زمان آخرین ملاقات e کمتر از زمان خروج از dهست یعنی قبل از اینکه d وقتش تموم شه e رو هم میتونیم ببینیم.پس این یال میتونه باشه. نباید زمان آخرین ملاقات d کمتر از e باشه چون در جستجوی عمقی وقتی d رو ملاقات میکنیم تموم مجاوراش میرن تو پشته تا وقتی یکی از مجاوراش یعنی e رو بررسی کنیم خود e هم باید کامل مجاوراش بررسی شده باشن و بعدا برگردیم و به گره مجاور بعدی d.
امیدوارم خوب توضیح داده باشم.



Sent from my GT-S5660 using Tapatalk 2

بله خیلی خوب بود ممنون
و طبق توضیحات شما h,b نمی تونه یال این گراف باشه چون h در لحظه 10 تموم شده و b در لحظه 13 شروع شده که b نمیتونه مجاورش باشه چون بعد از تموم شده h اومده