(۲۵ بهمن ۱۳۹۵ ۰۴:۳۱ ب.ظ)Kubo نوشته شده توسط:  سلام

منظور از یال پس سو در گزینه ۱ چی هست ؟
منظور از یال چپ سو در گزینه ۲ چی هست ؟ منظورش یال عبوریه ؟ یا خیر ؟ !

مرسی

مورد اول درست هست چون Back-edge یعنی اینکه در گراف دور داریم که در حالی که گفته شده DAG هست پس دور ندارد.

مورد دوم اشتباه هست. می‌توان گراف Cross edge داشته باشد و DAG هم باشد. مثلا یک درخت دودویی جهت‌دار در نظر بگیرید که جهت همه‌ی یال‌هاش به سمت پائین هست و یک یال هم از یک رأس در زیر درخت راست به یک رأس در زیر درخت چپ وصل شده است (الگوریتم DFS هم در ابتدا رأس‌های سمت چپ را پیمایش کرده است). این یال cross هست چون جزو پیمایش درخت نیست، back نیست چون این دو رأس والد یا فرزند همدیگر نیستند.

مورد چهارم هم درست هست. البته اگه در جواب تشریحی گفته شده که از DFS استفاده کنید اشتباه هست! چون در یک گراف جهت‌دار ممکن هست یک رأس رو چندین بار پیمایش کنید بدون اینکه دوری وجود داشته باشد. برای این منظور باید از مرتب‌سازی توپولوژیکی که از مرتبه‌ی [tex]O(V+ٍE)[/tex] هست استفاده کنید. اگر به جواب نرسید، پس گراف دور دارد.

مورد سوم هم درست هست و با DFS میشه انجام داد. به هر رأس که رسیدید، یکی از یال‌ها رو به دلخواه انتخاب کنید. اگر این یال به رأس رنگ نشده ختم شد، اون یال رو انتخاب کنید و به رأس جدید برید و تا آخر تکرار کنید.
اگر گراف بدون دور بود، یعنی درخت بود، تمامی یال‌ها پیمایش خواهند شد که از مرتبه‌ی [tex]O(V)[/tex] خواهد بود چون در درخت، یال‌ها و رأس‌ها هم مرتبه هستند.
اگر گراف بدون دور نبود، در بدترین حالت، اول به اندازه‌ی [tex]O(V)[/tex] از یال‌ها (همه‌ی رأس‌ها) رو پیمایش کردید و درخت ساختید. حال به یکی از رأس‌ها خواهید برگشت و یک یال دیگر انتخاب میکنید که در این حالت میبینید به یک رأس که قبلا رنگ شده وصل شد. یعنی V+1 پیمایش که دوباره از مرتبه‌ی V هست.