توی پیمایش DFS اگه یالی جزو گراف باشه ولی توی درخت DFS نباشه و بین اون دو نودی که توی گراف بینشون یال بوده توی درخت BFS هیچ رابطه پدر فرزندی نباشه یعنی forward , backward نباشه cross است.

یه نکته:اگر (u,v) (صلیبیcross)باشد آنگاه:
(d(v) < f(v) < d(u) < f(u

یه سوال:چرا رابطه زیر برقرار نیست:

(d(u) < f(u) < d(v) < f(v

برای توجیه بیشتر به سوال طراحی الگوریتم (نرم افزار)۸۸مراجعه کنید.

(۱۷ بهمن ۱۳۸۹ ۱۲:۲۳ ق.ظ)ROZA نوشته شده توسط:  یه نکته:اگر (u,v) (صلیبیcross)باشد آنگاه:
(d(v) < f(v) < d(u) < f(u

یه سوال:چرا رابطه زیر برقرار نیست:

(d(u) < f(u) < d(v) < f(v

برای توجیه بیشتر به سوال طراحی الگوریتم (نرم افزار)۸۸مراجعه کنید.

رابطه دوم برقرار نیست چون بین u,v یالی بود و قرار بود v بعد از u ملاقات شود خوب بلافاصله بعد از u ملاقات میشد و جزو یالهای درختی میشد نه کراس.
پس حتما v قبلا ملاقات شده بوده که پس از ملاقات u دیگه نیازی به ملاقات v نبوده و یال کراس ایجاد شده.

(۱۶ بهمن ۱۳۸۹ ۱۰:۱۰ ق.ظ)zr2358 نوشته شده توسط:  یال کراس چه یالیه؟
میشه توضیح بدین؟
و معنیش توی این جمله...
وجود یک یال کراس در پیمایش عمق اول معرف عدم وجود مسیر اویلری در گراف است.

توضیح کامل

در درخت DFS در یال U --->V‌، اگر گره U زودتر ملاقات شده باشه، به یال می گیم رو به جلو و رسم اش نمی کنیم
در درخت DFS در یال U --->V‌، اگر گره V زودتر ملاقات شده باشه، به یال می گیم بازگشتی و رسم اش نمی کنیم