یال کراس چه یالیه؟
میشه توضیح بدین؟
و معنیش توی این جمله...
وجود یک یال کراس در پیمایش عمق اول معرف عدم وجود مسیر اویلری در گراف است.
توی پیمایش 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 زودتر ملاقات شده باشه، به یال می گیم بازگشتی و رسم اش نمی کنیم