(۱۶ خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۱۶ خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟

(۱۶ خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)samanbeigmiri نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟

اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت

(۱۶ خرداد ۱۳۹۵ ۰۹:۱۹ ب.ظ)hamidrm509 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)samanbeigmiri نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟

اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت

۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟

(۱۶ خرداد ۱۳۹۵ ۰۹:۲۴ ب.ظ)samanbeigmiri نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۹:۱۹ ب.ظ)hamidrm509 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)samanbeigmiri نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟

اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت

۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟

پیشرو هست.
عذر خواهی میکنم.گویا جابه جا نوشتم.الان صحیح میکنم. تکس که مینویسم همیشه گیجم میکنه.

---

اصلاح شد.فقط یه جابه جایی بود.همه ی تعاریف و مثال ها درستن

(۱۶ خرداد ۱۳۹۵ ۰۶:۴۰ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۶:۱۲ ب.ظ)hamidrm509 نوشته شده توسط:  با سلام و خسته نباشید خدمت دوستان محترم

در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟

ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .

با تشکر

در فایل ضمیمه شده یال‌های مختلف با رنگ و pattern متفاوت نشون داده شده‌اند.
در پیماش درخت DFS، هر یال [tex](u,v)[/tex] که پیمایش شده باشه، یال عبوری هست: Tree Edge
اگر رأس u نیای رأس v باشد ولی این یال پیمایش نشده باشد، یال فوروارد یا پیشرو هست
یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست (همانطور که در شکل، a نیای e هست در درخت ولی از e به a یالی وجود داره در گراف).
بقیه‌ی یال‌ها cross یا نقاطعی هستند.


خیلی ممنون از جوابتون ..خیلی کمک کرد.

(۱۶ خرداد ۱۳۹۵ ۰۶:۱۲ ب.ظ)hamidrm509 نوشته شده توسط:  با سلام و خسته نباشید خدمت دوستان محترم

در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟

ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .

با تشکر