تالار گفتمان مانشت

گراف بدون جهت [tex]G=(V,E)[/tex]
مفروض است . میخواهیم مشخص کنیم که آیا گراف شامل حلقه است یا نه . کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
پاسخ‌: [tex]O(\left | V \right |)[/tex]

این سوال خیلی ساده هستش
ببینید الگوریتمی باید پیدا کنیم تا بتونیم ببینیم راسی حلقه داره یا نه.
خب اگه به روش DFS بریم و دوبار به یک گره برسیم قطعا یک مدار یا دور ایجاد شده و در نتیجه می توان اینطور در نظر گرفت که چون پیمایش الگوریتم DFS از مرتبه [tex]O(|V| |E|)[/tex] است و سوال گفته کوچکترین حد بالا و می دونیم که در تعداد یالها حداقل به اندازه رئوس و حداکثر [tex]\frac{n(n-1)}{2}[/tex] است و سوال کوچکترین رو خواسته پس میشه همان اندازه [tex]O(|V|)[/tex]

حالا اگه سوال بزرگترین حد رو خواسته بود میشد [tex]O(|V|^2)[/tex]

(19 بهمن 1390 11:11 ب.ظ)zeinab نوشته شده توسط: [ -> ]گراف بدون جهت [tex]G=(V,E)[/tex]
مفروض است . میخواهیم مشخص کنیم که آیا گراف شامل حلقه است یا نه . کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
پاسخ‌: [tex]O(\left | V \right |)[/tex]

تو یک گراف اگه همه‌ی راس‌ها توی حلقه شرکت داشته باشن که با پیمایش DFS از یک راس میشه شروع کرد و به اندازه‌ی تعداد راس‌ها حرکت کنیم و اگه دوباره به همون راس اول رسیدیم یعنی حلقه داریم
اما اگه حلقه هایی داشته باشیم که شامل فقط تعدادی راس گراف باشن باز هم حد بالا همون تعداد راس میشه چون سوال اینه که ما فقط بفهمیم حلقه داریم یا نه حا لا میشه هر چند تا حلقه تو گراف داشت یکیش که تشخیص دادیم کار ما تمومه و تو این شمارش(با DFS) اگه با ملا قات یک گره دوباره بعد از طی مسیری به همون گره رسیدیم یعنی حلقه داریم.

چون برای بررسی حلقه باید تمام یالها بررسی بشن که تعدادشون از تعداد گرهها کمتر باشه پس با هر الگوریتمی حل کنیم، حداقل زمان لازم به اندازه تعادا کل یالها |V| هست.