این سوال قبلا هم پرسیدم و لی کسی جواب نداده لطفا جواب بدید
در پیمایش bfs یک گراق جهتدار
چرا برای هر یال cross edge، (u,v داریم d[v] <= d[u]+1
d[v] نخستین زمان ملاقات گره v است
به نظر من چون در پیمایش bfs داریم گره هها رو به صورت سطحی ملاقات میکنیم. پس این ملاقات به صورت درخت هست. گرههای Uوv همجوارند وv پدر u است پس طبق همون فرمولی که نوشتید:
زمان ملاقات گرهv کوچکتر یا مساوی است با زمان ملاقات گره u بعلاوه ۱ .
با تشکر از توضیحتان منظور از یال cross edge همان یال ضلیبی است
یال ضلیبی یالی است که در پیمایش درخت bfs یا dfs هیجکدام از نودهای u , v پدر یا جد یکدیگد نباشند
فرص کنبد گراف ۳ راسی داریم که گره r پدر u و v باشد و یالی از u به v وحود داشته باشد (گراف جهتدار است) انکاه دو پیمایش bfs زیر برای ان وحود دارد ترتیب پیمایش را از راست به چپ ذر نظر بگیرید
v- u - r
u - v - r
پیمایش اول d[v] <= d[u]+1 را نقض می کند جون u زودتر از v ملاقات شده است
یال (u,v) در هر دو پیمایش bfs یال ضلیبی است
لطفا بگویید کجا اشتباه می کنم
(۰۳ بهمن ۱۳۹۰ ۱۲:۱۰ ق.ظ)rad.bahar نوشته شده توسط: پیمایش اول d[v] <= d[u]+1 را نقض می کند جون u زودتر از v ملاقات شده استعلامت => آمده یعنی میتونه اینطور تفسیر بشه: زمان ملاقات u بعلاوه یک = زمان ملاقات v
در گراف جهت دار ممکن است دو راس uوv مجاور باشند و در پیمایش گراف، دیر‌تر از بقیه گرهها مورد بازدید قرار بگیرند ولی رابطه پدر یا فرزندی با سایر گرهها نداشته باشد . به عبارتی اگر نتوانیم موقع پیمایش گراف مسیری از یک گره به گره دیگر بیابیم و مجبور باشیم مجددا نقطه شروع جستجو را تعیین کنیم راس متقاطع بوجود می آید
در چنین حالتی (یعنی وقتی که راسی پیدا نکنیم) مجبوریم از همان مسیری که گرهها را تا کنون پیمایش کردیم برگردیم و به این ترتیب زمان خاتمه راس‌ها از آخرین راسی که ملاقات شده به اولین راسی که ملاقات شده مشخص میشود . که مسلما آخرین راس (فرزند) ملاقات شده دارای کمترین زمان و اولین راس ملاقات شده دارای بیشترین زمان خاتمه است
حالا که کل گرههای قابل دسترس پیمایش شد باید مجددا دنبال گرههای باقیمانده بگردیم(همان گره مربوط به یال متقاطع که به علت جهت دار بودن یال قابل دسترس نبود)و دوباره برای این گره هم زمان ملاقات و زمان خاتمه کار ثبت خواهد شد. که مسلما زمان ملاقات این گره بیشتر از زمان گرههای قبلی است
در اینشکل هم به ترتیب گرههای u-v-y-x ملاقات میشوند و بعد چون هنوز یال باقیمانده داریم که هنوز ملاقات نشده مجبوریم از x به عقب برگردیم و اینجا زمان خاتمه x را تعیین میکنیم و بعد زمان خاتمه y (که بیشتر از زمان xاست)و... تا به u میرسیم.و دوباره باید از w شروع کنیم. زمان ملاقات و خاتمه wهم مسلما بیشتر از گرههای قبلی است
_____________________________
من فکر میکنم اگر منظور سئوال زمان خاتمه (ترک) گرهها باشه این رابطه درست درمیاد.